## Exercises in Set Theory: Ultrafilters and Boolean algebras

By fredw on Tuesday, November 27 2012, 14:10 - Permalink

Since my previous blog post, I have been working on exercises from chapter 7 of Thomas Jech’s book "Set Theory". I’ve published my solutions but I’m not yet done with exercises 7.22 and 7.28 which seem to be generalizations of theorems 4.3 and 3.2. I guess that before coming back to these two exercises, I’ll consider the content and exercises of subsequent chapters…

I had the opportunity to read chapter 7 again and to study more precisely the correctness of some claims (you know, those that are "clearly seen to be obvious via an easy proof based on a straightforward argument that makes them trivial" but actually take time before really being understood) I describe below the two statements for which the ratio between the time I spent on them and the length of the proof provided was the largest. I indicate the arguments I used to convince myself. I also had trouble to understand the proof of theorem 7.15 but most of the required arguments can actually be found in the exercises.

The first part of the chapter essentially deals with ultrafilters on an infinite set (a topic that should be familiar to Peter Krautzberger, MathJax’s manager). In particular, a nonprincipal ultrafilter $U$ on $\omega$ is a Ramsey ultrafilter if for every partition $\{ A_{n}|n<\omega\}$ of $\omega$ into $\aleph _{0}$ pieces such that $\forall n,A_{n}\notin U$, there exists $X\in U$ such that $\forall n,\left|X\cap A_{n}\right|=1$. We have:

###### Theorem 1.

The continuum hypothesis implies the existence of a Ramsey ultrafilter.

###### Proof.

The proof given in the book is to consider an enumeration $\mathcal{A}_{\alpha},\alpha<\omega _{1}$ of all partitions of $\omega$ and to construct by induction a sequence ${(X_{\alpha})}_{{\alpha<\omega _{1}}}$ of infinite subsets. $X_{{\alpha+1}}\subseteq X_{\alpha}$ is chosen to be included in some element of $\mathcal{A}_{\alpha}$ or to intersect each of them at, at most, one element. For $\alpha$ limit, $X_{\alpha}$ is chosen such that $X_{\alpha}\setminus X_{\beta}$ is finite for all $\beta<\alpha$. Such a $X_{\alpha}$ is claimed to exist because $\alpha<\omega _{1}$ is countable. Finally, $D=\{ X:X\supseteq X_{\alpha}\text{ for some }\alpha<\omega _{1}\}$ is claimed to be a Ramsey ultrafilter.

∎

There were several points that were not obvious to me. First, it’s good to count the number of partitions of $\omega$. On the one hand, given any $A_{0}\subseteq\omega$ which is neither empty nor cofinite we can define a partition of $\omega$ by $\forall n<\omega,A_{{n+1}}=\left\{\min{\left({\omega\setminus{\cup _{{m\leq n}}A_{m}}}\right)}\right\}$ and so there are at least $2^{{\aleph _{0}}}$ such partitions (cofinite subsets are in bijection with finite subsets and $|\omega^{{<\omega}}|=\aleph _{0}$). On the other hand, a partition is determined by the family of subsets $\{ A_{n}|n<\omega\}$ and so there are at most ${\left(2^{{\aleph _{0}}}\right)}^{{\aleph _{0}}}=2^{{\aleph _{0}}}$ such partitions. Since we assume the continuum hypothesis $2^{{\aleph _{0}}}=\aleph _{1}$ we get the enumeration $\mathcal{A}_{\alpha},\alpha<\omega _{1}$.

