Proof of Zorn's lemma clarification

Question

In the proof A Simple Proof of Zorn's Lemma, there is a result that says:

" 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".

Assuming the result is true: "we observe that 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. It now follows easily that the union $U$ of all the conforming subsets of $X$ is conforming".

I think that it means that there exists a conforming chain $U$ such that every conforming chain in $X$ is an initial segment of $U$. But I don't know if it is the case or how to argue that.

I am struggled to understand the consequence of the above result. Can someone give me a clarification of it?

---

Definition 1. We shall say that a subset $A$ of $X$ is conforming if the following two conditions hold:

• The order $\leq$ is a well order of the set $A$.
• For every element $x \in A$, we have $x = f(P(A, x))$, where $f$ maps the initial segment to its strict upper bound x.

Definition 2. If $C$ is a chain in $X$ and $x\in C$, then we define $P(C, x) = \{ y \in C: y < x\}$. A subset of a chain $C$ that has the form $P(C, x)$ is called an initial segment in $C$.

Answer 1

Let $U$ be the union of all conforming sets.

We need to show that $\le$ is a well-order on $U$. So let $V\subset U$ be a non-empty subset and $v\in V$. There exists a conforming set $A$ with $v\in A$. As $A$ is well-ordered, let $a=\min(A\cap V)$. Then $a=\min V$ because for any $b\in V$, we find a conforming $B$ with $b\in B$. As one of $A,B$ is an initial segment of the other, $A\cup B$ is comforming, hence by its well-order either $b\ge a$ or $b\in A$ and $b\in V$, contradicting $a=\min(A\cap V)$.

We also need to show the second property. So let $x\in U$. Then $x\in A$ for some conforming $A$. Then $P(A,x)=P(U,x)$ because $u\in U$ and $u<x$ implies $u\in A$. It follows that $x=f(P(U,x))$.

Now as $U$ is conforming, every conforming $A$ is either $=U$ or an initial segment of $U$.

Answer 2

The premise can be equivalently rephrased as $$ P_1 :\Leftrightarrow \forall A, B \subseteq X: [\neg A \subseteq B \Rightarrow \exists b \in A: P(A,b) = B] $$

We have to show that 1) for any nonempty subset $S$ of $U$, $S$ has a least element; and that 2) $$ \forall x \in U: x = f(P(U,x)) $$

I used element-chasing for the proof and I didn't use the property 'We observe that ... any conforming set.' The proposition 'The union $U$ of all ...' can be shown directly from $P_1$.

I will list some useful properties for the proof of the statement '$U$ are well-ordered by $\le$':

1. For any $x \in U$, there is a conforming subset of $X$ that contains $x$.
2. For any conforming sets $A$ and $B$, if there is an element $x \in A$ that is not in $B$, it follows that $\neg A \subseteq B$; thus, $\exists b \in A: P(A,b) = B$;
3. For any subset $S$ of $X$ and any conforming set $A$, the intersection $A \cap S$ has a least element because $A \cap S \subseteq A$ and $A$ is well-ordered; $\exists x \in A \cap S: \forall y \in A \cap S: x \le y $;
4. If $x$ and $y$ are in a conforming set, they are comparable, that is, $\neg x < y$ implies $y \le x$ because conforming sets are totally ordered;
5. For any nonempty set $A$, if it is given that $x \in A$ and $ x \notin A \lor Q $, we have $Q$. (resolution) This is used for the case $y \notin P(A,b)$, i.e., $y \notin A \lor \neg y < b$.

The proof is just repeated applications of the above properties. Start from a subset $S$ of $U$.

You can find the proof of the part involving the choice function $f$ from Brian M. Scott.

Answer 3

I struggled with this proof too so I'll just fill in the gaps that took me a while to figure out either myself or by Googling around, including the bits that the OP asks about. Note: the PDF still contains the complete proof; what I've written below contains gaps and probably won't make sense without reading it alongside the PDF.

Initial Segments of Minimal Elements

To warm up, let's consider a property of initial segments that we will use repeatedly in the following. Suppose $C$ is a conforming set and $D$ is any other set. Let $l$ be the least element of $C \setminus D$. Then $P(C, l) \subseteq C \cap D$.

To see why this is the case, consider any $d \in P(C, l)$. Well, we know by definition of $P(C, l)$ that $d < l$ and $d \in C$. Since $d \in C$, then we know that either $d \in C \cap D$ or $d \in C \setminus D$. We can proceed then by assuming $d \in C \setminus D$ towards a contradiction. Well, since $l$ is the least element of $C \setminus D$, we know that $l \leq d$. But this directly contradicts our earlier hypothesis that $d < l$. This concludes the proof.

