いおりのノート

二項関係の総数についてメモしておきます。


離散数学をやってるときに二項関係の総数についてすんなり理解できなかったのでメモです。


集合A＝｛1,2｝上の二項関係の総数を考えてみます。

集合A＝｛1,2｝の直積A×Aは、
A×A＝｛（1,1）（1,2）（2,1）（2,2）｝
であり、このときの集合A＝｛1,2｝上の二項関係とは
A×A＝｛（1,1）（1,2）（2,1）（2,2）｝
の部分集合のことをいいます。

すなわち
｛（1,1）｝
｛（1,2）｝
｛（2,1）｝
｛（2,2）｝

｛（1,1）（1,2）｝
｛（1,1）（2,1）｝
｛（1,1）（2,2）｝
｛（1,2）（2,1）｝
｛（1,2）（2,2）｝
｛（2,1）（2,2）｝

｛（1,1）（1,2）（2,1）｝
｛（1,1）（1,2）（2,2）｝
｛（1,1）（2,1）（2,2）｝
｛（1,2）（2,1）（2,2）｝

｛（1,1）（1,2）（2,1）（2,2）｝
の合計１５
これに空集合（何も取り出さない）
｛｝
を加えて１６
これが集合A＝｛1,2｝上の二項関係の総数となります。

これは
集合A＝｛1,2｝の直積A×A
A×A＝｛（1,1）（1,2）（2,1）（2,2）｝
の４つから任意の個数を取り出すとき、その取り出し方が何通りあるかということになります。

A×A＝｛（1,1）（1,2）（2,1）（2,2）｝
の４つについて取り出すか取り出さないかの２つの選び方があります。
取り出すか取り出さないかを４つについて選ぶので
２（（1,1）を取り出すか取り出さないか）×
２（（1,2）を取り出すか取り出さないか）×
２（（2,1）を取り出すか取り出さないか）×
２（（2,2）を取り出すか取り出さないか）
＝２×２×２×２
＝２^４
＝１６
となり上の数え上げと一致します。

また
＝２^４
ここで４は集合A＝｛1,2｝の直積A×A
A×A＝｛（1,1）（1,2）（2,1）（2,2）｝
の個数です。

集合A＝｛1,2｝の直積A×A
A×A＝｛（1,1）（1,2）（2,1）（2,2）｝
のそれぞれの要素は
（集合A＝｛1,2｝から1を選ぶか2を選ぶか,集合A＝｛1,2｝から1を選ぶか2を選ぶか）
二つに一つという選択を二回するので集合A＝｛1,2｝の直積A×Aの個数は
２×２
＝２^２
となります。

これを踏まえると二項関係の総数は
２^２^２＝１６となります。


次に集合A＝｛1,...,n｝（nは正の整数）上の二項関係の総数を考えてみます。

集合A＝｛1,...,n｝（nは正の整数）の直積A×Aは、
A×A＝｛（1,1）（1,2）...（1,(n-1)）（1,n）
（2,1）（2,2）
......................................
（n,1）（n,2）...（n,(n-1)）（n,n）｝
であり、このときの集合A＝｛1,...,n｝（nは正の整数）上の二項関係とは
A×A＝｛（1,1）（1,2）...（1,(n-1)）（1,n）
（2,1）（2,2）
......................................
（n,1）（n,2）...（n,(n-1)）（n,n）｝
の部分集合のことをいいます。

集合A＝｛1,...,n｝（nは正の整数）の直積A×A
A×A＝｛（1,1）（1,2）...（1,(n-1)）（1,n）
（2,1）（2,2）
......................................
（n,1）（n,2）...（n,(n-1)）（n,n）｝
の個数は ｎ^２ ですね。
縦にｎ個横にｎ個あるのでｎ×ｎ＝ｎ^２ですね。
ここから任意の個数を取り出すとき、その取り出し方が何通りあるかが二項関係の総数となります。

ｎ^２個について取り出すか取り出さないか２通りの選び方がるので二項関係の総数は
２×２×２×２×...×２ （ｎ^２個分）
＝２^ｎ^２
となります。


さらに集合A＝｛1,...,n｝（nは正の整数）上のｎ項関係の総数を考えてみます。
集合A＝｛1,...,n｝（nは正の整数）上の二項関係がｎ項関係になっただけです。

集合A＝｛1,...,n｝（nは正の整数）上のｎ項関係とは
直積A×A×A×A×...×A×A×A×A
の部分集合のことで
集合A＝｛1,...,n｝（nは正の整数）上のｎ項関係の総数はこの部分集合の総数です。

直積A×A×A×A×...×A×A×A×A
の要素の個数はｎ個からｎ回選ぶ選び方なのでｎ^ｎ
集合A＝｛1,...,n｝（nは正の整数）上のｎ項関係の総数は
２^ｎ^ｎ
となります。