Equivalence Classes Modulo ρ

Given a set X and an equivalence relation ρ, the equivalence class of an element β is the set [β] consisting of all elements x in X that are related to β under ρ: $$ [\beta]_\rho = \{ x \in X \:\: | \:\: x\rho\beta \} $$

The element a is called the representative of the class.

Every equivalence class contains at least one element - its representative.

Example

Consider the equivalence relation ρ on the set of integers ℤ, where two elements a and b are related if and only if \( a^2 = b^2 \).

$$ [a] = \{ b \in X \:\: | \:\: a^2 = b^2 \} $$

For instance, one equivalence class is:

$$ [a] = \{ +2, -2 \} $$

since both +2 and −2 yield the same square: 4.

In general, under this relation, each equivalence class [a] consists of two elements:

$$ [a] = \{ +a, -a \} $$

except for the case a = 0, whose equivalence class contains only one element:

$$ [0] = \{ 0 \} $$

A Concrete Example of an Equivalence Class

Consider the power set of A = {1, 2, 3}:

$$ P(A) = \{ \emptyset, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\} \} $$

The elements of the power set are all subsets of A.

Suppose we define an equivalence relation ρ on P(A) such that two subsets are related if they have the same cardinality - that is, the same number of elements.

The equivalence class of an element a is then defined as:

$$ [a]_\rho = \{ x \in P(A) \ | \ x\rho a \} $$

In this context, the equivalence classes are as follows:

The equivalence class of a = ∅ is just the singleton containing the empty set:

$$ [\emptyset]_\rho = \{ \emptyset \} $$

Note: This doesn’t mean the class is empty. It contains one element - the empty set itself {∅}, which is an element of P(A). As stated earlier, every equivalence class contains at least its representative.

The equivalence class of a = {1} includes all singleton subsets of A:

$$ [{1}]_\rho = \{ \{1\}, \{2\}, \{3\} \} $$

Likewise, the equivalence classes of {2} and {3} are identical:

$$ [{2}]_\rho = \{ \{1\}, \{2\}, \{3\} \} $$

$$ [{3}]_\rho = \{ \{1\}, \{2\}, \{3\} \} $$

The equivalence class of {1,2} includes all subsets of size 2:

$$ [{1,2}]_\rho = \{ \{1,2\}, \{1,3\}, \{2,3\} \} $$

Similarly, the classes of {1,3} and {2,3} are the same:

$$ [{1,3}]_\rho = \{ \{1,2\}, \{1,3\}, \{2,3\} \} $$

$$ [{2,3}]_\rho = \{ \{1,2\}, \{1,3\}, \{2,3\} \} $$

Finally, the class of {1,2,3} contains only itself:

$$ [{1,2,3}]_\rho = \{ \{1,2,3\} \} $$

Note: As we can see in this last example, an equivalence class always contains at least one element: its representative.

Properties of Equivalence Classes

Let A be a set and ρ an equivalence relation on A. For any two elements a and b in A, the following properties hold:

$$ [a] \ne \emptyset $$ $$ [a] = [b]_\rho \Leftrightarrow a\rho b $$ $$ [a] \ne [b]_\rho \Leftrightarrow [a] \cap [b] = \emptyset $$

Proof

First Property

An equivalence class is never empty.

$$ [a] \ne \emptyset $$

This follows from the reflexivity of the equivalence relation: every element a ∈ A is related to itself.

$$ \forall a \in A \ (a\rho a) \Rightarrow [a] \ne \emptyset $$

Therefore, every equivalence class contains at least one element - the representative - and is never empty.

In conclusion, equivalence classes always contain at least the element they represent, and thus cannot be empty.

Second Property

Two equivalence classes are equal if and only if their representatives are related.

$$ [a] = [b]_\rho \Leftrightarrow a\rho b $$

Since this is a biconditional statement, we must prove both the “if” and the “only if” directions.

A] Sufficient Condition

If \( [a] = [b] \), then the representatives a and b must be related:

$$ [a] = [b]_\rho \Rightarrow a\rho b $$

By the reflexive property, every element belongs to its own equivalence class:

$$ \forall a \in A,\ a \in [a] $$

Given that \( [a] = [b] \), we have:

$$ a \in [b] $$

But by definition, every element in \( [b] \) is related to b:

$$ [b] = \{ x \in A\ |\ x\rho b \} $$

So \( a\rho b \), as required.

This proves the sufficient condition.

B] Necessary Condition

Now assume that \( a\rho b \). We want to show that \( [a] = [b] \).

To prove equality, it’s enough to show mutual inclusion:

$$ [a] = [b] \Leftrightarrow [a] \subseteq [b] \land [b] \subseteq [a] $$

First inclusion: Let \( x \in [a] \), so \( x\rho a \).

Given \( a\rho b \), by transitivity we get:

$$ x\rho a \land a\rho b \Rightarrow x\rho b $$

Therefore, \( x \in [b] \), and thus \( [a] \subseteq [b] \).

Second inclusion: Let \( x \in [b] \), so \( x\rho b \).

Since \( a\rho b \), by symmetry we also have \( b\rho a \).

Then, by transitivity again:

$$ x\rho b \land b\rho a \Rightarrow x\rho a $$

So \( x \in [a] \), and hence \( [b] \subseteq [a] \).

Therefore, mutual inclusion implies:

$$ [a] \subseteq [b] \land [b] \subseteq [a] \Rightarrow [a] = [b] $$

This proves the necessary condition.

Third Property

Two equivalence classes are distinct if and only if they are disjoint - that is, their intersection is empty:

$$ [a] \ne [b] \Leftrightarrow [a] \cap [b] = \emptyset $$

This is also a biconditional, so we prove both directions.

Sufficient Condition

We proceed by contradiction. Suppose \( [a] \cap [b] \ne \emptyset \), i.e., there exists:

$$ \exists c \in [a] \cap [b] $$

Then c belongs to both \( [a] \) and \( [b] \).

If \( c \in [a] \), then \( c\rho a \Rightarrow [c] = [a] \)

If \( c \in [b] \), then \( c\rho b \Rightarrow [c] = [b] \)

So we conclude:

$$ [a] = [c] = [b] \Rightarrow [a] = [b] $$

This contradicts the assumption that \( [a] \ne [b] \). Therefore:

$$ [a] \ne [b] \Rightarrow [a] \cap [b] = \emptyset $$

Necessary Condition

Now suppose \( [a] \cap [b] = \emptyset \), and we want to prove that \( [a] \ne [b] \).

Assume instead that \( [a] = [b] \).

Then their intersection is equal to:

$$ [a] \cap [b] = [a] \cap [a] = [a] $$

By the idempotent law of set intersection:

$$ [a] \cap [a] = [a] $$

And since every equivalence class is non-empty:

$$ [a] \ne \emptyset $$

This contradicts our assumption that \( [a] \cap [b] = \emptyset \).

Hence, \( [a] \ne [b] \).