# Tukey's lemma by axiom of choice

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

-
Please state Tukey's Lemma for convenience. What have you tried? Did you look into Munkres' book, Topology, for instance. He does this in Chapter 1 perhaps through exercises. – user21436 Apr 23 '12 at 6:28
I'm an undergraduate student studying elementary set theory now, which means i dont know topology at all... – Katlus Apr 23 '12 at 6:35
@Kannappan, while its origin is topology, Tukey's lemma can be stated without referring to topology. It is a common exercise to prove its equivalence to the axiom of choice. – Asaf Karagila Apr 23 '12 at 7:36

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.

-
How can I show that union of the chain is an element of a set with finite character? – Katlus Apr 23 '12 at 7:40
@Katlus: You show that every finite subset of it is in $F$. Take a finite subset of a union of a chain. Then all of these elements have to be in one of the elements of the chain. Otherwise we would have elements as high as we wanted in the chain, and that would mean that the finite set contains infinite elements. Now since this finite set is in some element of $F$, by the finite character of $F$ you get that the finite set belongs in $F$. Using the finite character again, you have that the union is in $F$. – Apostolos Apr 23 '12 at 7:59

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}$.

-