\( \newcommand{\cat}[1] {\mathrm{#1}} \newcommand{\catobj}[1] {\operatorname{Obj}(\mathrm{#1})} \newcommand{\cathom}[1] {\operatorname{Hom}_{\cat{#1}}} \newcommand{\multiBetaReduction}[0] {\twoheadrightarrow_{\beta}} \newcommand{\betaReduction}[0] {\rightarrow_{\beta}} \newcommand{\betaEq}[0] {=_{\beta}} \newcommand{\string}[1] {\texttt{"}\mathtt{#1}\texttt{"}} \newcommand{\symbolq}[1] {\texttt{`}\mathtt{#1}\texttt{'}} \)

Equivalence relations

The datum of an equivalence relation is a [...]

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 [something of \( S \)]. Compare to the case of the product of two sets, which has a set of ordered pairs as its datum.

For example, \( \{\{1,3,5\}, \{2,4,6\}, \{0\}, \{7\}, \{8, 9\} \} \) is a [...] 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

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} \).