# 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:

- $\left({x, y}\right) \in \mathcal R \Leftrightarrow \left({x, y}\right) \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 equvalence class of an element $x$ of $S$ by $[x]_\mathcal R$ with respect to the relation $\mathcal R$.

Consider the relation:

- $\phi=\{([x]_\mathcal {R'},[x]_\mathcal R )|\text{ for } x\in S\}$

We prove that $\phi$ is a bijection(here function is defined as a special case of relation).

Let $[x]_\mathcal {R}=[y]_\mathcal {R}$, then $(x,y)\in \mathcal{R}$. Thus $(x,y)\in \mathcal{R'}$, therefore $[x]_\mathcal {R'}=[y]_\mathcal {R'}$, $\phi$ is single-rooted.

Let $[x]_\mathcal {R'}=[y]_\mathcal {R'}$, then $(x,y)\in \mathcal{R'}$. Thus $(x,y)\in \mathcal{R}$, therefore $[x]_\mathcal {R}=[y]_\mathcal {R}$, $\phi$ is a function.

$\phi$ is a single-rooted function, thus $\phi$ is injective. The surjectivity follows from the fact that $\text{ran}\phi=S/\mathcal R$.

$\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