An equivalence relation is a binary relation \(\sim\) on a set \(S\) that can be used to say whether elements of \(S\) are equivalent.

An equivalence relation satisfies the following properties:

1. For any \(x \in S\), \(x \sim x\) (the reflexive property).

2. For any \(x,y \in S\), if \(x \sim y\) then \(y \sim x\) (the symmetric property).

3. For any \(x,y,z \in S\), if \(x \sim y\) and \(y \sim z\) then \(x \sim z\) (the transitive property).

Intuitively, any element is equivalent to itself, equivalence isn’t directional, and if two elements are equivalent to the same third element then they’re equivalent.

Equivalence classes

Whenever we have a set \(S\) with an equivalence relation \(\sim\), we can divide \(S\) into equivalence classes, i.e. sets of mutually equivalent elements. The equivalence class of some \(x \in S\) is the set of elements of \(S\) equivalent to \(x\), written \([x]=\{y \in S \mid x \sim y\}\), and we say that \(x\) is a “representative” of \([x]\). We call the set of equivalence classes \(S/\sim = \{[x] \mid x \in S\}\).

From the definition of an equivalence relation, it’s easy to show that \(x \in [x]\) and \([x]=[y]\) if and only if \(x \sim y\).

If you have a set already partitioned into subsets ($S$ is the disjoint union of the elements of a collection \(A\)), you can go the other way and define a relation with two elements related whenever they’re in the same subset ($x \sim y$ when there is some \(U \in A\) with \(x,y \in U\)). Then this is an equivalence relation, and the partition of the set is the set of equivalence classes under this relation (that is, \([x] \in A\) and \(A=S/\sim\)).

Defining functions on equivalence classes

Suppose you have a function \(f: S \to U\) and want to define a corresponding function \(f^*: S/\sim \to U\), where \(U\) can be any set. You define \(f^*([x])\) to be \(f(x)\). This could be a problem; what if \(x \sim y\) but \(f(x) \neq f(y)\)? Then \(f^*([x])=f^*([y])\) wouldn’t be well-defined. Whenever you define a function on equivalence classes in terms of representatives, you have to make sure the definition doesn’t depend on which representative you happen to pick. In fact, one way you might arrive at an equivalence relation is to say that \(x \sim y\) whenever \(f(x)=f(y)\).

If you have a function \(f: S \to S\) and want to define \(f^*: S/\sim \to S/\sim\) by \(f^*([x])=[f(x)]\), you have to verify that whenever \(x \sim y\), \([f(x)]=[f(y)]\), equivalently \(f(x) \sim f(y)\).

Examples

Consider the integers with the relation \(x \sim y\) if \(n|x-y\), for some \(n \in \mathbb N\). This is the integers mod \(n\). The addition and multiplication operations can be inherited from the integers, so it makes sense to talk about addition and multiplication mod \(n\).

The real numbers can be defined as equivalence classes of Cauchy sequences.

Isomorphism is an equivalence relation (unless the objects form a proper class).