離散数学 2項関係についての問題

質問

某国立大の情報系の学科に通っているものです。情報系では離散数学を習うのですが、あまり理解が進まず困っています。
今回は下記の問題に関して質問があります。

Ｓ＝｛１，２，３，４，５，６，７，８，９，１０｝とする
（１）Ｓ上の2項関係で対照的なものはいくつあるか
（２）　　　〃　　　反射的なものはいくつあるか
（３）　　　〃　　　反射的かつ対照的なものはいくつあるか

という問題です。
Ｓ上の2項関係の総数は　２の１００乗　個あるというところまでは分かります。
Ｓ上の二項関係をＲとして
反射的・・・すべてのＳの要素Ｘに対して（Ｘ，Ｘ）∈Ｒ
対象的・・・（Ｘ，Ｙ）∈Ｒ　ならば　（Ｙ，Ｘ）∈Ｒ
こんな感じだとは思うのですが、ここからどう回答していけばよいのか見当がつきません。

もし、解法をご存知の方がいましたらご助力願います。

回答No.3

Tacosan · ベストアンサー

うん, S×S が 100個の要素からなっていて, R はその部分集合だから 2^100通り.
ちょいと #1 へのコメントを見たんだけど, 「反射的」と「対称的」が逆だよ....
反射的な関係であれば全ての x ∈ S に対して (x, x) ∈ R だから, 「R に入れるかどうか」の選択ができる組み合わせは x ≠ y であるような (x, y) に限定されます. これは何組ありますか?
対称的な関係も同様で, (x, y) ∈ R if and only if (y, x) ∈ R だということは, 「x > y であるような (x, y) については ((y, x) ∈ R かどうかを決めれば) 自動的に決まってしまうので考えなくてもよい」ということになります.

お礼

ちょいと #1 へのコメントを見たんだけど, 「反射的」と「対称的」が逆だよ....
>>>逆に書いてしまいました；（１）と（２）の答えは逆です。
考え方はあんな感じで合っているのでしょうか？お手数かけます・・・

回答No.2

Tacosan

S 上の 2項関係がなぜ 2^100個あるのかは理解できてますか?

お礼

まず直積Ｓ×Ｓ＝１０×１０＝１００
二項関係＝直積の部分集合なので、１００個の要素がある直積Ｓ×Ｓの部分集合の数を出せばよいので→２^１００個

自分ではこういう風に覚えているのですが・・・

回答No.1

koko_u_

まあ、S = {1, 2, 3} くらいでまずは考えるべ。

お礼

S = {1, 2, 3}とすると・・・
Ｓ×Ｓ＝９より二項関係の総数は２^９個

（１）（１,１）（２,２）（３,３）の３つが必ず含まれる直積の部分集合の数を出せばよい（？

（１,１）（２,２）（３,３）の３つは必ず含まれるので、直積の総数から３を引いて９－３＝６
直積の総数を6個と考えればよいので２^６個

（２）Ｘ、ＹをＳに含まれる数・Ｓ上の二項関係をＲとしてとして
（Ｘ，Ｙ）∈Ｒ　ならば　（Ｙ，Ｘ）∈Ｒ　
（Ｘ,Ｙ）（Ｙ,Ｘ）のどちらかがＲに含まれるかどうか調べればよい（？

（１,１）（２,２）（３,３）の３つと
それ以外の要素の半分６/３＝２を足して　５　したがって２^５個

（３）（１,１）（２,２）（３,３）の３つは必ず含まれるので
５－３＝２から　２^２個

一応やってみました。ぜんぜん自信ありませんけど・・・；
（１,１）や（２,２）とかは対照的と見ていいんでしょうか・・・？