【集合】4 二項関係とその性質

こんにちは、これが310本目の記事となったすうじょうです。今日は、大学数学の解説記事です。今回の内容は、集合論より二項関係の基礎を解説します。

この記事は、以下の記事の続きです。

直積集合(デカルト積)

2つの集合$${A,B}$$について、$${A}$$の要素と$${B}$$の要素を順に並べた組すべてを要素とする集合を$${A}$$と$${B}$$の直積集合(デカルト積)といい、$${A \times B}$$と表す。この定義は以下のように書くことができる。

$${A \times B = \{(a,b)|a \in A, b \in B\}}$$

この直積集合の要素$${(a,b)}$$を順序対という。順序対は、$${\lang a,b \rang}$$と書かれることもある。$${a \neq b}$$のとき、順序対$${(a,b)}$$と$${(b,a)}$$は異なるものなので注意する。

一般的に$${n}$$個の集合$${A_1,A_2,A_3,…,A_n}$$に対して、要素を順に並べた組すべてを要素とする集合を$${A_1,A_2,A_3,…,A_n}$$の直積集合といい、$${A_1 \times A_2 \times A_3 \times … \times A_n}$$と表す。この定義は以下のように書くことができる。

$${A_1 \times A_2 \times A_3 \times … \times A_n = \{(a_1,a_2,a_3,…,a_n)|a_i \in A_i\}}$$

この直積集合の要素$${(a_1,a_2,a_3,…,a_n)}$$を$${\bm{n}}$$項組という。

$${n}$$個の集合の直積集合は、以下のように略記をされることがある。

$${A_1 \times A_2 \times A_3 \times … \times A_n = \displaystyle\prod_{i=1}^n A_i}$$

また、集合$${A}$$の$${n}$$個の直積集合は、$${A \times A \times A \times … \times A = A^n}$$と表す。

一般に直積集合の要素数について、以下のことがいえる。

集合の要素数を$${|A|}$$のように表すとき、
$${|A \times B|=|A| \times |B|}$$
$${|A_1 \times A_2 \times A_3 \times … \times A_n| = |A_1| \times |A_2| \times |A_3| \times … \times |A_n|}$$
$${|A^n|=|A|^n}$$

直積集合の例としては、直交座標がある。2次元直交座標($${xy}$$平面座標)は$${\R ^2}$$、3次元直交座標($${xyz}$$空間座標)は$${\R ^3}$$で表すことができる。

二項関係

二項関係の定義

集合$${A}$$と$${B}$$において、「$${a \in A}$$と$${b \in B}$$に対して関係$${R}$$が成り立つ」とき、$${a}$$と$${b}$$は関係$${R}$$をもつといい、$${aRb}$$と表す。この$${R}$$は直積集合$${A \times B}$$の部分集合として定義され、$${(a,b) \in R}$$のとき$${aRb}$$である。関係が成り立たない、つまり$${(a,b) \notin R}$$のときは、$${a \cancel{R} b}$$と表す。

$${R}$$のことを、$${A}$$と$${B}$$の間の二項関係あるいは単に関係という。特に、関係$${R}$$が直積集合$${A \times A}$$の部分集合のとき、$${A}$$上の二項関係という。

一般的に$${n}$$個の集合の間の関係を$${\bm{n}}$$項関係(関係)といい、$${n}$$項関係$${R}$$は直積集合$${A_1 \times A_2 \times A_3 \times … \times A_n}$$の部分集合である。特に、関係$${R}$$が直積集合$${A \times A \times A \times … \times A=A^n}$$の部分集合のとき、$${A}$$上の$${\bm{n}}$$項関係という。

二項関係$${R}$$の例としては、大小関係を表す$${\leq}$$がある。
以下、$${\N}$$には、0を含めている。
直積集合$${\N \times \N=\N ^2}$$は、

$$
\N ^2 =\begin{Bmatrix}
(0,0),&(0,1),&(0,2),&\dots\\
(1,0),&(1,1),&(1,2),&\dots\\
(2,0),&(2,1),&(2,2),&\dots\\
\vdots&\vdots&\vdots&\ddots
\end{Bmatrix}
$$

