Frédéric Wang Yet another non-exponentially growing weblog

About Me  Blog Archive

Exercises in Set Theory: Ultrafilters and Boolean algebras

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 UU on ω\omega is a Ramsey ultrafilter if for every partition {An|n<ω}\{A_{n}|n<\omega\} of ω\omega into 0\aleph_{0} pieces such that n,AnU\forall n,A_{n}\notin U, there exists XUX\in U such that n,|XAn|=1\forall n,\left|X\cap A_{n}\right|=1. We have:

Theorem 1.

The continuum hypothesis implies the existence of a Ramsey ultrafilter.


The proof given in the book is to consider an enumeration 𝒜α,α<ω1\mathcal{A}_{\alpha},\alpha<\omega_{1} of all partitions of ω\omega and to construct by induction a sequence (Xα)α<ω1{(X_{\alpha})}_{\alpha<\omega_{1}} of infinite subsets. Xα+1Xα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αX_{\alpha} is chosen such that XαXβX_{\alpha}\setminus X_{\beta} is finite for all β<α\beta<\alpha. Such a XαX_{\alpha} is claimed to exist because α<ω1\alpha<\omega_{1} is countable. Finally, D={X:XXα for some α<ω1}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 A0ωA_{0}\subseteq\omega which is neither empty nor cofinite we can define a partition of ω\omega by n<ω,An+1={min(ωmnAm)}\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 202^{\aleph_{0}} such partitions (cofinite subsets are in bijection with finite subsets and |ω<ω|=0|\omega^{<\omega}|=\aleph_{0}). On the other hand, a partition is determined by the family of subsets {An|n<ω}\{A_{n}|n<\omega\} and so there are at most (20)0=20{\left(2^{\aleph_{0}}\right)}^{\aleph_{0}}=2^{\aleph_{0}} such partitions. Since we assume the continuum hypothesis 20=12^{\aleph_{0}}=\aleph_{1} we get the enumeration 𝒜α,α<ω1\mathcal{A}_{\alpha},\alpha<\omega_{1}.

Next, I’m not even sure that as it is defined DD is a filter. Because XαX_{\alpha} is infinite D\emptyset\notin D and YXXαYDY\supseteq X\supseteq X_{\alpha}\implies Y\in D but if XXαX\supseteq X_{\alpha} and YXβY\supseteq X_{\beta}, it does not seem really clear which XγXYX_{\gamma}\subseteq X\cap Y. However, if UU is a nonprincipal ultrafilter a remark from chapter 10 suggests that UU does not contain any finite set. By exercise 7.3, this is equivalent to the fact that UU does not contain any singleton {α}\{\alpha\}. This latter point is easy to verify: if we assume the contrary, because UU is nonprincipal, there exists XUX\in U such that X{α}X\nsupseteq\{\alpha\} and so κX{α}\kappa\setminus X\supseteq\{\alpha\} would be in UU. Hence any ultrafilter containing DD should also contain E={X:α<ω1,xκ<ω,XXαx}E=\{X:\exists\alpha<\omega_{1},\exists x\in\kappa^{<\omega},X\supseteq X_{% \alpha}\setminus x\}. EE is a filter: the arguments above still hold and XXαxYXβyXYXαXβ-(xy)Xα(XαXβxy)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αXβ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γXγ+1XαX_{\gamma}\supseteq X_{\gamma+1}\supseteq...\supseteq X_{\alpha} and so XαXβX_{\alpha}\setminus X_{\beta} is empty if γβα\gamma\leq\beta\leq\alpha and XαXβXγXβX_{\alpha}\setminus X_{\beta}\subseteq X_{\gamma}\setminus X_{\beta} is finite if β<γ\beta<\gamma. So we can replace DD by a "ultrafilter extending EE". It’s not too difficult to check that a ultrafilter containing DD must be Ramsey. For any partition 𝒜α\mathcal{A}_{\alpha} then by construction either Xα+1AnX_{\alpha+1}\subseteq A_{n} for some n<ωn<\omega and so AnDA_{n}\in D or n<ω,|Xα+1An|1\forall n<\omega,|X_{\alpha+1}\cap A_{n}|\leq 1. In the latter case we can find XXα+1X\supseteq X_{\alpha+1} (so XDX\in D) such that n,|XAn|=1\forall n,|X\cap A_{n}|=1 (we pick one element from each AnA_{n} such that Xα+1An=X_{\alpha+1}\cap A_{n}=\emptyset and put these elements into XX).

