The following question is exercise 7.4 from Ernest Schimmerling's A Course on Set Theory which involves a construction from Tarski's theorem that extends filters to ultrafilters. I couldn't find much at all on the web for this so I thought this could be a good question. Here is the background of the construction: let $\mathcal F$ be the Frechet filter over $\omega$ and take $\left< \mathcal G_\alpha \colon \alpha < 2^{\aleph_0}\right>$ to be a sequence of filters extending $\mathcal F$ constructed as follows: enumerate $\mathcal P(\omega)$ as $\left<A_\alpha \colon \alpha < 2^{\aleph_0}\right>$. Set $\mathcal G_0 =\mathcal F$. At each successor stage $\beta = \alpha+1$ it must be the case that
$$ \forall B \in \mathcal G_\alpha (B \cap A_\alpha \neq \varnothing) \oplus \forall B \in \mathcal G_\alpha(B \cap X\setminus A_\alpha \neq \varnothing)$$
In the first case set $$\mathcal G_{\alpha+1} = \{C \in \mathcal P(\omega)\colon \exists B \in \mathcal G_\alpha (B \cap A_\alpha \subseteq C)\}$$ Do the analogous operation for case two. Then this ensures that $\mathcal G_{\alpha+1}$ is a filter and either contains $A_\alpha$ or its complement. In the limit stage(s) set $$\mathcal G_\beta = \bigcup_{\alpha < \beta} \mathcal G_\alpha$$ The exercise is: prove by induction on $\alpha < 2^{\aleph_0}$ that $|\mathcal G_\alpha| < 2^{\aleph_0}$ and $G_\alpha$ is not an ultrafilter over $\omega$. I get the base case very easily since the Frechet filter is countable and contains neither the even nor odd naturals. Howevever I'm stuck on the successor step as I can't seem to make any connections why $|\mathcal G_{\alpha+1}| < 2^{\aleph_0}$. Also, while $G_\alpha$ may not contain $B$ nor $X\setminus B$ for some subset $B$ it's still possible that $\mathcal G_{\alpha+1}$ could contain either set at the next stage, so I also don't see how to show that it's not an ultrafilter. Now, at the limit stage it makes sense why the filter is not of cardinality the continuum, since you're unioning fewer than continuum-many sets of which all have size less than the continuum. And there is also a set and its complement who are not contained in any previous sets. So, it seems there is something really minor that I'm missing on the inductive step. Thanks!
Prove by induction on $\alpha < 2^{\aleph_0}$ that $|\mathcal G_\alpha| < 2^{\aleph_0}$ and $\mathcal G_\alpha$ is not an ultrafilter over $\omega$
filtersset-theorytransfinite-induction
Best Answer
(The following answer is mostly repeated from my comments above, but I have added the observation that the least $\alpha$ such that $\mathcal{G}_\alpha$ is an ultrafilter can (consistently) be a successor ordinal. I'm working in ZFC.)
There seems to be a problem with the exercise...
First, there is an easy observation to see that the $\mathcal{G}_\alpha$'s, for $\alpha<2^{\aleph_0}$, are not all of cardinality $<2^{\aleph_0}$. Recall $\mathcal{G}_0$ is the Frechet filter, so $\mathcal{G}_0$ is countable. Let $\beta$ be least such that $A_\beta$ is infinite, coinfinite (i.e. infinite and $\omega\backslash A_\beta$ is infinite). Note then that $\mathcal{G}_\beta=\mathcal{G}_0$, and $A_\beta\in\mathcal{G}_{\beta+1}$. Note that for every $X\subseteq\omega\backslash A_\beta$, we have $A_\beta\subseteq A_\beta\cup X\in\mathcal{G}_{\beta+1}$. But there are $2^{\aleph_0}$-many such sets $X$, hence $2^{\aleph_0}$-many such $A_\beta\cup X$, so $\mathcal{G}_{\beta+1}$ has cardinality $2^{\aleph_0}$.
So the exercise is incorrect. What if we weaken the exercise, and just demand that $\mathcal{G}_\alpha$ fail to be an ultrafilter for $\alpha<2^{\aleph_0}$? Then, consistently, it is still incorrect...
A base for an ultrafilter $U$ on $\omega$ is a set $B\subseteq U$ such that for every $X\in U$ there is $Y\in B$ with $Y\subseteq X$. Let $\mathfrak{u}$ be the least cardinal $\kappa$ such that for some nonprincipal ultrafilter $U$ on $\omega$, there is a base $B$ of $U$ of size $\kappa$. (This is well-defined, since there are non-principal ultrafilters on $\omega$.) Trivially then $\mathfrak{u}\leq 2^{\aleph_0}$. A direct combinatorial argument shows $\aleph_1\leq\mathfrak{u}$. So assuming CH, we have $\mathfrak{u}=2^{\aleph_0}=\aleph_1$, and the statement you wanted to prove can be proved using this extra assumption.
But Kunen constructed a model satisfying $2^{\aleph_0}=\aleph_{\omega_1}$ and $\mathfrak{u}=\aleph_1$; see Kunen "Set theory: An introduction to independence proofs" Chapter 8, Exercise A10. In that exercise, one constructs a model with an ultrafilter on $\omega$ with a base of size strictly smaller than the continuum. Also, Baumgartner and Laver showed that, assuming ZFC is consistent, so is ZFC + $2^{\aleph_0}=\aleph_2$ + $\mathfrak{u}=\aleph_1$. (See their paper "Iterated perfect set forcing".) (These points are mentioned in section 9 of Blass's chapter in the Handbook of set theory, "Combinatorial cardinal characteristics of the continuum", p. 448. That section also contains much more related information.)
So it could be that $\mathfrak{u}<2^{\aleph_0}$. Assume this, and let $U$ be a non-principal ultrafilter with a base $B$ of cardinality $\mathfrak{u}$. Let $\left<A_\alpha\right>_{\alpha<\mathfrak{u}}$ enumerate $B$. Let $\left<A_\alpha\right>_{\mathfrak{u}\leq\alpha<2^{\aleph_0}}$ then be such that $\left<A_\alpha\right>_{\alpha<2^{\aleph_0}}$ enumerates $\mathcal{P}(\omega)$. Define the sequence of filters $\mathcal{G}_\alpha$ as you do in the question. Note that since $U$ is a filter, we get by induction that $\mathcal{G}_\alpha\subseteq U$ and $A_\alpha\in\mathcal{G}_{\alpha+1}$, for each $\alpha<\mathfrak{u}$. But then $B\subseteq\mathcal{G}_{\mathfrak{u}}$, and since $B$ is a base for $U$, therefore $\mathcal{G}_{\mathfrak{u}}=U$, which is an ultrafilter. But $\mathfrak{u}<2^{\aleph_0}$, contradicting the weaker version of the exercise.
Note that in the construction above, the $\mathcal{G}_\alpha$ are not ultrafilters for $\alpha<\mathfrak{u}$, just by definition of $\mathfrak{u}$. So $\mathfrak{u}$ is the least $\alpha$ such that $\mathcal{G}_\alpha$ is an ultrafilter there.
Finally, let me just observe that, again assuming that $\mathfrak{u}<2^{\aleph_0}$, it can also be that $\mathcal{G}_\alpha$ is first an ultrafilter at some successor $\alpha$. For this, let $A\subseteq\omega$ be infinite, coinfinite, let $U_1$ be a nonprincipal ultrafilter on $A$, having a base of cardinality $\mathfrak{u}$, and let $U_2$ be a nonprincipal ultrafilter on $\omega\backslash A$, also with such a base. (Note that if $U$ is any nonprincipal ultrafilter on $\omega$ with a base of cardinality $\mathfrak{u}$, then we can easily produce such ultrafilters on $A$ or on $\omega\backslash A$, by shifting then according to a bijection $\pi:\omega\to A$ or $\pi:\omega\to\omega\backslash A$.)
Let $F$ be the filter on $\omega$ of sets of the form $C\cup D$ where $C\in U_1$ and $D\in U_2$ (note it is a filter). Then $F$ is not an ultrafilter on $\omega$, since $A\notin F$ and $\omega\backslash A\notin F$. But note that $U_1$ is a base for a unique ultrafilter on $\omega$ (as is $U_2$). Let $B_1=\{A_{1\alpha}\}_{\alpha<\mathfrak{u}}$ be a base for $U_1$ and $B_2=\{A_{2\alpha}\}_{\alpha<\mathfrak{u}}$ be a base for $U_2$. Let $A_\alpha=A_{1\alpha}\cup A_{2\alpha}$. Let $A_{\mathfrak{u}}=A$. Then let $\left<A_\alpha\right>_{\mathfrak{u}<\alpha<2^{\aleph_0}}$ enumerate the rest of $\mathcal{P}(\omega)$. Suppose we use this sequence and define the $\mathcal{G}_\alpha$'s. Then it is straightforward to see that $\mathcal{G}_{\mathfrak{u}}=F$, which is not an ultrafilter, but since $A_\mathfrak{u}=A$, that $\mathcal{G}_{\mathfrak{u}+1}$ is the ultrafilter with base $U_1$. So $\mathfrak{u}+1$ is the least stage where we get an ultrafilter in this case.