Equivalence Relations

Why

We want to handle at once all the objects of a set which are indistinguishable or equivalent in some aspect.

Definition

An equivalence relation on a set $X$ is a reflexive, symmetric, and transitive relation on $X$ (see Relations). The smallest equivalence relation in a set $X$ is the relation of equality in $X$. The largest equivalence relation in a set $X$ is $X \times X$.

Equivalence relations are useful because they partition (see Partitions) the set. If $R$ is an equivalence relation on $X$, the equivalence class of an object $x \in X$ is the set $\Set{y \in X}{x\;R\;y}$. We call the set of equivalence classes the quotient set of the set under the relation (or the quotient of the set by the relation). An equally good name is the divided set of the set under the relation, but this terminology is not standard. The language in both cases reminds us that the relation partitions the set into equivalence classes.

If $\mathcal{C} $ is a partition of $X$, we can define a relation $R$ on $X$ for which $x\,R\,y \iff (\exists A \in \mathcal{C} )(x \in A \land y \in A)$. In other words, if $x$ and $y$ are in the same piece (see Partitions) of $\mathcal{C} $.

The key result is that every equivalence relation partitions the set and every partition of the set is an equivalence relation. Moreover, if we start with an equivalence relation, look for the partition, and then get the relation defined by the partition, we end up with the relation we started with. Likewise, if we start with a partition relation, get the equivalence relation, and then get the partition defined by the relation, we end up with the partition we started with. Before stating and proving this result, we give some notation.

Notation

Let $R$ denote an equivalence relation on a set denoted by $X$. We denote the equivalence class of $x \in X$ by $x / R$. We denote the set of equivalence classes of $R$ by $X/R$, read aloud as “$X$ modulo $R$” or “$x$ mod $R$”. We denote the equivalence class of an element $x \in X$ by $\eqc{x}$.

Main Results

The proofs of these results are straightforward.¹

$X/\mathcal{C} $ is an equivalence relation.

$X/R$ is a a partition.

If $R$ is an equivalence relation on $X$, then $X/(X/R) = R$

If $\mathcal{C} $ is a partition of $X$, then $X/(X/\mathcal{C} ) = \mathcal{C} $.

These last two propositions make clear the rationale for the notation. The function mapping an element to its equivalence class is onto and is sometimes called the projection.

Nonetheless, the full accounts will appear in future editions. ↩︎