Blackburn's Modal Logic, Ex $2.5.4$: Let $W$ be an infinite set. Recall that $X\subseteq W$ is co-finite iff $W\setminus X$ is finite.
(a) Prove that the collection of co-finite subsets of $W$ has the finite intersection property.
(b) Show that there are ultrafilters over $W$ that do not contain any finite set.
(c) Prove that an ultrafilter is non-principal if and only if it contains only infinite sets
if and only if it contains all co-finite sets.
(d) Prove that any ultrafilter over $W$ has uncountably many elements.
(a) is already answered here. To prove (b), we can prove (c) and argue that non-principal ultrafilters exist. So I shall try $\color{red}{(c)}$ first. I want to show $$\text{non-principal} \stackrel{1}{\Longleftrightarrow} \text{contains only infinite sets} \stackrel{2}{\Longleftrightarrow} \text{contains all co-finite sets}$$
What is a principal ultrafilter? The principal ultrafilter generated by $w$, is $\{X
\in P(W): w\in X\}$.
The second double-implication is easier to prove, so let's do that first. Keep an ultrafilter $u \subset P(W)$ in mind for the entire proof. Suppose $u$ contains only infinite sets, and there is some co-finite set $A$ not contained in $u$. Since $u$ is an ultrafilter, $W\setminus A \in u$, but $W\setminus A$ is finite, which is a contradiction. Suppose $u$ contains all co-finite sets. If possible, let $u$ contain some finite set $B$. Then, $W\setminus B \notin u$. However, $B$ is finite $\implies W\setminus B$ is co-finite. This is a contradiction. So, the second double implication, i.e. $\stackrel{2}{\Longleftrightarrow}$ is proved.
Now, let us turn to $\stackrel{1}{\Longleftrightarrow}$. Suppose $u$ contains only infinite sets. If possible, let $u$ be principal. Then there exists some $w\in W$ such that $u = \{X
\in P(W): w\in X\}$. $w\in \{w\}$, obviously. So, $\{w\} \in u$, but $\{w\}$ is a finite set. This is a contradiction. Thus, $u$ is non-principal. For the other direction, suppose $u$ is non-principal. Suppose, for a contradiction, that $u$ contains some finite set $C$. So, $W\setminus C$ is infinite. Also, let $C = \{c_1,c_2,\ldots,c_n\}$. Stuck here! I want to show that $C\in u$ makes $u$ a principal filter, somehow, in order to find a contradiction. For that, I must find a $w\in W$ so that $\{w\} \in u$. Correct? Please help me out here.
Update for part $\color{red}{(c)}$: If $u$ is an ultrafilter, we know that $X\cup Y \in u$ if and only if $X\in u$ or $Y\in u$. $C\in u$ means that $\{c_1,c_2,\ldots,c_{n-1}\} \cup \{c_{n}\} \in u$. So, either $\{c_1,c_2,\ldots,c_{n-1}\} \in u$ or $\{c_n\}\in u$. If $\{c_n\} \in u$, we are done. If not, we can recursively apply the same argument to $\{c_1,\ldots,c_{n-1}\}$. At every step, we drop an element of this finite set, and so the process terminates. We will be able to find a singleton $\{c_i\}$ so that $\{c_i\}\in u$. This makes $u$ a principal filter (right?), which is the required contradiction.
Once (c) is proved, I must explicitly show that non-principal ultrafilters exist, in order to prove $\color{red}{(b)}$. Any ideas for this? Perhaps the author wanted something else, since they've put (b) before (c) – but I hope this way works too. Please drop some hints or ideas on how to proceed and conclude (b) from here!
Now, for part $\color{red}{(d)}$: Suppose $u\subset P(W)$ has at most countable number of elements. Then, $u$ is either finite or $u = \{X_1,X_2,…\}$. How do I find a contradiction from here? Looks like I'm stuck again!
Thanks a lot for your help. Let me know if any of your solution ideas are different from mine, I'd be happy to see different approaches. Also, please help me complete my solutions, if possible!
Best Answer
For (b): Do you know that any family of sets with FIP extends to an ultrafilter? If so, (b) follows immediately from (a). If not, prove this using Zorn's Lemma.
For (c): Show that if $X$ and $Y$ are not in the ultrafilter $U$, then $X\cup Y$ is not in $U$. Thus if $U$ is non-principal, it cannot contain any finite union of singletons (any finite set).
For (d): Hint. A union of two countable sets is countable. The powerset of an infinite set is uncountable.