Equivalence relations同値関係どうちかんけい and partitions分割ぶんかつ

1Introduction

The purpose of an equivalence relation同値関係どうちかんけい is to classify objects対象たいしょう by a rule that says when they should be treated as the same. The point is not that the objects are literally equal, but that they are the same for the purpose currently being considered.

For example, if integers are classified by their remainder when divided by 3, then $$1,4,7$$1,4,7 belong to the same class. This does not mean $$1=4$$1=4. It means they are the same as long as only the remainder modulo 3 is being observed.

An equivalence relation divides objects into boxes called equivalence classes同値類どうちるい; unlike an order, it does not place one object above or below another.

2Terms and definitions

A binary relation二項関係にこうかんけい $$\sim$$\sim on a set集合しゅうごう $$A$$A is an equivalence relation同値関係どうちかんけい if it satisfies the following three conditions for arbitrary $$a,b,c\in A$$a,b,c\in A.

For $$a\in A$$a\in A, the equivalence class同値類どうちるい of $$a$$a is defined by

An equivalence class is the set of elements regarded as the same kind as $$a$$a.

A partition分割ぶんかつ of $$A$$A is a collection of nonempty subsets of $$A$$A that are pairwise disjoint and whose union is all of $$A$$A. The subsets in the partition are often called blocks.

3Strategy

To verify an equivalence relation同値関係どうちかんけい, prove the three conditions separately. In particular, transitivity推移性すいいせい is easy to miss: from $$a\sim b$$a\sim b and $$b\sim c$$b\sim c, one must be able to derive $$a\sim c$$a\sim c.

The reason to introduce an equivalence relation is to divide a set into equivalence classes. Therefore, before asking what changes, ask what feature is being ignored so that objects are identified.

Prove the three properties separately. To disprove reflexivity, give an element for which $$a\text{[PARSE ERROR: Undefined("Command("not")")]}\sim a$$a\not\sim a. To disprove symmetry or transitivity, give one pair or triple that violates the corresponding implication.

4Intuitive explanation

An equivalence relation同値関係どうちかんけい can be imagined as coloring the elements of a set. Elements with the same color are treated as equivalent. Reflexivity反射性はんしゃせい means every element has some color, symmetry対称性たいしょうせい means sameness of color has no direction, and transitivity推移性すいいせい means the color does not change in the middle of a chain.

When this coloring is valid, the set is divided into non-overlapping subsets. That division is a partition分割ぶんかつ.

Equivalence classes behave like disjoint boxes: every element belongs to exactly one. If two classes overlap at even one element, symmetry and transitivity force them to be the same class.

5Precise explanation: from equivalence relations to partitions

Suppose an equivalence relation同値関係どうちかんけい $$\sim$$\sim is given on $$A$$A. The collection of equivalence classes forms a partition分割ぶんかつ of $$A$$A. This means two things.

1. Every $$a\in A$$a\in A belongs to at least one equivalence class.
2. Any two equivalence classes are either equal or disjoint.

The first point follows from reflexivity反射性はんしゃせい. Since $$a\sim a$$a\sim a, we have $$a\in \left[a\right]$$a\in[a].

For the second point, suppose $$\left[a\right]\cap \left[b\right]\ne \text{[PARSE ERROR: Undefined("Command("varnothing")")]}$$[a]\cap[b]\ne\varnothing. Then there exists $$x$$x such that $$x\in \left[a\right]$$x\in[a] and $$x\in \left[b\right]$$x\in[b]. By definition, $$x\sim a$$x\sim a and $$x\sim b$$x\sim b. By symmetry対称性たいしょうせい, $$a\sim x$$a\sim x, and by transitivity推移性すいいせい, $$a\sim b$$a\sim b.

Now take any $$y\in \left[a\right]$$y\in[a]. Then $$y\sim a$$y\sim a. Since $$a\sim b$$a\sim b, transitivity gives $$y\sim b$$y\sim b, so $$y\in \left[b\right]$$y\in[b]. Hence $$\left[a\right]\subseteq \left[b\right]$$[a]\subseteq[b]. The same argument gives $$\left[b\right]\subseteq \left[a\right]$$[b]\subseteq[a], so $$\left[a\right]=\left[b\right]$$[a]=[b].

