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:

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