Tukey's lemma by axiom of choice

Question

How can i prove Tukey's lemma directly from axiom of choice?

Tukey' lemma : every nonempty collection of finite character has a maximal element with respect to inclusion. Help

Answer 1

This is my attempt for a direct proof from the axiom of choice:

Take a collection with finite character ($F$) and let $a_0$ be an element of it (there exists some such $a$ since $F$ is non-empty). Take a choice function $f:\mathcal{P}(F)\setminus\{\varnothing\}\to F$. Define a sequence with transfinite induction in the following way: If $a_\delta$ is defined then let $f(\{b\in F : a_\delta\subsetneq b\})$. For limit steps just take the union $\bigcup_{\delta<\gamma}a_\delta$. Observe that this is an element of $F$ because every finite subset of it is a finite subset of some $a_\delta$. This construction will come to a halt at some point since $F$ is a set. That point won't be a limit step, because of the construction, we can always define our element after limit many steps. Therefore it will halt at some successor step. Taking the last element created, we have a maximal element of $F$.

Notice that assuming Zorn's Lemma yields a much more direct proof. Every chain of a set with finite character has an upper bound, the union of the chain. Hence, by applying Zorn's Lemma you directly get that $F$ has a maximal element.

Answer 2

Suppose that $\mathcal{X}$ is a family of subsets of a set $X$ of finite character, and let $* \notin X$. Using the Axiom of Choice there is a function $f : \mathcal{P} ( X \cup \{ * \} ) \to X \cup \{ * \}$ such that

1. $f(A) = *$ if either $* \in A$, or $A \subseteq X$ is not in $\mathcal{X}$, or if $A$ is a $\subseteq$-maximal element of $\mathcal{X}$;
2. $f(A) \in \{ x \in X \setminus A : A \cup \{ x \} \in \mathcal{X} \}$, otherwise.

Pick an ordinal $\alpha$ such that there is no one-to-one $\alpha$-sequence in $X \cup \{ * \}$ (i.e., there is no one-to-one function from $\alpha$ into $X \cup \{ * \}$). By Transfinite Recursion define an $\alpha$-sequence $\langle x_\xi \rangle_{\xi < \alpha}$ so that

1. $x_0 \in X$ is arbitrary such that $\{ x_0 \} \in \mathcal{X}$; and
2. $x_\xi = f ( \{ x_\eta : \eta < \xi \} )$ for $\xi > 0$.

Since this sequence cannot be one-to-one, there must be a minimal $\beta < \alpha$ such that there is a $\beta < \delta < \alpha$ such that $x_\beta = x_\delta$.

• Note that given $\xi < \alpha$, if $x_\xi \in X$, then by definition of $f$ it follows that $x_\zeta \neq x_\xi$ for all $\zeta \neq \xi$. Therefore $x_\beta = *$. It also follows that $x_\xi \neq *$ for all $\xi < \beta$.
• As $\{ x_\xi : \xi < \beta \} \subseteq X$, it follows that either $\{ x_\xi : \xi < \beta \} \notin \mathcal{X}$, or it is a $\subseteq$-maximal element of $\mathcal{X}$.
• Since $x_\xi = f ( \{ x_\eta : \eta < \xi \} ) \in X$ for all $\xi < \beta$, it follows that $\{ x_\eta : \eta < \xi \}$ is a non-$\subseteq$-maximal element of $\mathcal{X}$ for all $\xi < \beta$. If $\{ x_\xi : \xi < \beta \} \notin \mathcal{X}$, then there must be $\xi_1 < \cdots < \xi_n < \beta$ such that $\{ x_{\xi_1} , \ldots , x_{\xi_n} \} \notin \mathcal{F}$. Since $\{ x_\eta : \eta < \xi_n \}$ is a non-$\subseteq$-maximal element of $\mathcal{X}$, this then contradicts the definition of $x_{\xi_n}$.

Therefore $\{ x_\xi : \xi < \beta \}$ is a $\subseteq$-maximal element of $\mathcal{X}$.