I'm reading Jonathan Lewin's "A Simple Proof of Zorn's Lemma" and cannot see the justification for one statement (which I've labeled Lemma 3 below). I'll summarize the proof below (adding a few lemma numbers for ease of communication).
Immediately after stating Lemma 2, Lewin claims, "It now follows easily that [Lemma 3]." It does not follow so easily for me. In particular, Lemma 3 requires verifying the two properties of a "conforming set" (see below), and I find neither one to follow obviously from Lemma 2. Please avoid using any results about ordinals and transfinite recursion/induction in the clarification, since the whole point of this "simple" proof is to omit those concepts.
Proof Summary:
Let $(X,\leqslant)$ be a partially ordered set in which every chain has an upper bound, and assume by contradiction that there is no maximal element. Then by the axiom of choice, there exists a function $f$ mapping every chain in $X$ to a strict upper bound.
For any chain $C\subseteq X$ and $x\in C$, let $P(C,x)$ denote the strict initial segment of $x$ in $C$, that is, $P(C,x)=\{y\in C:y<x\}$.
A subset $A\subseteq X$ is conforming if:
- $A$ is well ordered by $\leqslant$,
- For all $x\in A$, $x=f(P(A,x))$
Lemma 1: If $A$ and $B$ are conforming subsets of $X$ and $A \neq B$, then one of these two sets is an initial segment of the other.
Lemma 2: If $A$ is a conforming subset of $X$ and $x\in A$, then whenever $y < x$, either $y\in A$ or $y$ does not belong to any conforming set.
*Lemma 3: The union $U$ of all conforming subsets of $X$ is conforming.
To reiterate: How can we prove Lemma 3, assuming Lemma 2 and using minimal other set-theoretic results?
Best Answer
We first show that $U$ is a chain. It’s not hard to see that $U$ is a chain. Suppose that $x,y\in U$; there are conforming sets $A_x$ and $A_y$ such that $x\in A_x$ and $y\in A_y$. Lemma $1$ implies that one of these sets is a subset of the other, so without loss of generality suppose that $A_x\subseteq A_y$. Then $x,y\in A_y$, and $A_y$ is a chain, so either $x\le y$, or $y\le x$.
Now we show that $U$ is well-ordered by $\le$. Suppose that $\varnothing\ne S\subseteq U$; we want to show that $S$ has a $\le$-least element. Fix $s\in S$; there is some conforming set $A$ such that $s\in A$. $A$ is well-ordered by $\le$, so let $a=\min\{x\in A\cap S:x\le s\}$; I claim that $a=\min S$. Let $x\in S$; if $x\in A$, then certainly $a\le x$, so suppose that $x\in S\setminus A$. There is some conforming $A_x$ such that $x\in A_x$, and clearly $A_x\nsubseteq A$, so $A$ is an initial segment of $A_x$. Since $x\in A_x\setminus A$, it’s clear that $a<x$ in this case as well and hence that $a=\min S$.
It remains to be shown that if $x\in U$, then $x=f(P(U,x))$. Let $x\in U$; there is a conforming set $A_x$ such that $x\in A_x$. By definition $x=f(P(A_x,x))$, so we’re done if we can show that $f(P(U,x))=f(P(A_x,x))$. It suffices to show that $P(U,x)=P(A_x,x)$. Clearly $P(A_x,x)\subseteq P(U,x)$, so we need only show that $P(U,x)\subseteq P(A_x,x)$, i.e., that if $y\in U$ and $y<x$, then $y\in A_x$. Suppose, then, that $y\in U$ and $y<x$; there is a conforming set $A_y$ such that $y\in A_y$. If $A_y\subseteq A_x$, then certainly $y\in A_x$, and we’re done. Otherwise, $A_x$ is an initial segment of $A_y$, and again $y\in A_x$, since $y<x$.