Exercises in Set Theory: Ultrafilters and Boolean algebras

27 Nov 2012

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 exercices.

The first part of the chapter essentially deals with ultrafilters on an infinite set. 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 :-)