Correspondence Theorem (Set Theory)

From ProofWiki
Jump to: navigation, 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