📂Set Theory

Equivalence Class, Quotient Set

Definition ¹

Let an equivalence relation $R$ be defined on a set $X$. For $x \in X$, the set $x / R := \left\{ y \in X : y R x \right\}$ is called the equivalence class of $x$ with respect to $x \in X$. The collection of all equivalence classes of $X$ is denoted by $X / R := \left\{ x / R : x \in X \right\}$.

We call $X / R$ the quotient set of $X$ by $R$, and read it as $X$ modulo $R$.

Explanation

Although the notation may look a little messy, the concept is not difficult if you consider an example. On the set of natural numbers $\mathbb{N}$, declare two numbers equivalent if they have the same remainder when divided by $3$, and denote the equivalence class of $x,y \in \mathbb{Z}$ by $x \equiv y \pmod{3}$. $5,7$ are not equivalent because their remainders upon division by $3$ are $2,1$ respectively, but $11,17$ has remainder $2$ modulo $3$, so it can be written as $11 \equiv 17 \pmod{3}$. $$ 1 \equiv 4 \equiv 7 \equiv 10 \equiv \cdots \pmod{3} \\ 2 \equiv 5 \equiv 8 \equiv 11 \equiv \cdots \pmod{3} \\ 3 \equiv 6 \equiv 9 \equiv 12 \equiv \cdots \pmod{3} $$ As the calculation above shows, the equivalence class of $1$ is $( 1 / \equiv) = \left\{ 1, 4, 7, 10, \cdots \right\}$, the equivalence class of $2$ is $(2 / \equiv) = \left\{ 2, 5, 8, 11, \cdots \right\}$, and the equivalence class of $3$ is $(3 / \equiv) = \left\{ 3, 6, 9, 12, \cdots \right\}$. For numbers larger than $3$ the three equivalence classes repeat, hence $$ (\mathbb{N} / \equiv) = \left\{ 1 / \equiv , 2 / \equiv , 3 / \equiv \right\} $$ As can be seen in the example above, equivalence classes satisfy the following natural properties.

Basic properties

• [1] $x / R \ne \emptyset$
• [2] $ x / R \cap y / R \ne \emptyset \iff xRy$
• [3] $x/R = y/R \iff x R y$
• [4] $x / R \cap y / R \ne \emptyset \iff x/R = y/R $

Proof

[1]

Since $R$ is an equivalence relation on $X$, by reflexivity for every $x \in X$ we have $x R x$, and $x \in x / R$ must hold.

■

Strategy for [2][3]: choose a $z$ distinct from $x,y$ and connect the statements using the symmetry and transitivity of the equivalence relation.

[2]

$x/R$ and $y/R$ are nonempty and $X$-subsets related by the equivalence relation, so $x/R \cap y/R \ne \emptyset$, which is equivalent to the existence of some $z$ such that $$ \begin{align*} & z \in x / R \land z \in y / R \\ \iff & z R x \land z R y \\ \iff & x R z \land z R y \\ \iff & x R y \end{align*} $$

■

[3]

If $( \implies )$ and $x/R = y/R$ then $x/R \cap y/R \ne \emptyset$, so by [2] we obtain $x R y$.

---

If $( \impliedby )$ and $x R y$ then for every $z \in x / R$ we have $z R x$. Since $x R y$, by the transitivity of $R$ we get $z R y$, and $z \in y / R$. In summary, $$ z \in x / R \implies z \in y / R $$ Rewriting this in terms of inclusion of sets, $$ x / R \subset y / R $$ By the same method we can obtain $ y / R \subset x / R$, hence $$ x / R = y / R $$

■

[4]

By syllogism, from [2] and [3] we get $$ x / R \cap y / R \ne \emptyset \iff xRy \iff x/R = y/R $$

■