- ベストアンサー
集合{1,2}上の半順序関係は何個存在するか?
- みんなの回答 (2)
- 専門家の回答
質問者が選んだベストアンサー
>反射、反対称、推移、対称 が満たされていても半順序関係といえるのですね? >先の3つだけ満たされている場合が半順序関係ではないのですね? 対称とはおそらく (1,1)と(2,2)のことを言っておられるのだと思いますが、これは順序関係の公理でいうと反射律が成り立つということを言っているに過ぎません。 とにかく、順序関係は反射・反対称・推移の3つの公理を満たすもの、と定義されているのですから順序の3公理を満たしさえすれば対称的であろうがなかろうがそれは半順序集合です。 おそらく「反対称」という言葉にひきづられて対称的な組があると反対称律と矛盾するような気がするのでしょうが、そんなことはありません。 すべての(「すべての」ということが重要です)要素間に(自分自身も含めて)対称的かつ反対称律を満たすような関係がある場合は、反対称律よりその集合のすべての要素は等しい、いいかえれば1点集合{1}と言うことになります。 もちろん{1}には{(1,1)}という(ただひとつの)半順序関係が成り立ちます。これは「すべての」関係が対称的であるような唯一の半順序集合です。 {(1,1),(2,2)}の場合は1と2の間に関係は定義されませんから、「すべての」要素間に対称的な関係があるわけではないですよね。 というわけでこの問題については対称的等は気にする必要はありません。
その他の回答 (1)
- oodaiko
- ベストアンサー率67% (126/186)
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の場合も考えてみて下さい。
補足
反射、反対称、推移、対称 が満たされていても半順序関係といえるのですね? 先の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)} 除去する組:( , ) 除去する組:( , ) 追加する組:( , ) 宜しくお願いします
- ベストアンサー
- 数学・算数
- 正整数の集合上の割り切る関係は半順序関係
正整数の集合Z+上の割り切る関係|は半順序関係であることを示せ。 どういうように考えれば良いかわかりませんので、是非教えてください。
- ベストアンサー
- 数学・算数
- 全順序集合ではあるが整列集合ではない集合って…?
こんにちは。 整列集合の定義は、全順序集合の中で、その部分集合が必ず最小限を持つもの でした。 ところでわざわざ全順序集合と整列集合をわけるということは、全順序集合の中でも整列集合じゃないものがあるってことですよね? しかしその部分集合が最小限を持たないような全順序集合ってどんなものなのでしょうか? 直観的にはよくわかりません… お願いします!
- ベストアンサー
- 数学・算数
- 離散数学の半順序集合に関する問題
離散数学の半順序集合に関する問題 離散数学の問題が解けずに困っています。 以下の問題を詳しく解説を交えて解いていただけるとありがたいです。 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),⊆)は束であるかどうか述べよ。 以上です。よろしくお願いします。
- ベストアンサー
- 数学・算数
お礼
そうなんですか,なんかややこしいので困ってました。どうもありがとうございました。