Equivalence Relations

An equivalence relation is a relation which "looks like" ordinary equality of numbers, but which may hold between other kinds of objects. Here are three familiar properties of equality of real numbers:

1. Every number is equal to itself: $x = x$ for all $x \in \real$ .

2. Equalities can be "reversed": If $x, y \in \real$ and $x = y$ , then $y = x$ .

3. You can "chain" equalities together: If $x, y, z \in \real$ and $x = y$ and $y = z$ , then $x = z$ .

These three properties are captured in the axioms for an equivalence relation.

Definition. An equivalence relation on a set X is a relation $\sim$ on X such that:

1. $x \sim x$ for all $x \in X$ . (The relation is reflexive.)

2. If $x \sim y$ , then $y \sim x$ . (The relation is symmetric.)

3. If $x \sim y$ and $y \sim z$ , then $x \sim z$ . (The relation is transitive.)

Example. Show that the less-than relation $<$ on the set of real numbers is not an equivalence relation. What about the relation $\le$ ? For no real number x is it true that $x < x$ , so reflexivity never holds.

If x and y are real numbers and $x < y$ , it is false that $y < x$ . For example, $3 < 4$ is true, but $4 < 3$ is false.

It is true that if $x < y$ and $y < z$ , then $x < z$ . Thus, $<$ is transitive.

Suppose instead I consider less-than-or-equal-to, the relation $\le$ on $\real$ .

Reflexivity now holds, since for any $x \in \real$ it is true that $x \le x$ . Transitivity holds just as before.

However, symmetry still doesn't hold: $3 \le 4$ , but $4 \not\le 3$ . Thus, $\le$ is not an equivalence relation.

Example. (a) Is the relation whose graph is drawn below an equivalence relation?

$$\hbox{\epsfysize=1.5in \epsffile{equivalence-relations-1.eps}}$$

(b) Is the relation whose graph is drawn below an equivalence relation?

$$\hbox{\epsfysize=1.5in \epsffile{equivalence-relations-2.eps}}$$

(c) Is the relation whose graph is drawn below an equivalence relation?

$$\hbox{\epsfysize=1.5in \epsffile{equivalence-relations-3.eps}}$$

(a) The relation is not an equivalence relation. $(b, b)$ is not in the relation, so the relation is not reflexive.

(b) $(c, b)$ is in the relation, but $(b, c)$ is not. Therefore, the relation is not symmetric, so it's not an equivalence relation.

(c) This relation is reflexive and symmetric. However, $(b, c)$ and $(c, a)$ are in the relation, but $(b, a)$ is not. The relation is not transitive, and therefore it's not an equivalence relation.

Example. A relation is defined on $\real$ by

$$x \sim y \quad\hbox{means}\quad (x + y)^2 = x^2 + y^2.$$

Check each axiom for an equivalence relation. If the axiom holds, prove it. If the axiom does not hold, give a specific counterexample.

$(1 + 1)^2 = 4$ but $1^2 + 1^2 = 2$ , and $4 \ne 2$ . Hence, $1 \not\sim 1$ and the relation is not reflexive.

Suppose $x \sim y$ . Then $(x + y)^2 = x^2 + y^2$ , so $(y + x)^2 = y^2 + x^2$ . Hence, $y \sim x$ . The relation is symmetric.

$1 \sim 0$ , because $(1 + 0)^2 = 1$ and $1^2 + 0^2 = 1$ .

$0 \sim 1$ , because $(0 + 1)^2 = 1$ and $0^2 + 1^2 = 1$ .

However, $1 \not\sim 1$ , as I showed above. Hence, the relation is not transitive.

Example. Define a relation $\sim$ on $\real$ by

$$x \sim y \quad\hbox{means}\quad |x| + |y| = |x + y|.$$

Check each axiom for an equivalence relation. If the axioms holds, prove it. If the axiom does not hold, give a specific counterexample.

For all $x \in \real$ ,

$$|x| + |x| = 2 |x| = |2 x| = |x + x|.$$

Therefore, $x \sim x$ for all x, and $\sim$ is reflexive.

Suppose $x \sim y$ . This means that $|x| + |y| = |x + y|$ . By commutativity of addition, $|y| + |x| = |y + x|$ . Hence, $y \sim x$ . Therefore, $\sim$ is symmetric.

Transitivity does not hold.

