反射性、対称性、推移性について

質問

「反射性、対称性、推移性のうち二つが成立するならば，全て成立する。」ということを論理学の授業で聴いたことがあるのですが，どうしてかわからなくなってしまいました。
おそらく何らかの制約があるから上記のことがいえると思うのですが，それは何でしょうか？

回答No.2

shkwta · ベストアンサー

一般に、３個以上の要素を有する任意の集合Sで、
　(1)反射性と対称性はあるが、推移性のない関係
　(2)対称性と推移性はあるが、反射性のない関係
　(3)推移性と反射性はあるが、対称性のない関係
の３種がすべて存在します。

(実例）
集合Sを、どれも空でなく、互いに共通部分のない３つの真部分集合A, B, Cに分割します。

(1)関係＆について、
x＆yとは：　x∈B または y∈B または x,y∈A または x,y∈C

と定義すると、反射性と対称性があることは簡単に示せます。
x∈A, y∈B, z∈C のとき x＆y, y＆zですが、x＆zではないので推移性はありません。

(2)関係＄について、
x＄y とは：　x,y∈A
と定義すると、対称性と推移性は簡単に示せます。
x∈B または x∈C のとき x＄x ではないので反射性はありません。

(3)関係％について、
x％y とは：　x∈A または y∈C または x,y∈B

と定義すると、反射性は簡単に示せます。
x％y かつ y％z のとき、
　ア: x∈A かつ (y∈A または z∈C または y,z∈B)
イ: x,y∈B かつ (z∈B または z∈C)
　ウ: x∈B かつ y,z∈C
　エ: x,y,z∈C
のどれかなので、x％z となり、推移性も示せます。

x∈A かつ y∈C のとき、 x＆y だが y＆x でないので対称性はありません。

お礼

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

実例は少し難しいですが，なんとなくわかりました。
これは別の授業（計算機科学）でやったことでもあると思います。
私はこの考えに汚染されてしまっているのです。
それとも、論理学の授業でやったことが間違っていたのでしょうか？

補足

３個の要素があったとき、その３個からなる反射性をすべてもち、その３個からなる対称性をすべてもつとき、その３個からなる推移性をすべてもつということはないでしょうか？
つまり、shkwtaさんのやりかたは部分的な反射性や部分的な対称性や部分的な推移性でしかないと思います。すべての反射性がいえないから反射性とは呼ばないということだと思います。いや、逆に部分的に反射性が成り立てば、それを反射性が成り立つとしているのかもしれません。
私もよくわかっていないのですが、少し記憶が回復してきたような気がしています。

回答No.3

sunasearch

#1です。

（A)「２つの条件が成り立つ→３つとも条件が成り立つ」
において、
逆は当然成り立つことと、
「３つとも条件が成り立つこと」と「同値関係がある」ことは同値ですから、

（A）が成り立つときは必ず同値関係にある必要があります。

無理やり制約の形で書くとすれば、
「同値関係にある」という制約（条件）のもとでは、「反射性、対称性、推移性のうち二つが成立するならば，全て成立する。」でしょうか。

お礼

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

そのとおりだと思います。しかし、私が習ったこととは違う感じです。

補足

私の昔のノートを読み返していたら、間違っているということがわかりました。
反射性∀x∀y(xRy→xRx)が対称性∀x∀y(xRy→yRx)と推移性∀x∀y∀z((xRy＆yRz)→xRz))から導かれるということでした。これは確かに導けます。ただし、他の二つから一つを導くことはできませんでした。それが本当かどうかもわかりませんが。
しかし、別の箇所で反射性の述語論理の形を∀x(xRx)としていたので、反射性∀x∀y(xRy→xRx)というのは証明の都合上、考え出されたものに過ぎないということだと解釈しています。

回答No.1

sunasearch

一般には上記のことは言えないと思います。

二項関係Rについて言うと、
「反射性、対称性、推移性」の３つが同時に成立するとき、Rを同値関係と呼びます。

反射性：A=A
対称性：A=B → B=A
推移性：A=B かつ B=C → A=C

しかし、Rに小なりイコール≦（もしくは⊆）を用いると、

反射性：A ≦ A
推移性：A ≦ B かつ B ≦ C → A ≦ C
は満たしますが、
対称性：A ≦ B → B ≦ A
は満たしません。

お礼

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

＞一般には上記のことは言えないと思います。

そのとおりだと思っています。だから、何らかの制約があるからだと思っているのです。

それが同値関係である場合にはという制約だったのでしょうか？それでは、３つが同時に成立するときは３つが同時に成立する。これでは同語反復になってしまいます。少しも面白くありません。

どれか２つが成立するならばすべてが成立するということが言える条件を知りたいのです。