Show Question
Math and science::Algebra::Aluffi

# Equivalence relations

### The datum of an equivalence relation is a partition

What is the information that is contained by an equivalence relation on a set?

The datum of an equivalence relation on a set $$S$$ turns out to be a partition of $$S$$. Compare to the case of the product of two sets, which has a set of ordered pairs as its datum.

### Partition. Definition.

Let $$S$$ be a set. A partiton $$\mathcal{P}$$ of $$S$$ is a family of disjoint non-empty subsets of $$S$$ that union to $$S$$.

For example, $$\{\{1,3,5\}, \{2,4,6\}, \{0\}, \{7\}, \{8, 9\} \}$$ is a partition of the set $$\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$$.

### From equivalence relations to partitions, and back

There is a 1-1 correspondence between partitions and equivalence relations, and in this sense they represent the same notion.

Here is the process of obtaining a partition from an equivalence relation. Let $$\sim$$ be an equivalence relation on a set $$S$$. For every $$a \in S$$ the equivalence class of $$a$$ is the subset of $$S$$ defined by

$[a]_{\sim} = \{ b \in S | b \sim a \}.$

The set of all equivalence classes is a partition of $$S$$, denoted $$\mathcal{P}_{\sim}$$.

Conversely, given a partition $$\mathcal{P}$$, we can form an equivalence relation $$\sim$$ where $$a \sim b$$ is true if $$a$$ and $$b$$ are in the same element of $$\mathcal{P}$$.

### Quotients

The quotient of a set $$S$$ with respect to an equivalence relation $$\sim$$ is preciely the partition $$\mathcal{P}_{\sim}$$ (the set of equivalence classes formed by $$\sim$$ with respect to $$S$$). We write the quotient as $$S$$:

$S / \mathord{\sim} = \mathcal{P}_{\sim}$

#### Quotients and equivalence relations, a perspective

The equivalence relation becomes equality in the quotient. Taking a quotient turns an equivalence relation into an equality.

### Example

Let $$\sim$$ be the relation defined for $$\mathbb{Z}$$ like so:

$a \sim b \iff a - b \text{ is even}.$

Then the quotient is the set containing two equivalence classes, $$\mathbb{Z}/ \mathord{\sim} = \{ [0]_{\sim}, [1]_{\sim} \}$$.

#### Source

Aluffi, Algebra: Chapter 0
p8