• ベストアンサー

集合{1,2}上の半順序関係は何個存在するか?

oodaikoの回答

  • oodaiko
  • ベストアンサー率67% (126/186)
回答No.1

3つめのパターンは{(1,1),(2,2)}でOKですよ >対称的が入ってしまうので… なにか勘違いしていませんか? 半順序関係というのは要するにその関係が順序の3公理(反射、反対称、推移)を満たせば良いのですから {(1,1),(2,2)}が3公理を満たしていることをチェックしてみましょう。 反射律は明らかですね。 多分mahiro19さんは反対称性について思い違いをしていると思うので、これについて解説します。 順序関係と言うのは必ずしも対称な関係ではありません。AとBに順序関係があるということをイメージしやすい言葉で置き換えて「AはBより《前》の要素である」(逆にBはAより《後》の要素であるといっても同様です)と言い替えてみましょう。 「AはBより《前》の要素である」という命題が成り立っていたとしても、AとBを入れ換えると命題は必ずしも成り立つとは限りません。ですが 「AはBより《前》の要素であり、かつBはAより《前》の要素である」と言う条件が成りたつならばA=B …(H) という命題は成り立ってくれないと不便でしょう。反対称律というのはこの命題を公理にしたものです。 そして重要なことは、そもそもAとBの間に順序関係が定義されていない場合にはこの命題Hは無条件で成り立つ、ということです。つまりその場合はA=BだろうがA≠Bだろうが関係ないのです。 それは前提条件である「AはBより《前》の要素であり、かつBはAより《前》の要素である」が偽だからです。「PならばQ」という形の命題は前提(命題P)が偽なら結論(命題Q)の真偽に関わらず命題自体は真です。これは命題論理の基本的な規則です。 というわけで反対称律を満たしていることをいうためには前提が成り立つような組合せについてのみチェックすれば良いのです。 このパターンについて書き下してみると (1,1)かつ(1,1)ならば1=1 (2,2)かつ(2,2)ならば2=2 の2つをチェックすればよろしい。どちらも明らかに正しいですね。だから反対称律もOK 推移律についても同様に、前提部分の「(A,B)かつ(B,C)」が成り立つ組合せのみチェックすればOKです。これも大丈夫ですね。 *********************************************** 質問の回答はここまでですが、ちょっとついでの話を 「どの2つの要素にも(同じ要素同士にも)関係が定義されない」という「関係」を空関係といいます。空関係はもちろん順序関係ではありませんが、反射律・反対称律・推移律のどれも満たさないわけではありません。直感に反するようですが空関係は反対称律・推移律を満たします。その理由は……もうおわかりですね。 も一つついでの話を n個の集合の上の半順序集合の数はnが大きくなると急速に増えます。n=3で19個,n=4で219個,n=5で4231個,n=6で130023個と急速に増えます。もっともこれは個々の要素を区別する場合です。つまり{(1,1),(1,2),(2,2)}と{(1,1),(2,1),(2,2)}を異なる半順序集合と見なす場合です。個々の要素を区別しない、つまりこの2つを同じ半順序とみなすような場合はもう少し少なくなります。(それでもn=6で318個になります)お時間があればn=3の場合も考えてみて下さい。

mahiro19
質問者

補足

反射、反対称、推移、対称 が満たされていても半順序関係といえるのですね? 先の3つだけ満たされている場合が半順序関係ではないのですね?

