Hatena::ブログ(Diary)

わさっき RSSフィード

2015年08月17日

同値関係になぜ反射律が必要か

いきなりですが問題です.

集合S上の二項関係〜が,反射律,対称律,推移律をすべて満たすとき,〜はSの同値関係であるといいます.

「対称律と推移律を満たせば,反射律が導かれる.したがって同値関係の定義に反射律は不要である」という主張に対して,どう答えますか.

元ネタです.

問1 ある人が「対称律があれば、x〜yとするとき、y〜x。ここで推移律を用いるとx〜xが導かれる。だから同値関係の定義で反射律は実は余分である。」と言った。正しいだろうか?

http://nalab.mind.meiji.ac.jp/~mk/lecture/literacy-2014/equivalence.pdf

これを目にしたところで,スクロールする手を止め,少し考えました.

以前,「≠」は同値関係ではないと書いたっけ…あれは,対称律のみを満たし,反射律と推移律を満たさないのでした*1

そのあと,少し検索して,以下のPDFを見つけました.

しかしこちらは問題だけで,答えがありません.そろそろインターネットの情報を頼らず,自分で考えますか.

本腰を入れて検討すること3分…

Sの任意の要素a,bに対し,a〜bが偽となるよう,〜を定めれば,対称律と推移律を満たし,反射律は満たさないことに気づきました.

文字を使って確認:

  • 対称律とは「a〜bならばb〜a」.仮定(ここではa〜b)が成り立たないときは,結論(ここではb〜a)の真偽にかかわらず,「仮定ならば結論」は真である.よって対称律が成り立つ.
  • 推移律とは「a〜bかつb〜cならばa〜c」.仮定(ここではa〜bかつb〜c)が成り立たないときは,結論(ここではa〜c)の真偽にかかわらず,「仮定ならば結論」は真である.よって対称律が成り立つ.
  • 反射律とは「a〜a」.上で定めた〜は,この性質を満たさない.

Sは有限集合でも,無限集合でも良さそうです.要素数1でも大丈夫ですね.空集合は,まずそうです.

それで,先ほどの「問1」のPDFファイルを読み進めていくと,末尾に答えが書かれていました.

f:id:takehikom:20150817224820j:image

自分なりに検討したことが含まれており,別解もありまして,勉強になりました.

ここまでは言ってみれば,「対称律と推移律を満たすが,反射律を満たさない二項関係が存在する」です.「反射律と対称律を満たすが,推移律を満たさない二項関係」に変更すると,http://okwave.jp/qa/q402551.htmlのベストアンサーで丁寧に書かれていました.

当記事をつくるきっかけとなる情報もあるのですが割愛します.http://b.hatena.ne.jp/takehikom/20150817にて,上記のほかいくつかのブックマークを入れましたのでどうぞご覧ください.

(最終更新:2015-08-18 朝

トラックバック - http://d.hatena.ne.jp/takehikom/20150817/1439819517
リンク元