Correspondence Theorem (Set Theory)

From ProofWiki
Jump to navigation Jump to search

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