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 $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 $P_{\sim}$ .

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

Quotients

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

S / \sim = 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 $Z$ like so:

a \sim b ⟺ a - b is even .

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

Source

Aluffi, Algebra: Chapter 0