6Conversely, from partitions to equivalence relations

Let a partition分割ぶんかつ of $$A$$A be given. Define $$a\sim b$$a\sim b to mean that $$a$$a and $$b$$b belong to the same block of the partition. Then $$\sim$$\sim is an equivalence relation同値関係どうちかんけい.

Reflexivity反射性はんしゃせい holds because every element belongs to some block. Symmetry対称性たいしょうせい holds because the statement "belong to the same block" is symmetric in $$a$$a and $$b$$b. Transitivity推移性すいいせい holds because distinct blocks of a partition do not overlap: if $$a,b$$a,b are in the same block and $$b,c$$b,c are in the same block, then those two blocks share $$b$$b and therefore must be the same block, so $$a,c$$a,c are in the same block.

7Example: equivalence by congruence

7.1Problem

On the set of all integers $$\mathbb{Z}$$\mathbb Z, define $$a\sim b$$a\sim b to mean that $$a-b$$a-b is a multiple of 3. Verify that this is an equivalence relation同値関係どうちかんけい and describe the equivalence classes同値類どうちるい.

7.2Explanation

For reflexivity反射性はんしゃせい, $$a-a=0$$a-a=0 is a multiple of 3, so $$a\sim a$$a\sim a.

For symmetry対称性たいしょうせい, suppose $$a\sim b$$a\sim b. Then $$a-b=3k$$a-b=3k for some integer $$k$$k. Hence $$b-a=-3k=3(-k)$$b-a=-3k=3(-k), so $$b\sim a$$b\sim a.

For transitivity推移性すいいせい, suppose $$a\sim b$$a\sim b and $$b\sim c$$b\sim c. Then $$a-b=3k$$a-b=3k and $$b-c=3\ell$$b-c=3\ell for integers $$k,\ell$$k,\ell. Adding the two equations gives $$a-c=3(k+\ell )$$a-c=3(k+\ell), so $$a\sim c$$a\sim c.

The equivalence classes are the classes according to remainders modulo 3:

This example shows how an equivalence relation同値関係どうちかんけい decomposes a set into non-overlapping classes.

8Recognition criteria

• Use an equivalence relation同値関係どうちかんけい when objects should be divided into classes of the same kind.
• To prove that a relation is an equivalence relation, check reflexivity反射性はんしゃせい, symmetry対称性たいしょうせい, and transitivity推移性すいいせい separately.
• An equivalence class同値類どうちるい is not a chosen representative. It is the set of all elements equivalent to the representative.
• When a partition分割ぶんかつ appears, one can define an equivalence relation by saying that two elements are in the same block.

Match properties of the relation with properties of the classification: overlapping equivalence classes are equal, and changing the representative does not change its equivalence class.

9Proof supplement: the two constructions are inverse

We have constructed the collection of equivalence classes

from an equivalence relation同値関係どうちかんけい, and an equivalence relation from a partition分割ぶんかつ by declaring two elements equivalent when they lie in the same block. Applying these constructions successively returns the original data.

Starting with an equivalence relation, $$x$$x and $$y$$y lie in the same equivalence class exactly when $$\left[x\right]=\left[y\right]$$[x]=[y], which is equivalent to $$x\sim y$$x\sim y. Thus the relation reconstructed from the partition is the original relation.

Starting with a partition $$\text{[PARSE ERROR: Undefined("Command("mathcal")")]}C$$\mathcal C, the equivalence class of $$x$$x is exactly the unique block of $$\text{[PARSE ERROR: Undefined("Command("mathcal")")]}C$$\mathcal C containing $$x$$x. Thus the partition reconstructed from the equivalence classes is $$\text{[PARSE ERROR: Undefined("Command("mathcal")")]}C$$\mathcal C itself.

10Exercise links

11Related links