離散数学

質問

大至急です．大学の学部の離散数学の授業で、
(1)RとSが集合X上の順序のときR∘SはX上の順序になるか？理由とともに結論を述べよ．という問題で，
反対称的のとき
(x,y)∈R∘S ∩ (y,x)∈R∘S
⇒∃a,b∈X, {((x,a)∈R かつ (a,y)∈S) ∩ ((y,b)∈R かつ (b,x)∈S)}
⇒ここからどういうふうにすればわかりません．
推移的のとき
<x,y>∈R∘S ∩ <y,z>∈R∘S
⇒∃a,b∈X, {((x,a)∈R かつ (a,y)∈S) ∩ ((y, b)∈R かつ(b, z)∈S)}
⇒ ここからどういうふうにすればわかりません．

(2)<A,≦_A>と<B,≦_B>が整礎な順序集合ならば，A×B上の辞書式順序≦_lは整礎な順序であることを示せ．
A×Bの空でない任意の部分集合Sが辞書式順序≦_lに関する極小元を持つことを示せばいいんですが，どうやって示せばいいかわかりません

分かる方，教えてください。.お願いします。

回答No.5

muturajcp

(1)
RとSはX上の順序であってもR○Sは順序にならない
X={0,1}
R={(0,1),(0,0),(1,1)}
S={(1,0),(0,0),(1,1)}
とすると
RとSはX上の順序だが
R○S={(0,1),(1,0),(0,0),(1,1)}
(0,1)∈R○S&(1,0)∈R○S&0≠1だから反対称律は成り立たないから
順序とならない。

(2)
S_1={a∈A|∃b∈B((a,b)∈S)}
はAの部分集合だから
極小元をもつからそれを
e_1
とすると
S_2={b∈B|(e_1,b)∈S}
はBの部分集合だから
極小元をもつからそれを
e_2
とすると
(e_1,e_2)∈S

(a,b)≦(e_1,e_2),となる(a,b)∈S　があるとすると
a≦e_1
a∈S_1
e_1はS_1の極小元だから
a=e_1
(e_1,b)≦(e_1,e_2)
b≦e_2
b∈S_2
e_2はS_2の極小元だから
b=e_2
(a,b)=(e_1,e_2)
∴
(e_1,e_2)は極小元となる

回答No.4

graphaffine

#3の方、極小元と最小元を混同していませんか。
証明の方針としては、合っていそうですが。

回答No.3

muturajcp

(1)
RとSはX上の順序であってもR○Sは順序にならない
X={0,1}
R={(0,1),(0,0),(1,1)}
S={(1,0),(0,0),(1,1)}
とすると
RとSはX上の順序だが
R○S={(0,1),(1,0),(0,0),(1,1)}
(0,1)∈R○S&(1,0)∈R○S&0≠1だから反対称律は成り立たないから
順序とならない。
X={0,1,2}
R={(1,2),(0,0),(1,1),(2,2)}
S={(0,1),(0,0),(1,1),(2,2)}
とすると
RとSはX上の順序だが
R○S={(0,1),(1,2),(1,1),(2,2)}
(0,1)∈R○S&(1,2)∈R○Sだが、
(0,2)はR○Sに属さないから推移律は成り立たないから
順序とならない。

(2)
S_1={a∈A|∃b∈B((a,b)∈S)}
はAの部分集合だから
極小元をもつから
e_1=min(S_1)
とすると
S_2={b∈B|(e_1,b)∈S}
はBの部分集合だから
極小元をもつから
e_2=min(S_2)
とすると
(e_1,e_2)∈S
任意の
(a,b)∈Sに対して
a∈S_1だから
e_1≦a
e_1<aの場合は(e_1,e_2)<(a,b)
e_1=aの場合は
b∈S_2だから
e_2≦b
(e_1,e_2)≦(e_1,b)=(a,b)
∴
(e_1,e_2)は極小元となる

回答No.2

Tacosan

(1) 「順序であることを示す」ならこのようにすることは理解できるが, 「順序でない」と思っていながらこんなことをしている意味が分からん. 具体例を作れば百万倍は早い.

書き方もおかしいけどなぁ. 「反対称的のとき」とか「推移的のとき」は現代の日本語としておかしいし, そもそも「何が」を書かなければ全く通じない. さらに「反対称的のとき」には「(x,y)∈R∘S」なのに「推移的のとき」にはわざわざ「<x,y>∈R∘S」と書いている. わざわざ記号を使い分けてた意図は何?

(2) 「もうちょっとわかりやすく」とは, どこが分かりにくいということでしょうか? 具体的な事例は想定できますか?

補足

すいませんが，具体的な事例が想定できません．
後，A上の順序≦_Aによる順序に保存したまま移ることを使えばできるかな?ってどういうことですか?

回答No.1

Tacosan

(1) そもそも「R∘S が順序かどうか」を予測しておかないと話が進まないんだけど, それは大丈夫? どっちだと思いますか?
(2) φ: A×B→A, φ((a, b)) = a を考えると, 「A×B上の辞書式順序≦_l」における順序は φ によって「A上の順序≦_A」による順序に保存したまま移ることを使えばできる, かな?

補足

(1)自分は順序でないと思います．

(2)もうちょっと分かりやすく教えてもらえませんか?