3.7.2: Equivalence relations
- Page ID
- 10910
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)We’ll approach another important kind of binary relation indirectly, through what might at first appear to be an unrelated idea. Let A be a set. A partition of A is defined to be a collection of non-empty subsets of A such that each pair of distinct subsets in the collection is disjoint and the union of all the subsets in the collection is A. A partition of A is just a division of all the elements of A into non-overlapping subsets. For example, the sets {1,2,6}, {3,7}, {4,5,8,10}, and {9} form a partition of the set {1,2,...,10}. Each element of {1, 2, . . . , 10} occurs in exactly one of the sets that make up the partition. As another example, we can partition the set of all people into two sets, the set of males and the set of females. Biologists try to partition the set of all organisms into different species. Librarians try to partition books into various categories such as fiction, biography, and poetry. In the real world, classifying things into categories is an essential activity, although the boundaries between categories are not always well-defined. The abstract mathematical notion of a partition of a set models the real-world notion of classification. In the mathematical world, though, the categories are sets and the boundary between two categories is sharp.
In the real world, items are classified in the same category because they are related in some way. This leads us from partitions back to relations. Suppose that we have a partition of a set A. We can define a relation R on A by declaring that for any a and b in A, a R b if and only if a and b are members of the same subset in the partition. That is, two elements of A are related if they are in the same category. It is clear that the relation defined in this way is reflexive, symmetric, and transitive.
An equivalence relation is defined to be a binary relation that is reflexive, symmetric, and transitive. Any relation defined, as above, from a partition is an equivalence relation. Conversely, we can show that any equivalence relation defines a partition. Suppose that R is an equivalence relation on a set A. Let a ∈ A. We define the equivalence class of a under the equivalence relation R to be the subset [a]R defined as [a]R = {b ∈ A | b R a}. That is, the equivalence class of a is the set of all elements of A that are related to a. In most cases, we’ll assume that the relation in question is understood, and we’ll write [a]instead of [a]R. Note that each equivalence class is a subset of A. The following theorem shows that the collection of equivalence classes form a partition of A.
Theorem 4.12.
Let A be a set and let R be an equivalence relation on A. Then the collection of all equivalence classes under R is a partition of A.
Proof. To show that a collection of subsets of A is a partition, we must show that each subset is non-empty, that the intersection of two distinct subsets is empty, and that the union of all the subsets is A.
If [a] is one of the equivalence classes, it is certainly non-empty, since a ∈ [a]. (This follows from the fact that R is reflexive, and hence a R a.) To show that A is the union of all the equivalence classes, we just have to show that each element of A is a member of one of the equivalence classes. Again, the fact that a ∈ [a] for each a ∈ A shows that this is true.
Finally, we have to show that the intersection of two distinct equivalence classes is empty. Suppose that a and b are elements of A and consider the equivalence classes [a]and [b]. We have to show that if [a]\(\neq\) [b], then [a] ∩ [b] = ∅. Equivalently, we can show the converse: If [a] ∩ [b]\(\neq\) ∅ then [a] = [b]. So, assume that [a] ∩ [b]\(\neq\) ∅. Saying that a set is not empty just means that the set contains some element, so there must be an x ∈ A such that x ∈ [a]∩[b]. Since x ∈ [a], xRa. Since R is symmetric, we also have a R x. Since x ∈ [b], x R b. Since R is transitive and since (a R x) ∧ (x R b), it follows that aRb.
Our object is to deduce that [a] = [b]. Since [a] and [b] are sets, they are equal if and only if [a] ⊆ [b] and [b] ⊆ [a]. To show that [a] ⊆ [b], let c be an arbitrary element of[a]. We must show that c ∈ [b]. Since c ∈ [a], we have that c R a. And we have already shown that a R b. From these two facts and the transitivity of R, it follows that c R b. By definition, this means that c ∈ [b]. We have shown that any member of [a] is a member of [b] and therefore that [a] ⊆ [b]. The fact that [b] ⊆ [a] can be shown in the same way. We deduce that [a] = [b], which proves the theorem.
The point of this theorem is that if we can find a binary relation that satisfies certain properties, namely the properties of an equivalence relation, then we can classify things into categories, where the categories are the equivalence classes.
For example, suppose that U is a possibly infinite set. Define a binary relation ∼ onP(U) as follows: For X and Y in P(U), X ∼ Y if and only if there is a bijective function from the set X to the set Y. In other words, X ∼ Y means that X and Y have the same cardinality. Then ∼ is an equivalence relation on P(U). (The symbol ∼ is often used to denote equivalence relations. It is usually read ‘is equivalent to’.) If X ∈ P(U), then the equivalence class [X]∼ consists of all the subsets of U that have the same cardinality as X. We have classified all the subsets of U according to their cardinality—even though we have never said what an infinite cardinality is. (We have only said what it means to have the same cardinality.)
You might know the popular puzzle called Rubik’s Cube 9, a cube made of smaller cubes with coloured sides that could be manipulated by twisting layers of little cubes. The object was to manipulate the cube so that the colours of the little cubes formed a certain configuration. Define two configurations of the cube to be equivalent if it’s possible to manipulate one configuration into the other by a sequence of twists. This is, in fact, an equivalence relation on the set of possible configurations. (Symmetry follows from the fact that each move is reversible.) It has been shown that this equivalence relation has exactly twelve equivalence classes. The interesting fact is that it has more than one equivalence class: If the configuration that the cube is in and the configuration that you want to achieve are not in the same equivalence class, then you are doomed to failure.
Fortunately if you buy the cube in the configuration you want it to be in (i.e., with 6 faces all having just one colour), you can still be successful. Since all configurations you can get to using legal moves are in the same class, you can only move to another class of configurations with an illegal move. So it is only by taking the cube apart and incorrectly putting it back together that you can really change this puzzle from difficult to impossible.
Suppose that R is a binary relation on a set A. Even though R might not be transitive, it is always possible to construct a transitive relation from R in a natural way. If we think of a R b as meaning that a is related by R to b ‘in one step’, then we consider the relationship that holds between two elements x and y when x is related by R to y ‘in one or more steps’. This relationship defines a binary relation on A that is called the transitive closure of R. The transitive closure of R is denoted R∗. Formally, R∗ is defined as follows: For \(a\) and \(b\) in \(A, a \mathcal{R}^{*} b\) if there is a sequence \(x_{0}, x_{1}, \ldots x_{n}\) of elements of \(A\), where \(n>0\) and \(x_{0}=a\) and \(x_{n}=b,\) such that \(x_{0} \mathcal{R} x_{1}, x_{1} \mathcal{R} x_{2}, \ldots,\) and \(x_{n-1} \mathcal{R} x_{n}\).
You will revist the notion of transitive closures in the course Automata, Languages, and Computability.
For example, if aRc, cRd, and dRb, then we would have that aR∗ b. Of course, we would also have that a R∗ c, and a R∗ d.
For a practical example, suppose that C is the set of all cities and let A be the binary relation on C such that for x and y in C, x A y if there is a regularly scheduled airline flight from x to y. Then the transitive closure A has a natural interpretation: x A∗ y if it’s possible to get from x to y by a sequence of one or more regularly-scheduled airline flights. You’ll find a few more examples of transitive closures in the exercises.
Exercises
- For a finite set, it is possible to define a binary relation on the set by listing the elements of the relation, considered as a set of ordered pairs. Let A be the set {a, b, c, d}, where a, b, c, andd are distinct. Consider each of the following binary relations on A. Is the relation reflexive? Symmetric? Antisymmetric? Transitive? Is it a partial order? An equivalence relation?
a) R = {(a, b), (a, c), (a, d)}.
b) S = {(a,a), (b,b), (c,c), (d,d), (a,b), (b,a)}.c) T = {(b, b), (c, c), (d, d)}.
d) C = {(a, b), (b, c), (a, c), (d, d)}.e) D = {(a, b), (b, a), (c, d), (d, c)}. - Let A be the set {1, 2, 3, 4, 5, 6}. Consider the partition of A into the subsets {1, 4, 5}, {3}, and{2, 6}. Write out the associated equivalence relation on A as a set of ordered pairs.
- Consider each of the following relations on the set of people. Is the relation reflexive? Sym- metric? Transitive? Is it an equivalence relation?
a) x is related to y if x and y have the same biological parents.
b) x is related to y if x and y have at least one biological parent in common.c) x is related to y if x and y were born in the same year.d) x is related to y if x is taller than y.
e) x is related to y if x and y have both visited Indonesia. - It is possible for a relation to be both symmetric and antisymmetric. For example, the equality relation, =, is a relation on any set which is both symmetric and antisymmetric. Suppose thatA is a set and R is a relation on A that is both symmetric and antisymmetric. Show that R is a
subset of = (when both relations are considered as sets of ordered pairs). That is, show that
for any a and b in A, (a R b) → (a = b).
- Let ∼ be the relation on R, the set of real numbers, such that for x and y in R, x ∼ y if and only if \(x-y \in \mathbb{Z} .\) For example, \(\sqrt{2}-1 \sim \sqrt{2}+17\) because the difference, \((\sqrt{2}-1)-\) \((\sqrt{2}+17),\) is \(-18,\) which is an integer. Show that \(\sim\) is an equivalence relation. Show that each equivalence class [x]∼ contains exactly one number a which satisfies 0 ≤ a < 1. (Thus, the set of equivalence classes under ∼ is in one-to-one correspondence with the half-open interval[0, 1).
- Let A and B be any sets, and suppose f : A → B. Define a relation ∼ on B such that for any xand y in A, x ∼ y if and only if f(x) = f(y). Show that ∼ is an equivalence relation on A.
- Let \(\mathbb{Z}^{+}\) be the set of positive integers \(\{1,2,3, \ldots\} .\) Define a binary relation \(\mathcal{D}\) on \(\mathbb{Z}^{+}\) such that for \(n\) and \(m\) in \(\mathbb{Z}^{+}, n \supset m\) if \(n\) divides evenly into \(m,\) with no remainder. Equivalently, \(n \supset m\) if \(n\) is a factor of \(m,\) that is, if there is a \(k\) in \(\mathbb{Z}^{+}\) such that \(m=n k .\) Show that \(\mathcal{D}\) is a partial order.
- Consider the set N × N, which consists of all ordered pairs of natural numbers. Since N × Nis a set, it is possible to have binary relations on N × N. Such a relation would be a subset of (N×N)×(N×N). Define a binary relation ⪯ on N×N such that for (m,n) and (k,l)inN×N,(m,n) ⪯ (k,l)ifandonlyifeitherm < kor((m = k)∧(n ≤ l)). Whichofthe following are true?
- (2,7) ⪯ (5,1)
- (8,5) ⪯ (8,0)
- (0,1) ⪯ (0,2)
- (17,17) ⪯ (17,17) Show that ⪯ is a total order on N × N.
- Let ∼ be the relation defined on N × N such that (n, m) ∼ (k, l) if and only if n + l = m + k. Show that ∼ is an equivalence relation.
- Let P be the set of people and let Cbethe‘child of relation. That is xCy means that x is a child of y. What is the meaning of the transitive closure C∗? Explain your answer.
- Let R be the binary relation on N such that x R y if and only if y = x + 1. Identify the transitive closure R∗. (It is a well-known relation.) Explain your answer.
- Suppose that R is a reflexive, symmetric binary relation on a set A. Show that the transitive closure R∗ is an equivalence relation.