# Correspondence Theorem (Set Theory)

*This proof is about correspondence of certain partitions and equivalence relations. For other uses, see Correspondence Theorem.*

## Theorem

Let $S$ be a set.

Let $\mathcal R \subseteq S \times S$ be an equivalence relation on $S$.

Let $\mathscr A$ be the set of partitions of $S$ associated with equivalence relations $\mathcal R'$ on $S$ such that:

- $\tuple {x, y} \in \mathcal R \iff \tuple {x, y} \in \mathcal R'$

Then there exists a bijection $\phi$ from $\mathscr A$ onto the set of partitions of the quotient set $S / \mathcal R$.

## Proof

Denote the equivalence class of an element $x$ of $S$ by $\eqclass x {\mathcal R}$ with respect to the relation $\mathcal R$.

Consider the relation on $S$:

- $\phi = \set {\tuple {\eqclass x {\mathcal R'}, \eqclass x {\mathcal R} }: x \in S}$

We prove that $\phi$ is a bijection.

Let $\eqclass x {\mathcal R} = \eqclass y {\mathcal R}$.

Then:

- $\tuple {x, y} \in \mathcal R$

Thus:

- $\tuple {x, y} \in \mathcal R'$

Therefore:

- $\eqclass x {\mathcal R'} = \eqclass y {\mathcal R'}$

and so $\phi$ is one-to-many.

Let $\eqclass x {\mathcal R'} = \eqclass y {\mathcal R'}$.

Then:

- $\tuple {x, y} \in \mathcal R'$

Thus:

- $\tuple {x, y} \in \mathcal R$

Therefore $\eqclass x {\mathcal R} = \eqclass y {\mathcal R}$

Hence $\phi$ is many-to-one.

As $\phi$ is both one-to-many and many-to-one, it is by definition a one-to-one relation.

From the fact that $\Rng \phi = S / \mathcal R$ we have that $\phi$ is both left-total and right-total.

We have demonstrated that $\phi$ is left-total and many-to-one, and so by definition is a mapping.

We have demonstrated that $\phi$ is right-total, and so by definition is a surjection.

We have demonstrated that $\phi$ is one-to-one, and so by definition is an injection.

Hence by definition $\phi$ is a bijection.

$\blacksquare$

## Sources

- 1975: T.S. Blyth:
*Set Theory and Abstract Algebra*... (previous) ... (next): $\S 6$: Exercise $18$

- 1977: Herbert B. Enderton:
*Elements of Set Theory*P60