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

Relations関係かんけい and equivalence relations同値関係どうちかんけい - basic exercises

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

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

1Exercise method

For a relation関係かんけい, judge properties by returning to the definitions of reflexivity反射性はんしゃせい, symmetry対称性たいしょうせい, antisymmetry反対称性はんたいしょうせい, and transitivity推移性すいいせい, not by the names alone.

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を判定はんていせよ。

2Problem 1

For the 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)\} on $$A=\{1,2,3\}$$A=\{1,2,3\}, decide whether it is reflexive反射性はんしゃせい and symmetric対称性たいしょうせい.

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.1Answer

The pairs $$(1,1),(2,2),(3,3)$$(1,1),(2,2),(3,3) are all included, so $$R$$R is reflexive反射性はんしゃせい. Also, $$(1,2)$$(1,2) and $$(2,1)$$(2,1) are both included, and diagonal pairs remain the same when reversed. Hence $$R$$R is symmetric対称性たいしょうせい.

2.2解説かいせつ

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

2.2Explanation

For reflexivity反射性はんしゃせい, every $$a\in A$$a\in A must have $$(a,a)$$(a,a) in the relation. For symmetry対称性たいしょうせい, every arrow present in the relation must also have its reversed arrow present.

2.3よくある誤あやまり

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

2.3Common mistake

A common mistake is to check only $$(1,1)$$(1,1) and conclude reflexivity. Reflexivity requires all self-pairs.

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を求もとめよ。

3Problem 2

Find the transitive closure推移閉包すいいへいほう of $$R=\left\{\right(1,2),(2,3\left)\right\}$$R=\{(1,2),(2,3)\} on $$A=\{1,2,3\}$$A=\{1,2,3\}.

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.1Answer

Because $$(1,2)\in R$$(1,2)\in R and $$(2,3)\in R$$(2,3)\in R, transitivity推移性すいいせい requires $$(1,3)$$(1,3). Therefore the transitive closure is

3.2解説かいせつ

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

3.2Explanation

The transitive closure推移閉包すいいへいほう adds reachability as a direct relation関係かんけい. Here one can reach $$3$$3 from $$1$$1 through $$2$$2, so the direct pair $$(1,3)$$(1,3) must be added.

3.3よくある誤あやまり

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

3.3Common mistake

A common mistake is to confuse it with the reflexive closure反射閉包はんしゃへいほう and add $$(1,1),(2,2),(3,3)$$(1,1),(2,2),(3,3). Those are not forced by transitivity here.

4問題もんだい 3

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

4Problem 3

On $$\mathbb{Z}$$\mathbb Z, define $$a\sim b$$a\sim b to mean that $$a-b$$a-b is divisible by $$2$$2. Prove that this is an 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.1Answer

Reflexivity反射性はんしゃせい: $$a-a=0$$a-a=0 is divisible by $$2$$2, so $$a\sim a$$a\sim a.

Symmetry対称性たいしょうせい: if $$a-b=2k$$a-b=2k, then $$b-a=-2k=2(-k)$$b-a=-2k=2(-k), so $$b\sim a$$b\sim a.

Transitivity推移性すいいせい: if $$a-b=2k$$a-b=2k and $$b-c=2\ell$$b-c=2\ell, then $$a-c=2(k+\ell )$$a-c=2(k+\ell), so $$a\sim c$$a\sim c.

4.2解説かいせつ

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

4.2Explanation

An equivalence relation同値関係どうちかんけい is checked by verifying the three conditions separately. In this example, the relation is classifying integers by having the same remainder modulo $$2$$2.

4.3よくある誤あやまり

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

4.3Common mistake

A common mistake is to rely only on the intuition of "even or odd" without verifying the three defining conditions.

5問題もんだい 4

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

5Problem 4

For the equivalence relation同値関係どうちかんけい in Problem 3, describe the 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.1Answer

The integers split into the equivalence class同値類どうちるい $$\left[0\right]$$[0] of all even integers and the equivalence class $$\left[1\right]$$[1] of all odd integers. Therefore

5.2解説かいせつ

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

5.2Explanation

The elements元げん of a quotient set商集合しょうしゅうごう are not the original integers themselves. They are equivalence classes同値類どうちるい.

5.3よくある誤あやまり

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

5.3Common mistake

A common mistake is to write $$\mathbb{Z}/\sim =\{0,1\}$$\mathbb Z/{\sim}=\{0,1\} and confuse representatives with equivalence classes.

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) は等ひとしいか。

6Problem 5

Let $$\pi :\mathbb{Z}\to \mathbb{Z}/\sim$$\pi:\mathbb Z\to\mathbb Z/{\sim} be the natural projection for the equivalence relation同値関係どうちかんけい in Problem 3. Are $$\pi \left(5\right)$$\pi(5) and $$\pi (-1)$$\pi(-1) equal?

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.1Answer

We have $$\pi \left(5\right)=\left[5\right]$$\pi(5)=[5] and $$\pi (-1)=[-1]$$\pi(-1)=[-1]. Since $$5-(-1)=6$$5-(-1)=6 is divisible by $$2$$2, $$5\sim -1$$5\sim -1. Hence $$\left[5\right]=[-1]$$[5]=[-1] and $$\pi \left(5\right)=\pi (-1)$$\pi(5)=\pi(-1).

6.2解説かいせつ

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

6.2Explanation

The canonical projection自然な射影 sends equivalent同値どうち elements to the same 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を比較ひかくする。

6.3Common mistake

A common mistake is to decide that $$\pi \left(5\right)\ne \pi (-1)$$\pi(5)\ne\pi(-1) because $$5\ne -1$$5\ne -1. In a quotient set商集合しょうしゅうごう, one compares equivalence classes, not the original values alone.

7関連かんれんリンク

7Related links

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

8Proof exercise: constructing a partition from an equivalence relation

8.1問題もんだい

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

8.1Problem

Let $$\sim$$\sim be an equivalence relation同値関係どうちかんけい on $$X$$X. Prove that the collection of equivalence classes同値類どうちるい $$\left[x\right]$$[x] is a partition分割ぶんかつ of $$X$$X.

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.2Answer

By reflexivity反射性はんしゃせい, $$x\sim x$$x\sim x, so $$x\in \left[x\right]$$x\in[x]. Therefore every element belongs to at least one equivalence class.

Next suppose $$\left[x\right]\cap \left[y\right]\ne \text{[PARSE ERROR: Undefined("Command("varnothing")")]}$$[x]\cap[y]\ne\varnothing. Take $$z\in \left[x\right]\cap \left[y\right]$$z\in[x]\cap[y]. Then $$z\sim x$$z\sim x and $$z\sim y$$z\sim y. By symmetry対称性たいしょうせい, $$x\sim z$$x\sim z, and by transitivity推移性すいいせい, $$x\sim y$$x\sim y. If $$u\in \left[x\right]$$u\in[x], then $$u\sim x\sim y$$u\sim x\sim y, so $$u\in \left[y\right]$$u\in[y]. Hence $$\left[x\right]\subseteq \left[y\right]$$[x]\subseteq[y]. Similarly $$\left[y\right]\subseteq \left[x\right]$$[y]\subseteq[x], so $$\left[x\right]=\left[y\right]$$[x]=[y].

8.3解説かいせつ

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

8.3Explanation

The three conditions of an equivalence relation guarantee the partition properties. Reflexivity puts each element into its own class, while symmetry and transitivity force intersecting classes to coincide.