10 .Zorn's "Lemma"

Discussion:

Our goal in this section is to show that for any two sets $\QTR{Large}{A}$ and $\QTR{Large}{B}$, either MATH or MATH . In particular, we need to show that there exists a 1 to 1 map

MATH or a 1 to 1 map MATH. (or both).

In order to meet our goal we have to augment the Zermelo-Frankel axioms.

10. 1 Axiom:(Zorn's Lemma) Let $\QTR{Large}{S}$ be a poset under $\QTR{Large}{\leq }$ . Suppose every chain in $\QTR{Large}{S}$ has an upper bound, then $\QTR{Large}{S}$ has a maximal element. That is, there exists an element MATH such that for no MATH is it the case that $\QTR{Large}{u<v}$.

For Discussion:

  1. Consider well ordering vs. Zorn's Lemma as they apply to MATH.

  2. Consider well ordering vs. Zorn's Lemma as they apply to MATH , any $\QTR{Large}{S.}$

  3. Look at Tarski's Theorem and compare it to Zorn's Lemma

10. 2 Theorem:

For any two sets $\QTR{Large}{A}$ and $\QTR{Large}{B}$, either there exists a 1 to 1 map MATH or a 1 to 1 map MATH. (or both).

Proof:

Define a poset $\QTR{Large}{S}$ whose elements are all pairs MATH with MATH and with MATH one to one

We set MATH MATH MATHif MATH and MATH. Clearly MATH is a partial ordering.

Moreover, any chain MATH has a least upper bound, in particular, the pair MATHgiven by MATH and MATH .

Therefore, by Zorn's Lemma there exists a maximal element MATH. Either MATH or MATH if not we could choose MATHand MATH and define

the pair MATH where MATH and MATH. Contradicting the maximality of MATH.

We now prove the following,

10.3 Theorem:

In the presence of Zorn's Lemma every Set can be Well Ordered.

Proof:

Given a Set $\QTR{Large}{A}$, Define a poset $\QTR{Large}{S}$ whose elements are all pairs MATH with MATH and MATH a Well Ordering of MATH . We now copy the previous proof, replacing MATH with MATH appropriately. Care has to be taken with the definition of MATH MATH because we will need to know that the lub MATH inherits a Well Order from the MATH.

We define MATH MATHby the following three properties.

  1. MATH

  2. MATH

  3. If MATH then MATH for some MATH .

Now let MATH be a chain. As above, we verify that the pair MATHis a lub, where MATH and

MATH . The one thing that requires some proof is that MATH is Well Ordered.

Let MATH be a none empty Set. One needs to show that $\QTR{Large}{T}$ has a least member. Pick any MATH .

$\QTR{Large}{t\in }$ MATH for some MATH . Let $\QTR{Large}{l}$ be the least member of MATH MATH. $\QTR{Large}{l}$ is also the least member $\QTR{Large}{T}$ because if

MATH MATH and MATH MATH, then MATH and thus, by 3., MATH

Finally, invoking Zorn's Lemma, choose a maximal Well Ordered subset MATH.

Again, MATH. If not, again as before chose MATHand MATH

Define a Well Order on MATH by setting MATH for MATH and letting

MATH

10.4 Axiom:

The Well Ordering Principle states that every Set can be Well Ordered.

10.5 A restatement of 10.3:

Zorn's Lemma implies the Well Ordering Principle.

We close this Page by stating

10.6 The Axiom 0f Choice:

Let $\QTR{Large}{S}$ be a set and MATH . There exists at least one map $\QTR{Large}{f}$ MATH ,

such that MATH $\ $for each set MATH

and proving

10.6 Theorem:

The Well Ordering Principle implies the Axiom of Choice.

Proof:

Choose a Well Ordering of $\QTR{Large}{S}$. Introducing some obvious notation, let MATH