Corollary: Since $P(C, l) \subseteq C \cap D$ then $P(C, l) \subseteq D$. Often this form will be used.

All Conforming Sets are Comparable

A good chunk of this proof boils down to the result that all distinct conforming sets are comparable in the sense that one is always an initial segment of the other.

Let $A \neq B$ be the two conforming sets in question. WLOG we can assume that $A \setminus B$ is non-empty. Since $A$ is conforming, any subset of it has a least element. So let $x$ be the least element of $A \setminus B \subseteq A$.

Now, consider the set $P(A, x)$. By our earlier property about initial segments of minimal elements, $P(A, x) \subseteq A \cap B \subseteq B$.

The remainder of the proof now goes to show that actually $P(A, x) = B$. This is done by contradiction. So we assume that $P(A, x) \neq B$, towards a contradiction. Well, since we already have that $P(A, x) \subseteq B$, this would imply that $P(A, x) \subset B$, and so the set $B \setminus P(A, x)$ is non-empty.

Now we proceed in a similar way to how we defined $x$ earlier. Since $B$ is conforming, it is well-ordered, and so our non-empty subset $B \setminus P(A, x) \subseteq B$ has a least element. Call that $y$. Again, by our earlier property about initial segments of minimal elements we have: $P(B, y) \subseteq P(A, x)$.

It gets a bit dizzying... but we need to do that "least element" trick now just one more time. Consider the set $A \setminus P(B, y)$. Since $P(B, y) \subseteq B$ then $A \setminus P(B, y) \supseteq A \setminus B$ and so $A \setminus P(B, y)$ is non-empty, is a subset of the conforming, well-ordered set $A$ and therefore has a least element. Call that $z$. Again, by our earlier property about initial segments of minimal elements we have: $P(A, z) \subseteq P(B, y)$.

Let's stop here and take a breather, to recap what has been done. Three times, we have applied the same sort of construction to get:

$P(A, z) \subseteq P(B, y) \subseteq P(A, x) \subseteq A \cap B$

Now we're ready to prove a key identity:

$P(A, z) = P(B, y)$

From our construction, we already have $P(A, z) \subseteq P(B, y)$. Therefore, it remains to show that:

$P(B, y) \subseteq P(A, z)$.

Consider $u \in P(B, y)$. Since $P(B, y) \subseteq P(A, x) \subseteq A$, then $u \in A$. Also, since $z$ is the least element of $A \setminus P(B, y)$, then $z \notin P(B, y)$ and so $z \neq u$. Since $A$ is conforming, it is totally ordered. And so either $z < u$ or $u < z$. If $u < z$, then since we already have $u \in A$, we can conclude that $u \in P(A, z)$, as desired.

So assume that $z < u$. Well, since $u \in P(B, y)$, we have that $u < y$ and so $z < y$. And since $z$ is the least element of $A \setminus P(B, y) \supseteq A \setminus B$, and $x \in A \setminus B$, then $z \leq x$. If $z < x$ then $z \in P(A, x) \subseteq B$ and so we have that $z \in P(B, y)$, which contradicts the fact that $z$ is the least element of $A \setminus P(B, y)$. Therefore, we must have $z = x$. But then since $P(B, y) \subseteq P(A, x) = P(A, z)$, we are done.

And so we now know that:

$P(A, z) = P(B, y)$

Now, it's time to introduce the choice function $f$, to get our desired contradiction. Since $A$ and $B$ are conforming, we have:

$z = f(P(A, z)) = f(P(B, y)) = y \implies z = y$

Now, consider the element $x$, the least element of $A \setminus B$. Since $z$ is the least element of $A \setminus P(B, y) \supseteq A \setminus B$ then we have $z \leq x$. And so $y \leq x$. Now $y \in B$ but $x \notin B$ and so $y \neq x$. Therefore, $y < x$. Now we also have that $y = z \in A$ and so $y \in P(A, x)$. But this contradicts $y$ as we defined it earlier as the least element of $B \setminus P(A, x)$.

And so we can conclude that $P(A, x) = B$, meaning $B$ is an initial segment of $A$, as required.

Any union of conforming sets is conforming

The main idea comes from this answer. Suppose $A_i$ are conforming sets, for $i$ in some arbitrary index set $I$. Then $U = \bigcup_{i \in I} A_i$ is conforming. To show that $U$ is conforming, we need to show:

1. $\leq$ is a total order on $U$.
2. Every non-empty subset $A \subseteq U$ has a least element under $\leq$ (making it a well-order).
3. For every element $x \in U$, we have $x = f(P(U, x))$.

