関係かんけいrelationと同値関係どうちかんけいequivalence relation-基本演習きほんえんしゅう

1演習えんしゅう方針ほうしん

関係かんけいrelationの性質せいしつは、名前なまえではなく反射性はんしゃせいreflexivity、対称性たいしょうせいsymmetry、反対称性はんたいしょうせいantisymmetry、推移性すいいせいtransitivityの定義ていぎに戻もどって判定はんていする。

2問題もんだい 1

$$A=\{1,2,3\}$$A=\{1,2,3\} 上うえの関係かんけいrelation $$R=\left\{\right(1,1),(2,2),(3,3),(1,2),(2,1\left)\right\}$$R=\{(1,1),(2,2),(3,3),(1,2),(2,1)\} について、反射性はんしゃせいreflexivityと対称性たいしょうせいsymmetryを判定はんていせよ。

2.1解答かいとう

$$(1,1),(2,2),(3,3)$$(1,1),(2,2),(3,3) がすべて含ふくまれるので、$$R$$R は反射性はんしゃせいreflexivityを満みたす。また $$(1,2)$$(1,2) と $$(2,1)$$(2,1) は両方りょうほう含ふくまれ、対角成分たいかくせいぶんは逆向ぎゃくむきにしても同おなじなので、$$R$$R は対称性たいしょうせいsymmetryを満みたす。

2.2解説かいせつ

反射性はんしゃせいreflexivityではすべての $$a\in A$$a\in A について $$(a,a)$$(a,a) が必要ひつようである。対称性たいしょうせいsymmetryでは、入はいっている矢印やじるしの逆向ぎゃくむきが必要ひつようである。

2.3よくある誤あやまり

$$(1,1)$$(1,1) だけを見みて反射性はんしゃせいreflexivityを判断はんだんする誤あやまりである。反射性はんしゃせいreflexivityには、すべての自己対じこつい $$(a,a)$$(a,a) が必要ひつようである。

3問題もんだい 2

$$A=\{1,2,3\}$$A=\{1,2,3\} 上うえの $$R=\left\{\right(1,2),(2,3\left)\right\}$$R=\{(1,2),(2,3)\} の推移閉包すいいへいほうtransitive closureを求もとめよ。

3.1解答かいとう

$$(1,2)\in R$$(1,2)\in R かつ $$(2,3)\in R$$(2,3)\in R なので、推移性すいいせいtransitivityのために $$(1,3)$$(1,3) が必要ひつようである。したがって推移閉包すいいへいほうtransitive closureは $$\left\{\right(1,2),(2,3),(1,3\left)\right\}$$\{(1,2),(2,3),(1,3)\} である。

3.2解説かいせつ

推移閉包すいいへいほうtransitive closureは、到達可能性とうたつかのうせいを直接ちょくせつの関係かんけいrelationとして追加ついかする操作そうさである。ここでは $$1$$1 から $$2$$2 を経へて $$3$$3 に到達とうたつできるので、直接ちょくせつの組くみ $$(1,3)$$(1,3) を追加ついかする必要ひつようがある。

3.3よくある誤あやまり

反射閉包はんしゃへいほうreflexive closureと混同こんどうし、$$(1,1),(2,2),(3,3)$$(1,1),(2,2),(3,3) を追加ついかする誤あやまりである。これらは、この問題もんだいでは推移性すいいせいtransitivityからは要求ようきゅうされない。

4問題もんだい 3

$$\mathbb{Z}$$\mathbb Z 上うえで $$a\sim b$$a\sim b を「$$a-b$$a-b が 2 の倍数ばいすうである」と定義ていぎする。これは同値関係どうちかんけいequivalence relationであることを示しめせ。

4.1解答かいとう

反射性はんしゃせいreflexivity: $$a-a=0$$a-a=0 は 2 の倍数ばいすうなので $$a\sim a$$a\sim a である。

対称性たいしょうせいsymmetry: $$a-b=2k$$a-b=2k なら $$b-a=-2k=2(-k)$$b-a=-2k=2(-k) なので $$b\sim a$$b\sim a である。

推移性すいいせいtransitivity: $$a-b=2k$$a-b=2k、$$b-c=2\ell$$b-c=2\ell なら $$a-c=2(k+\ell )$$a-c=2(k+\ell) なので $$a\sim c$$a\sim c である。

4.2解説かいせつ

同値関係どうちかんけいequivalence relationは 3 条件じょうけんを別々べつべつに確認かくにんする。ここでは 2 で割わった余あまりが同おなじ、つまり moduloモジュロ $$2$$2 で同おなじという分類ぶんるいを作つくっている。

4.3よくある誤あやまり

