うさぎでもわかる離散数学　第4羽　二項関係編

こんにちは、ももやまです！

今回は、離散数学で習うだろう単元の1つ、「二項関係」についてまとめていこうと思います。

 

なお、今回は、説明と例題を交互に挟んでいきたいと思います。

 

 

前回の第3羽はこちらから↓ 

www.momoyama-usagi.com

スポンサードリンク

１．二項関係ってなに？

二項関係とは、とある集合 \( S \) から、集合 \( S \) の要素を2つ並べたものを何個か集めた集合のことです。

前回の集合編で習った言葉を使って説明すると、\( S \times S \) の部分集合を集合 \( S \) の二項関係といいます。

 

とはいっても言葉だけだと少しわかりにくいかもしれないので、

具体例でさらに説明したいと思います。

例えば、\( S = \{1,2,3\} \) とします。このとき、集合 \( S \) の直積集合である \( S \times S \) は、\( S \times S = \{(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)\} \) となります。\( S \times S \) の部分集合が \( S \) の二項関係なので、\( S \times S \) の要素の中からいくつかを選んだものが \( S \) の二項関係となります。

 

\( S \) の二項関係の例としては、\( \{(1,2),(2,3)\} \), \( \{(2,1),(3,2),(1,2)\} \) , \( \{(2,2)\} \), \( \phi \) などが挙げられます。 

では、ここで復習もかねて例題を1つ解いてみましょう。

例題1

集合 \( S \) を \( S = \{1,2,3,…,n\} \) とする。このとき、次の問いに答えなさい。

(1) 集合 \( S \) の要素数を求めなさい。
(2) 直積集合 \( S \times S \) の要素数を求めなさい。
(3) 集合 \( S \) のべき集合 \( 2^{S} \) の要素数を求めなさい。
(4) \( S \) の二項関係の総数はいくつですか。
(5) 直積集合の直積集合 \( (S \times S) \times (S \times S) \) の要素数を求めなさい。
(6) \( S \times S \) の二項関係の総数はいくつですか。

解答1

(1)

\( n \) 個（これはウォーミングアップ）

 

(2)

直積集合の要素数は、それぞれの要素数の積となる。
よって、\( n \times n = n^{2} \) となり、答えは \(  n^{2} \) 個となる。

(3)

\( S \) のべき集合は集合 \( S \) の要素数、つまり\(  n \) 個の要素に対して、選ぶか選ばないかの2つの選び方があるので、答えは \( 2^{n} \) 個となります。

(4)

\( S \) の二項関係の総数は直積集合 \( S \times S \) の部分集合の総数に一致する。
つまり、\( S \times S \) のそれぞれの要素を選ぶか選ばないかの2つの選び方がある（考え方は \( S \times S \) のべき集合の要素数を求めるときと同じ）。

よって、\( 2^{n^{2}} \) 個となる。

 

(5)

ここから若干むずかしめ。

\( S \times S \) の要素数は \(  n^{2} \) 個なので、\( (S \times S) \times (S \times S) \) の要素数は、\( n^{2} \times n^{2} = n^{4} \) となり、答えは \(  n^{4} \) 個となります。

 

(6) 

\( S \times S \) の二項関係の総数は直積集合 \( (S \times S) \times (S \times S) \) の部分集合の総数と一致する。

直積集合 \( (S \times S) \times (S \times S) \) の要素数は(5)より \(  n^{4} \) 個となるので、\( (S \times S) \times (S \times S) \) のそれぞれの要素を選ぶか選ばないかの2つの選び方がある。

よって、\( 2^{n^{4}} \) 個となる。

 

スポンサードリンク

２．二項関係の4つの性質＋おまけ

ここからは、二項関係の大切な4つの性質についてまとめていきます。

ただし、集合 \( A \) は、0以上の整数全体とします。また、\( x,y,n \) は0以上の整数とします。

1. 反射性 

\( \forall x \in A,\ x R x \) ( \( (x,x) \in R \) ) が数式での定義

