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
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
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.
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
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
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$.
Therefore \{ x_\xi : \xi < \beta \} is a $\subseteq$-maximal element of $\mathcal{X}$.