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

1Exercise method

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

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.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.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.3Common mistake

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

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

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.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.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.3Common mistake

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

5Problem 4

For the equivalence relation同値関係どうちかんけい in Problem 3, describe the quotient set商集合しょうしゅうごう $$\mathbb{Z}/\sim$$\mathbb Z/{\sim}.

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

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

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.

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

The canonical projection自然な射影 sends equivalent同値どうち elements to the same 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.

7Related links

8Proof exercise: constructing a partition from an equivalence relation

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