要素数nの集合Aにおける反射律・対称律

質問

要素数ｎの集合Aにおいて

(1)A上の関係で反射的なものはいくつあるか？
これは空集合以外の(n-1)個でしょうか？

(2)A上の関係で反射的かつ対称的なものはいくつあるか？
これは{a}や{a,b,c}などは反射・対称を満たしているのでしょうか？

離散数学の問題の考え方が分からずに困ってます。説明よろしくお願いします。

回答No.2

rabbit_cat

＞補足
R={(a,a)(a,b)(b,a)(b,b)} なら、反射律を満たしますね。
これ以外にも、
R={(a,a)(b,b)}
R={(a,a)(a,b)(b,b)}
R={(a,a)(b,a)(b,b)}
なら、反射律を満たしているわけです。

お礼

そうなるとｎ=3のときは64個ありますから、
1,4,64,・・・から　2^(n^2 -n)個　となるんですね。
ありがとうございます。

回答No.1

rabbit_cat

(1) だけ。
＞これは空集合以外の(n-1)個でしょうか？
まず、「関係」というのを何だか理解していますか？
http://ja.wikipedia.org/wiki/%E4%BA%8C%E9%A0%85%E9%96%A2%E4%BF%82
ここにwikipediaでの定義が書いてありますが、授業では「関係」をどう定義してましたか？

とりあえず、wikipediaの定義だと思えば、
集合Ａと集合Ａの直積A×Aは、n^2個の要素を持っていますが、この直積集合の部分集合Ｒのことを「Ａ上の関係」と言います。
で、反射律を満たすってことですから、
任意のα∈Aについて、{α,α}∈R　…☆
は満たしてないといけないので、これを満たすような、A×Aの部分集合Ｒの取り方を数えればいいです。
ここからは、まあ、高校の場合の数の問題なわけですが、つまり、A×Aは全部でn^2個要素がある集合で、そのうち、☆から、n個は常にＲに入っていないといけませんから、残りの n^2-n 個の要素をＲに入れるか入れないかを考えれば、題意を満たす関係は、全部で
2^(n^2-n)
個あることがわかります。

補足

Rの取り方についてですが、要素数2のA={a,b}とします。
R={(a,a)(a,b)(b,a)(b,b)}ですね。このとき、(a,b)に関して a∊A b∊A　なので　(a,a)(b,b)∊R　なので反射律が成り立つといえるのでしょうか？