Finally, the most difficult part was to understand how the sequence (Xα)α<ω1{(X_{\alpha})}_{\alpha<\omega_{1}} can be built. We can choose X0X_{0} arbitrarily as this set is not involved in the arguments above. For any α<ω1\alpha<\omega_{1}, if there exists some A𝒜αA\in\mathcal{A}_{\alpha} such that XαAX_{\alpha}\cap A is infinite, we just set Xα+1=XαAX_{\alpha+1}=X_{\alpha}\cap A. Otherwise, since Xα=A𝒜α(XαA)X_{\alpha}=\cup_{A\in\mathcal{A}_{\alpha}}(X_{\alpha}\cap A) is infinite, XαAX_{\alpha}\cap A is nonempty for infinitely many A𝒜αA\in\mathcal{A}_{\alpha}. Pick one element from each nonempty set to form the set Xα+1X_{\alpha+1}. By definition, A𝒜α,|Xα+1A|1\forall A\in\mathcal{A}_{\alpha},\left|X_{\alpha+1}\cap A\right|\leq 1. Now we consider the case α<ω1\alpha<\omega_{1} limit. Let β1<β2<βn<\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<ωn<\omega, we define Yn=i<nXβiY_{n}=\bigcap_{i<n}X_{\beta_{i}}. We have XβnX_{\beta_{n}} infinite and XβnXβn-1X_{\beta_{n}}\setminus X_{\beta_{n-1}} finite so XβnXβn-1X_{\beta_{n}}\cap X_{\beta_{n-1}} is infinite. Similarly, XβnXβn-1X_{\beta_{n}}\setminus X_{\beta_{n-1}} and Xβn-1Xβn-2X_{\beta_{n-1}}\setminus X_{\beta_{n-2}} are finite so XβnXβn-1Xβn-2X_{\beta_{n}}\cap X_{\beta_{n-1}}\cap X_{\beta_{n-2}} is infinite etc and finally YnY_{n} is infinite. Thus we can use a classical technique from Cantor (I can’t find a reference) and construct the set Xα={xn|n<ω}X_{\alpha}=\{x_{n}|n<\omega\} by picking each xnYn{x0,x1,,xn-1}x_{n}\in Y_{n}\setminus\{x_{0},x_{1},...,x_{n-1}\} so that XαXβn{x0,x1,,xn-1}X_{\alpha}\setminus X_{\beta_{n}}\subseteq\{x_{0},x_{1},...,x_{n-1}\} is finite. Moreover for each β<α\beta<\alpha consider some βn>β\beta_{n}>\beta: |XαXβ||XαXβ|+|XβXβn||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 CC is a completion of a Boolean algebra BB if it is complete (every subset XCX\subseteq C has a least upper bound X\sum X) and if BB is a dense subalgebra of CC (for any 0<cC0<c\in C there exists bBb\in B such that 0<bc0<b\leq c). I got stuck on the apparently easy proof of the following lemma:

Lemma 1.

The completion of a Boolean algebra BB is unique up to isomorphism


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

Two or three pages before, it is mentioned that "if π:CD\pi:C\rightarrow D is a one-to-one mapping such that u,vC,uvπ(u)π(v)\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 π:{0,1}𝒫({0,1})\pi:\{0,1\}\rightarrow\operatorname{\mathcal{P}}(\{0,1\}) which is one-to-one but not surjective. Actually, the property u,vC,uvπ(u)π(v)\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 dDd\in D, we want to find cCc\in C such that π(c)=d\pi(c)=d. By symmetry, the natural candidate is c=C{uB|ud}c=\sum^{C}\{u\in B|u\leq d\}. For all udu\leq d, we have ucu\leq c and so dD{uB|ud}D{uB|uc}=π(c)d\leq\sum^{D}\{u\in B|u\leq d\}\leq\sum^{D}\{u\in B|u\leq c\}=\pi(c). If d<π(c)d<\pi(c) then by density we can find bBb\in B such that 0<bπ(c)-d0<b\leq\pi(c)-d. Hence bπ(c)b\leq\pi(c) and b-db\leq-d. The latter implies that for all udu\leq d we have u-bu\leq-b an so π(c)-b\pi(c)\leq-b. Combining this with the former, we would have bπ(c)-π(c)=0b\leq\pi(c)\cdot-\pi(c)=0. Thus π\pi is surjective.

It remains to prove u,vC,uvπ(u)π(v)\forall u,v\in C,u\leq v\Leftrightarrow\pi(u)\leq\pi(v). If uvu\leq v then π(u)=D{bB|bu}D{bB|bv}π(v)\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 uvu\nleq v. Then u-v0u\cdot-v\neq 0 and 0<π(u-v)0<\pi(u\cdot-v) (we use the hint given in the book). If we are able to prove π(u-v)π(u)-π(v)\pi(u\cdot-v)\leq\pi(u)\cdot-\pi(v) then we would have 0<π(u)-π(v)0<\pi(u)\cdot-\pi(v) and so π(u)π(v)\pi(u)\nleq\pi(v) as desired. It suffices to show two inequalities on the \cdot and -- operations. Note that bB,π(b)=b\forall b\in B,\pi(b)=b. Let wCw\in C. Let w1,w2Cw_{1},w_{2}\in C. Then for all bBb\in B, bw1w2bw1,w2b=π(b)π(w1),π(w1)bπ(w1)π(w2)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 π(w1w2)π(w1)π(w2)\pi(w_{1}\cdot w_{2})\leq\pi(w_{1})\cdot\pi(w_{2}). Similarly, we have for all bBb\in B, b-w-bw-b=π(-b)π(w)b-π(w)b\leq-w\implies-b\geq w\implies-b=\pi(-b)\geq\pi(w)\implies b\leq-\pi(w). So π(-w)-π(w)\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 ("DD 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 :-)