$$|1| + |0| = |1 + 0|, \quad\hbox{so}\quad 1 \sim 0.$$

$$|0| + |-1| = |0 + -1|, \quad\hbox{so}\quad 0 \sim -1.$$

However, $1 \not\sim -1$ , because

$$|1| + |-1| \ne |1 + (-1)|.$$

Therefore, $1 \sim 0$ and $0 \sim -1$ do not imply $1 \sim -1$ .

Example. A relation is defined on $\real^2$ by

$$(a, b) \sim (c, d) \quad\hbox{means}\quad (a = c \quad\hbox{or}\quad b = d).$$

Check each axiom for an equivalence relation. If the axiom holds, prove it. If the axiom does not hold, give a specific counterexample.

In words, the definition says two pairs are related if either their first components are equal or their second components are equal.

$(a, b) \sim (a, b)$ , because the first components are both a and hence equal.

Suppose $(a, b) \sim (c, d)$ . Then either $a = c$ or $b = d$ . In the first case, if $a = c$ , then $(c, d) \sim (a, b)$ , because their first components are equal: $a = c$ implies $c = a$ . In the second case, if $b = d$ , then $(c, d) \sim (a, b)$ , because their second components are equal: $b = d$ implies $d = b$ .

$(1, 2) \sim (1, 3)$ , because their first components are equal. And $(1, 3) \sim (2, 3)$ , because their second components are equal. But $(1, 2) \not\sim (2, 3)$ , because neither their first nor their second components are equal.

Example. Define a relation on $\integer$ by $x \sim y$ if and only if $x + 2 y$ is divisible by 3.

Check each axiom for an equivalence relation. If the axiom holds, prove it. If the axiom does not hold, give a specific counterexample.

For example, $2 \sim 11$ , since $2 + 2 \cdot 11 = 24$ , and 24 is divisible by 3. And $7 \sim -8$ , since $7 + 2 \cdot (-8) = -9$ , and -9 is divisible by 3.

However, $6 \not\sim 14$ , since $6 + 2 \cdot 14 = 34$ , and 34 is not divisible by 3.

If x is an integer, $x + 2 x = 3 x$ is divisible by 3. Therefore, $x \sim x$ for all $x \in \integer$ , and $\sim$ is reflexive.

Suppose x and y are integers. If $x \sim y$ , then $x + 2 y$ is divisible by 3. Say $x + 2 y = 3 n$ , where $n \in \integer$ . Now

$$\eqalign{ y + 2 x & = (3 x + 3 y) - (x + 2 y) \cr & = (3 x + 3 y) - 3 n \cr & = 3(x + y - n) \cr}$$

Therefore, $y + 2 x$ is divisible by 3, so $y \sim x$ . Hence, $\sim$ is symmetric.

You might be wondering how I knew to start with "$y + 2 x = (3 x + 3 y) - (x + 2 y)$ ". I reasoned backwards on scratch paper this way.

To prove symmetry, I had to show that if $x \sim y$ , then $y \sim x$ .

By the definition of $\sim$ , that's the same as showing: If $x + 2 y$ is divisible by 3, then $y + 2 x$ is divisible by 3.

If $x + 2 y$ being divisible by 3 is going to force $y + 2 x$ to be divisible by 3, there's probably be some connection involving 3, $x + 2 y$ , and $y + 2 x$ .

As in many proofs, you often reach a point where you need to play around with the stuff you have. You don't know in advance what will work, and there isn't a step-by-step method for finding out. You have to experiment.

