集合｛１，２｝上の半順序関係は何個存在するか？

質問

自分で解いてみると2個になったんですが3個のようです
｛（１，１）,（１，２）,（２，２）｝と
｛（１，１）,（２，１）,（２，２））は出たのですけど
もうひとつありますか?
｛（１，１）,（２，２）｝だと対称的が入ってしまうので…
誰か教えてください　お願いします

回答No.2

oodaiko · ベストアンサー

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

対称とはおそらく
(１,１)と(２,２)のことを言っておられるのだと思いますが、これは順序関係の公理でいうと反射律が成り立つということを言っているに過ぎません。

とにかく、順序関係は反射・反対称・推移の３つの公理を満たすもの、と定義されているのですから順序の３公理を満たしさえすれば対称的であろうがなかろうがそれは半順序集合です。
おそらく「反対称」という言葉にひきづられて対称的な組があると反対称律と矛盾するような気がするのでしょうが、そんなことはありません。
すべての(「すべての」ということが重要です)要素間に(自分自身も含めて)対称的かつ反対称律を満たすような関係がある場合は、反対称律よりその集合のすべての要素は等しい、いいかえれば１点集合{1}と言うことになります。
もちろん{1}には{(1,1)}という(ただひとつの)半順序関係が成り立ちます。これは「すべての」関係が対称的であるような唯一の半順序集合です。
｛（１，１）,（２，２）｝の場合は１と２の間に関係は定義されませんから、「すべての」要素間に対称的な関係があるわけではないですよね。

というわけでこの問題については対称的等は気にする必要はありません。

お礼

そうなんですか,なんかややこしいので困ってました。どうもありがとうございました。

回答No.1

oodaiko

３つめのパターンは｛（１，１）,（２，２）｝でＯＫですよ

＞対称的が入ってしまうので…
なにか勘違いしていませんか？
半順序関係というのは要するにその関係が順序の３公理（反射、反対称、推移）を満たせば良いのですから
｛（１，１）,（２，２）｝が３公理を満たしていることをチェックしてみましょう。

反射律は明らかですね。

多分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より《前》の要素である」が偽だからです。「ＰならばＱ」という形の命題は前提（命題Ｐ）が偽なら結論（命題Ｑ）の真偽に関わらず命題自体は真です。これは命題論理の基本的な規則です。

というわけで反対称律を満たしていることをいうためには前提が成り立つような組合せについてのみチェックすれば良いのです。
このパターンについて書き下してみると
（１，１）かつ（１，１）ならば１＝１
（２，２）かつ（２，２）ならば２＝２
の２つをチェックすればよろしい。どちらも明らかに正しいですね。だから反対称律もＯＫ

推移律についても同様に、前提部分の「(A,B)かつ(B,C)」が成り立つ組合せのみチェックすればＯＫです。これも大丈夫ですね。

***********************************************

質問の回答はここまでですが、ちょっとついでの話を
「どの２つの要素にも（同じ要素同士にも）関係が定義されない」という「関係」を空関係といいます。空関係はもちろん順序関係ではありませんが、反射律・反対称律・推移律のどれも満たさないわけではありません。直感に反するようですが空関係は反対称律・推移律を満たします。その理由は……もうおわかりですね。

も一つついでの話を
n個の集合の上の半順序集合の数はnが大きくなると急速に増えます。n=3で19個,n=4で219個,n=5で4231個,n=6で130023個と急速に増えます。もっともこれは個々の要素を区別する場合です。つまり｛（１，１）,（１，２）,（２，２）｝と｛（１，１）,（２，１）,（２，２）｝を異なる半順序集合と見なす場合です。個々の要素を区別しない、つまりこの２つを同じ半順序とみなすような場合はもう少し少なくなります。（それでもn=6で318個になります）お時間があればn=3の場合も考えてみて下さい。

補足

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