Skip to main content

Section 4.1 Equivalence Relations

You will have seen equivalence relations in MAT102. Recall that they allow us to talk about the same-ness of objects in terms of some defining characteristic, even if those two objects are not necessarily equal.

Relations generalize functions; equivalence relations are relations that satisfy a number of properties.

Definition 4.1.1. Relation.

Given sets S and T, a relation between S and T is a subset of S×T; that is, R is a relation if R⊆S×T.

If S=T then we call R a relation on S.

Let \(A = \{0,2,4,6\}\) and \(B = \{0,1,2,3,4\}\text{.}\)

The set

\begin{equation*} R = \{(0,0),(0,2),(2,2),(6,3),(6,4)\} \end{equation*}

is a subset of \(A \times B\text{,}\) so \(R\) is a relation between \(A\) and \(B\text{.}\)

How many relations are there between the sets \(A = \{0,2,4,6\}\) and \(B = \{0,1,2,3,4\}\text{?}\)

Hint

How many subsets does \(A \times B\) have?

Let \(A\) and \(B\) be finite sets.

  1. How many relations are there between \(A\) and \(B\text{?}\)
  2. How many functions are there from \(A\) to \(B\text{?}\)

Which of your anwers from (a) or (b) should be larger? Why?

Equivalence relations are a special type of relation—they satisfy a number of additional conditions that allow for a reasonable way to talk about objects being equivalent.

Video: Equivalence Relations, Part 1 (by Mike Pawliuk)

Video: Equivalence Relations, Part 2 (by Mike Pawliuk)

Definition 4.1.5. Equivalence Relation.

An equivalence relation R on a set S is a relation such that

Reflexive property

For all x∈S, (x,x)∈R.

Symmetric property

For all x,y∈S, (x,y)∈R implies (y,x)∈R.

Transitive property

For all x,y,z∈S, (x,y)∈R and (y,z)∈R imply (x,z)∈R.

For each relation, determine whether or not it satisfies the reflexive, symmetric, and transitive properties. Then conclude whether or not it is an equivalence relation.

  1. The order relation \(\lt\) on \(\mathbb{R}\)
  2. The relation \(R = \{(a,a),(b,b),(c,c),(a,b),(b,a),(a,c),(c,a)\}\) on the set \(\{a,b,c\}\)
  3. The relation \(D = \{(m,n): m + n \text{ is odd} \}\) on \(\mathbb{Z}\)
  4. The relation \(\equiv\) on \(\mathbb{Z}\) given by \(a \equiv b \ \Leftrightarrow \ n \mid (a-b)\text{,}\) for a fixed \(n \in \mathbb{N}\)
  5. The relation \(\sim\) on \(\mathbb{R}\) given by \(x \sim y \Leftrightarrow (x-y)(x^2+y^2-1) = 0\)
  6. The relation \(\approx\) on \(\mathbb{R}^2\) given by \((x,y) \approx (w,z) \Leftrightarrow xy = wz\)

Video: Equivalence Classes, Part 1 (by Mike Pawliuk)

Definition 4.1.7. Equivalence Class.

Let R be an equivalence relation on a set S, and x an element in S.

The equivalence class of x, denoted by [x], is the set of all elements in S related to x under R; that is,

[x]={y∈S:(x,y)∈R}.

List all equivalence classes of the equivalence relation

\begin{equation*} R = \{(v,v),(w,w),(x,x),(y,y),(z,z),(v,z),(z,v),(w,x),(x,w),(y,y)\} \end{equation*}

on the set \(S = \{v,w,x,y,z\}\text{.}\)

An equivalence relation on a set S induces a partition of S into its equivalence classes. This is shown by proving that none of the equivalence classes overlap, and that their union is S. First, we prove the following lemma that states that if two elements are equivalent, then their equivalence classes are equal. Note the extra care in using the equivalence relation properties.

Let \(R\) be an equivalence relation on \(S\text{,}\) and let \(a, b \in S\) such that \((a,b) \in R\text{.}\) We will prove \([a] \subseteq [b]\text{.}\)

Let \(y \in [a]\text{.}\) Then:

\begin{align*} (a,y) \amp \in R \qquad \amp \text{(by definition of $[a]$)}\\ (y,a) \amp \in R \qquad \amp \text{(since $R$ is symmetric)}\\ (a,b) \amp \in R \qquad \amp \text{(given)}\\ (y,b) \amp \in R \qquad \amp \text{(since $R$ is transitive)}\\ (b,y) \amp \in R \qquad \amp \text{(since $R$ is symmetric)}\\ y \amp \in [b] \qquad \amp \text{(by definition of $[b]$)} \end{align*}

Hence \([a] \subseteq [b]\text{.}\) The other inclusion is similarly proved, from which \([a] = [b]\) follows.

Prove part (b) of Theorem 4.1.10 by showing that any two equivalence classes that have a common element must be the same equivalence class.

Hint

You may want to use Lemma 4.1.9.

Video: Equivalence Classes, Part 2 (by Mike Pawliuk)

Describe the equivalence classes of the equivalence relation \(\sim\) on \(\mathbb{Z}\) defined by

\begin{equation*} m \sim n \Leftrightarrow 3 \mid (m - n)\text{.} \end{equation*}

Let \(A = \{0,1,2\}\text{,}\) and consider the relation \(\cong\) on \(P(A) \setminus \{\varnothing\}\) defined by

\begin{equation*} X \cong Y \Leftrightarrow \text{ the largest element in } X \text{ equals the largest element in } Y\text{.} \end{equation*}

Prove \(\cong\) is an equivalence relation, and describe the equivalence classes.

Give examples of equivalence relations on \(\mathbb{Z}\text{:}\)

  1. with exactly one equivalence class;
  2. with exactly two equivalence classes;
  3. with infinitely many equivalence classes.
Remark 4.1.16. Representatives of Equivalence Classes.

If x and y are in the same equivalence class, then [x]=[y], and we can use either of them to refer to the same class. In fact, we can use any member of the class to represent it!

Consider the equivalence relation

\begin{equation*} E = \{(a,b) : a + b \text{ is even}\} \end{equation*}

on \(\mathbb{Z}\text{.}\)

The equivalence class of \(0\) is

\begin{equation*} [0] = \{a : a + 0 \text{ is even}\} = \{a : a \text{ is even}\}\text{,} \end{equation*}

and hence \([0]\) contains exactly all even integers. This means we can also call \([0]\) as \([2] = [-2] = [4] = \cdots\) (any of these names).

Similarly,

\begin{equation*} [1] = \{a : a + 1 \text{ is even}\} = \{ a : a \text{ is odd}\}\text{.} \end{equation*}

So, \([1] = [-1] = [3] = [-3] = [5] = \cdots\text{.}\)

We can use the properties of equivalence classes and the additional results we've proven to derive interesting consequences about equivalence relations. For instance, if two objects are in the same equivalence class, then they must be equivalent to one another. (This sounds obvious—try to prove it below!)

Given an equivalence relation \(R\) on a set \(S\text{,}\) and an equivalence class \([x]\text{,}\) show that for all \(a, b \in S\text{,}\)

\begin{equation*} a \in [x] \text{ and } b \in [x] \Rightarrow (a,b) \in R\text{.} \end{equation*}