Next, I’m not even sure that as it is defined $D$ is a filter. Because $X_{\alpha}$ is infinite $\emptyset\notin D$ and $Y\supseteq X\supseteq X_{\alpha}\implies Y\in D$ but if $X\supseteq X_{\alpha}$ and $Y\supseteq X_{\beta}$, it does not seem really clear which $X_{\gamma}\subseteq X\cap Y$. However, if $U$ is a nonprincipal ultrafilter a remark from chapter 10 suggests that $U$ does not contain any finite set. By exercise 7.3, this is equivalent to the fact that $U$ does not contain any singleton $\{\alpha\}$. This latter point is easy to verify: if we assume the contrary, because $U$ is nonprincipal, there exists $X\in U$ such that $X\nsupseteq\{\alpha\}$ and so $\kappa\setminus X\supseteq\{\alpha\}$ would be in $U$. Hence any ultrafilter containing $D$ should also contain $E=\{ X:\exists\alpha<\omega _{1},\exists x\in\kappa^{{<\omega}},X\supseteq X_{\alpha}\setminus x\}$. $E$ is a filter: the arguments above still hold and $X\supseteq X_{\alpha}\setminus x\wedge Y\supseteq X_{\beta}\setminus y\implies X\cap Y\supseteq X_{\alpha}\cap X_{\beta}-(x\cup y)\supseteq X_{\alpha}\setminus(X_{\alpha}\setminus X_{\beta}\cup x\cup y)$ and so we only need to verify that $X_{\alpha}\setminus X_{\beta}$ is finite if $\beta<\alpha$. This is already what is claimed for $\alpha$ a limit ordinal. In general if $\gamma$ is the greatest limit ordinal such that $\gamma\leq\alpha$ then by construction, $X_{\gamma}\supseteq X_{{\gamma+1}}\supseteq...\supseteq X_{{\alpha}}$ and so $X_{\alpha}\setminus X_{\beta}$ is empty if $\gamma\leq\beta\leq\alpha$ and $X_{\alpha}\setminus X_{\beta}\subseteq X_{\gamma}\setminus X_{\beta}$ is finite if $\beta<\gamma$. So we can replace $D$ by a "ultrafilter extending $E$". It’s not too difficult to check that a ultrafilter containing $D$ must be Ramsey. For any partition $\mathcal{A}_{\alpha}$ then by construction either $X_{{\alpha+1}}\subseteq A_{n}$ for some $n<\omega$ and so $A_{n}\in D$ or $\forall n<\omega,|X_{{\alpha+1}}\cap A_{n}|\leq 1$. In the latter case we can find $X\supseteq X_{{\alpha+1}}$ (so $X\in D$) such that $\forall n,|X\cap A_{n}|=1$ (we pick one element from each $A_{n}$ such that $X_{{\alpha+1}}\cap A_{n}=\emptyset$ and put these elements into $X$).

Finally, the most difficult part was to understand how the sequence ${(X_{\alpha})}_{{\alpha<\omega _{1}}}$ can be built. We can choose $X_{0}$ arbitrarily as this set is not involved in the arguments above. For any $\alpha<\omega _{1}$, if there exists some $A\in\mathcal{A}_{\alpha}$ such that $X_{\alpha}\cap A$ is infinite, we just set $X_{{\alpha+1}}=X_{\alpha}\cap A$. Otherwise, since $X_{\alpha}=\cup _{{A\in\mathcal{A}_{\alpha}}}(X_{\alpha}\cap A)$ is infinite, $X_{\alpha}\cap A$ is nonempty for infinitely many $A\in\mathcal{A}_{\alpha}$. Pick one element from each nonempty set to form the set $X_{{\alpha+1}}$. By definition, $\forall A\in\mathcal{A}_{\alpha},\left|X_{{\alpha+1}}\cap A\right|\leq 1$. Now we consider the case $\alpha<\omega _{1}$ limit. Let $\beta _{1}<\beta _{2}<...\beta _{n}<...$ be a cofinal $\omega$-sequence in $\alpha$. Note that it is the only place where we use the continuum hypothesis! For each $n<\omega$, we define $Y_{n}=\bigcap _{{i<n}}X_{{\beta _{i}}}$. We have $X_{{\beta _{n}}}$ infinite and $X_{{\beta _{n}}}\setminus X_{{\beta _{{n-1}}}}$ finite so $X_{{\beta _{n}}}\cap X_{{\beta _{{n-1}}}}$ is infinite. Similarly, $X_{{\beta _{n}}}\setminus X_{{\beta _{{n-1}}}}$ and $X_{{\beta _{{n-1}}}}\setminus X_{{\beta _{{n-2}}}}$ are finite so $X_{{\beta _{n}}}\cap X_{{\beta _{{n-1}}}}\cap X_{{\beta _{{n-2}}}}$ is infinite etc and finally $Y_{n}$ is infinite. Thus we can use a classical technique from Cantor (I can’t find a reference) and construct the set $X_{{\alpha}}=\{ x_{n}|n<\omega\}$ by picking each $x_{n}\in Y_{n}\setminus\{ x_{0},x_{1},...,x_{{n-1}}\}$ so that $X_{{\alpha}}\setminus X_{{\beta _{n}}}\subseteq\{ x_{0},x_{1},...,x_{{n-1}}\}$ is finite. Moreover for each $\beta<\alpha$ consider some $\beta _{n}>\beta$: $|X_{\alpha}\setminus X_{\beta}|\leq{|X_{{\alpha}}\setminus X_{\beta}|}+{|X_{{\beta}}\setminus X_{{\beta _{n}}}|}$ is finite.

