二項関係

二項関係の定義

定義（二項関係）
集合 \(A,B\) に対して、これらの直積の部分集合 \[ R\subset A\times B \] を \(A\) から \(B\) への二項関係という。

任意の \(a\in A,~b\in B\) に対して \[ (a,b)\in R \] が成り立つとき、\(R\) のもとで \(a\) と \(b\) は関係を持つといい \[ aRb \] と書く。

二項関係の性質

反射律

定義（反射律）
集合 \(A\) 上の二項関係 \(R\) に対して \[ \forall x\in A,~xRx \] ならば、\(R\) は反射律を満たす（反射的）という。

値が等しい組の間には必ず関係が成立するという性質である。

対称律

定義（対称律）
集合 \(A\) 上の二項関係 \(R\) に対して \[ \forall x,y\in A,~xRy\Longrightarrow yRx \] ならば、\(R\) は対称律を満たす（対称的）という。

ある組が関係があるとき、その要素の順番を入れ替えた組も関係があるという性質である。

反対称律

定義（反対称律）
集合 \(A\) 上の二項関係 \(R\) に対して \[ \forall x,y\in A,~xRy,~yRx\Longrightarrow x=y \] ならば、\(R\) は反対称律を満たす（反対称的）という。

関係がある組と、その要素の順番を入れ替えた組も関係があるとき、組の要素の値は等しいという性質である。

推移律

定義（推移律）
集合 \(A\) 上の二項関係 \(R\) に対して \[ \forall x,y,z\in A,~xRy,~yRx\Longrightarrow xRz \] ならば、\(R\) は推移律を満たす（推移的）という。

組 \((x,y)\) と組 \((y,z)\) がともに関係があるとき、組 \((x,z)\) も関係があるという性質である。

完全律

定義（完全律）
集合 \(A\) 上の二項関係 \(R\) に対して \[ \forall x,y\in A,~xRy~\mathrm{or}~yRx \] ならば、\(R\) は完全律を満たすという。

演習問題

問題
次の集合 \(A=\{1,2,3\}\) 上の二項関係について、反射律、対称律、反対称律、推移律を満たしているか調べよ。
  1. \(R_1=\{(1,1),~(1,3),~(2,2),~(3,1)\}\)
  2. \(R_2=\{(1,1),~(1,2),~(2,2),~(2,3),~(3,1),~(3,3)\}\)
解答
  1. \((3,3)\notin R_1\) より、\(R_1\) は反射律を満たさない。

    対称律を満たす。

    \((1,3)\in R_1\) かつ \((3,1)\in R_1\) だが、\(1\neq3\) より、反対称律を満たさない。

    推移律を満たす。
  2. 反射律を満たす。

    \((1,2)\in R_2\) だが、\((2,1)\notin R_2\) より、対称律を満たさない。

    反対称律を満たす。

    \((1,2)\in R_2\) かつ \((2,3)\in R_2\) だが、\((1,3)\notin R_2\) より、推移律を満たさない。