関連するQ&A

  • 全順序集合と半順序集合

    x=(x1,…xn) , y=(y1,…,yn) ∈R^n に対して x≦yを Σ(i=1からkまで)x(i) ≦ Σ(i=1からkまで)y(i) (k=1,2,…,n) によってR^nに関係≦を導入する。 R^nはこの≦に関して半順序集合になっていることを示せ。 また、x≦(にならない)y , y≦(にならない)x となるx,yの例をあげよ。 という順序集合の問題です。 反射的・反対称的・推移的の3つを示せば良いのは分かるのですが、どのように書いて良のか分かりません。 例:推移的を示す 任意のx=(x1,…xn) , y=(y1,…,yn) , z=(z1,…,zn) ∈R^n に対して Σ(i=1からkまで)x(i) ≦ Σ(i=1からkまで)y(i) かつ Σ(i=1からkまで)y(i) ≦ Σ(i=1からkまで)z(i) ならば Σ(i=1からkまで)x(i) ≦ Σ(i=1からkまで)z(i)  は成り立つ。 このように、そのまま書けば良いのでしょうか・・・? それから、最後の例をあげよのところは、全順序集合にはならないための反例になっているのだと思いますが、どうしても思いつきません。 ∞を考えるのでしょうか・・・? そもそも全順序集合は半順序集合が成り立つことが前提みたいに習いましたが、反対称的の 任意のa,b∈Xに対して aRb,bRa⇒a=b ここで、aRbとbRaが成り立つことを言ってしまっているので、必ずaRbかbRaになっているような半順序集合は全順序集合という定義も意味がないような気がしてしまいます。 よろしくお願いします。

  • 「半順序集合になるようにせよ」という問が解けません

    急ぎです。 次の問が全く解けません。どなたかお願いします。 以下の集合Aと二項関係Rの組は順序集合ではないが、Rに対して操作(要素の除去や追加)によって半順序集合(A,R)になるようにせよ(反射律、反対称律、推移律を満たすようにせよ)。なお、行ってよい操作は最大で除去は2回、追加は1界までとする。 A={a,b,c,d,e,f,g} R={(a,a),(a,c),(a,e),(a,g),(b,a),(b,b),(b,e),(c,c),(c,g),(d,b),(d,d),(d,f),(e,e),(e,g),(f,f),(f,g),(g,g)} 除去する組:(  ,  ) 除去する組:(  ,  ) 追加する組:(  ,  ) 宜しくお願いします

  • 半順序集合の問題

    集合Sの冪集合φ(s)上の2項関係⊆が半順序関係であることを示せ。また、全順序関係でないことを S={1,2,3}の場合で反例を挙げて示せ。が分からないです。 含まれる項の数で比較できないから半順序? 分からないです。 無知な僕にも分かるように解説していただけると嬉しいです

  • 正整数の集合上の割り切る関係は半順序関係

    正整数の集合Z+上の割り切る関係|は半順序関係であることを示せ。 どういうように考えれば良いかわかりませんので、是非教えてください。

  • 正整数の集合上の割り切る関係は半順序関係

    正整数の集合上Z+の割り切る関係|は半順序関係を示せ。 どういうように考ればよいか、よくわからないので、ぜひ教えてください。

  • 全順序集合について

    以下の命題の真偽が分かりません。 「(A, ≦): 全順序集合, X⊆A, Y⊆A, inf(X∪Y)=aとしたとき、 inf(X)とinf(Y)の少なくとも一方が存在してaに一致する」 真であれば証明の方針を、 偽であれば反例を教えていただけないでしょうか? よろしくお願いします。

  • 順序集合について…

    Aが全順序集合ならば、Aの最大元と極大元の最小元と極小元の概念は一致することを示せ。 という問題なのですが、 つまり最大元(最小元)⇒極大元(極小元)これは、定義より当たり前なので 極大元(極小元)⇒最大元(最小元)これを示せばいんですよね。 ここが問題で、私にはこの最大元(最小元)と極大元(極小元)の違いがよく分かりません。詳しく教えてくれませんか?

  • 順序集合

    自然数の順序集合(N,|)について A={1,2,3,4,5,6,7,8,9,10}に対し,n|m⇔∃k[m=nk](nはmの約数)の順序関係のもとでAの最大元,最小元,極大元,極小元,上限,下限を求めよ(存在しない場合は「存在しない」と解答) 最大元:存在しない,最小元:1,極大元:6,7,8,9,10,極小元:1,上限:2520,下限:1・・・参考書をいろいろ読んで考えたのですが、最大元~下限の各語句の意味があまり理解できず答えに自信がないので、なぜそれが答えなのかと聞かれた場合きちんと説明ができません。どなたか詳しく説明してもらえないでしょうか

  • 全順序集合ではあるが整列集合ではない集合って…?

    こんにちは。 整列集合の定義は、全順序集合の中で、その部分集合が必ず最小限を持つもの でした。 ところでわざわざ全順序集合と整列集合をわけるということは、全順序集合の中でも整列集合じゃないものがあるってことですよね? しかしその部分集合が最小限を持たないような全順序集合ってどんなものなのでしょうか? 直観的にはよくわかりません… お願いします!

  • 離散数学の半順序集合に関する問題

    離散数学の半順序集合に関する問題 離散数学の問題が解けずに困っています。 以下の問題を詳しく解説を交えて解いていただけるとありがたいです。 Aを集合とするとき、半順序集合(P(A),⊆)について、次の(1)(2)に答えよ。 (1)X,Y∈P(A)の上限、下限をそれぞれsup{X,Y}、inf{X,Y}とする。 このとき、sup{X,Y}=X∪Y      inf{X,Y}=X∩Y をそれぞれ証明せよ。 (2)半順序集合(P(A),⊆)は束であるかどうか述べよ。 以上です。よろしくお願いします。