Question

Q. State and prove Zorn, s Lemma.

Answer 1

Zorn's lemma

Statement: Let $M \neq 0$ be a partially ordered set. Suppose that every chain $C \subset P$ has an upper bound. Then $P$ has at least one maximal element.

Proof: For each $A \in P$, Let TA be the set defined by

$$T_A = \begin{cases} \{A\} & \text{if } A \text{ is a maximal element of } P \\ \{Q \in \text{Pl } A \notin Q\} & \text{if } A \text{ is not a maximal element of } P \end{cases}$$

Observe that TA non-empty for every $A \in P$, and hence $\{TA\}A \in P$ is a family of non-empty sets.

By the Axiom of Choice there is a family of sets $\{FA\}A \in P$ such that $FA \subseteq TA$ and $FA$ has exactly one element for all $A \in P$. For each $A \in P$, let $SA$ be the single element in $FA$.

By the definition of TA we see that $SA \in P$ and $A \subseteq SA$ for all $A \in P$; moreover, we have $SA = A$ if and only if $A$ is a maximal element of $P$.

To prove the theorem, it therefore suffices to find some $M \in P$ such that $SM = M$.

Let $R \subseteq P$.

The family $R$ is closed if $A \in R$ implies $SA \in R$, and if $C \subseteq R$ is a chain then

$$\underset{C \in C}{\mathrm{Y}} C \in R$$

By hypothesis the family $P$ is closed. Let $M$ be the intersection of all closed families in $P$.

We now prove four Points about $M$. Using these Points, we deduce the theorem, as follows.

Let $M = \underset{C \in M}{\mathrm{Y}} C \in R$. Point 4 says that $M$ is a chain, and Point 1 says that $M$ is closed.

It follows that $M \in M$. Again using the fact that $M$ is closed, we deduce that $SM \in M$.

However, we know that $C \subseteq M$ for all $C \in M$, and hence in particular that $SM \subseteq M$.

As noted above, we know that $M \subseteq SM$, and we deduce that $SM = M$, and that is what needed to be proved.

**Point 1.** We will show that the family $M$ is closed.

Let $A \in M$. Then $A \in R$ for all closed families $R \subseteq P$, and

hence $SA \in R$ for all closed families $R \subseteq P$, and

hence $SA \in M$. A similar argument shows that

if $C \subseteq M$ is a chain then $\underset{C \in C}{\mathsf{Y}} C \in M$ the details are left to the reader.

**Point 2.** Let $A \in M$. Suppose that $B \in M$ and $B \neq A$ imply $SB \subseteq A$. We will show that $B \subseteq A$ or $B \supseteq SA$ for all $B \in M$.

Let $ZA = \{C \in M \mid C \subseteq A \text{ or } C \supseteq SA\}$.

We first show that $ZA$ is closed.

First, let $D \in ZA$. Then $D \in M$, and $D \subseteq A$ or $D \supseteq SA$.

Because $M$ is closed, then $SD \in M$. Suppose first that $D \subseteq A$. If $D \neq A$,

then by hypothesis on $A$ we deduce that $SD \subseteq A$,

which implies that $SD \in ZA$.

If $D = A$, then $SD = SA$, and hence $SD \supseteq SA$,

which implies $SD \in ZA$.

Suppose second that $D \supseteq SA$. Because $SD \supseteq D$, it follows that $SD \supseteq SA$, which implies $SD \in ZA$.

Next, let $C \subseteq ZA$ be a chain. Because $M$ is closed, we know that $\underset{C \in C}{\mathsf{Y}} C \in M$

There are two cases. First, suppose that $C \subseteq A$ for all $C \in C$.

Then it follows that $\underset{C \in C}{\mathsf{Y}} C \subseteq A$ and hence $\underset{C \in C}{\mathsf{Y}} C \subseteq Z_A$

Second, suppose that there is some $E \in C$ such that $E \notin A$. Because $E \in ZA$, then

