関係は2つの集合の直積の部分集合として定式化されます。
集合 A から集合 B への関係 R が与えられたとき、R の要素である順序対 (a,b) の要素を入れ替えて得られる順序対 (b,a) からなる B から A への関係を R の逆関係と呼びます。
2つの関係 R, S が与えられたとき、xRy と ySz がともに成り立つような y が存在するような順序対 (x,z) からなる集合を R と S の合成関係と呼び、これを S∘R で表します。
二項関係の基本的な性質について解説します。
集合A上の二項関係Rのもとで、Aの任意の要素xがx自身と関係を持たない場合、Rは非反射律を満たすと言います。非反射律を満たす二項関係の例を挙げます。
集合A上の二項関係Rのもとで、Aの任意の要素x,yについて、Rのもとでxがyと関係を持つ場合にはyとxが関係を持つ場合、Rは対称律を満たすと言います。対称律を満たす二項関係の例を挙げます。
集合A上の二項関係Rのもとで、Aの任意の要素x,yについて、xがyと関係を持つとともにyがxと関係を持つ場合にはxとyが一致する場合、Rは反対称律を満たすと言います。反対称律を満たす二項関係の例を挙げます。
集合A上の二項関係Rのもとで、Aの任意の要素x,yについて、xがyと関係を持つ場合にはyがxと関係を持たない場合、Rは非対称律を満たすと言います。非対称律を満たす二項関係の例を挙げます。
集合A上の二項関係Rのもとで、Aの任意の要素x,y,zについて、xがyと関係を持つとともにyがzと関係を持つ場合にxとzが関係を持つことが保証されるならば、Rは推移律を満たすと言います。推移律を満たす二項関係の例を挙げます。
反射律、対称律、推移律を満たす二項関係を同値関係と呼びます。また、同値関係のもとで 2 つの要素が関係を持つとき、それらの要素は同値であると言います。同値関係を定義した上で、同値関係の具体例を提示します。
集合 A 上の同値関係 R が与えられたとき、A の要素 x を任意に選べば、R のもとで x と同値であるような A のすべての要素からなる集合を構成できます。このような A の部分集合を x を代表元とする同値類と呼びます。
集合 A のそれぞれの要素 a に対して、それを代表元とする同値類 [a] を生成できますが、そのようなすべての同値類からなる A の部分集合族を商集合と呼びます。商集合は A の分割です。つまり、A の任意の要素は何らかの同値類に属するとともに、異なる複数の同値類に属することはありません。
反射律、反対称律、推移律を満たす関係を順序関係と呼びます。
反射律、反対称律、推移律を満たす二項関係を半順序や順序などと呼びます。また、半順序のもとで2つの要素が関係を持つとき、一方の要素は他方の要素以下であると言います。半順序を定義した上で、半順序の具体例を提示します。
非対称律と推移律を満たす二項関係を狭義半順序や狭義順序などと呼びます。また、狭義半順序のもとで2つの要素が関係を持つとき、一方の要素は他方の要素より小さいと言います。狭義半順序を定義した上で、狭義半順序の具体例を提示します。
反射律、反対称律、推移律、完備律を満たす二項関係、すなわち完備律を満たす半順序を全順序や線型順序などと呼びます。全順序を定義した上で、全順序の具体例を提示します。
非対称律、推移律、三分律を満たす二項関係、すなわち三分律を満たす狭義半順序を狭義全順序や狭義線型順序などと呼びます。狭義全順序を定義した上で、その具体例を提示します。
有向グラフを用いることにより半順序集合を視覚的に表現できます。加えて、半順序の性質を利用することにより、有向グラフを簡略化したハッセ図と呼ばれる図を得ることができます。
非空な順序部分集合のある要素が、他の任意の要素以上である場合、それを最大元と呼びます。また、非空な順序部分集合のある要素が、他の任意の要素以下である場合、それを最小元と呼びます。
非空な順序部分集合のある要素よりも大きい要素がその集合の中に存在しない場合、その要素を極大元と呼びます。また、非空な順序部分集合のある要素よりも小さい要素がその集合の中に存在しない場合、その要素を極小元と呼びます。
非空な順序部分集合の任意の要素以上の要素が順序集合上に存在する場合、その要素を上界と呼びます。また、非空な順序部分集合の任意の要素以下の要素が順序集合上に存在する場合、その要素を下界と呼びます。
全順序集合の任意の非空の部分集合が最小元を持つ場合、そのような全順序集合を整列集合と呼びます。
全順序集合の任意の非空な部分集合が最小限を持つ場合、このような全順序集合を整列集合と呼びます。また、整列集合上に定義された全順序を整列関係と呼びます。
本節を学ぶ上で集合に関する知識が必須になります。
集合論は数学の土台です。あらゆる数学的概念は集合を用いて記述できます。ここでは集合を定義した上で、集合演算とその性質について学び、さらには集合族や直積集合、関係などについて学びます。
有限個の要素を持つ集合については、その要素の個数は有限な自然数として表現されます。一方、無限個の要素を持つ集合については、すべての要素を数え尽くすことができないため、要素の個数を自然数として表現できません。集合の濃度とは要素の個数を一般化した概念であり、これを用いることにより無限どうしを比較できるようになります。