So you think: "3?" "$x + 2 y$ ?" "$y + 2 x$ ?" You might try various ways of combining the expressions ... and maybe you realize that $x + 2 x = 3 x$ and $y + 2 y = 3 y$ (notice the 3's!), and then:

$$(x + 2 y) + (y + 2 x) = 3 x + 3 y.$$

Since the "then" part of what I want to prove involves $y + 2 x$ , I'll solve the last equation for $y + 2 x$ :

$$y + 2 x = (3 x + 3 y) - (x + 2 y).$$

And there's the equation I started with.

Now suppose x, y, and z are integers. Assume $x \sim y$ and $y \sim z$ . This means that $x + 2 y$ is divisible by 3, and $y + 2 z$ is divisible by 3. I'll express these as equations:

$$x + 2 y = 3 m \quad\hbox{for some}\quad m \in \integer.$$

$$y + 2 z = 3 n \quad\hbox{for some}\quad n \in \integer.$$

I want to show that $x + 2 z$ is divisible by 3. My proof looks like this so far, with the assumptions at the top and the conclusion at the bottom.

$$\matrix{ x \sim y & & y \sim z \cr 3 \mid x + 2 y & & 3 \mid y + 2 z \cr x + 2 y = 3 m & & y + 2 z = 3 n \cr & \vdots & \cr & x + 2 z = 3(\hbox{something}) & \cr & 3 \mid x + 2 z & \cr & x \sim z & \cr}$$

How can I get from $x + 2 y = 3 m$ and $y + 2 z = 3 n$ to $x + 2 z = 3(\hbox{something})$ ? Make what you've got look like what you want. What I have involves x, y, and z, but what I want seems to involve only x and z. It looks like I want to get rid of the y's. How can I do that? One way is to solve the second equation for y:

$$\eqalign{ y + 2 z & = 3 n \cr y & = 3 n - 2 z \cr}$$

Then plug into the first:

$$\eqalign{ x + 2 y & = 3 m \cr x + 2(3 n - 2 z) & = 3 m \cr x + 6 n - 4 z & = 3 m \cr}$$

I look at my target equation $x + 2 z = 3(\hbox{something})$ . Make what you've got look like what you want. I need $x + 2 z$ on the left side, so I'll just do algebra to force it to happen:

$$\eqalign{ x + 6 n - 4 z & = 3 m \cr x & = 3 m - 6 n + 4 z \cr x + 2 z & = 3 m - 6 n + 6 z \cr}$$

The left side is what I want ($x + 2 z$ ), but I need $3(\hbox{something})$ on the right ... oh, just factor out 3:

$$x + 2 z = 3(m - 2 n + 2 z).$$

I'll plug this derivation into the proof outline above:

$$\matrix{ x \sim y & & y \sim z \cr 3 \mid x + 2 y & & 3 \mid y + 2 z \cr x + 2 y = 3 m & & y + 2 z = 3 n \cr & & y = 3 n - 2 z \cr & x + 2(3 n - 2 z) = 3 m & \cr & x + 6 n - 4 z = 3 m & \cr & x = 3 m - 6 n + 4 z & \cr & x + 2 z = 3 m - 6 n + 6 z & \cr & x + 2 z = 3(m - 2 n + 2 z) & \cr & x + 2 z = 3(\hbox{something}) & \cr & 3 \mid x + 2 z & \cr & x \sim z & \cr}$$

This is a complete proof of transitivity, though some people might prefer more words. Thus, $\sim$ is an equivalence relation.

Notice that if you were presented with this proof without any of the scratchwork or backward reasoning, it might look a little mysterious: You can see each step is correct, but you might wonder how anyone would think of doing those things in that order. This is an unfortunate consequence of the way math is often presented: After the building is finished, the scaffolding is removed, and you may then wonder how the builders managed to get the materials up to the roof!

The lesson here is that you should not look at a finished proof and assume that the person who wrote it had a flash of genius and then wrote the thing down from start to finish. While that can happen, more often proofs involve messing around and attempts that don't work and lots of scratch paper!

Equivalence relations give rise to partitions. As a real-world example, consider a deck of playing cards. It is divided into 4 suits: spades, hearts, diamonds, and clubs. Define two cards in the deck to be equivalent if they belong to the same suit. This is an equivalence relation. Every card in the deck belongs to one and only one suit, which is the set of all cards in the same suit as the given card.

In general, if $\sim$ is an equivalence relation on a set X and $x \in X$ , the equivalence class of x consists of all the elements of X which are equivalent to x. In the previous example, the suits are the equivalence classes.

Definition. Let X be a set. A partition of X is a collection of subsets $\{X_i\}_{i\in I}$ of X such that:

1. $\displaystyle X = \bigcup_{i \in I} X_i$ .

2. If $i, j \in I$ and $i \ne j$ , then $X_i \cap X_j = \emptyset$ . (The subsets $X_i$ are pairwise disjoint.)

Thus, the elements of a partition are like the pieces of a jigsaw puzzle:

$$\hbox{\epsfysize=2in \epsffile{equivalence-relations-4.eps}}$$

Example. Why don't the following sets partition the set of integers $\integer$ ?

(a)

$$\{0, 1, 2, 3, \ldots\} \quad\hbox{and}\quad \{\ldots, -3, -2, -1, 0\}$$

(b)

$$\{1, 2, 3, \ldots\} \quad\hbox{and}\quad \{\ldots, -4, -3, -2, 0\}$$

(a) Every integer is in one of these sets, but the two sets overlap (at 0).

(b) The sets don't overlap, but -1 is not contained in either set.

Example. Prove: If X is a set and S is a subset of X, then $\{S, X - S\}$ is a partition of X.

If $x \in X$ , then either $x \in S$ or $x \notin S$ . In the second case, $x \in X - S$ . Thus, every element of X is either in S or in $X - S$ .

If $x \in S \cap (X - S)$ , then $x \in S$ and $x \notin S$ , which is a contradiction. Hence, S and $X - S$ are disjoint.

Therefore, $\{S, X - S\}$ is a partition of X.

Here is how equivalence relations are related to partitions.

Theorem. Let X be a set. An equivalence relation $\sim$ on X gives rise to a partition of X into equivalence classes. Conversely, a partition of X gives rise to an equivalence relation on X whose equivalence classes are exactly the elements of the partition.

Proof. Suppose $\sim$ is an equivalence relation on X. If $x \in X$ , let

$$S(x) = \{y \in X \mid y \sim x\}.$$

Thus, $S(x)$ is the equivalence class of x. Now $x \sim x$ , so $x \in S(x)$ . Clearly, $\displaystyle X = \bigcup_{x \in X} S(x)$ .

Now some of the $S(x)$ 's may be identical; throw out the duplicates. This means that I have $S(x)$ 's where $x \in Y$ , and Y is a subset of X --- and if $x, y \in Y$ and $x \ne y$ , then $S(x) \ne S(y)$ . Since I've just thrown out duplicates, I still have $\displaystyle X = \bigcup_{x \in Y} S(x)$ . I will have a partition if I show that the remaining $S(x)$ 's don't intersect.

Suppose $x, y \in Y$ and $x \ne y$ , but $z \in S(x) \cap S(y)$ . I'll show that this gives a contradiction. By definition, $z \sim x$ and $z \sim y$ , so by symmetry and transitivity, $x \sim y$ .

$$\hbox{\epsfysize=1.5in \epsffile{equivalence-relations-9.eps}}$$

Now I'll show $S(x) = S(y)$ . I'll show each is contained in the other. Suppose $w \in S(x)$ . Then $w \sim x$ , but $x \sim y$ , so $w \sim y$ , and $w \in S(y)$ .

$$\hbox{\epsfysize=1.5in \epsffile{equivalence-relations-10.eps}}$$

This shows $S(x) \subset S(y)$ . But the argument clearly works the other way around, so $S(y) \subset S(x)$ . Hence, $S(x) = S(y)$ .

Since I threw out all the duplicates earlier, this is a contradiction. Hence, there is no such z, which means $S(x) \cap S(y) = \emptyset$ . This means that the $S(x)$ 's for $x \in Y$ partition X.

Conversely, suppose $\{X_i\}_{i \in I}$ is a partition of X. Define a relation on X by saying $x \sim y$ if and only if $x, y \in X_i$ for some $i \in I$ .

If $x \in X$ , then $x \in X_i$ for some i because $X = \bigcup_{i \in I} X_i$ --- to be in the union means you're in one of the sets in the union. Now x is in the same $X_i$ as itself --- $x, x \in X_i$ --- so $x \sim x$ . It's reflexive.

If $x \sim y$ , then $x, y \in X_i$ for some i. Obviously, $y, x \in X_i$ , so $y \sim x$ . It's symmetric.

Finally, if $x \sim y$ and $y \sim z$ , then $x, y \in X_i$ and $y, z \in X_j$ for some i and j. Now $y \in X_i \cap X_j$ , but this can only happen if $X_i = X_j$ . Then $x, z \in X_i$ , so $x \sim z$ .

$$\hbox{\epsfysize=1.5in \epsffile{equivalence-relations-11.eps}}$$

It's transitive, and hence it's an equivalence relation.

The equivalence classes of $\sim$ are exactly the $X_i$ 's, by construction.

Example. Suppose $X = \{1, 2, 3, 4, 5, 6\}$ . Consider the following partition of X:

$$\hbox{\epsfysize=1.5in \epsffile{equivalence-relations-6.eps}}$$

What is the equivalence relation defined by this partition?

The equivalence relation defined by this partition is: $x \sim x$ for all $x \in X$ , and

$$1 \sim 4 \sim 5, \quad 2 \sim 6.$$

In other words, 1, 4, and 5 are equivalence to each other, 2 and 6 are equivalent, and 3 is only equivalent to itself.

Example. Consider the relation on $\real$ defined by $x \sim y$ if and only if $x - y \in \integer$ --- that is, if $x - y$ is an integer.

Check each axiom for an equivalence relation. If the axioms holds, prove it. If the axiom does not hold, give a specific counterexample.

Let $x \in \real$ . Then $x - x = 0 \in \integer$ . Therefore, $x \sim x$ , and $\sim$ is reflexive.

Suppose $x \sim y$ , so $x - y \in \integer$ . Since the negative of an integer is an integer, $y - x \in \integer$ . Hence, $y \sim x$ , and $\sim$ is symmetric.

Suppose $x \sim y$ and $y \sim z$ . Then $x - y \in \integer$ and $y - z \in \integer$ . But the sum of integers is an integer, so

$$x - z = (x - y) + (y - z) \in \integer.$$

Therefore, $x \sim z$ , and $\sim$ is transitive. Thus, $\sim$ is an equivalence relation.

Here's a typical equivalence class for $\sim$ :

$$\{\ldots, -4.3942, -3.3942, -2.3942, -1.3942, 0.3942, 1.3942, \ldots\}.$$

A little thought shows that all the equivalence classes look like like one: All real numbers with the same "decimal part". Each class will contain one element --- 0.3942 in the case of the class above --- in the interval $0 \le x < 1$ . Therefore, the set of equivalence classes of $\sim$ looks like $0 \le x < 1$ . Moreover, since $0 \sim 1$ , it's as if this interval had its ends "glued together":

$$\hbox{\epsfysize=1.25in \epsffile{equivalence-relations-7.eps}}$$

This is an important use of equivalence relations in mathematics --- to "glue together" or identify parts of a set to create a new set.

Example. Let $X = \real^2$ , the x-y plane. Define $(a,b) \sim (c,d)$ to mean that

$$a^2 + b^2 = c^2 + d^2.$$

In words, this means that $(a, b)$ and $(c, d)$ are the same distance from the origin.

Show that this is an equivalence relation, and sketch the partition of $\real^2$ into equivalence classes that it determines.

Since $x^2 + y^2 = x^2 + y^2$ , it follows that $(x, y) \sim (x, y)$ . Hence, the relation is reflexive.

Suppose $(a, b) \sim (c, d)$ , so

$$a^2 + b^2 = c^2 + d^2.$$

Then

$$c^2 + d^2 = a^2 + b^2.$$

Hence, $(c, d) \sim (a, b)$ . Hence, the relation is symmetric.

Suppose $(a, b) \sim (c, d)$ and $(c, d) \sim (e, f)$ . Then

$$a^2 + b^2 = c^2 + d^2 \quad\hbox{and}\quad c^2 + d^2 = e^2 + f^2.$$

Hence,

$$a^2 + b^2 = e^2 + f^2.$$

Therefore, $(a, b) \sim (e, f)$ . Hence, the relation is transitive. This show that $\sim$ is an equivalence relation.

The resulting partition of $\real^2$ into equivalence classes consists of circles centered at the origin. The origin is in an equivalence class by itself.

$$\hbox{\epsfysize=1.in \epsffile{equivalence-relations-8.eps}}$$

Notice that the axioms for a partition are satisfied: Every point in the plane lies in one of the circles, and no point lies in two of the circles.

Example. An equivalence relation is defined on the set $S = \{0, 1, 2, 3, 4, 5, 6, 7, 11, 12\}$ by:

$$x \sim y \quad\hbox{means}\quad 3 \mid x - y.$$

List the elements of the equivalence classes of $\sim$ .

Two numbers are in the same class if they differ by a multiple of 3. So the equivalence classes are:

$$\{0, 3, 6, 12\}, \quad \{1, 4, 7\}, \quad \{2, 5, 11\}.\quad\halmos$$

Contact information

Bruce Ikenaga's Home Page

Copyright 2019 by Bruce Ikenaga