のようになる。ここで、$${\N}$$上の二項関係$${\leq}$$の直積集合は、以下のようになっている。

$$
\leq \space =\begin{Bmatrix}
(0,0),&(0,1),&(0,2),&\dots\\
&(1,1),&(1,2),&\dots\\
&&(2,2),&\dots\\
\\
&&&\ddots
\end{Bmatrix}
$$

二項関係$${\leq}$$では、例えば$${(0,0) \in \space \leq}$$なので、$${0 \leq 0}$$となる。また、$${(1,0) \notin \space \leq}$$なので、$${1 \nleq 0}$$となる。
ここで、2つの直積集合を比較すると、$${\leq \space \subseteq \N ^2}$$となっていることがわかる。

ここまでのことから、以下のようにして自然数における大小関係$${\leq}$$が定義される。
$${\forall x, \forall y \in \N, \space x \leq y \xLeftrightarrow{def} (x,y) \in \space \leq}$$

二項関係の性質

集合$${X}$$上の二項関係$${R}$$について、基本的な性質には以下のものがある。

反射律 $${\forall x \in X, xRx}$$
対称律 $${\forall x, \forall y \in X, xRy \to yRx}$$
反対称律 $${\forall x, \forall y \in X, xRy \land yRx \to x=y}$$
推移律 $${\forall x, \forall y, \forall z \in X, xRy \land yRz \to xRz}$$
完全律(比較可能律) $${\forall x, \forall y \in X, xRy \lor yRx}$$

二項関係$${R}$$が反射律を満たすとき、$${R}$$は反射的であるという。
二項関係$${R}$$が対称律を満たすとき、$${R}$$は対称的であるという。
二項関係$${R}$$が反対称律を満たすとき、$${R}$$は反対称的であるという。
二項関係$${R}$$が推移律を満たすとき、$${R}$$は推移的であるという。
二項関係$${R}$$が完全律(比較可能律)を満たすとき、$${R}$$は完全(比較可能)であるという。

※二項関係の性質をもつかどうかの考え方
・反射的かどうか
二項関係のもととなっている集合のすべての要素$${x}$$について、$${(x,x) }$$が二項関係の要素に含まれているかどうか考える。
・対称的かどうか
二項関係の要素である$${(x,y)}$$の組すべてについて、$${(y,x)}$$も要素に含まれているかどうか考える。
・反対称的かどうか
二項関係に$${(x,y)}$$と$${(y,x)}$$が含まれている組すべてについて、$${x=y}$$となっているかどうか考える。
・推移的かどうか
二項関係に$${(x,y)}$$と$${(y,z)}$$が含まれているものすべてについて、$${(x,z)}$$も要素に含まれているかどうか考える。
反対称的でないときは、その反例が推移的でない反例として使える場合がある。
・完全(比較可能)かどうか
二項関係のもととなっている集合のすべての要素の組み合わせ$${x}$$と$${y}$$について、$${(x,y)}$$か$${(y,x)}$$の少なくとも一方が二項関係の要素に含まれているかどうか考える。

$${\N}$$上の二項関係$${\leq}$$を例にしてそれぞれの性質をもつか考える。
$${x \leq x}$$は常に成り立つので、反射的である。
例えば、$${0 \leq 1}$$であるが$${1 \nleq 0}$$なので、対称的ではない。
$${x \leq y}$$かつ$${y \leq x}$$のとき$${x=y}$$なので、反対称的である。
$${x \leq y}$$かつ$${y \leq z}$$のとき$${x \leq z}$$なので、推移的である。
すべての自然数$${x,y}$$について、$${x \leq y}$$または$${y \leq x}$$は成り立つので、完全(比較可能)である。

推移閉包・反射推移閉包

二項関係$${R}$$について、推移律を満たすように最小限の要素を加えて拡張した関係を推移閉包といい、$${R^+}$$と表す。
$${R}$$がもともと推移的であるときは、$${R^+ =R}$$となる。

二項関係$${R}$$について、反射律と推移律を満たすように最小限の要素を加えて拡張した関係を反射推移閉包といい、$${R^*}$$と表す。

演習問題4