The second part of the chapter is about Boolean algebras. A Boolean algebra $C$ is a completion of a Boolean algebra $B$ if it is complete (every subset $X\subseteq C$ has a least upper bound $\sum X$) and if $B$ is a dense subalgebra of $C$ (for any $0<c\in C$ there exists $b\in B$ such that $0<b\leq c$). I got stuck on the apparently easy proof of the following lemma:

###### Lemma 1.

The completion of a Boolean algebra $B$ is unique up to isomorphism

###### Proof.

Let $C,D$ are two completions of $B$. It is indicated in the book that the density of $B$ in $C$ and $D$ is used to prove that $\pi(c)=\sum^{D}\{ u\in B|u\leq c\}$ defines an isomorphism between $C$ and $D$. The example of $c\neq 0\implies\pi(c)\neq 0$ is given: indeed if $0<c$ we can find an element $b\in B$ such that $0<b\leq c$ and so $0<b\leq\pi(c)$. ∎

Two or three pages before, it is mentioned that "if $\pi:C\rightarrow D$ is a one-to-one mapping such that $\forall u,v\in C,u\leq v\Leftrightarrow\pi(u)\leq\pi(v)$ then $\pi$ is an isomorphism". That seems to be the most natural method to prove the lemma above. However, this statement is false: consider the morphism of Boolean algebra $\pi:\{ 0,1\}\rightarrow\operatorname{\mathcal{P}}(\{ 0,1\})$ which is one-to-one but not surjective. Actually, the property $\forall u,v\in C,u\leq v\Leftrightarrow\pi(u)\leq\pi(v)$ implies the fact that $\pi$ is one-to-one, which becomes vacuous. So I suspect the author rather means "surjective" instead of "one-to-one". Indeed, in that case $\pi$ is a bijection that preserves the order $\leq$ in both directions and since all the operations of the Boolean algebra can be described in terms of this order, $\pi$ is an isomorphism.

So first, given $d\in D$, we want to find $c\in C$ such that $\pi(c)=d$. By symmetry, the natural candidate is $c=\sum^{C}\{ u\in B|u\leq d\}$. For all $u\leq d$, we have $u\leq c$ and so $d\leq\sum^{D}\{ u\in B|u\leq d\}\leq\sum^{D}\{ u\in B|u\leq c\}=\pi(c)$. If $d<\pi(c)$ then by density we can find $b\in B$ such that $0<b\leq\pi(c)-d$. Hence $b\leq\pi(c)$ and $b\leq-d$. The latter implies that for all $u\leq d$ we have $u\leq-b$ an so $\pi(c)\leq-b$. Combining this with the former, we would have $b\leq\pi(c)\cdot\pi(-c)=0$. Thus $\pi$ is surjective.

