# Zorn's Lemma $\implies$ Tukey's Lemma

Let $$\mathcal{F}\neq \varnothing$$ be of finite character and consider the strict partial order $$\subsetneq$$ in it. Let $$C\subseteq \mathcal{F}$$ be a chain and $$A:=\bigcup C$$.

If we prove that every finite subset of $$A$$ belongs to $$\mathcal{F}$$, then $$A\in \mathcal{F}$$. As every element of $$C$$ is a subset of $$A$$, then $$A$$ is an upper bound of $$C$$. Hence, by Zorn's Lemma, there exists a $$\subsetneq$$-maximal $$B\in C$$. QED

My doubt is: how do we prove that every finite subset of $$A$$ belongs to $$\mathcal{F}$$?

I've conjectured that "If $$C$$ is a non-empty set such that $$\forall X,Y\in C (X\subseteq Y \vee Y\subseteq X)$$, then $$\bigcup C\in C$$", but I couldn't prove that this is true.

I tried, then, to split the proof in the cases where $$A\in C$$ and the ones where $$A\not\in C$$.

If $$A\in C$$, then $$A\in \mathcal{F}$$, because $$C\subseteq \mathcal{F}$$.

If $$A\not \in C$$, then $$C$$ doesn't have a maximal element. But, by definitions, it just means that $$\forall X\in C \exists Y\in C (X\subsetneq Y)$$, so I didn't get anywhere.

Confusion in Proof of "Zorn's Lemma $\implies$ Tukey's Lemma"

"Either $$C$$ has a maximal element, in which it's $$A$$. Or it doesn't, in which case every finite subset is a subset of some element of the chain."

The part that I don't get is this one: "Or it doesn't, in which case every finite subset is a subset of some element of the chain". Why is this true?

In case you wanna know, I'm using Kenneth Kunnen's "The Foundations of Mathematics" book. For the proof of this theorem he only gives a hint, but it didn't help me a bit.

Let $$\{a_1,\ldots, a_n\}$$ be a finite subset of $$A:=\bigcup C$$ and let $$Z_1,\ldots, Z_n\in C$$ such that $$a_i\in Z_i.$$ Since $$C$$ is a chain, the $$Z_i$$ are totally ordered by $$\subseteq,$$ so, reindexing if necessary, we can assume $$Z_1\subseteq Z_2\subseteq\ldots \subseteq Z_n.$$ Thus, for all $$i\le n,$$ $$a_i\in Z_n,$$ i.e. $$\{a_1,\ldots, a_n\}\subseteq Z_n.$$ Since $$\mathcal F$$ is of finite character and $$Z_n\in \mathcal F$$, $$\{a_1,\ldots,a_n\}\in\mathcal F.$$
• @GleisonStanlley This is just saying that if we have a finite totally ordered set, we can always label the elements in order, i.e. a finite totally ordered set of size $n$ is order-isomorphic to $\{1,2,\ldots, n\}$. I'd say it's "obvious", but obvious facts about finite sets are notoriously tricky to prove rigorously. The answer is always "use induction". Here's a somewhat simpler route that gets you to the same place: Prove (by induction) that a finite totally ordered set has a maximum. Then, $\{a_1,\ldots, a_n\}$ is a subset of the maximum $Z_i.$ Feb 1, 2022 at 6:44
• @GleisonStanlley (If we're being super rigorous we need to take care with the initial statement too: Show (by induction on size) that if $A_0\subseteq \bigcup C$ is finite, then there is a function $f:A_0\to C$ such that $a\in f(a)$ for all $a\in A_0.$) Feb 1, 2022 at 6:57
• @Gleison $\{Z_1,\ldots, Z_n\}$ are totally ordered by $\subseteq$. The maximum in that ordering. I wouldn’t worry too much about the second part, it’s just a way to make the construction of the set $\{Z_1,\ldots,Z_n\}$ and the mapping $a_i\mapsto Z_i$ more formal. Feb 1, 2022 at 18:04