擬順序

質問

擬順序集合であって、半順序集合(順序集合)でないような集合って具体的にどのようなものがありますか。
例をあげていただけると助かります。よろしくおねがいします。

回答No.1

stomachman · ベストアンサー

集合X={0, 1}上の関係R={<0,0>, <0,1>, <1,0>, <1,1>}は反射的であり推移的だから擬順序関係だけれども，反対称性を持ちませんから半順序関係ではない．
　なお念のため，「擬順序集合であって、半順序集合(順序集合)でないような集合」とおっしゃるけれども，それは集合Xの性質ではなくて，X上の関係Rの性質の話です．関係Rとは，Xの要素の対<x,y>を全部集めた集合X×Xの部分集合だ，ってことはお分かりなんでしょう？

お礼

ご回答ありがとうございました。

具体的で身近な例をあげていただきたいとおもったので、擬順序関係とせず、あえて擬順序集合とさせていただいた次第です。

＞関係Rとは，Xの要素の対<x,y>を全部集めた集合X×Xの部分集合だ，ってことはお分かりなんでしょう？
これに関してはよくわかりません、お暇があればどういうことなのか教えていただけるとありがたいです。

回答No.3

stomachman

ANo.1につけられたコメントについて．

[1]

> これに関してはよくわかりません

(1)　集合Xにおける何かある２項関係Rが分かっているものだとしましょう．すると，Xの任意の要素二つa,bを持ってくれば「aRb が成り立つか，成り立たないかのどっちか」である．そこで，Xの要素二つのペア<a,b>の集合
X×X = {<a,b> | a∈X, b∈X}
を用意して，その部分集合
　Y={<a,b> | <a,b>∈X×X であって aRbである }
を考えれば，もちろん，<a,b>∈Y と aRb は同じ意味になります．

(2) さて，最初に「関係Rが分かっているものだと」しましたが，Rが「一体どう分かっている」のか．つまりRをどうやって数学で書き表せばいいかというと，結局このYを使うのです．つまり，「aRbが成り立つ」と言いたいペア<a,b>を全部含み，「aRbが成り立たない」と言いたいペア<a,b>を一切含まないような集合Yを作れば，これでRが決まった事になります．
　だから，aRbとは<a,b>∈Yによって定義された関係ということです．

(3) そこでさらに，YのことをRと書く事にすると，aRbとは<a,b>∈Rのことに他なりません．

　以上を整理しますと，

「２項関係RとはX×X = {<a,b> | a∈X, b∈X}の部分集合である．なお，<a,b>∈RのことをaRbと書く」

　非常に簡潔ですね．Rがどういう関係なのかは，集合Rによって表されていますから，これ以上ごちゃごちゃ言う必要はありません．

．
[2] なお，XがN個の要素を持つ有限集合なら，X×XはN^2個の要素を持ち，したがって２項関係はちょうど2^(N^2)通り存在します．それを性質によって分類したのが「擬順序」だの「半順序」だの「全順序」だの．

[3] 具体的な例として挙げた
X={0, 1}, R={<0,0>, <0,1>, <1,0>, <1,1>}
が「具体的」でないとおっしゃるのは，あらゆる関係を統一して扱う上記[1]のような観点をご存じなかったのでしょう．[1]をご理解になれば，これは最も具体的に書かれた関係の例だってことがお分かりになるはず．

さて，これを「身近」に感じるかどうかは，「身近と感じるように」解釈すればいいわけでして，たとえば

0：ラーメン
1：つけめん
aRb ：「P氏はaに比べて，bが同じぐらい好き」という関係

　で，このP氏はラーメンとつけめんが同じぐらい好きなのだとして，X={0, 1}の要素同士を比べてもらうと
0R0 ：「P氏はラーメンに比べて，ラーメンが同じぐらい好き」
0R1 ：「P氏はラーメンに比べて，つけめんが同じぐらい好き」
1R0 ：「P氏はつけめんに比べて，ラーメンが同じぐらい好き」
1R1 ：「P氏はつけめんに比べて，つけめんが同じぐらい好き」
はいずれも真になるので，

R={<0,0>, <0,1>, <1,0>, <1,1>}

ということになります．

回答No.2

hrsmmhr

擬順序関係aRbを
グラフG上の点の集合上で、
特定の点oからの各点aへの最短経路のリンクの数をl(a)として
経路a→....→bが存在し、経路上の任意の隣接点x,y(a→..→x→y→..→b)でl(x)>l(y)とならない
a,bに対して定義します

このとき反射律（aのみのリンクを辿らない経路も経路として認めるものとすれば）は成り立ち
推移律も明らかですが、
隣接する２点x,yでl(x)=l(y)ならばxRyかつyRxですがx!=yで、反対称律は成り立ちません