問題10 $${X=\{1,2,3\}, Y=\{a,b\}}$$とするとき、$${X \times Y, Y \times X, Y^3}$$をそれぞれ求めよ。

[方針]
$${X \times Y}$$と$${Y \times X}$$は一般には等しくない
[解答]
$${X \times Y=\{(1,a),(1,b),(2,a),(2,b),(3,a),(3,b)\}}$$
$${Y \times X=\{(a,1),(a,2),(a,3),(b,1),(b,2),(b,3)\}}$$
$${Y^3=\{(a,a,a),(a,a,b),(a,b,a),(a,b,b),(b,a,a),(b,a,b),(b,b,a),(b,b,b)\}}$$

※直積集合で、すべての要素を挙げることができているかどうかは、もとの集合の要素数から直積集合の要素数を計算して確かめるとよい。

問題11 $${S=\{1,2,3,4,5\}}$$とする。次の$${S}$$上の二項関係について、反射的、対称的、反対称的、推移的のそれぞれの性質をもつかどうか答えよ。また、もたない場合は反例を1つ挙げよ。
(1)$${R_1=\{(1,1),(2,2),(3,3),(4,4),(5,5)\}}$$
(2)$${R_2=\{(2,3),(3,2)\}}$$
(3)$${R_3=\{(1,2),(3,3),(5,4)\}}$$
(4)$${R_4=\empty}$$

[方針]
解き方については、この記事で書いた「※二項関係の性質をもつかどうかの考え方」を参考にするとよい
対称的、反対称的、推移的かどうかの判断のとき、定義の前提が真になる要素が二項関係にない場合は含意式全体は真になる
[解答]
(1)
反射的である
対称的である
反対称的である
推移的である
(2)
反射的ではない, 反例:$${1 \cancel{R}_2 1}$$ $${((1,1) \notin R_2)}$$
対称的である
反対称的ではない, 反例:$${2R_23}$$かつ$${3R_22}$$だが$${2 \neq 3}$$$${((2,3) \in R_2,(3,2) \in R_2}$$だが$${2 \neq 3)}$$
推移的ではない, 反例:$${2R_23}$$かつ$${3R_22}$$だが$${2 \cancel{R}_2 2}$$ $${((2,3) \in R_2,(3,2) \in R_2}$$だが$${(2,2) \notin R_2)}$$
(3)
反射的ではない, 反例:$${1 \cancel{R}_3 1}$$ $${((1,1) \notin R_3)}$$
対称的ではない, 反例:$${1R_32}$$だが$${2\cancel{R}_3 1}$$ $${((1,2) \in R_3}$$だが$${(2,1) \notin R_3)}$$
反対称的である
推移的である
(4)
反射的ではない, 反例:$${1 \cancel{R}_4 1}$$ $${((1,1) \notin R_4)}$$
対称的である
反対称的である
推移的である

※(2)の「推移的でない」に用いた反例は「反対称的でない」に用いたものと同じである。

問題12 $${S=\{1,2,3,…,n\}}$$とするとき、次の各問に答えよ。
(1) $${S}$$上の二項関係は全部で何個あるか。
(2) $${S}$$上の二項関係のうち、反射的なものは全部で何個あるか。
(3) $${S}$$上の二項関係のうち、対称的なものは全部で何個あるか。
(4) $${S}$$上の二項関係のうち、反射的かつ対称的なものは全部で何個あるか。
(5) $${S}$$上の二項関係のうち、反対称的なものは全部で何個あるか。
(6) $${S}$$上の二項関係のうち、完全(比較可能)なものは全部で何個あるか。

[解答]

$$
S ^2 =\begin{Bmatrix}
(1,1),&(1,2),&(1,3),&\dots&,(1.n)\\
(2,1),&(2,2),&(2,3),&\dots&,(2,n)\\
(3,1),&(3,2),&(3,3),&\dots&,(3,n)\\
\vdots&\vdots&\vdots&\ddots&\vdots\\
(n,1),&(n,2),&(n,3),&\dots&,(n,n)
\end{Bmatrix}
$$

(1)
二項関係は直積集合$${S \times S}$$の部分集合なので
$${\Large 2^{\small |S^2|}=2^{\small |S|^2}=2^{\small n^2}}$$

