2
$\begingroup$

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

  • 0
    @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.2012-04-23

2 Answers 2

2

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.

  • 0
    @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$.2012-04-23
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}$.