関係が「ある」とか「ない」ということを言葉上我々はよく言います。集合論の言葉に従っても関係を定義することが出来ます。 例えば、a と b に関係があるとき (a,b) という組が存在し、a と b に関係がないとき (a,b) が存在しないように組の集合 R を作ったとき、それを関係(relation)と呼びます。(参照→集合,対応,直積集合)

　関係では、ある要素と別の要素につながりが「ある」か「ない」かに着目します。人間の集合であれば、親子(uとvは親子)とか兄弟(uとvは兄弟)は関係になります。

　関係とは、集合ですから記号 ∩,∪,⊂ などを直接適用できます。関係 R と Q で R∩Q を定義してもかまわないということです。

　関係は、関係データモデル(relation data model) などの基礎を与えます。

　関係は対応によく似ています。X から Y へという広い定義を対応、X から X へという狭い定義を関係と言葉上区別します。(参照→対応,関数)

　集合 U,V があるとき、直積集合 U×V の部分集合 R⊂U×V を U と V の対応(correspondence) といいます。(参照→集合,直積集合) U×U の部分集合は特別に関係(relation) といいます。

　集合 R⊂U×U を2項関係(binary relation) といいます。集合が３個以上、例えば U×U×U の部分集合も関係で、3項関係(ternary relation) といいます。一般に n 個の集合の直積から定義した場合は n項関係(n-ary relation) といいます。

　(u,v) がRの元のとき u,v に関係Rがあるといいます。このとき、uRv と表記することがあります。

　一般的に関係とだけいった場合は対称的とは限りません。例えば、a から b へ関係があっても b から a への関係があるかどうかは別問題です。

　もし、U 上の関係 R が自分自身への関係を必ず持つ場合は、反射的関係(reflexive relation) といいます。

　u から vへの関係と vから uへの関係が同様にある場合は対称的関係(symmetric relation) といいます。u が v の配偶者なら v は u の？

　関係が連鎖出来る場合は推移的関係(transitive relation) といいます。αのαはαですのように連鎖できる場合です。

　例えば、関係親(uはvの親である) は推移的関係ではありません。親の親は親ではありませんから。関係兄や弟や兄弟は推移的関係です。兄の兄は兄ですし、弟の弟も弟ですから。もちろん兄弟の兄弟も兄弟です。関係祖先も推移的関係です。祖先の祖先は祖先ですから。

　一般に、ある関係が示されたときに、その関係が推移的であることを効率的に確かめるのは難しい問題です。与えられた関係が推移的かどうか効率的に確かめるというそれだけで重要な研究課題になることもあります。

　U の元 u,v∈U が u=v の場合を除いて uRv と vRu を両立しないとき、反対称的関係(antisymmetric relation) といいます。

　初めて定義6だけ見たときは、何のことかピンときませんでした。対偶という言葉を知っていると" u=v でない限り uRv と vRu は両立しない。" と同じ意味だとわかります。この対偶のほうが直感的にはわかりやすいでしょう。

　じゃんけんでいう勝ち(uはｖに勝つ) も反対称的関係です。勝ちまたは引き分けでも反対称的関係です。

　集合 U 上の関係 R が反射的で、対称的で、推移的な関係を同値関係(equivalence relation) といいます。同値関係 R は、U を分割し、独立したブロックを作ります。(参照→分割)ブロックの集合はRの同値類(equivalence classes) と呼ばれます。

　U の同値関係 R1 と R2 があり、R1 が作る同値類を P1、 R2が作る同値類を P2 とします。ここで、R1⊂R2 のとき、P1 を P2 の細分といいます。

　関係同部屋(uとvはルームメート) は同値関係です。関係同苗字(uとvは苗字が同じ)も同値関係です。もちろん同姓同名も同値関係です。

　 しかし、関係苗字か名前が同じは同値関係ではありません。 "A.B."と"A.D."の苗字が同じで、"A.D."と"C.D"の名も同じですが、"A.B."と"C.D."は苗字も名も違います。

　学生の集合上の関係を考えたとき、同学級が作る同値類は同学年が作る同値類の細分になります。

　集合 U 上の関係 R が、反射的、推移的、反対称的関係のとき、半順序関係(partially ordered relation) といいます。半順序関係は、特に ≦ で表記し、関係がある場合は u≦v のように表記します。

　一般に、U 上で半順序関係が成り立つだけでは集合 U の上で比較ができるかどうかわかりません。学生同士に関係優秀(uはvより優秀である) を導入してみます。例えば、数学も文学も得点が高い学生を優秀と定義します。優秀は uとv が常に比較できるとは限りません。数学はできるけど文学がダメな学生 u と文学ができるけど数学がダメな学生 v は優秀では比較できません。この関係は半順序関係です。

　集合 U 上の関係 ≦が半順序関係であるとき、(U,≦) を半順序集合(partially ordered set) といいます。

　U 上の関係 ≦ がすべての u,v について、 u≦v か v≦u の少なくとも一方が成り立つとき、関係 ≦ は比較可能であるといいます。半順序集合 (U,≦) の関係 ≦ が比較可能のとき全順序関係(totally ordered relation) といいます。

　≦ が U の全順序関係のとき、(U,≦) を全順序集合(totally ordered set) といいます。

　感覚的には、全順序集合は要素が一列に並ぶ集合です。実数や整数のように小さい順に並べることが可能になります。

　関係に閉包(transitive closure)という概念を導入します。一般に、集合 S の閉包 S' というのは操作に対して閉じるように元を新たに補った集合で最小のものを差します。

　関係 R の推移閉包(transitive closure) というのは、R が必ず推移的関係であるように拡張した関係です。他に良く使われるものに、対称閉包(symmetric closure)、反射閉包(reflexive closure)、反射推移閉包(reflexive transitive closure)、などがあります。

　まず、推移閉包から定義しますが、その前に推移拡張(transitive extension) を定義します。

　R₀=R として、R_i+1 を R_i の推移拡張とします。従って、R₂ は R₁ の推移拡張です。R の推移拡張は、R　が2回推移してたどり着くような別地点までバイパス推移をつなぐ感覚です。

　同様に反射閉包、反射推移閉包、対称閉包も定義できます。