関係の定義

定義 1 (関係). 集合族に対して、これらの直積集合の部分集合

を考える. このとき, 組を上の関係(relation)という. 特にが濃度の有限集合であるとき、項関係(-ary relation), の場合は単項関係という. またの場合は上の関係といい, 特に上の2項関係は自己関係(endrelation)ともいう.

を満たすとき, は関係を持つといい, これをと表す。特にが有限集合のとき、2項関係はなどとも表す.

上の関係であることが文脈上明らかで誤解が生じない場合は, 集合族を明示せずに単に関係と言うこともある.

例 2 (空関係). は定義より上の関係となる。これを空関係という。

例 3 (全体関係). は定義より上の関係となる。これを全体関係という。

例 4 (0項関係). のときは点集合となるので、項関係はまたはの2つのみである。

例 5 (1項関係). に対し、は上の項関係である。

関係の和集合・共通部分

定義 6 (関係の和集合・共通部分). 2つの上の関係に対し, これらの和集合, 共通部分も上の関係である.

証明. なので、部分集合の性質より。よって関係の定義より、は上の関係である. ◻

関係の射影・拡張

定義 7 (関係の射影). 上の関係とに対し、

をへの射影といい、を関係のへの射影などという。

定義 8 (関係の拡張). 上の関係とに対し、射影の逆関係をへの拡張といい、

を関係のへの拡張などという。

関係の合成

定義 9 (関係の合成). 上の関係と上の関係に対し、をとる。それぞれのへの拡張の共通部分のへの射影

は、上の関係となる. これを関係とのについての合成といい,や、あるいは簡単にやなどと表す.

が文脈上明らかで誤解が生じない場合は, 単に関係やと書くこともある.

定義 10 (関係の制限). 上の関係と上の1項関係のについての合成を関係の制限といい、などと表す。

2項関係の性質

定義 11 (始域と終域). 上の2項関係に対し,を始域、を終域という。それぞれで表す。

定義 12 (逆関係). 上の2項関係に対し,を定める.するとは上の2項関係であり,これをの逆関係という.定義より、である。

定義 13 (像と逆像). 上の2項関係とに対し,

を関係によるの像という。に対し,逆関係の像

を関係によるの逆像という。

定義 14 (定義域と値域). 上の2項関係に対し,終域の逆像を関係の定義域、始域の像を関係の値域という。それぞれで表す。値域のことを関係の像といってで表すこともある。

定義域の記号は始域の記号と同じなので、これらが一致せずまた文脈上明らかでないときは明示的に区別する必要がある。

定義 15 (一意性). 上の2項関係に対し,

  • すなわちかつが成り立つとき, 関係は左一意的あるいは単射であるという.

  • すなわちかつが成り立つとき, 関係は右一意的あるいは関数的であるという.

  • 関係が左一意的かつ右一意的であるとき, 一対一であるという.

定義 16 (全域性).

  • 定義域が始域と一致する、すなわちが成り立つとき, 関係は左全域的であるという.

  • 値域が終域と一致する、すなわちが成り立つとき, 関係は右全域的あるいは全射であるという.

  • 関係が左全域的かつ右全域的であるとき, 対応であるという.

自己関係の性質

定義 17 (自己関係). 2項関係のうち始域と終域が等しいものを上の自己関係という。

例 18. の対角集合は上の自己関係となる。これを恒等関係といい、や単になどと表す。

定義 19 (自己関係の合成). 上の自己関係の合成は、特に断らない限りの終域との始域についてのものとし、これを単にと表す。合成の位置をこのように固定することで、逆関係を用いればの非自明な合成を全て表現することができる。

定義 20 (自己関係の冪). 自己関係の冪を以下のように恒等関係と自己関係の合成を用いて定める.

定義 21 (反射性).

  • すなわちが成り立つとき, 関係は反射的であるという.

  • すなわちが成り立つとき, 関係は非反射的であるという.

  • すなわちが成り立つとき, 関係は余反射的であるという.

定義 22 (推移性).

  • すなわちが成り立つとき, 関係は推移的であるという.

  • すなわちが成り立つとき, 関係は非推移的であるという.

  • すなわちが成り立つとき, 関係は反推移的であるという.

定義 23 (対称性).

  • すなわちが成り立つとき, 関係は対称的であるという.

  • すなわちが成り立つとき, 関係は非対称的であるという.

  • すなわちが成り立つとき, 関係は反対称的であるという.