すべての \( x \) に対して、2つの変数 \( x,y \) が等しい、つまり \( x = y \) のときは常に成り立つという性質。

馴染みがある関係としては \(  \geqq \) がある。

（\( x \geqq x \) は常に成り立つでしょ）

2. 対称性 

\( \forall x, \forall y \in A,\ x R y \to y R x \) ( \( (x,y) \in R \to (y,x) \in R \) ) が数式での定義

2つの変数 \( x,y \) が関係を満たすとき、その2つの変数を入れ替えても関係が成立する性質。

日本語バージョンの例をあげると、

• 鈴木くんは桃山さんのことを好きなら、桃山さんは鈴木さんのことを好き
• さとしくんがももかちゃんのこと友達だと思ってくれてたら、ももかちゃんはさとしくんのことも友達！

みたいな感じ。友達関係も恋愛関係も対称性満たせるように頑張ろう。

対称性を満たす馴染みの深い関係としては、\( = \) が1つある。

（\( x = y \) ならば必ず \( y = x \) だよね？）

 

3. 反対称性 

\( \forall x, \forall y \in A,\ x R y \land y R x \to x = y \) ( \( (x,y) \in R \land (y,x) \in R \to x = y \) ) が数式での定義

2つの変数 \( x,y \) を入れ替えても関係を満たすとき、その2つの変数は必ず等しいという性質です。

日本語バージョンで言うと、

• 鈴木さんは桃山さんのことが好きで、桃山さんは鈴木さんのことが好きなら鈴木さんと桃山さんは一心同体だね！
• さとしくんがももかちゃんのことを友達だと思ってて、ももかちゃんもさとしくんのことも友達だと思ってたら、さとしくんとももかちゃんは一心同体だね！

みたいな感じ。一心同体を「＝」としています。

目指せ一心同体！

 

4. 推移性 

\( \forall x, \forall y, \forall z \in A,\ x R y \land y R z \to x R z \) ( \( (x,y) \in R \land (y,z) \in R \to(y,z) \in R \) ) が数式での定義

三段論法です、はい。

\( x \) と \( y \) の関係が成立し、 \( y \) と \( z \) の関係が成立したら、\( x \) と \( z \) の関係も成立するという関係。

日本語で言うと、

• 山田くんが佐藤さんと友達で、佐藤さんが桃山くんと友達なら山田くんと桃山くんも友達！

みたいな感じ。友達関係の推移性は意外と難しい…

おまけ　比較可能（完全性）

\( \forall x, \forall y \in A,\ x R y \lor y R x \) ( \( (x,y) \in R \lor (y,x) \in R \) ) が数式での定義

集合の範囲内で適当に数を2つ選んだとき、その数そのままか \( x,y \) を入れ替えると必ず関係を満たすもの。

具体例で説明したほうが早いので具体例で説明していこう。

 

例えば、\( S = \{1,2,3,4\} \) とします。すると、\( S \times S \) の要素は下の図のような感じになります。この黒色の部分（反射性満たす部分）＋同じ色がついた2つの要素のうちの1つ以上の要素から集めて作った部分集合が比較可能な（完全性を持つ）2項関係。

(1,1)	(1,2)	(1,3)	(1,4)
(2,1)	(2,2)	(2,3)	(2,4)
(3,1)	(3,2)	(3,3)	(3,4)
(4,1)	(4,2)	(4,3)	(4,4)