(2)
$${S}$$上の二項関係が反射的であるためには, $${(x,x)}$$となっている要素は含めなければならず, 他の要素については含める場合と含めない場合の2通りある
よって, $${\Large 2^{\small n^2-n}}$$

※(2)の計算は、指数部分を全体の要素数$${n^2}$$から$${S^2}$$の対角線の要素数$${n}$$を引いた数にしている

(3)
$${S}$$上の二項関係が対称的であるためには, $${(x,y)}$$を要素に含める場合は$${(y,x)}$$も要素に含めなければならない
$${(x,x)}$$となっている要素は含める場合と含めない場合の2通りある
$${x \neq y}$$のとき$${(x,y)}$$と$${(y,x)}$$は1つの組として考え, 含める場合と含めない場合の2通りある
よって, $${\Large 2^{\large \frac{n(n+1)}{2}}}$$

※(3)の計算は、指数部分を$${S^2}$$の各列で数えるものの数$${1,2,3,…,n}$$の和にしている

(4)
$${S}$$上の二項関係が反射的かつ対称的であるためには,
$${(x,x)}$$となっている要素は含めなければならない
$${x \neq y}$$のとき$${(x,y)}$$と$${(y,x)}$$は1つの組として考え, 含める場合と含めない場合の2通りある
よって, $${\Large 2^{\large \frac{n(n-1)}{2}}}$$

※(4)の計算は、指数部分を$${S^2}$$の各列で数えるものの数$${0,1,2,…,n-1}$$の和にしている

(5)
$${S}$$上の二項関係が反対称的であるためには,
$${(x,x)}$$となっている要素は含める場合と含めない場合の2通りある
$${x \neq y}$$のとき$${(x,y)}$$と$${(y,x)}$$のどちらかしか要素に含めてはいけないので, $${(x,y)}$$と$${(y,x)}$$は1つの組として考え,$${(x,y)}$$と$${(y,x)}$$の両方を含めない場合, $${(x,y)}$$のみを含める場合, $${(y,x)}$$のみを含める場合の3通りある
よって, $${\Large 2^n 3^{\large \frac{n(n-1)}{2}}}$$

※(5)の計算は、対角線の要素とそれ以外の組とで分けて考え、3のべき乗の指数部分は$${S^2}$$の各列で数えるものの数$${0,1,2,…,n-1}$$の和にしている

(6)
$${S}$$上の二項関係が完全であるためには, $${(x,y)}$$と$${(y,x)}$$の少なくとも一方を要素に含めなければならないので,
$${(x,x)}$$となっている要素は含めなければならない
$${x \neq y}$$のとき$${(x,y)}$$と$${(y,x)}$$は1つの組として考え,$${(x,y)}$$と$${(y,x)}$$の両方を含める場合, $${(x,y)}$$のみを含める場合, $${(y,x)}$$のみを含める場合の3通りある
よって, $${\Large 3^{\large \frac{n(n-1)}{2}}}$$

※(6)の計算は、指数部分を$${S^2}$$の各列で数えるものの数$${0,1,2,…,n-1}$$の和にしている

問題13 $${A=\{a,b,c,d,e\}}$$とする。$${A}$$上の二項関係$${R=\{(a,b),(b,c),(c,e)\}}$$について、推移閉包$${R^+}$$と反射推移閉包$${R^*}$$をそれぞれ求めよ。

[解答]
$${R^+=R \cup \{(a,c),(a,e),(b,e)\}=\{(a,b),(a,e),(b,c),(b,e),(c,e)\}}$$
$${R^*=R^+ \cup \{(a,a),(b,b),(c,c),(d,d),(e,e)\}\\ \quad =\{(a,a),(a,b),(a,e),(b,b),(b,c),(b,e),(c,c),(c,e),(d,d),(e,e)\}}$$

最後に

今回は、大学数学・集合論の解説記事として、二項関係の基礎について解説しました。今回の内容は、解説と演習問題を合わせると、なかなかの分量ですが(記事を書くのがとても大変でした)、次回以降の半順序関係や同値関係の基礎となるものです。次回は、半順序関係の解説記事となる予定です。では。

この記事の続きは以下の記事です。