It remains to prove $\forall u,v\in C,u\leq v\Leftrightarrow\pi(u)\leq\pi(v)$. If $u\leq v$ then $\pi(u)=\sum^{D}\{ b\in B|b\leq u\}\leq\sum^{D}\{ b\in B|b\leq v\}\leq\pi(v)$. Let’s consider the contrapositive of the converse implication: suppose $u\nleq v$. Then $u\cdot-v\neq 0$ and $0<\pi(u\cdot-v)$ (we use the hint given in the book). If we are able to prove $\pi(u\cdot-v)\leq\pi(u)\cdot-\pi(v)$ then we would have $0<\pi(u)\cdot-\pi(v)$ and so $\pi(u)\nleq\pi(v)$ as desired. It suffices to show two inequalities on the $\cdot$ and $-$ operations. Note that $\forall b\in B,\pi(b)=b$. Let $w\in C$. Let $w_{1},w_{2}\in C$. Then for all $b\in B$, $b\leq w_{1}\cdot w_{2}\implies b\leq w_{1},w_{2}\implies b=\pi(b)\leq\pi(w_{1}),\pi(w_{1})\implies b\leq\pi(w_{1})\cdot\pi(w_{2})$ so $\pi(w_{1}\cdot w_{2})\leq\pi(w_{1})\cdot\pi(w_{2})$. Similarly, we have for all $b\in B$, $b\leq-w\implies-b\geq w\implies-b=\pi(-b)\geq\pi(w)\implies b\leq-\pi(w)$. So $\pi(-w)\leq-\pi(w)$.

As a conclusion, I notice a similarity between these too cases: both have a sketchy proof based on a statement that seems incorrect ("$D$ is a filter", "any one-to-one mapping between Boolean algebra that preserves the order $\leq$ in both directions is an isomorphism"). Sometimes, I’m wondering if these kinds of inaccuracy are not intentional in order to force readers to try and find the proof themselves :-)

## Comments

A few thoughts from the top of my head.

First off, the advice from the book to look at partitions is imho bad advice (who am I to question Jech ;) ). While partition-properties are often easier when using ultrafilter arguments, they are rarely good for constructions. So I would switch definitions and use the "every $f: \mathbb{N} \to \mathbb{N}$ is constant or one-to-one on a set in the ultrafilter". Then you're enumerating pairs, $(A, f)$, where the $A$'s range over the power set and the $f$ over $\omega^\omega$. At each step, add a set to $D$ that "decides" how the ultrafilter will deal with both $A$ (rejecting or including it) and $f$ (making it one-to-one or constant).

Secondly, when constructing (free, but really what else) ultrafilters it's always best to start with the Fréchet filter of co-finite sets. You're going to end up with that anyway, so you might as we start from there immediately. That simplifies that D is a filter, and your $X$'s guarantee it's "ultra".

When you write "this is the only time we use CH", you're of course right. But it might be fun to do this under MA + non CH. You actually get something that looks stronger, namely you get pseudo-intersections for $<\mathfrak{c}$-many elements of your ultrafilter -- though I don't remember if that's actually different for Ramsey ultrafilters, I know it's makes a difference for P-points.

Ramsey ultrafilters are defined in the book just after $p$-points so I guess the idea is really just to use definitions via partitions and ultrafilters so that it appears clearly that a Ramsey ultrafilter is a $p$-point. Alternative definitions using $f \in \omega^\omega$ or the Rudin-Keisler ordering are given in the exercises, though.

I first had to replace $D$ by my $E$ above, which essentially adds the cofinite sets, to make the proof work. Then reading chapter 10 again and articles from Wikipedia, I realized that indeed any nonprincipal ultrafilter contains the Fréchet filter. It's actually weird that that this is not mentioned at all in chapter 7 or perhaps it's too obvious :-) I suspect that starting from the Fréchet filter is so usual that Jech really meant to have these cofinite sets in $D$.

I'm not sure I have the background to understand what you mean in your last paragraph :-) But I see in chapter 16 a theorem from Booth that MA implies the existence of a $p$-point. The proof seems to use a similar enumeration technique so I doubt the proof in this blog could be generalized to make something stronger. It is indicated in Wikipedia that the existence of Ramsey ultrafilter follows from MA but the proof is probably more sophisticated than what is presented here...