Naive Set Theory: Relations

Equivalence Relations


One of the most straightforward and common kinds of relation is an equivalence relation. Up until now, for two elements $a \in A$ and $b \in A$, the notation $a=b$ has meant that the symbols $a$ and $b$ in fact refer to the same exact element within $A$. In contrast, an equivalence relation expresses the idea that two elements are  equivalent in some way but are not identical.

For example, consider the set $T$ of all possible 2-dimensional triangles. We might want to express that two triangles are equivalent if they have the same angles. Alternatively, we might want to state that two triangles are equivalent if they have the same areas, in which case the aforementioned triangles would not be equivalent. Equivalence classes are just the thing to express this concept of "equivalent but not identical."

An equivalence relation on a set $A$ is a relation $\sim$ on $A$ that has the following three properties:

  1. Reflexivity: $a\sim a$ for all $a \in A$.
  2. Symmetry: If $a \sim b$, then $b \sim a$.
  3. Transitivity: If $a \sim b$ and $b \sim c$, then $a \sim c$.

Given an equivalence relation on a set, it is natural to define subsets for each group of elements that are equivalent to one another. Such a subset is called an equivalence class. Formally, the equivalence class $E$ for an element $a$ in a set $A$ equipped with an equivalence relation $\sim$ is a subset defined by $E = \{ x \in A : x \sim a \}$. Given an element $a \in A$, we use the shorthand $[a]_{\sim}$ to denote the equivalence class to which $a$ belongs. When the equivalence relation is clearly implied by the context, we can drop the subscript and simply write $[a]$.

Consider again the set of triangles from before, and let $\sim_1$ consider triangles equal based on angles, and let $\sim_2$ consider triangles equal based on area. If we represent triangles as sets of side lengths, we would observe that $\{ 2, 2, 2\sqrt{2} \} \in \left[ \{1, 1, \sqrt{2}\} \right]_{\sim_1}$ and $\{ 2, 2, 2\sqrt{2} \} \notin \left[ \{ 1, 1, \sqrt{2} \} \right]_{\sim_2}$.

The collection of all equivalence classes generated by an equivalence relation $\sim$ on a set $S$ is called the quotient set of $S$ under $\sim$, and is written as $S \, / \sim$. In the triangles example, the quotient set $T \, / \sim_2$ includes the set of all triangles of area $1$, the set of all triangles of area $7$, the set of all triangles of area $4\pi+3$, and every other set of triangles of identical size.