例えば、R = {(1,1),(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(3,3),(3,4),(4,4)} は完全性を持ちます。（色の部分が対応しています）

 

以上4つの性質です！

 

では、例題で1つ練習してみましょう！

例題2

つぎのように定義される0以上の整数上の二項関係 \( R \) が
(1) 反射性　(2) 対称性　(3) 反対称性　(4) 推移性
を満たすかどうかを調べなさい。ただし、\( n \) は0以上の整数とする。

\( x R y \Leftrightarrow xy = 2n \) 

 

解答2

これは、\( x,y \) の積が偶数となるという関係である。

基本的に、このような問題の場合は反例を1つ見つければ成立しないことがわかるため、明らかに成り立つもの以外は1つ反例を頑張って見つけようとするのがよい。

(1)

反射性が成り立つということは、\( x = y \) が成り立つということである。しかし、\( (x,y) = (1,1) \) のとき、積が奇数となってしまい、成立しない。

 

(2)

対称性が成り立つということは、変数を入れ替えても関係が成立するということである。掛け算の積は、順序を入れ替えても計算結果は変わらないため、対称性は成立する。

 

(3)

反対称性が成り立つということは、変数を入れ替えても関係が成立する場合、その2つの変数は等しいという関係だが、例えば \( (x,y) = (1,2) \) と \( (x,y) = (2,1) \) はともに関係を満たすが、\( 1 \not= 2 \) なため、反対称性は成立しない。

 

(4) 例えば \( (x,y) = (1,2) \) と \( (x,y) = (2,3) \) はともに関係を満たすが、\( (x,y) = (1,3) \) の関係が成立しないので推移性も成り立たない。

よって、
(1) 成立しない（反例： \( 1R1 \) ではない。）
(2) 成立する
(3) 成立しない（反例：\( 1R2 \) かつ \( 2R1 \) だが \( 1\not= 2 \) ）
(4) 成立しない（反例：\( 1R2 \) かつ\( 2R3 \) だが \( 1R3 \) ではない）
となる。

 

スポンサードリンク

3．半順序・同値関係

関係が反射性・反対称性・推移性の3つを満たすとき、半順序関係ということができます。

また、半順序関係に加えて比較可能と言えるとき、全順序関係ということができます。

さらに、反射性・対称性・推移性の3つを満たすとき、同値関係ということができます。

これだけです()

 

例題3

つぎのように定義される集合 \( S = \{1,2,3\} \) 上の2項関係 \( R_1 \) , \( R_2 \), \( R_3 \) 
(1) 反射性　(2) 対称性　(3) 反対称性　(4) 推移性
を満たすかどうかを調べ、さらに同値関係、半順序であるかどうかも調べよ。

\( R_1 = \{(1,1),(2,2),(3,3)\} \)
\( R_2 = \{(1,2),(2,1),(1,1),(2,3),(3,3)\} \)
\( R_3 = \phi \)

解説3

(1)

反射性は2つの変数が等しいときは常に成立する。

今回は \( S = \{1,2,3\} \) 上なので、\( (1,1),(2,2),(3,3) \) が集合の要素にすべて含まれていれば成立。

よって \( R_1 \) は成立し、それ以外は成立しない。
（\( R_2 \) の反例：\( (2,2) \notin R_2 \)　\( R_3 \) の反例：\( (1,1) \notin R_3 \)）

 

(2)

対称性は、関係が成立している変数を入れ替えても成立したままになる法則。

そもそも関係が成立している変数がない \( R_3 \) は前提が偽となり、成立する。

\( R_1 \) は、そもそも \( (x,x) \) なものしかないため、入れ替えても \( (x,x) \) のままになるため \( R_1 \) も成立する。

しかし \( R_2 \) は、\( (2,3) \in R_2 \) にもかかわらず、\( (3,2) \notin R_2 \) なので反例となり、成立しない。よって、\( R_1 , R_3 \) が成立する。
（\( R_2 \) の反例：\( (2,3) \in R_2 \) だが \( (3,2) \notin R_2 \)）

 

(3)

反対称性は変数を入れ替えても成立したままの場合はその2つの数は等しいという法則。

\( R_1 \) は、\( (t,t) \) なので、\( t=t \) となり、反対称性を満たす。
（\( t \) は、1か2か3の変数とします。(4)も同様。）

\( R_2 \) は、\( (1,2) \in R_2 \) かつ \( (2,1) \in R_2 \) と入れ替えても成立するものがあるが、\( 1 \not= 2 \) なため、反例があり、反対称性は満たさない。

\( R_3 \) は、成り立つものがないため、前提が偽。よって反対称性を満たす。

(4)

推移性は三段論法。

\( R_1 \) は、\( (t,t) \) しかないので、\( (t,t) \in R_1 \) かつ \( (t,t) \in R_1 \) を満たしてたら \( (t,t) \in R_1 \) を満たすのは当たり前。よって満たす。

\( R_2 \) は、一見成り立ちそうな感じがするが、反例がある。反例は、\( (2,1) \in R_1 \) かつ \( (1,2) \in R_1 \) だが \( (2,2) \notin R_1 \) である。よって満たさない。

\( R_3 \) は、成り立つものがないため、前提が偽。よって推移性を満たす。
空集合って前提が偽になりまくるから簡単だよね。

 

表で答えをまとめてみたのでこちらでも確認してください（○が成立、×が成立しない）。
答え偏りすぎたな…

	反射性	対称性	反対称性	推移性	半順序	同値関係
\( R_1 \)	○	○	○	○	○	○
\( R_2 \)	×	×	×	×	×	×
\( R_3 \)	×	○	○	○	×	×

 

最後に関数を数え上げる問題をもう1つ行ってみましょう。

ちょっと難しめですが、がんばってください！

例題4

集合 \( S \) を \( S = \{1,2,3,…,n\} \) とする。このとき、次の問いに答えなさい。
（例題1のつづき）

(1) \( S \) の二項関係の総数は何個ありますか。
(2) \( S \) の二項関係のうち、反射性を満たすものは何個ありますか。
(3) \( S \) の二項関係のうち、対称性を満たすものは何個ありますか。
(4) \( S \) の二項関係のうち、反射性かつ対称性を満たすものは何個ありますか。
(5) \( S \) の二項関係のうち、比較可能なもの（完全性を満たすもの）は何個ありますか。

解答4

この手の問題は、\( n = 3,4,5 \) くらいで表で実際に試してみたほうがいいでしょう！
\( n = 4 \) の表を書いてみました。

(1,1)	(1,2)	(1,3)	(1,4)
(2,1)	(2,2)	(2,3)	(2,4)
(3,1)	(3,2)	(3,3)	(3,4)
(4,1)	(4,2)	(4,3)	(4,4)

(1)

これは例題1と全く同じ問題、復習で出してみました。 \( 2^{n^{2}} \) 個です。

 

(2)

反射性を満たすということは、\( R=\{(1,1),(2,2),…(n,n)\} \) は必ず含まれている必要がある。この要素は \( n \) 個ある。残りの \( n^{2} - n \) 個の要素に対して、選べるか選べないかの2通りがあるので、答えは \( 2^{n^{2} - n} \) 個となる。

(1,1)	(1,2)	(1,3)	(1,4)
(2,1)	(2,2)	(2,3)	(2,4)
(3,1)	(3,2)	(3,3)	(3,4)
(4,1)	(4,2)	(4,3)	(4,4)

 

(3)

対称性を満たすということは、片方の要素があれば \( (x,y) \) を入れ替えた \( (y,x) \) の要素も満たす必要がある。例えば、\( (2,1) \) の要素があれば、\( (1,2) \) の要素も存在している必要がある。ここでさらにわかりやすくするために着色を行う。

(1,1)	(1,2)	(1,3)	(1,4)
(2,1)	(2,2)	(2,3)	(2,4)
(3,1)	(3,2)	(3,3)	(3,4)
(4,1)	(4,2)	(4,3)	(4,4)

のように、黒色以外の同じ色で囲われている部分は互いにペアで存在しなければならない。

黒色部分（反射性満たす部分）は、\( (x,y) \) の変数を入れ替えてもそのままのため、ペアである必要はなく、含まれていようが含まれていないが関係ない。

黒色以外の同じ色で囲われている部分の個数は \( n^{2} - n \) 個、ペアで \( \frac{n^{2}-n}{2} \) 個存在する。これに反射性部分の \( n \) 個を足すので、\( \frac{n^{2}+n}{2} \) 個の要素に対して、選ぶか選ばないかの2パターンがあるので、答えは \( 2^{\frac{n^{2}+n}{2}} \) 個となる。

(1,1)	(1,2)	(1,3)	(1,4)
(2,1)	(2,2)	(2,3)	(2,4)
(3,1)	(3,2)	(3,3)	(3,4)
(4,1)	(4,2)	(4,3)	(4,4)

赤色の部分は強制的に選ばれる部分、黒色部分のほうが自由に選べる部分である、そこから \( \frac{n^{2}+n}{2} \) 個の要素に対して、選ぶか選ばないかの2パターンがあると考えるパターンもある。

(4)

(3)とほぼ同じ問題。

(3)の場合に加えて反射性を満たす必要があるので、 \( R=\{(1,1),(2,2),…(n,n)\} \) は必ず含まれている必要がある。

さらに、(3)の図のように対称性を満たすためには、黒色以外の同じ色で囲われている部分は互いにペアで存在しなければならないため、\( \frac{n^{2}-n}{2} \) 個の要素に対して、選ぶか選ばないかの2パターンを選ぶこととなる。

答えは \( 2^{\frac{n^{2}-n}{2}} \) 個である。

(1,1)	(1,2)	(1,3)	(1,4)
(2,1)	(2,2)	(2,3)	(2,4)
(3,1)	(3,2)	(3,3)	(3,4)
(4,1)	(4,2)	(4,3)	(4,4)

上の図で言うと、赤色の部分が強制的に選ばれる部分、黒色部分のほうが自由に選べる部分である。

(5)

かなり発展問題。これが解けたら離散得意なフレンズになれるかもね！

また色でわかりやすく着色してみました。

(1,1)	(1,2)	(1,3)	(1,4)
(2,1)	(2,2)	(2,3)	(2,4)
(3,1)	(3,2)	(3,3)	(3,4)
(4,1)	(4,2)	(4,3)	(4,4)

上記の図で言う黒色の部分（反射性満たす部分）＋同じ色がついた2つの要素のうちの1つ以上の要素から集めて作った部分集合が比較可能な（完全性を持つ）2項関係となります。

同じ色で囲われている部分の個数は \( n^{2} - n \) 個、ペアで \( \frac{n^{2}-n}{2} \) 個存在する。

他の問題と同じように強制的に選ばれる部分と自由に選べる部分を色で分けると下の図のようになります。

(1,1)	(1,2)	(1,3)	(1,4)
(2,1)	(2,2)	(2,3)	(2,4)
(3,1)	(3,2)	(3,3)	(3,4)
(4,1)	(4,2)	(4,3)	(4,4)

\( (x,y) \in R \) または \( (y,x) \in R \) を満たせば比較可能といえるため、 \( \frac{n^{2}-n}{2} \) 個の要素に対して、その要素を \( (x,y) \) とすると、選び方は次のようになります。

1. \( (x,y) \in R \) だけを選ぶパターン
2. \( (y,x) \in R \) だけを選ぶパターン
3. \( (x,y) \in R \) と \( (y,x) \in R \) の両方を選ぶパターン

この3つのパターンがあるため、\( \frac{n^{2}-n}{2} \) 個の要素に対してそれぞれ3通りの選び方があります。よって答えは \( 3^{\frac{n^{2}-n}{2}} \) 個となります！

 

 

今回もチェック用にフォームを用意してみたので、ぜひ挑戦してみてください！
目安時間は10分です！

forms.office.com

さいごに

今回は二項関係と、二項関係における大事な4つのパターン、そして集合の要素数の数え上げ方についてまとめてみました。次回はハッセ図というちょっとパズルっぽいものを取り上げてみようと思います。では、また次回。

第5羽はこちらから↓

www.momoyama-usagi.com