二項関係

二項関係の定義

定義（二項関係）

集合 \(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~\text{または}~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\) より、推移律を満たさない。