Problems

  1. Let $A = \{ a, b, c \}$, and let $H = \{(a,a)\}$, $J = \{(b,c), (c,b)\}$, and $K = \{(b,b), (c,c)\}$. Determine which of the following are equivalence relations:

    1. $H$

    2. $J$

    3. $K$

    4. $H \cup K$

    5. $H \cup J \cup K$

    1. $H$ is not an equivalence relation because it violates reflexivity. While $(a,a) \in H$, we can see that $(b,b) \notin H$ and $(c,c)\notin H$.

    2. $J$ is not an equivalence relation because it violates reflexivity - for no element $a \in A$ is it true that $(a,a) \in H$.

    3. $K$ is not an equivalence relation because it violates reflexivity, as $(a,a) \notin H$.

    4. $H \cup K$ satisfies reflexivity, as $(a,a), (b,b), (c,c) \in H \cup K$. Likewise, $H \cup K$ vacuously satisfies symmetry and transitivity. $H \cup K$ is therefore an equivalence class.

    5. $H \cup J \cup K$ also clearly satisfies reflexivity. $H \cup J \cup K$ also satisfies symmetry, as $(b,c)$ and $(c,b)$ are both included. Likewise, $H \cup J \cup K$ also satisfies transitivity, as $(b,c)$ and $(c,b)$ are satisfied by the inclusion of $(b,b)$, and $(c,b)$ and $(b,c)$ are satisfied by the inclusion of $(c,c)$. Therefore $H \cup J \cup K$ is an equivalence relation.

    Show Answer
  2. Define a relation $\sim$ for points $(x,y)$ in the real plane $\mathbb{R}^2$ as $\sim = \{ ((x_0, y_0),(x_1,y_1)) : x_0^2 + y_0^2 = x_1^2 + y_1^2 \}$. Determine whether $\sim$ is an equivalence relation, and if so, describe the equivalence classes.

    To determine whether a relation is an equivalence relation, we need to check that it fulfills the three properties of equivalence relations.

    Reflexivity: Let $(x,y) \in \mathbb{R}^2$. We can see that $x^2 + y^2 = x^2 + y^2$, so $(x,y)\sim(x,y)$.

    Symmetry: Let $(x_0, y_0), (x_1,y_1) \in \mathbb{R}^2$ such that $(x_0, y_0)\sim(x_1,y_1)$. Then $x_0^2 + y_0^2 = x_1^2 + y_1^2$. Since equality between two real numbers is of course symmetric, we see that $x_1^2 + y_1^2 = x_0^2 + y_0^2$, and therefore $(x_1, y_1) \sim (x_0, y_0)$.

    Transitivity: Let $(x_0, y_0), (x_1,y_1), (x_2, y_2) \in \mathbb{R}^2$ such that $(x_0, y_0)\sim(x_1,y_1)$ and $(x_1, y_1)\sim(x_2, y_2)$. Then $x_0^2 + y_0^2 = x_1^2 + y_1^2$ and $x_1^2 + y_1^2 = x_2^2 + y_2^2$. Since equality between real numbers is of course transitive, we see that $x_0^2 + y_0^2 = x_2^2 + y_2^2$. Therefore $(x_0, y_0)\sim(x_2,y_2)$.

    Well, folks, it looks like $\sim$ is indeed an equivalence relation. Specifically, each equivalence class describes a circle centered around the origin.

    Show Answer
  3. Let $f : \mathbb{R}^n \rightarrow \mathbb{R}^m$ be a function, where $n$ and $m$ are positive integers. Show that $\sim = \{ ({\bf x}_0, {\bf x}_1) : f({\bf x}_0) = f({\bf x}_1) \}$ is an equivalence relation on $\mathbb{R}^n$.

    To determine whether a relation is an equivalence relation, we must test to see that it fulfills the three properties of equivalence relations.

    Reflexivity: Given ${\bf x} \in \mathbb{R}^n$,  reflexivity in $\mathbb{R}^m$ shows that $f({\bf x}) = f({\bf x})$, therefore $\sim$ is reflexive.

    Symmetry: Given ${\bf x}_0, {\bf x}_1 \in \mathbb{R}^n$, symmetry in $\mathbb{R}^m$ shows that if $f({\bf x}_0) = f({\bf x}_1)$, then $f({\bf x}_1) = f({\bf x}_0)$. Therefore $\sim$ is symmetric.

    Transitivity: Given ${\bf x}_0, {\bf x}_1, {\bf x}_2 \in \mathbb{R}^n$, transitivity in $\mathbb{R}^m$ shows that if $f({\bf x}_0) = f({\bf x}_1)$ and $f({\bf x}_1) = f({\bf x}_2)$, then $f({\bf x}_0) = f({\bf x}_2)$. Therefore $\sim$ is symmetric.

    Look at that. Looks like $\sim$ is an equivalence relation.

    Show Answer
  4. Prove that two equivalence classes for a given set are either equal or disjoint.

    Let $E_0$ be an equivalence class defined by $a_0$ and $E_1$ be equivalence class defined by $a_1$.

    If $E_0 \cap E_1 = \varnothing$, then, well, hey, they're disjoint.

    If $E_0 \cap E_1 \neq \varnothing$, then there exists some element $x \in E_0 \cap E_1$. Then $x \in E_0$, so $x \sim a_0$, and by symmetry, $a_0 \sim x$. Let $b \in E_1$. Then $b \sim a_0$, so by transitivity $b \sim x$. Note also that $x \in E_1$, so $x \sim a_1$. By transitivity, $b \sim a_1$. Therefore $b \in E_2$, so $E_0 \subseteq E_1$. By a similar argument, let $c \in E_2$, so $c \sim a_1$. Recall that $x \sim a_1$, so then by symmetry, $a_1 \sim x$. By transitivity, $c \sim x$, and by transitivity again $c \sim a_0$. Therefore $c \in E_0$, so $E_1 \subseteq E_0$. Therefore $E_0 = E_1$.

    Show Answer
  5. Let $A$ denote the set of letters in the alphabet, $\{a, b, c, \ldots, z\}$, and let $\sim$ hold all letters that are strictly vowels equivalent to be equivalent and all letters that are not strictly vowels to be equivalent. Write out $A \, / \sim$.

    $A \, / \sim \; = \{ \{a, e, i, o, u\}, \{ b, c, d, f, g, h, j, k, l, m, n, p, q, r, s, t, v, w, x, y, z\} \}$.

    Show Answer