# $\mathsf{AC}^+\implies$ Tukey's Lemma

I'm using Kenneth Kunen's book: The Foundations of Mathematics. I have a doubt about a fact stated in the proof.

Let $$A$$ be a set, $$\mathcal{F}\subseteq \mathcal{P}(A)$$ of finite character and $$X\in \mathcal{F}$$. As every set is well orderable, $$A$$ is well orderable. Let $$\kappa:=|A|$$ and $$f:\kappa \to A$$ a bijection. Let $$a_\alpha:=f(\alpha)$$, for every $$\alpha<\kappa$$. Therefore, $$A=\{a_\alpha;\alpha<\kappa\}$$. Recursively, we define $$Y_\beta\subseteq \{a_\xi;\xi<\beta\}$$, for every $$\beta\leq \kappa$$, by:

• $$Y_0:=X$$.
• $$Y_{\alpha+1}:= \begin{cases} Y_\alpha\cup\{a_\alpha\}, & \textrm{ if } Y_\alpha\cup\{\alpha\}\in \mathcal{F}\\ Y_\alpha, & \textrm{ if } Y_\alpha\cup\{\alpha\}\not\in \mathcal{F} \end{cases}$$.
• $$Y_\gamma:=\bigcup \{Y_\alpha;\alpha<\gamma\}$$, if $$\gamma$$ is a limit ordinal.

If we prove that $$Y_\beta\in \mathcal{F}$$, for every $$\beta\leq \kappa$$, then $$Y:=Y_\kappa\in \mathcal{F}$$. Let $$Z$$ be a set such that $$Y\subsetneq Z\subseteq A$$. Hence, $$Z\setminus Y\neq \varnothing$$. Let $$\alpha\leq \kappa$$ be an ordinal such that $$a_\alpha\in Z\setminus Y$$. If $$Y_\alpha\cup \{a_\alpha\}\in \mathcal{F}$$, then $$a_\alpha\in Y_{\alpha+1}\subseteq Y$$. Hence, $$Y_\alpha \cup \{a_\alpha\}\not\in \mathcal{F}$$ and then $$Z\not\in \mathcal{F}$$ (since $$Y_\alpha\cup \{a_\alpha\}\subseteq Z$$). QED

If we use Transfinite Induction to prove that $$Y_\beta\in \mathcal{F}$$, for every $$\beta\leq \kappa$$, we suppose it's false and, therefore, there is a least ordinal $$\delta$$ such that $$Y_\delta\not\in \mathcal{F}$$. It was quite easy to prove for the cases where $$\delta$$ isn't a limit ordinal. For the case where it is, the book says we could use the fact that $$\mathcal{F}$$ is of finite character, but I still don't realize any contradictions here. How can we prove that every finite subset of $$Y_\delta$$ is in $$\mathcal{F}$$, when $$\delta$$ is a limit ordinal?

• If $\delta$ is a limit ordinal, then every finite subset of $Y_\delta$ is also a subset of $Y_\alpha$ for some $\alpha<\delta$ (and is therefore in $\mathcal F$). Jan 30, 2022 at 19:16
• @AndreasBlass How do you prove that "every finite subset of $Y_\delta$ is also a subset of $Y_\alpha$ for some $\alpha<\delta$"? Jan 30, 2022 at 19:21
• Since the claim is obvious for the empty set, let $s$ be a nonempty finite subset of $Y_\delta=\bigcup_{\alpha<\delta}A_\alpha$. So we have, for each $a\in s$, some $\alpha_a<\delta$ such that $a\in A_{\alpha_a}$. The nonempty finite set of ordinals $\{\alpha_a:a\in s\}$ has a largest element, and that element serves as the required $\alpha$. Jan 30, 2022 at 20:25
• @AndreasBlass Let $H\subseteq Y_\delta$ be finite and non-empty. Therefore, $\forall x\in H \exists \beta<\delta (x\in Y_\beta)$. Let $\alpha(x):=\min(\{\beta<\delta;x\in Y_\beta\})$, for each $x\in H$. Since $H\neq \varnothing$ is finite, then $\{\alpha(x); x\in H\}$ is a non-empty and a finite set of ordinals. Hence, it has a largest element. Call it $\mu$. You are saying that $H\subseteq Y_\mu\in \mathcal{F}$ and, because $\mathcal{F}$ is of finite character, then $H\in \mathcal{F}$. Hence, $Y_\delta\in \mathcal{F}$, which is a contradiction. But, how do you prove that $H\subseteq Y_\mu$? Feb 1, 2022 at 0:08
• Each element $x$ of $H$ is in $Y_{\alpha(x)}$, which is a subset of $Y_\mu$ because $\alpha(x)\leq\mu$. (I'm assuming you know that the sequence of $Y$'s is monotone, i.e., $\xi\leq\eta\implies Y_\xi\subseteq Y_\eta$. If you don't know that, prove it by induction on $\eta$.) Feb 1, 2022 at 1:20

If $$\delta$$ is the minimal such that $$Y_\delta\notin\mathcal F$$, and $$\delta$$ is limit, let $$B=\{a_0,\ldots,a_{n-1}\}\subseteq Y_\delta$$ finite.
Each $$a_i$$ is in minimal $$Y_{\alpha_i}$$, and so $$B\subseteq \bigcup Y_{\alpha_i}=Y_{\max_{0\le i, so $$Y_{\max_{0\le i(from minimality of $$\delta$$), so $$B\in \cal F$$(from finite character), hence $$Y_\delta\in \cal F$$ (again from finite character), contradiction.
• Let $H\subseteq Y_\delta$ be finite and non-empty. Therefore, $\forall x\in H \exists \beta<\delta (x\in Y_\beta)$. Let $\alpha(x):=\min(\{\beta<\delta;x\in Y_\beta\})$, for each $x\in H$. Since $H\neq \varnothing$ is finite, then $\{\alpha(x); x\in H\}$ is a non-empty and a finite set of ordinals. Hence, it has a largest element. Call it $\mu$. You are saying that $H\subseteq \bigcup\{Y_{\alpha(x);x\in H}\}=Y_\mu\in \mathcal{F}$ and, because $\mathcal{F}$ is of finite character, then $H\in \mathcal{F}$. Hence, $Y_\delta\in \mathcal{F}$, which is a contradiction. Feb 1, 2022 at 0:12
• But, how do you prove that $\bigcup \{Y_{\alpha(x)};x\in H\}=Y_\mu$? Feb 1, 2022 at 0:13
• @GleisonStanlley By definition, if $α<β$ we have $Y_α⊆Y_β$, so if $(α_i\mid i<Γ≤κ)$ is any sequence of elements $α_i<κ$ we have that $\bigcup Y_{α_i}=Y_{\sup(α_i)}$, if we know that $α_i<δ$ for all $i$, and that $Γ$ is finite, we have that $\sup(α_i)=\max(α_i)<δ$