Total Order: Choose $x, y \in U$. Then there exist conforming sets $A, B$ with $x \in A$ and $y \in B$. WLOG, by our above result, $A$ is an initial segment of $B$. And so $A \subseteq B$. Therefore $x \in B$. And since $B$ is conforming, it is totally ordered. Meaning $x \leq y$ or $y \leq x$, as required.

Least Element: Consider a non-empty subset $A \subseteq U$. Since $A$ is non-empty, there must be some conforming set $B$ such that $C = A \cap B \subseteq B$ is non empty. And so, since $B$ is conforming, every non-empty subset has a least element, and so let $x$ be the least element of $C$. Now, we can show that $x$ is actually the least element of $A$. We need to show that for all $y \in A$:

$x \leq y$

Well, consider $y \in A$. We know that $A = C \cup A \setminus B$. So then $y \in C$ or else $y \in A \setminus B$. If $y \in C$ then by the definition of $x$ as the least element, we have $x \leq y$ as desired.

So we need only now consider $y \in A \setminus B$. Well, since $y \in U$, then there is some conforming set $D$ such that $y \in D$. By the comparability of conforming sets, we have that either $D$ is an initial segment of $B$ or vice versa. But since initial segments are subsets, and since $y \notin B$, then $B$ must be an initial segment of $D$. And so there is some $z \in D$ such that $B = P(D, z)$.

Now, since $y \in D$, and $D$ is totally ordered, either $y < z$ or else $z \leq y$. If $y < z$ then $y \in P(D, z) = B$, but this contradicts $y \notin B$. Therefore $z \leq y$, then notice that $x \in C \subseteq B = P(D, z)$ and so $x < z$ and so $x < y$, as desired.

Choice Function: The final thing to show to ensure $U$ is conforming is that every element is expressible as the choice function applied to the initial segment for that element. That is, given $x \in U$ we want to show that:

$x = f(P(U, x))$

Well, if $x \in U$ then there is some conforming set $A$ such that $x \in A$. Now let's show that:

$P(A, x) = P(U, x)$

Since $A \subseteq U$, it follows that $P(A, x) \subseteq P(U, x)$. Therefore it remains to show that $P(U, x) \subseteq P(A, x)$. Consider $u \in P(U, x)$. We want to show that $u \in P(A, x)$. Since $u \in P(U, x) \implies u < x$, it remains to show that $u \in A$.

Since $u \in P(U, x)$ then $u \in U$ and so $u \in B$ for some conforming set $B$. By the comparability of conforming sets, we have either that $B$ is an initial segment of $A$ or vice versa. If $B$ is an initial segment of $A$ we have $u \in B \subseteq A$ and we are done. So consider that $A$ is an initial segment of $B$. Then there is some $w \in B$ such that $A = P(B, w)$. Since $x \in A = P(B, w)$ then $x < w$. And we already have that $u < x$. Therefore $u < w$ and so $u \in P(B, w) = A$, as desired.

Finishing the Proof

Since any union of conforming sets is conforming, then we can take the union of all conforming sets, and call this $U$. Since it's conforming, it is totally ordered i.e. it is a chain. Since it's a chain, it is in the domain of the function $f$ and we can apply $f$ to it to get an element $f(U)$ such that:

$\forall x \in U : x < f(U)$

Now we define $V = U \cup \{f(U)\}$. We can show that $V$ is conforming:

1. It's totally ordered because $x \neq y \in V$ are either $x \neq y \in U$, and then we have the total order following from $U$, or else WLOG $y = f(U)$ and then by definition of $f(U)$ we have $x < y$.
2. Every non-empty subset of $V$ has a least element. Well, consider $A \subseteq V$. We can rewrite $A$ as $A = A \cap U \cup A \setminus U = A \cap U \cup \{f(U)\}$. If $A \cap U$ is empty, then $A = \{f(U)\}$ and so the least element is just $f(U)$. Else since $U$ is well-ordered, we can take the least element of $A \cap U \subseteq U$; this is less than $f(U)$ by definition of $f(U)$ and so it is a least element of $A$.
3. Every element $v \in V$ can be written as $v = f(P(V, v))$. Well, we notice for this that if $v \in U$ then $P(V, v) = P(U, v)$. And since $U$ is conforming then $v = f(P(U, v)) = f(P(V, v))$ as required. The only other element to consider is $f(U)$. But we notice that $U = P(V, f(U))$. And so $f(U) = f(P(V, f(U)))$, as required.

Since $V$ is conforming, and $U$ is the union of all conforming sets, we have $V \subseteq U$ and so we have $f(U) \in U$. But this contradicts $f(U)$ as being greater than all elements in $U$. Which completes the proof.