Zermelo's Theorem (Set Theory)

From ProofWiki
Jump to navigation Jump to search

Theorem

Every set of cardinals is well-ordered with respect to $\le$.


Proof

Let $S_1$ and $S_2$ be sets which are not empty.

Suppose there exists an injection $f: S_1 \to S_2$ and another injection $g: S_2 \to S_1$.

Then by the Cantor-Bernstein-Schröder Theorem there exists a bijection between $S_1$ and $S_2$ and by definition $S_1$ is equivalent to $S_2$.

Let $\mathcal A$ be the set of invertible mappings $\phi: A \to B$ where $A \subseteq S_1$ and $B \subseteq S_2$.

Since $S_1$ and $S_2$ are not empty, $\exists s_1 \in S_1$ and $\exists s_2 \in S_2$.

Thus we can construct the mapping $\alpha: \set {s_1} \to \set {s_2}$ such that $\map \alpha {s_1} = s_2$.

This is trivially an invertible mapping, so $\mathcal A$ is not empty.

We can impose an ordering $\le$ on $\mathcal A$ by letting $\phi_1 \le \phi_2 \iff \phi_1 \subseteq \phi_2$, that is, if $\phi_2$ is an extension of $\phi_1$.

Let $\mathcal C$ be a chain in $\struct {\mathcal A, \le}$.

Then $\displaystyle \bigcup \set {\phi \in \mathcal C}$ is an upper bound of every $\phi \in \mathcal C$, and it lies in $\mathcal A$.

The conditions of Zorn's Lemma are satisfied, so we can find a maximal element $M$ in $\mathcal A$.

Let:

$M_1 = \set {s_1: \tuple {s_1, s_2} \in M}$
$M_2 = \set {s_2: \tuple {s_1, s_2} \in M}$

We have that $M_1 \subsetneq S_1$ and $M_2 \subsetneq S_2$ both together contradict the fact that $M$ is maximal element.

Thus either $M_1 = S_1$ or $M_2 = S_2$, and possibly both.

Thus either:

$M$ is an injection of $S_1$ into $S_2$

or:

$M^{-1}$ is an injection of $S_2$ into $S_1$.

Thus either $S_1 \le S_2$ or $S_2 \le S_1$, and the result follows.

$\blacksquare$


Axiom of Choice

This proof depends on the Axiom of Choice.

Because of some of its bewilderingly paradoxical implications, the Axiom of Choice is considered in some mathematical circles to be controversial.

Most mathematicians are convinced of its truth and insist that it should nowadays be generally accepted.

However, others consider its implications so counter-intuitive and nonsensical that they adopt the philosophical position that it cannot be true.


Also known as

This is called by some authors the Trichotomy Problem.


Also see


Source of Name

This entry was named for Ernst Friedrich Ferdinand Zermelo.


Sources