偶数ぐうすうか奇数きすうかの直感ちょっかんだけで説明せつめいし、3 条件じょうけんを確認かくにんしない誤あやまりである。

5問題もんだい 4

問題もんだい 3 の同値関係どうちかんけいequivalence relationについて、商集合しょうしゅうごうquotient set $$\mathbb{Z}/\sim$$\mathbb Z/{\sim} を述のべよ。

5.1解答かいとう

偶数ぐうすう全体ぜんたいの同値類どうちるいequivalence class $$\left[0\right]$$[0] と、奇数きすう全体ぜんたいの同値類どうちるいequivalence class $$\left[1\right]$$[1] に分わかれる。したがって $$\mathbb{Z}/\sim =\left\{\right[0],[1\left]\right\}$$\mathbb Z/{\sim}=\{[0],[1]\} である。

5.2解説かいせつ

商集合しょうしゅうごうquotient setの元げんelementは、元げんの整数せいすうではなく同値類どうちるいequivalence classである。

5.3よくある誤あやまり

$$\mathbb{Z}/\sim =\{0,1\}$$\mathbb Z/{\sim}=\{0,1\} と書かき、代表元だいひょうげんと同値類どうちるいequivalence classを混同こんどうする誤あやまりである。

6問題もんだい 5

$$\pi :\mathbb{Z}\to \mathbb{Z}/\sim$$\pi:\mathbb Z\to\mathbb Z/{\sim} を自然しぜんな射影しゃえいとする。問題もんだい 3 の同値関係どうちかんけいequivalence relationで、$$\pi \left(5\right)$$\pi(5) と $$\pi (-1)$$\pi(-1) は等ひとしいか。

6.1解答かいとう

$$\pi \left(5\right)=\left[5\right]$$\pi(5)=[5]、$$\pi (-1)=[-1]$$\pi(-1)=[-1] である。$$5-(-1)=6$$5-(-1)=6 は 2 の倍数ばいすうなので $$5\sim -1$$5\sim -1 である。したがって $$\left[5\right]=[-1]$$[5]=[-1] であり、$$\pi \left(5\right)=\pi (-1)$$\pi(5)=\pi(-1) である。

6.2解説かいせつ

自然しぜんな射影しゃえいcanonical projectionは、同値どうちequivalentな元げんelementを同おなじ同値類どうちるいequivalence classへ送おくる。

6.3よくある誤あやまり

$$5\ne -1$$5\ne -1 だから $$\pi \left(5\right)\ne \pi (-1)$$\pi(5)\ne\pi(-1) と判断はんだんする誤あやまりである。商集合しょうしゅうごうquotient setでは、元げんの値あたいではなく同値類どうちるいequivalence classを比較ひかくする。

7関連かんれんリンク

8証明しょうめい演習えんしゅう：同値関係どうちかんけいから分割ぶんかつを作つくる

8.1問題もんだい

$$\sim$$\sim を $$X$$X 上うえの同値関係どうちかんけいequivalence relationとする。同値類どうちるいequivalence class $$\left[x\right]$$[x] の集あつまりが $$X$$X の分割ぶんかつpartitionになることを証明しょうめいせよ。

8.2解答かいとう

反射性はんしゃせいより $$x\sim x$$x\sim x なので、$$x\in \left[x\right]$$x\in[x] である。したがって、すべての元げんは少すくなくとも一ひとつの同値類どうちるいに属ぞくする。

つぎに $$\left[x\right]\cap \left[y\right]\ne \text{[PARSE ERROR: Undefined("Command("varnothing")")]}$$[x]\cap[y]\ne\varnothing とする。$$z\in \left[x\right]\cap \left[y\right]$$z\in[x]\cap[y] を取とる。すると $$z\sim x$$z\sim x かつ $$z\sim y$$z\sim y である。対称性たいしょうせいより $$x\sim z$$x\sim z、推移性すいいせいより $$x\sim y$$x\sim y である。$$u\in \left[x\right]$$u\in[x] なら $$u\sim x\sim y$$u\sim x\sim y なので $$u\in \left[y\right]$$u\in[y] である。よって $$\left[x\right]\subseteq \left[y\right]$$[x]\subseteq[y] である。同様どうように $$\left[y\right]\subseteq \left[x\right]$$[y]\subseteq[x] であり、$$\left[x\right]=\left[y\right]$$[x]=[y] である。

8.3解説かいせつ

同値関係どうちかんけいequivalence relationの三みっつの条件じょうけんは、分割ぶんかつpartitionの性質せいしつを保証ほしょうしている。反射性はんしゃせいreflexivityは各かく元げんelementを自分じぶんの類るいに入いれ、対称性たいしょうせいsymmetryと推移性すいいせいtransitivityは交まじわった類るいが一致いっちすることを強制きょうせいする。