$E \supseteq SA$. Because $\underset{C \in C}{\mathsf{Y}} C \supseteq E$

it follows that

$$\underset{C \in C}{\mathrm{Y}} C \supseteq S_{A} \text{ Hence } \underset{C \in C}{\mathrm{Y}} C \in Z_{A}$$

We deduce that ZA is closed. Because M is the intersection of all closed families of sets in P, it follows that M ⊆ ZA.

On the other hand, by definition we know that ZA ⊆ M, and it follows that

ZA = M. We deduce that B ⊆ A or B ⊋ SA for all B ∈ M.

**Point 3.** We will show that if A ∈ M, then B ∈ M and B ≠ A imply SB ⊆ A.

Let W = {A ∈ M | B ∈ M and B ≠ A imply SB ⊆ A}.

We first show that W is closed.

First, let F ∈ W. Then F ∈ M, and B ∈ M and B ≠ F imply SB ⊆ F. Because M is closed, we know that SF ∈ M.

Let G ∈ M, and suppose that G ≠ SF.

It follows that G ≠ SF. By Point 2 we know that G ⊆ F.

There are two cases.

First, suppose that G ≠ F. Then SG ⊆ F. Because F ⊆ SF, it follows that SG ⊆ SF.

Second, suppose that G = F. Then SG = SF, and hence SG ⊆ SF. We deduce that SF ∈ W.

Next, let C ⊆ W be a chain. Because M is closed we know that $\underset{C \in C}{\mathrm{Y}} C \in M$

Let H ∈ M, and suppose that H $\underset{C \in C}{\mathrm{Y}} C$. If it were the case that C ⊆ H for all C ∈ C, then it would follow that $\underset{C \in C}{\mathrm{Y}} C \subseteq H$ which is not possible.

Hence there is some K ∈ C such that K∉ H.

Because K ∈ W, then B ∈ M and B∉ K imply SB ⊆ K.

By Point 2 we deduce that B ⊆ K or B ⊋ SK for all B ∈ M. Because SK ⊋ K, it follows that B ⊆ K or B ⊋ K for all B ∈ M.

Because K ≠ H, it follows that K ⊋ H. If K = H then it would follow that K ⊆ H, which is not true, and hence we deduce that H ≠ K.

It then follows that SH ⊆ K. Because K ∈ C, we deduce that

$\mathrm{SH} \subseteq \underset{C \in C}{\mathrm{Y}C}$ Hence $\underset{C \in C}{\mathrm{Y}C} \in W$ We deduce that $W$ is closed.

By an argument similar to the one used in Point 2, we deduce that $\mathbf{W} = \mathbf{M}$ , and

therefore we know that

if $\mathrm{A} \in \mathrm{M}$ , then $\mathrm{B} \neq \mathrm{A}$ implies $\mathrm{SB} \subseteq \mathrm{A}$ for all $\mathrm{B} \in \mathrm{M}$ .

Point 4. We will show that $\mathbf{M}$ is a chain.

Let $\mathrm{A}, \mathrm{C} \in \mathrm{M}$ . By Point 3 we know that $\mathrm{B} \neq \mathrm{A}$

implies $\mathrm{SB} \subseteq \mathrm{A}$ for all $\mathrm{B} \in \mathrm{M}$ ,

and hence by Point 2 we deduce that $\mathrm{B} \subseteq \mathrm{A}$ or $\mathrm{B} \supseteq \mathrm{SA}$ for all $\mathrm{B} \in \mathrm{M}$ .

Hence $\mathrm{C} \subseteq \mathrm{A}$ or $\mathrm{C} \supseteq \mathrm{SA}$ . Because $\mathrm{SA} \supseteq \mathrm{A}$ ,

it follows that $\mathrm{C} \subseteq \mathrm{A}$ or $\mathrm{C} \supseteq \mathrm{A}$ . We deduce that $\mathbf{M}$ is a chain.

Hence Proved.

Answer provided by AssignmentExpert.com