Set theory - Chapter 7: Filters, Ultrafilters and Boolean Algebras

7.1

Let FF be a filter and XFX\in F.

  1. (1)

    𝒫(X)F\emptyset\notin{\operatorname{\mathcal{P}}(X)\cap F} (because FF is a filter) and X𝒫(X)FX\in{\operatorname{\mathcal{P}}(X)\cap F}.

  2. (2)

    If A,B𝒫(X)FA,B\in{\operatorname{\mathcal{P}}(X)\cap F}, then ABXA\cap B\subseteq X and ABFA\cap B\in F (because FF is a filter). So AB𝒫(X)FA\cap B\in{\operatorname{\mathcal{P}}(X)\cap F}.

  3. (3)

    Let A,BXA,B\subseteq X and A𝒫(X)FA\in{\operatorname{\mathcal{P}}(X)\cap F}. If ABA\subseteq B then BFB\in F (because FF is a filter) so B𝒫(X)FB\in{\operatorname{\mathcal{P}}(X)\cap F}.

So 𝒫(X)F\operatorname{\mathcal{P}}(X)\cap F is a filter on XX.

7.2

Let AA be an infinite set and S=[A]<ωS={[A]}^{{<\omega}} be the set of all finite subsets of AA. For each PSP\in S, let P^={QS:PQ}\hat{P}=\{Q\in S:P\subseteq Q\}. Let FF be the set of all XSX\subseteq S such that XP^X\subseteq\hat{P} for some PSP\in S. Clearly, FF is a filter: we have PP^P\in\hat{P} so XP^XX\subseteq\hat{P}\implies X\neq\emptyset ; ^=S\hat{\emptyset}=S ; if XP^X\supseteq\hat{P} and YQ^Y\supseteq\hat{Q} then XYP^Q^=PQ^X\cap Y\subseteq\hat{P}\cap\hat{Q}=\hat{P\cup Q} ; if YXY\supseteq X and XP^X\supseteq\hat{P} then YP^Y\supseteq\hat{P}. If there exists some X0SX_{0}\subseteq S such that F={XS:XX0}F=\{X\subseteq S:X\supseteq X_{0}\} then there is PSP\in S such that X0=P^X_{0}=\hat{P}. Because PP is finite and AA is infinite, we can find xAPx\in A\setminus P then {a}^F\hat{\{a\}}\in F but {a}^P^\hat{\{a\}}\nsupseteq\hat{P} (PP^P\in\hat{P} and P{a}^P\notin\hat{\{a\}}) Hence PP is nonprincipal.

Let G={{a}:aA}G=\{\{a\}:a\in A\}. GG has the finite intersection property: for any a1,a2,anAa_{1},a_{2},...a_{n}\in A, i<n{ai}^={QS:i<n,aiQ}={a1,a2,,an}^\bigcap_{{i<n}}\hat{\{a_{i}\}}={\{Q\in S:\forall i<n,a_{i}\in Q\}}=\hat{\{a_{1% },a_{2},...,a_{n}\}}\neq\emptyset. Let HH be the filter generated by GG. He wave GFG\subseteq F so HFH\subseteq F. Moreover, if XFX\in F, there is PSP\in S such that XP^X\supseteq\hat{P}. If P=P=\emptyset then X=SHX=S\in H. Otherwise, there is n>0n>0 and a1,a2,anAa_{1},a_{2},...a_{n}\in A such that P={a1,a2,,an}P=\{a_{1},a_{2},...,a_{n}\}. We just saw that P^={a1,a2,,an}^H\hat{P}=\hat{\{a_{1},a_{2},...,a_{n}\}}\in H, hence XHX\in H. Finally, F=HF=H.

7.3

Let UU be an ultrafilter on SS and XYUX\cup Y\in U. If X,YUX,Y\notin U then (S\X),(S\Y)U(S\backslash X),(S\backslash Y)\in U and so S\(XY)=(S\X)(S\Y)US\backslash(X\cup Y)=(S\backslash X)\cap(S\backslash Y)\in U. A contradiction.

7.4

Let UU be an ultrafilter on a set SS. And VV the set of all XS×SX\subseteq S\times S such that X^={aS:{bS:(a,b)X}U}U\hat{X}=\{a\in S:{\{b\in S:(a,b)\in X\}}\in U\}\in U. We have ^={aS:U}=U\hat{\emptyset}=\{a\in S:\emptyset\in U\}=\emptyset\notin U so V\emptyset\notin V. S×S^={aS:SU}=SU\hat{S\times S}=\{a\in S:S\in U\}=S\in U so S×SVS\times S\in V. Let X,YVX,Y\in V and aSa\in S such that aX^Y^a\in\hat{X}\cap\hat{Y} i.e. {bS:(a,b)X}U{\{b\in S:(a,b)\in X\}}\in U and {bS:(a,b)Y}U{\{b\in S:(a,b)\in Y\}}\in U. Then {bS:(a,b)XY}{\{b\in S:(a,b)\in{X\cap Y}\}} is the intersection of these two sets and so is in UU. Hence XY^X^Y^\hat{X\cap Y}\supseteq\hat{X}\cap\hat{Y} and because X^,Y^U\hat{X},\hat{Y}\in U we have XY^U\hat{X\cap Y}\in U. Hence XYVX\cap Y\in V. Finally, let X,YS×SX,Y\in S\times S such that XVX\in V and YXY\supseteq X. Given aSa\in S, we have {bS:(a,b)X}{bS:(a,b)Y}{\{b\in S:(a,b)\in X\}}\subseteq{\{b\in S:(a,b)\in Y\}} so if the first one is in UU so is the second one. This means that X^Y^\hat{X}\subseteq\hat{Y}. Because X^U\hat{X}\in U, we have Y^U\hat{Y}\in U and so YVY\in V. Hence VV is a filter on S×SS\times S and it remains to prove it is actually an ultrafilter. Let XS×SX\subset S\times S such that XVX\notin V. Then X^U\hat{X}\notin U and so SX^US\setminus{\hat{X}}\in U. But SX^={aS:{bS:(a,b)X}U}={aS:{bS:(a,b)X}U}=S×SX^{S\setminus\hat{X}}=\{a\in S:{\{b\in S:(a,b)\in X\}}\notin U\}=\{a\in S:{\{b% \in S:(a,b)\notin X\}}\in U\}=\hat{{S\times S}\setminus X}. Hence S×SXV{{S\times S}\setminus X}\in V.

7.5

Let UU be an ultrafilter on SS and f:STf:S\rightarrow T. Define f(U)={XT:f-1(X)U}f_{\star}(U)=\{X\subseteq T:f_{{-1}}(X)\in U\}. We have f-1()=Uf_{{-1}}(\emptyset)=\emptyset\notin U and f-1(T)=SUf_{{-1}}(T)=S\in U so f(U)\emptyset\notin f_{\star}(U) and Tf(U)T\in f_{\star}(U). If X,Yf(U)X,Y\in f_{\star}(U) then f-1(XY)=f-1(X)f-1(Y)Uf_{{-1}}(X\cap Y)=f_{{-1}}(X)\cap f_{{-1}}(Y)\in U so XYf(U)X\cap Y\in f_{\star}(U). If Xf(U)X\in f_{\star}(U) and XYX\subseteq Y then f-1(Y)f-1(X)Uf_{{-1}}(Y)\supseteq f_{{-1}}(X)\in U and so f-1(Y)Uf_{{-1}}(Y)\in U and Yf(U)Y\in f_{\star}(U). Finally, for any XTX\subseteq T we have S=f-1(T)=f-1(X(TX))=f-1(X)f-1(TX)S=f_{{-1}}(T)=f_{{-1}}({X\cup(T\setminus X)})=f_{{-1}}(X)\cup f_{{-1}}(T% \setminus X) so by exercise 7.3 either f-1(X)f_{{-1}}(X) or f-1(TX)f_{{-1}}(T\setminus X) is in UU i.e. Xf(U)X\in f_{\star}(U) or TXf(U)T\setminus X\in f_{\star}(U). Finally f(U)f_{\star}(U) is an ultrafilter on TT.

7.6

Suppose a,ba,b are two UU-limits. Then given any ϵ>0\epsilon>0, the sets {n:|an-a|<ϵ2}\{n:\left|a_{n}-a\right|<\frac{\epsilon}{2}\} and {n:|an-b|<ϵ2}\{n:\left|a_{n}-b\right|<\frac{\epsilon}{2}\} are in UU. As a consequence, the intersection of these sets is in UU and in particular non empty: there exists nn such that |an-a|<ϵ2\left|a_{n}-a\right|<\frac{\epsilon}{2} and |an-b|<ϵ2\left|a_{n}-b\right|<\frac{\epsilon}{2}. Hence, for all ϵ>0,|a-b||an-a|+|an-b|<ϵ\epsilon>0,\left|a-b\right|\leq\left|a_{n}-a\right|+\left|a_{n}-b\right|<\epsilon and so a=ba=b.

Now take RR such that {an:n}(-R,R)\{a_{n}:n\in\mathbb{N}\}\subseteq(-R,R). We will try to define by induction sequences xn,yn,Vnx_{n},y_{n},V_{n} such that Vn={n:an(xn,yn)}UV_{n}=\left\{n\in\mathbb{N}:a_{n}\in\left(x_{n},y_{n}\right)\right\}\in U. For n=0n=0, we set xn=-Rx_{n}=-R, yn=+Ry_{n}=+R and Vn=V_{n}=\mathbb{N}. If VnV_{n} is defined, we can write it:

Vn={m,am(xn,xn+yn2)}Vn1{m,am(xn+yn2,yn)}Vn2{m,am=xn+yn2}Vn3V_{n}=\underbrace{\{m\in\mathbb{N},a_{m}\in\left(x_{n},\frac{x_{n}+y_{n}}{2}% \right)\}}_{{V_{n}^{1}}}\cup\underbrace{\{m\in\mathbb{N},a_{m}\in\left(\frac{x% _{n}+y_{n}}{2},y_{n}\right)\}}_{{V_{n}^{2}}}\cup\underbrace{\{m\in\mathbb{N},a% _{m}=\frac{x_{n}+y_{n}}{2}\}}_{{V_{n}^{3}}}

If Vn3UV_{n}^{3}\in U then we stop the construction here. Otherwise, Vn=(Vn1Vn2)Vn3UV_{n}=(V_{n}^{1}\cup V_{n}^{2})\cup V_{n}^{3}\in U so (Vn1Vn2)U(V_{n}^{1}\cup V_{n}^{2})\in U and either Vn1V_{n}^{1} or Vn2V_{n}^{2} is in UU. Set Vn+1V_{{n+1}} to be the one which is in UU and set (xn+1,yn+1(x_{{n+1}},y_{{n+1}} to be (xn,xn+yn2)\left(x_{n},\frac{x_{n}+y_{n}}{2}\right) or (xn+yn2,yn)\left(\frac{x_{n}+y_{n}}{2},y_{n}\right).

If we stopped the construction at nn, set a=xn+yn2a=\frac{x_{n}+y_{n}}{2}. For all ϵ>0\epsilon>0, we have {m:|am-a|<ϵ}Vn3U\{m:\left|a_{m}-a\right|<\epsilon\}\supseteq V_{n}^{3}\in U and so aa is a UU-limit. Otherwise, xnx_{n} is nondecreasing, yny_{n} is nonincreasing and |yn-xn|=21-nR0\left|y_{n}-x_{n}\right|=2^{{1-n}}R\to 0. So xnx_{n}, yny_{n} have a same limit aa. For any ϵ>0\epsilon>0, consider nn such that 21-nR<ϵ2^{{1-n}}R<\epsilon. Then for all mVnm\in V_{n}, |am-a|21-nR<ϵ\left|a_{m}-a\right|\leq 2^{{1-n}}R<\epsilon. Hence {m:|am-a|<ϵ}VnU\{m:\left|a_{m}-a\right|<\epsilon\}\supseteq V_{n}\in U and aa is a UU-limit.

7.7

Let DD be a nonprincipal filter on ω\omega.

Suppose first DD is a pp-point and A0A1A2A_{0}\subseteq A_{1}\subseteq A_{2}\subseteq... is a decreasing sequence of elements of DD. Define B0=ωA0B_{0}=\omega\setminus A_{0} and for all n<ω,Bn+1=(ωAn+1)(ωAn+1).n<\omega,B_{{n+1}}={(\omega\setminus A_{{n+1}})}\setminus{(\omega\setminus A_{% {n+1}})}. Then {Bn:n<ω}\{B_{n}:n<\omega\} is a partition of ω\omega. For all n<ωn<\omega, Bn(ωAn)DB_{n}\subseteq(\omega\setminus A_{n})\notin D so BnDB_{n}\notin D. Hence we can find XDX\in D such that n,XBn\forall n,X\cap B_{n} is finite. Then XAn=in(XBi)X\setminus A_{n}=\bigcup_{{i\leq n}}(X\cap B_{i}) is finite.

Conversely, suppose the right hand side of the equivalence holds. Let {Bn:n<ω}\{B_{n}:n<\omega\} be a partition of ω\omega such that n,BnD\forall n,B_{n}\notin D. Define An=in(ωBi)DA_{n}=\bigcap_{{i\leq n}}(\omega\setminus B_{i})\in D. We have A0A1A2A_{0}\subseteq A_{1}\subseteq A_{2}\subseteq... so there exists some XDX\in D such that for all n<ωn<\omega, XAnX\setminus A_{n} is finite. So XBnXinBi=XAnX\cap B_{n}\subseteq X\cap\bigcup_{{i\leq n}}B_{i}=X\setminus A_{n} is finite too. Hence DD is a pp-point.

7.8

Let (P, <)(P,<) be a countable linearly ordered set and DD be a pp-point on PP. We will consider sequences AnDA_{n}\in D and xnAnx_{n}\in A_{n}. We define A0=ωA_{0}=\omega and we choose x0x_{0} an element of A0A_{0}. If AnA_{n} and xnx_{n} are defined, we have a decomposition in disjoint subsets An=An-{xn}An+A_{n}=A_{n}^{-}\cup\{x_{n}\}\cup A_{n}^{+} where An-={xAn:x<xn}A_{n}^{-}=\{x\in A_{n}:x<x_{n}\} and An+={xAn:x>xn}A_{n}^{+}=\{x\in A_{n}:x>x_{n}\}. AnDA_{n}\in D and {xn}D\{x_{n}\}\notin D, so let An+1A_{{n+1}} be the unique subset among An-,An+A_{n}^{-},A_{n}^{+} which is in DD. In particular, An+1A_{{n+1}}\neq\emptyset and we can pick xn+1An+1x_{{n+1}}\in A_{{n+1}}.

By construction, we have A0A1A2A_{0}\supseteq A_{1}\supseteq A_{2}\supseteq... where n,AnD\forall n,A_{n}\in D. By exercise 7.7, there exists XDX\in D such that XAnX\setminus A_{n} is finite for any n<ωn<\omega. We define

X±=n<ω;An+1=An±(XAnAn+1)Xn±X^{\pm}=\bigcup_{{n<\omega;A_{{n+1}}=A_{n}^{\pm}}}\underbrace{(X\cap A_{n}% \setminus A_{{n+1}})}_{{X_{n}^{\pm}}}

Each Xn±X_{n}^{\pm} is finite. If n0<n1<n2n_{0}<n_{1}<n_{2}... are the integers such that An+1=An+A_{{n+1}}=A_{n}^{+} then X+X^{+} is order as follows: the elements of Xn0+X_{{n_{0}}}^{+} at the beginning, followed by the elements of Xn1+X_{{n_{1}}}^{+}, followed by the elements of Xn2+X_{{n_{2}}}^{+}, … So X+X^{+} is of order type ω\omega or a finite ordinal. Similarly, if m0<m1<m2m_{0}<m_{1}<m_{2}... are the integers such that An+1=An-A_{{n+1}}=A_{n}^{-} then X-X^{-} is order as follows: the elements of Xn0+X_{{n_{0}}}^{+} at then end, preceded by the elements of Xn1+X_{{n_{1}}}^{+}, preceded by the elements of Xn2+X_{{n_{2}}}^{+}, … So X+X^{+} is of order type ω\omega^{\star} or a finite ordinal. Clearly, X=X+X-X=X^{+}\cup X^{-} and so one of X-,X+X^{-},X^{+} is in DD and in particular infinite. Thus there is an element of DD of order-type ω\omega or ω\omega^{\star}.

7.9

Let DD be an ultrafilter.

Suppose that DD is Ramsey. Let f:ωωf:\omega\rightarrow\omega. Define An=f-1({n})A_{n}=f_{{-1}}({\{n\}}). If one of the AnA_{n} is in DD, then ff is constant on AnDA_{n}\in D. Otherwise, there exists XDX\in D such that n,|XAn|1\forall n,{|X\cap A_{n}|}\leq 1 i.e. ff is one-to-one on XDX\in D.

Conversely, suppose the right hand side of the equivalence holds. Let AnA_{n} be a partition of ω\omega such that n,AnD\forall n,A_{n}\notin D. Define f:ωωf:\omega\rightarrow\omega the function that associates to each xx the unique nn such that xAnx\in A_{n}. ff is not constant on a set XDX\in D, otherwise there is nn such that XAnX\subseteq A_{n} and so AnDA_{n}\in D contrary to our assumption. Hence ff is one-to-one on a set XDX\in D which means that n,|XAn|1\forall n,{|X\cap A_{n}|}\leq 1. Finally, DD is Ramsey.

7.10

Suppose D=f(D)={Xω:f-1(X)D}D=f_{{\star}}(D)=\{X\subseteq\omega:f_{{-1}}(X)\in D\}.

Define X={n:f(n)<n}X=\{n:f(n)<n\}. For each nXn\in X, the maximal decreasing sequence n>f(n)>f(f(n))>n>f(n)>f(f(n))>... is of finite length l(n)l(n). Let X0X_{0} and X1X_{1} be the elements of XX of even and odd length respectively. If nf-1(X0)n\in f_{{-1}}(X_{0}) then there is mX0m\in X_{0} such that f(n)=mf(n)=m. If moreover nXn\in X then l(n)=l(m)+1l(n)=l(m)+1 so nX1n\in X_{1}. Hence f(-1)(X0)X0=f_{{(-1)}}(X_{0})\cap X_{0}=\emptyset. X0DX_{0}\notin D for otherwise by D=f(D)D=f_{{\star}}(D) we would have f(-1)(X0)Df_{{(-1)}}(X_{0})\in D and so =f(-1)(X0)X0D\emptyset=f_{{(-1)}}(X_{0})\cap X_{0}\in D. Similarly, f(-1)(X1)X1=f_{{(-1)}}(X_{1})\cap X_{1}=\emptyset and so X1DX_{1}\notin D. Finally, XDX\notin D.

Now let Y={n:f(n)>n}Y=\{n:f(n)>n\}. As above, the subset {nY:any increasing sequencen<f(n)<f(f(n))<is of finite length}\{n\in Y:\text{any increasing sequence}\,n<f(n)<f(f(n))<...\,\text{is of % finite length}\} is not in DD. Let’s consider the set ZZ of elements of YY such that there is an infinite increasing sequence n<f(n)<f(f(n))<n<f(n)<f(f(n))<.... For x,yZx,y\in Z, define xyx\equiv y if there are k,mk,m such that fk(x)=fm(y)f^{k}(x)=f^{m}(y). For each xZx\in Z, let axa_{x} be a fixed representative of the class {y:yx}\{y:y\equiv x\} and let l(x)l(x) be the least k+mk+m such that fk(x)=fm(ax)f^{{k}}(x)=f^{{m}}(a_{x}). Let Z0Z_{0} and Z1Z_{1} be the elements of ZZ of even and odd length respectively. If nf-1(Z)Zn\in f_{{-1}}(Z)\cap Z then there is pZp\in Z such that n<f(n)=p<f(f(n))=f(p)<n<f(n)=p<f(f(n))=f(p)<.... So npn\equiv p and ap=ana_{p}=a_{n}. Let k,m,r,sk,m,r,s such that k+m=l(p),r+s=l(n),fk(p)=fm(ap),fr(n)=fs(an)k+m=l(p),r+s=l(n),f^{{k}}(p)=f^{{m}}(a_{p}),f^{{r}}(n)=f^{{s}}(a_{n}). If r=0r=0 then fs+1(an)=f(n)=pf^{{s+1}}(a_{n})=f(n)=p so mk+m=l(p)s+1m\leq k+m=l(p)\leq s+1 and so sm-1s\geq m-1. If sms\geq m we would have n=fs(an)=fs-m+m(ap)=fs-m+k(p)=fs-m+k+1(n)n=f^{s}(a_{n})=f^{{s-m+m}}(a_{p})=f^{{s-m+k}}(p)=f^{{s-m+k+1}}(n) with s-m+k+11s-m+k+1\geq 1 which contradicts nZn\in Z. Hence s=m-1s=m-1 and m=s+1k+mmm=s+1\geq k+m\geq m implies k=0k=0. We obtain l(p)=k+m=m=s+1=l(n)+1l(p)=k+m=m=s+1=l(n)+1. Now suppose r>0r>0, on the one hand we have fk+1(n)=fk(p)=fm(an)f^{{k+1}}(n)=f^{k}(p)=f^{{m}}(a_{n}) i.e. l(n)k+1+m=l(p)+1l(n)\leq k+1+m=l(p)+1 and on the other hand, we have fr-1(p)=fr(n)=fs(an)f^{{r-1}}(p)=f^{{r}}(n)=f^{{s}}(a_{n}) and so l(p)r-1+s=l(n)-1l(p)\leq r-1+s=l(n)-1. Hence l(p)=l(n)-1l(p)=l(n)-1. Finally, l(p)l(p) and l(n)l(n) have different parities. So f-1(Z0)Z0=f_{{-1}}(Z_{0})\cap Z_{0}=\emptyset and f-1(Z1)Z1=f_{{-1}}(Z_{1})\cap Z_{1}=\emptyset. As above, we deduce that ZDZ\notin D and finally YDY\notin D.

We thus have XYDX\cup Y\notin D and {n:f(n)=n}=ωXYD\{n:f(n)=n\}=\omega\setminus{X\cup Y}\in D.

7.11

Suppose that DED\leq E and EDE\leq D. Then there are functions f,gωωf,g\in\omega^{\omega} such that D=f(E)={Xω:f-1(X)E}D=f_{\star}(E)=\{X\subseteq\omega:f_{{-1}}(X)\in E\} and E=g(D)={Xω:g-1(X)D}E=g_{\star}(D)=\{X\subseteq\omega:g_{{-1}}(X)\in D\}. Hence E={Xω:f-1(g-1(X))E}=(gf)(E)E=\{X\subseteq\omega:f_{{-1}}(g_{{-1}}(X))\in E\}={(g\circ f)}_{\star}(E). By exercise 7.10, the set S={nω:g(f(n))=n}S=\{n\in\omega:g({f(n)})=n\} is in EE and in particular SS is infinite. (gf)S(g\circ f)_{{S}} is one-to-one and has image SS so f|Sf_{{|S}} is one-to-one and g|f(S)g_{{|f(S)}} has image SS. Hence fˇ:Sf(S)\check{f}:S\rightarrow f(S) and gˇ:f(S)S\check{g}:f(S)\rightarrow S are bijections (where we write fˇ,gˇ\check{f},\check{g} the functions with restricted domain and codomain). Let S0,S1S_{0},S_{1} be two disjoint infinite sets such that S=S0S1S=S_{0}\cup S_{1} and take T2=SiT_{2}=S_{i} the one which is in EE. The set T1=gˇ-1(T2)T_{1}=\check{g}_{{-1}}(T_{2}) is in DD because f-1(T1)f-1(g-1(T2))Ef_{{-1}}(T_{1})\supseteq f_{{-1}}(g_{{-1}}(T_{2}))\in E. Moreover ωT2S1-i\omega\setminus T_{2}\supseteq S_{{1-i}} and ωT1gˇ-1(S1-i)\omega\setminus T_{1}\supseteq\check{g}_{{-1}}(S_{{1-i}}) are infinite and thus there is a bijection between ωT1\omega\setminus T_{1} and ωT2\omega\setminus T_{2}. Thus the bijection between T1T_{1} and T2T_{2} provided by gˇ\check{g} can be extended to a bijection hωωh\in\omega^{\omega}.

Now, if XEX\in E then XT2EX\cap T_{2}\in E. Thus h-1(XT2)=gˇ-1(XT2)=g-1(XT2)Dh_{{-1}}(X\cap T_{2})=\check{g}_{{-1}}(X\cap T_{2})=g_{{-1}}(X\cap T_{2})\in D. But h-1(X)h-1(XT2)h_{{-1}}(X)\supseteq h_{{-1}}(X\cap T_{2}), and so h-1(X)Dh_{{-1}}(X)\in D. Then g-1(X)D=gˇ-1(X)D=h-1(X)DDg_{{-1}}(X)\cap D=\check{g}_{{-1}}(X)\cap D=h_{{-1}}(X)\cap D\in D. Because g-1(X)g-1(X)Dg_{{-1}}(X)\supseteq g_{{-1}}(X)\cap D we get g-1(X)Dg_{{-1}}(X)\in D. Finally, our assumption E=g(D)E=g_{\star}(D) allows to come back to XEX\in E. With this sequence of implications, we have proved that E={Xω:h-1(X)D}=h(D)E=\{X\subseteq\omega:h_{{-1}}(X)\in D\}=h_{\star}(D). Since h:ωωh:\omega\rightarrow\omega is a bijection, this means DED\equiv E.

7.12

(We use the characterisation of Ramsey ultrafilters given in exercise 7.9)

Suppose DD is a Ramsey ultrafilter. And suppose EE is a nonprincipal ultrafilter such that EDE\leq D. There is f:ωωf:\omega\rightarrow\omega such that E=f(D)={Xω:f-1(X)D}E=f_{\star}(D)=\{X\subseteq\omega:f_{{-1}}(X)\in D\} There exists XDX\in D such that ff is either constant or one-to-one on XX. ff is not constant: if f(ω)f(\omega) is a singleton then Y=ωf(ω)EY=\omega\setminus f(\omega)\in E (because EE is nonprincipal) and so =f-1(Y)D\emptyset=f_{{-1}}(Y)\in D. Thus ff is one-to-one on XX and gives a bijection from XX to f(X)f(X) that can be extended to a bijection hωωh\in\omega^{\omega}. But f-1(f(X))Xf_{{-1}}(f(X))\subseteq X and so f(X)Df(X)\in D. As in 7.11, we get E=h(D)E=h_{\star}(D) and so DED\equiv E.

Now suppose DD is a minimal ultrafilter on ω\omega. Let f:ωωf:\omega\rightarrow\omega such that for any XDX\in D the restriction f|Xf_{{|X}} is not constant. Let Y0f(D)Y_{0}\in f_{{\star}}(D) and X0DX_{0}\in D such that X0=f-1(Y0)X_{0}=f_{{-1}}(Y_{0}). Let mX0m\in X_{0} (and so f(m)Y0f(m)\in Y_{0}) and X1=X0f-1({f(m)})X_{1}=X_{0}\cap f_{{-1}}(\{{f(m)}\}). mX1m\in X_{1}\neq\emptyset and because f|X1f_{{|X_{1}}} is contant we have X1DX_{1}\notin D. Then f-1(Y0{f(m)})=X0X1Df_{{-1}}(Y_{0}\setminus\{f(m)\})=X_{0}\setminus X_{1}\in D and consequently Y0{f(m)}DY_{0}\setminus\{f(m)\}\in D. Hence f(D)f_{{\star}}(D) is nonprincipal. By definition, f(D)Df_{\star}(D)\leq D and by minimality f(D)Df_{\star}(D)\equiv D. Hence there is a bijection gg such that D=g(f(D))D=g_{\star}(f_{\star}(D)). Using exercise DD we find that X={n:g(f(n))=n}DX=\{n:g(f(n))=n\}\in D. (gf)|X(g\circ f)_{{|X}} is a bijection and so f|Xf_{{|X}} is one-to-one on XDX\in D.

7.13

Let ωα\omega_{\alpha} be a regular cardinal and suppose II is a nonprincipal ωα\omega_{\alpha}-complete ideal on ωα\omega_{\alpha}. Let I={Xδ:δ<λI=\{X_{\delta}:\delta<\lambda be an enumeration of II. Because II is nonprincipal, we have δ<λ=ωα\bigcup_{{\delta<\lambda}}=\omega_{\alpha}. Let {Yγωα:γ<cf(ωα)}\{Y_{\gamma}\subseteq\omega_{\alpha}:\gamma<\operatorname{cf}(\omega_{\alpha})\} such that γ<cf(ωα)Yγ=ωα\bigcup_{{\gamma<\operatorname{cf}(\omega_{\alpha})}}Y_{\gamma}=\omega_{\alpha}. Define for all γ<cf(ωα)\gamma<\operatorname{cf}(\omega_{\alpha}) the ordinal δγ\delta_{\gamma} to be least δ\delta such that β<δYββ<δXβ\bigcup_{{\beta<\delta}}Y_{\beta}\subseteq\bigcup_{{\beta<\delta}}X_{\beta}. By construction, we have ωα=γ<cf(ωα)β<δγXβ\omega_{\alpha}=\bigcup_{{\gamma<\operatorname{cf}(\omega_{\alpha})}}\bigcup_{% {\beta<\delta_{\gamma}}}X_{\beta}. But each XβIX_{\beta}\in I, δγ<cf(ωα)<ωα\delta_{\gamma}<\operatorname{cf}(\omega_{\alpha})<\omega_{\alpha} and II is ωα\omega_{\alpha}-complete: hence this union is in II. A contradiction.

7.14

Let II be the set of borel sets of Lebesgue measure 0. We have μ()=0\mu(\emptyset)=0, μ()=\mu(\mathbb{R})=\infty. If XYX\subseteq Y are borel sets and μ(Y)=0\mu(Y)=0 then 0μ(X)μ(Y)=00\leq\mu(X)\leq\mu(Y)=0. Finally, if {Xn:n}\{X_{n}:n\in\mathbb{N}\} are borel sets, then so are Yn=Xni<nXiY_{n}=X_{n}\setminus\bigcup_{{i<n}}X_{i} and 0=μ(nXn)=μ(nYn)=nμ(Yn)nμ(Xn)=00\leq=\mu\left({\bigcup_{{n\in\mathbb{N}}}X_{n}}\right)=\mu\left({\bigcup_{{n% \in\mathbb{N}}}Y_{n}}\right)=\sum_{{n\in\mathbb{N}}}\mu(Y_{n})\leq\sum_{{n\in% \mathbb{N}}}\mu(X_{n})=0. Hence II is a σ\sigma-ideal.

(We have followed the statement given page 82. Should the proof be generalized to non-borel sets of measure 0?)

7.15

We have =n\emptyset=\bigcup_{{n\in\mathbb{N}}}\emptyset and \mathbb{R} is no meager by the Baire Category Theorem. If we XnX_{n} is a countable family of meager sets then the union is still a countable union of nowhere dense sets and so is meager. Finally, if XYX\subseteq Y, X=nXnX=\bigcup_{{n\in\mathbb{N}}}X_{n} and Y=nYnY=\bigcup_{{n\in\mathbb{N}}}Y_{n} where each Xn,YnX_{n},Y_{n} is meager, we have X=XY=n,mXnYmX=X\cap Y=\bigcup_{{n,m\in\mathbb{N}}}X_{n}\cap Y_{m} and each XnYmX_{n}\cap Y_{m} is nowhere dense (e.g included in the nowhere dense set XnX_{n}).

7.16

As in 7.2, we prove that FF is a nonprincipal filter on SS. Moreover, suppose λ<κ\lambda<\kappa and we have a sequence {XαF:α<λ}\{X_{\alpha}\in F:\alpha<\lambda\}. Let PαSP_{\alpha}\in S such that α<λ,XαPα^\forall\alpha<\lambda,X_{\alpha}\supseteq\hat{P_{\alpha}}. Then

α<λXαα<λPα^=α<λPα^\bigcap_{{\alpha<\lambda}}X_{\alpha}\supseteq\bigcap_{{\alpha<\lambda}}\hat{P_% {\alpha}}=\hat{\bigcup_{{\alpha<\lambda}}P_{\alpha}}

And because κ\kappa is regular, α<λPαS\bigcup_{{\alpha<\lambda}}P_{\alpha}\in S. Hence FF is κ\kappa-complete.

7.17

Most of the properties are obvious. Let’s prove the associativity of \oplus and the distributivity of \cdot over \oplus. We have u(vw)=u-(v-w+-vw)+-u(v-w+-vw)=u((-v+w)(v-w))-u(v-w+-vw)=u-v-w+uwv+-uv-w+-u-vwu\oplus(v\oplus w)=u\cdot{-(v\cdot-w+-v\cdot w)}+-u\cdot{(v\cdot-w+-v\cdot w)}% =u\cdot{\left((-v+w)\cdot(v\cdot-w)\right)}-u\cdot{(v\cdot-w+-v\cdot w)}=u% \cdot-v\cdot-w+u\cdot w\cdot v+-u\cdot v\cdot-w+-u\cdot-v\cdot w. This expression is symmetric in u,v,wu,v,w and \oplus is clearly commutative so \oplus is associative. Similarly, u(vw)=u(v-w+-vw)=uv-w+u-vw=uv(-u+-w)+(-u+-v)uw=uv-(uw)+-(u-v)uw=(uv)(uw)u\cdot(v\oplus w)=u\cdot{(v\cdot-w+-v\cdot w)}=u\cdot v\cdot-w+u\cdot-v\cdot w% =u\cdot v\cdot{(-u+-w)}+(-u+-v)\cdot u\cdot w=u\cdot v\cdot{-(u\cdot w)}+-{(u% \cdot-v)}\cdot u\cdot w=(u\cdot v)\oplus(u\cdot w)

7.18

Let XBX\subseteq B and AA the subalgebra generated by XX. Let YY be the set of boolean combinations as defined in the exercise. We have XAX\subseteq A and AA is stable by boolean operations so YAY\subseteq A.

For the inverse inclusion, it suffices not note that YY is a subalgebra. 0,1Y0,1\in Y as empty sum and product. If we consider boolean operations on elements of YY, then it is clear that using the usal properties of the boolean algebra (absorption, distributivity…) we can put the result in the form of elements of YY.

If XX is infinite, first it is clear |X||A||X|\leq|A|. The inverse equality is obtained by considering that

|A|n<ω(m<ω(2|X|)n)m=|X||A|\leq\sum_{{n<\omega}}{\left(\sum_{{m<\omega}}{{(2|X|)}^{n}}\right)}^{m}=|X|

7.19

Let ABA\subseteq B, uBu\in B and define C=a.u+b.(-u):a,bAC={a.u+b.(-u):a,b\in A} and DD the subalgebra generated by A{u}A\cup\{u\}. We shall prove that C=DC=D.

First, we notice that for a=1a=1 and b=0b=0, we get uCu\in C. If we consider a=ba=b, we get ACA\subseteq C. So to show DCD\subseteq C it is enough to prove that CC is a subalgebra. We already have 0,1AC0,1\in A\subseteq C. Moreover, we see that CC is stable by boolean operations, if a1,a2,b1,b2Aa_{1},a_{2},b_{1},b_{2}\in A we have:

(a1.u+b1.(-u))+(a2.u+b2.(-u))\displaystyle{\left(a_{1}.u+b_{1}.(-u)\right)}+{\left(a_{2}.u+b_{2}.(-u)\right)} =(a1+a2).u+(b1+b2).(-u)\displaystyle={(a_{1}+a_{2}).u+(b_{1}+b_{2}).(-u)}
(a1.u+b1.(-u)).(a2.u+b2.(-u))\displaystyle{\left(a_{1}.u+b_{1}.(-u)\right)}.{\left(a_{2}.u+b_{2}.(-u)\right)} =(a1.a2).u+(b1.b2).(-u)\displaystyle={(a_{1}.a_{2}).u+(b_{1}.b_{2}).(-u)}
-(a1.u+b1.(-u))\displaystyle-{\left(a_{1}.u+b_{1}.(-u)\right)} =(-a1+(-u)).(-b1+u)\displaystyle={\left(-a_{1}+(-u)\right)}.{\left(-b_{1}+u\right)}
=(-a1).(-b1)+(-a1).u+(-b1).(-u)\displaystyle={(-a_{1}).(-b_{1})}+{(-a_{1}).u}+{(-b_{1}).(-u)}

7.20

By induction on k=|X|k=|X|. If k=0k=0 then A=0,1A={0,1} and |A|=2220|A|=2\leq 2^{{2^{0}}}. If the result is true for some k0k\geq 0 and we add an element uu to AA then the boolean algebra generate by A{u}A\cup\{u\} is of size at most 22k22k=22k+2k=222k=22k+12^{{2^{k}}}2^{{2^{k}}}=2^{{2^{k}+2^{k}}}=2^{{22^{k}}}=2^{{2^{{k+1}}}}.

7.21

Let BB be a finite boolean algebra. For all xBx\in B, any sequence x=u0>u1>u2>x=u_{0}>u_{1}>u_{2}>... is finite, so xx is atomic. Let A={a1,a2,,an}A=\{a_{1},a_{2},...,a_{n}\} be the set of atoms of BB. Then we have for all 1ijn1\leq i\neq j\leq n, aiaj{0,ai}{0,aj}={0}a_{i}\cdot a_{j}\in\{0,a_{i}\}\cap\{0,a_{j}\}=\{0\} i.e. aiaj=0a_{i}\cdot a_{j}=0. Consequently, for all 1jn1\leq j\leq n we have aji=1nai=i=1n(ajai)=aj0a_{j}\cdot\sum_{{i=1}}^{n}a_{i}=\sum_{{i=1}}^{n}(a_{j}\cdot a_{i})=a_{j}\neq 0 and so aj-i=1naia_{j}\nleq-{\sum_{{i=1}}^{n}a_{i}} and -i=1nai=0-\sum_{{i=1}}^{n}a_{i}=0 i.e. i=1nai=1\sum_{{i=1}}^{n}a_{i}=1.

Define the application ϕ:𝒫(A)B\phi:\operatorname{\mathcal{P}}(A)\rightarrow B by ϕ(X)=i=1nχX(ai)ai\phi(X)=\sum_{{i=1}}^{n}{\chi_{X}(a_{i})}a_{i}. We have ϕ()=0\phi(\emptyset)=0 and ϕ(A)=i=1nai=1\phi(A)=\sum_{{i=1}}^{n}a_{i}=1. Let X,YAX,Y\subseteq A. We have

ϕ(X)ϕ(Y)\displaystyle\phi(X)\cdot\phi(Y) =(i=1nχX(ai)ai)(i=1nχY(ai)ai)\displaystyle=\left(\sum_{{i=1}}^{n}\chi_{{X}}(a_{i})a_{i}\right)\left(\sum_{{% i=1}}^{n}\chi_{{Y}}(a_{i})a_{i}\right)
=i=1nχX(ai)χY(ai)ai\displaystyle=\sum_{{i=1}}^{n}\chi_{{X}}(a_{i})\chi_{{Y}}(a_{i})a_{i}
=i=1nχ(XY)(ai)ai\displaystyle=\sum_{{i=1}}^{n}\chi_{{(X\cap Y)}}(a_{i})a_{i}
=ϕ(XY)\displaystyle=\phi(X\cap Y)

The sum χX(ai)+χY(ai)\chi_{X}(a_{i})+\chi_{Y}(a_{i}) takes the values ai+ai=ai,ai+0=ai,0+0=0a_{i}+a_{i}=a_{i},a_{i}+0=a_{i},0+0=0 according to whether aia_{i} is in XYX\cap Y, XYX\triangle Y or outside XYX\cup Y. Hence

ϕ(X)+ϕ(Y)\displaystyle\phi(X)+\phi(Y) =i=1n(χX(ai)+χY(ai))ai\displaystyle=\sum_{{i=1}}^{n}(\chi_{X}(a_{i})+\chi_{Y}(a_{i}))a_{i}
=i=1nχ(XY)(ai)ai\displaystyle=\sum_{{i=1}}^{n}\chi_{{(X\cup Y)}}(a_{i})a_{i}
=ϕ(XY)\displaystyle=\phi(X\cup Y)

Finally, we note that ϕ(AX)=-ϕ(X)\phi(A\setminus X)=-\phi(X) because ϕ(AX)+ϕ(X)=i=1n(χ(AX)(ai)+χX(ai))ai=i=1nai=1\phi(A\setminus X)+\phi(X)=\sum_{{i=1}}^{n}{(\chi_{{(A\setminus X)}}(a_{i})+% \chi_{{X}}(a_{i}))a_{i}}=\sum_{{i=1}}^{n}a_{i}=1 and ϕ(AX)ϕ(X)=i=1n(χ(AX)(ai)χX(ai))ai=0\phi(A\setminus X)\cdot\phi(X)=\sum_{{i=1}}^{n}{(\chi_{{(A\setminus X)}}(a_{i}% )\chi_{{X}}(a_{i}))a_{i}}=0. Hence ϕ\phi is a homomorphism of boolean algebras.

Suppose ϕ(X)=ϕ(Y)\phi(X)=\phi(Y). Then i=1nχX(ai)ai=i=1nχY(ai)ai\sum_{{i=1}}^{n}\chi_{{X}}(a_{i})a_{i}=\sum_{{i=1}}^{n}\chi_{{Y}}(a_{i})a_{i}. So for all 1jn1\leq j\leq n then χX(aj)aj=aji=1nχX(ai)ai=aji=1nχY(ai)ai=χY(aj)aj\chi_{{X}}(a_{j})a_{j}=a_{j}\cdot\sum_{{i=1}}^{n}\chi_{{X}}(a_{i})a_{i}=a_{j}% \cdot\sum_{{i=1}}^{n}\chi_{{Y}}(a_{i})a_{i}=\chi_{{Y}}(a_{j})a_{j} and thus χX(ai)=χY(ai)\chi_{{X}}(a_{i})=\chi_{{Y}}(a_{i}). Hence X=YX=Y and ϕ\phi is one-to-one.

Let bBb\in B and X={n:anb}X=\{n:a_{n}\leq b\}. Then nX,anb\forall n\in X,a_{n}\leq b so ϕ(X)=nXanb\phi(X)=\sum_{{n\in X}}a_{n}\leq b. If ϕ(X)<b\phi(X)<b then b-ϕ(X)0b-\phi(X)\neq 0. Thus there exists an atom aja_{j} such that ajb-ϕ(X)a_{j}\leq b-\phi(X) i.e. ajba_{j}\leq b and aj-ϕ(X)=i=1nχ(AX)(ai)ai=i=1n(1-χX(ai))aia_{j}\leq-\phi(X)=\sum_{{i=1}}^{n}\chi_{{(A\setminus X)}}(a_{i})a_{i}=\sum_{{i% =1}}^{n}{(1-\chi_{X}(a_{i}))}a_{i}. Then aj=ajaj(1-χX(aj))aja_{j}=a_{j}\cdot a_{j}\leq{(1-\chi_{X}(a_{j}))}a_{j} and so 1-χX(aj)=11-\chi_{X}(a_{j})=1 i.e. χX(aj)=0\chi_{X}(a_{j})=0 and ajXa_{j}\notin X. This contradicts ajba_{j}\leq b. So ϕ(X)=b\phi(X)=b and ϕ\phi is surjective.

Finally, ϕ:𝒫(A)B\phi:\operatorname{\mathcal{P}}(A)\cong B is an isomorphism of algebras. In particular |B|=|𝒫(A)|=2n|B|=|\operatorname{\mathcal{P}}(A)|=2^{n}.

7.22

7.23

Let ϕ:BB|a\phi:B\rightarrow B_{{|a}} such that ϕ(x)=xa\phi(x)=x\cdot a. We have ϕ(xy)=xya=xaya=ϕ(x)ϕ(y)\phi(x\cdot y)=x\cdot y\cdot a=x\cdot a\cdot y\cdot a=\phi(x)\cdot\phi(y), ϕ(x+y)=(x+y)a=xa+ya=ϕ(x)+ϕ(y)\phi(x+y)=(x+y)\cdot a=x\cdot a+y\cdot a=\phi(x)+\phi(y), ϕ(0)=0a=0\phi(0)=0\cdot a=0, ϕ(1)=1a=a\phi(1)=1\cdot a=a and ϕ(-x)=-xa=a-x\phi(-x)=-x\cdot a=a-x. Hence ϕ\phi is a homomorphism of boolean algebras. For all xB|ax\in B_{{|a}}, xax\leq a and so ϕ(x)=xa=x\phi(x)=x\cdot a=x. Hence ϕ(B)=B|a\phi(B)=B_{{|a}}. Moreover ϕ(x)=0xa=0x-axI={u,u-a}\phi(x)=0\Leftrightarrow x\cdot a=0\Leftrightarrow x\leq-a\Leftrightarrow x\in I% =\{u,u\leq-a\}. Hence kerϕ=I\ker\phi=I and B|aB/IB_{{|a}}\cong B/I.

7.24

Let AA be a subalgebra of BB and uBAu\in B\setminus A. Define H={aA:u<a-u<a}H=\{a\in A:u<a\vee-u<a\}. For all a,bHa,b\in H we have either ab=u0a\cdot b=u\neq 0, ab=-u0a\cdot b=-u\neq 0 or e.g. u<au<a and -u<b-u<b. In that latter case, we have aua\nleq u and so aba-u0a\cdot b\geq a\cdot-u\neq 0. Hence HH has the finite intersection property and generates a filter on AA that can be extended to an ultrafilter H^A\hat{H}\subseteq A. Note that if aH^a\in\hat{H} then ua0u\cdot a\neq 0 or otherwise u-au\leq-a and so -aH^-a\in\hat{H}. Consequently, H^{u}\hat{H}\cup\{u\} has the finite intersection property and generates a filter on that can be extended to an ultrafilter FF on BB. Similarly, we get an ultrafilter GH^{-u}G\supseteq\hat{H}\cup\{-u\} on BB. Then by definition, uFu\in F and uGu\notin G. Moreover, because H^\hat{H} is an ultrafilter on AA we have aH^a\in\hat{H} or -aH^-a\in\hat{H} for all aAa\in A and so FA=GA=H^F\cap A=G\cap A=\hat{H}.

7.25

Let BB be an infinite boolean algebra and SS the set of ultrafilter on BB. Suppose |S|<|B||S|<|B|. For all F,GSF,G\in S such that FGF\neq G we have FGF\nsubseteq G because FF is maximal and so FG0F\setminus G\neq 0. For each such pairs FGF\neq G, pick uFGu\in F\setminus G to form a set XX and let AA be the subalgebra generated by XX. Hence for all FGF\neq G, we have some uFXFAu\in F\cap X\subseteq F\cap A such that uGGAu\notin G\supseteq G\cap A and so FAGAF\cap A\neq G\cap A.

If AA is infinite then by exercise 7.18, |A|=|X||S|2<|B||A|=|X|\leq{|S|}^{2}<|B| and if AA is finite, |A|<|B||A|<|B| is obvious. So there is uBAu\in B\setminus A. By exercise 7.24, we can use this element uu to construct ultrafilters FGF\neq G such that FA=GAF\cap A=G\cap A. Contradiction.

7.26

Let BB a boolean algebra such that \sum is defined for any subset. Let XBX\subseteq B and define Y={yB:xX,yx}Y=\{y\in B:\forall x\in X,y\leq x\}. If xXx\in X then xX,yx\forall x\in X,y\leq x and so Yx\sum Y\leq x. If zz is a lower bound of XX i.e. xX,zx\forall x\in X,z\leq x then zYz\in Y and so zYz\leq\sum Y. Finally Y\sum Y is the greatest lower bound of XX and X\prod X is defined for all XX.

7.27

Let BB a complete boolean algebra XBX\subseteq B and aBa\in B.

  1. (1)

    For all uXu\in X we have uXu\leq{\sum X} and so auaXa\cdot u\leq a\cdot{\sum X}. Thus aXaX\sum{a\cdot X}\leq a\cdot{\sum X}. For all uXu\in X we have auuXa\cdot u\leq u\leq{\sum X} so aXX{\sum a\cdot X}\leq{\sum X}. Moreover, auaa\cdot u\leq a so aXa{\sum a\cdot X}\leq a. Hence aXaX{\sum a\cdot X}\leq a\cdot{\sum X}.

  2. (2)

    For all uXu\in X we have uXu\geq{\prod X} and so a+ua+Xa+u\geq a+{\prod X}. Thus a+Xa+X\prod{a+X}\geq a+{\prod X}. For all uXu\in X we have a+uuXa+u\geq u\geq{\prod X} so a+XX{\prod a+X}\geq{\prod X}. Moreover, a+uaa+u\geq a so a+Xa{\prod a+X}\geq a. Hence a+Xa+X{\prod a+X}\geq a+{\prod X}.

  3. (3)

    For all uXu\in X we have uXu\leq{\sum X} and so -X-u-{\sum X}\leq-u and -X-X-{\sum X}\leq{\prod-X}. Moreover, -X-u{\prod-X}\leq-u, u--Xu\leq-{\prod-X}, X--X{\sum X}\leq-{\prod-X}. Finally, -X=-X-{\sum X}={\prod-X}.

  4. (4)

    For all uXu\in X we have uXu\geq{\prod X} and so -X-u-{\prod X}\geq-u and -X-X-{\prod X}\geq{\sum-X}. Moreover, -X-u{\sum-X}\geq-u, u--Xu\geq-{\sum-X}, X--X{\prod X}\geq-{\sum-X}. Finally, -X=-X-{\prod X}={\sum-X}.

7.28

7.29

Let AA be a subalgebra of a Boolean algebra BB. Let uBu\in B and A(u)A(u) be the algebra generated by A{u}A\cup\{u\}. Let hh be a homomorphism from AA into a complete Boolean algebra CC.

Let a,bAa,b\in A such that auba\leq u\leq b then h(a)h(b)h(a)\leq h(b). Thus for all bAb\in A such that ubu\leq b, we have {h(a):aA,au}h(b)\sum\{h(a):a\in A,a\leq u\}\leq h(b) and finally {h(a):aA,au}{h(b):bA,ub}\sum\{h(a):a\in A,a\leq u\}\leq\prod\{h(b):b\in A,u\leq b\}. Let’s choose vCv\in C is such that {h(a):aA,au}v{h(b):bA,ub}\sum\{h(a):a\in A,a\leq u\}\leq v\leq\prod\{h(b):b\in A,u\leq b\}.

Let a1,a2,b1,b2Aa_{1},a_{2},b_{1},b_{2}\in A such that a1u+b1-u=a2u+b2-ua_{1}\cdot u+b_{1}\cdot-u=a_{2}\cdot u+b_{2}\cdot-u. If we multiply both sides by -a2u-a_{2}\cdot u and -b2-u-b_{2}\cdot-u we get two new equalities -a2a1u=0-a_{2}\cdot a_{1}\cdot u=0 and -b2b1-u=0-b_{2}\cdot b_{1}\cdot-u=0 respectively. This means -a2a1-u-a_{2}\cdot a_{1}\leq-u and -b2b1u-b_{2}\cdot b_{1}\leq u respectively. Now from -b2b1ua2+-a1-b_{2}\cdot b_{1}\leq u\leq a_{2}+-a_{1} and the definition of vv, we get -h(b2)h(b1)vh(a2)+-h(a1)-h(b_{2})\cdot h(b_{1})\leq v\leq h(a_{2})+-h(a_{1}). Hence vh(a2)+-h(a1)v\leq h(a_{2})+-h(a_{1}) and -vh(b2)+-h(b1)-v\leq h(b_{2})+-h(b_{1}). If we multiply the first inequality by h(a1)vh(a_{1})\cdot v and the second by h(b1)-vh(b_{1})\cdot-v we get h(a1)vh(a1)h(a2)vh(a_{1})\cdot v\leq h(a_{1})\cdot h(a_{2})\cdot v and h(b1)-vh(b1)h(b2)-vh(b_{1})\cdot-v\leq h(b_{1})\cdot h(b_{2})\cdot-v respectively. A fortiori, h(a1)vh(a2)vh(a_{1})\cdot v\leq h(a_{2})\cdot v and h(b1)-vh(b2)-vh(b_{1})\cdot-v\leq h(b_{2})\cdot-v. By symmetry, we have h(a1)v=h(a2)vh(a_{1})\cdot v=h(a_{2})\cdot v, h(b1)-v=h(b2)-vh(b_{1})\cdot-v=h(b_{2})\cdot-v and finally h(a1)v+h(b1)-v=h(a2)v+h(b2)-vh(a_{1})\cdot v+h(b_{1})\cdot-v=h(a_{2})\cdot v+h(b_{2})\cdot-v.

By the previous analysis, for any xA(u)x\in A(u) we can define f(x)=h(a)v+h(b)-vf(x)=h(a)\cdot v+h(b)\cdot-v if x=au+b-ux=a\cdot u+b\cdot-u and this does not depend on the decomposition of xx. In particular for all aAa\in A, we have f(a)=f(au+a-u)=h(a)v+h(a)-v=h(a)f(a)=f(a\cdot u+a\cdot-u)=h(a)\cdot v+h(a)\cdot-v=h(a) and so f(0)=h(0)=0f(0)=h(0)=0 and f(1)=h(1)=1f(1)=h(1)=1.

f((a1u+b1-u)+(a2u+b2-u))\displaystyle f((a_{1}\cdot u+b_{1}\cdot-u)+(a_{2}\cdot u+b_{2}\cdot-u)) =f((a1+a2)u+(b1+b2)-u)\displaystyle=f((a_{1}+a_{2})\cdot u+(b_{1}+b_{2})\cdot-u)
=h(a1+a2)v+h(b1+b2)-v\displaystyle=h(a_{1}+a_{2})\cdot v+h(b_{1}+b_{2})\cdot-v
=(h(a1)v+h(b1)-v)+(h(a2)v+h(b2)-v)\displaystyle=(h(a_{1})\cdot v+h(b_{1})\cdot-v)+(h(a_{2})\cdot v+h(b_{2})\cdot% -v)
=f(a1u+b1-u)+f(a2u+b2-u)\displaystyle=f(a_{1}\cdot u+b_{1}\cdot-u)+f(a_{2}\cdot u+b_{2}\cdot-u)
f((a1u+b1-u)(a2u+b2-u))\displaystyle f((a_{1}\cdot u+b_{1}\cdot-u)\cdot(a_{2}\cdot u+b_{2}\cdot-u)) =f(a1a2u+b1b2-u)\displaystyle=f(a_{1}\cdot a_{2}\cdot u+b_{1}\cdot b_{2}\cdot-u)
=h(a1a2)v+h(b1b2)-v\displaystyle=h(a_{1}\cdot a_{2})\cdot v+h(b_{1}\cdot b_{2})\cdot-v
=(h(a1)v+h(b1)-v)(h(a2)v+h(b2)-v)\displaystyle=(h(a_{1})\cdot v+h(b_{1})\cdot-v)\cdot(h(a_{2})\cdot v+h(b_{2})% \cdot-v)
=f(a1u+b1-u)f(a2u+b2-u)\displaystyle=f(a_{1}\cdot u+b_{1}\cdot-u)\cdot f(a_{2}\cdot u+b_{2}\cdot-u)

Finally we have

f(-(au+b-u))\displaystyle f(-(a\cdot u+b\cdot-u)) =f((-a+-u)(-b+u))\displaystyle=f((-a+-u)\cdot(-b+u))
=f((-a-b+-a)u+(-a-b+-b)-u)\displaystyle=f((-a\cdot-b+-a)\cdot u+(-a\cdot-b+-b)\cdot-u)
=f(-au+-b-u)\displaystyle=f(-a\cdot u+-b\cdot-u)
=-h(a)v+-h(b)-v\displaystyle=-h(a)v+-h(b)\cdot-v
f(-(au+b-u))+f(au+b-u)\displaystyle f(-(a\cdot u+b\cdot-u))+f(a\cdot u+b\cdot-u) =(-h(a)+h(a))v+(-h(b)+h(b))-v\displaystyle=(-h(a)+h(a))v+(-h(b)+h(b))\cdot-v
=v+-v\displaystyle=v+-v
=1\displaystyle=1
f(-(au+b-u))f(au+b-u)\displaystyle f(-(a\cdot u+b\cdot-u))\cdot f(a\cdot u+b\cdot-u) =(-h(a)h(a))v+(-h(b)h(b))-v\displaystyle=(-h(a)\cdot h(a))v+(-h(b)\cdot h(b))\cdot-v
=0\displaystyle=0

and so f(-(au+b-u))=-f(au+b-u)f(-(a\cdot u+b\cdot-u))=-f(a\cdot u+b\cdot-u). Finally, ff is a homomorphism from A(u)A(u) to CC that extends hh.

7.30

Let AA be a subalgebra of a Boolean algebra BB. Let hh be a homomorphism from AA into a complete Boolean algebra CC. Let PP be the set of all Boolean algebra homomorphisms from a subalgebra of BB to CC which extends hh. (P, )(P,\subseteq) is a nonempty partially ordered set. If CC is a chain and fc=Cf_{c}=\bigcup C then BC=domfC=fCdomfB_{C}=\operatorname{dom}f_{C}=\bigcup_{{f\in C}}\operatorname{dom}f is a subalgebra of BB. We have BCAB_{C}\supseteq A and fc|A=h{f_{c}}_{{|A}}=h so fcPf_{c}\in P. Moreover fC,fcf\forall f\in C,f_{c}\supseteq f. By Zorn’s Lemma PP has a maximal element fmaxf_{{\text{m}ax}}. If domfmaxB\operatorname{dom}f_{{\text{m}ax}}\subsetneq B then let uBdomfu\in B\setminus{\operatorname{dom}f}. Using exercise 7.29 we can construct a Boolean homomorphism g:A(u)Cg:A(u)\rightarrow C and we would have gfmaxg\supsetneq f_{{\text{m}ax}}. So fmax:BCf_{{\text{m}ax}}:B\rightarrow C is a Boolean homomorphism from BB into CC such that fmax|A=h{f_{{\text{m}ax}}}_{{|A}}=h.

7.31

Let BB be a Boolean algebra and AA be a regular subalgebra of BB. Denote by iA:AA~i_{A}:A\rightarrow\tilde{A} and iB:BB~i_{B}:B\rightarrow\tilde{B} the one-to-one mapping from A,BA,B to their respective completions. By exercise 7.30, iB|A:AB~{i_{B}}_{{|A}}:A\rightarrow\tilde{B} can be extended to a mapping iA~:A~B~i_{{\tilde{A}}}:\tilde{A}\rightarrow\tilde{B} such that iB|A=iA~iA{i_{B}}_{{|A}}=i_{{\tilde{A}}}\circ i_{A}.

Let x,yA~x,y\in\tilde{A} and suppose xyx\neq y. Then we have either xyx\nleq y or yxy\nleq x. If for example the first assertion holds, then 0<x-y0<x\cdot-y and because iA(A)i_{{A}}(A) is a dense subalgebra, there exists aAa\in A such that 0<iA(a)x-y0<i_{{A}}(a)\leq x\cdot-y. But a0a\neq 0 because iAi_{A} is one-to-one and so iB(a)0i_{B}(a)\neq 0 because iBi_{B} is one-to-one. Hence 0<iB(a)=iA~iA(a)iA~(x-y)=iA~(x)-iA~(y)0<i_{B}(a)=i_{{\tilde{A}}}\circ i_{{A}}(a)\leq i_{{\tilde{A}}}(x\cdot-y)=i_{{% \tilde{A}}}(x)\cdot-i_{{\tilde{A}}}(y). Thus iA~(x)iA~(y)i_{{\tilde{A}}}(x)\nleq i_{{\tilde{A}}}(y). Finally iA~iA~(y)i_{{\tilde{A}}}\neq i_{{\tilde{A}}}(y) and iA~i_{{\tilde{A}}} is an embedding.

Using the density of iA~(A)i_{{\tilde{A}}}(A) in A~\tilde{A}, we can construct for each aA~a\in\tilde{A} a partition VaAV_{a}\subseteq A of a=iA(Va)a=\sum i_{A}(V_{a}) by ordinal induction as follows. For any ordinal α\alpha, if vβv_{{\beta}} is defined for all β<α\beta<\alpha and if a-β<αiA(vβ)>0a-\sum_{{\beta<\alpha}}i_{A}(v_{\beta})>0 then let vαAv_{{\alpha}}\in A such that iA(vα)a-β<αiA(vβ)i_{A}(v_{{\alpha}})\leq a-\sum_{{\beta<\alpha}}i_{A}(v_{\beta}). By construction, the vαv_{\alpha} are disjoint. By Replacement, there is α\alpha such that a-β<αiA(vβ)=0a-\sum_{{\beta<\alpha}}i_{A}(v_{\beta})=0 and we define Va={vβ:β<α}V_{a}=\{v_{\beta}:\beta<\alpha\}. Note that V0=V_{0}=\emptyset.

Now let X={xα:α<λ}AX=\{x_{\alpha}:\alpha<\lambda\}\subseteq A and denote σ=A~X\sigma=\sum^{{\tilde{A}}}X. For all α<λ\alpha<\lambda, let yα=xα-β<αyβy_{\alpha}=x_{\alpha}-\sum_{{\beta<\alpha}}y_{\beta} so that the yαy_{\alpha} are pairwise disjoint and σ=α<λyα\sigma=\sum_{{\alpha<\lambda}}y_{\alpha}. Let V=α<βVyαV=\bigcup_{{\alpha<\beta}}V_{{y_{\alpha}}} and W=V-σW=V_{{-\sigma}}. Clearly, V=σ\sum V=\sigma, iA(VW)=iA(V)iA(W)σ-σ=0i_{A}(V\cdot W)=i_{A}(V)\cdot i_{A}(W)\leq\sigma\cdot-\sigma=0 and A~iA(VW)=A~iA(V)+A~iA(W)=σ+-σ=1\sum^{{\tilde{A}}}{i_{A}(V\cup W)}={\sum^{{\tilde{A}}}i_{A}(V)}+{\sum^{{\tilde% {A}}}i_{A}(W)}=\sigma+-\sigma=1. Hence 1=A~iA(VW)A(VW)1=\sum^{{\tilde{A}}}i_{A}(V\cup W)\leq\sum^{{A}}(V\cup W) and VWV\cup W is a maximal antichain in AA. Because AA is a regular subalgebra of BB and iB(B)i_{{B}}(B) is a regular subalgebra of B~\tilde{B}, we have 1=A(VW)=B(VW)=B~iB(VW)1=\sum^{{A}}(V\cup W)=\sum^{{B}}(V\cup W)=\sum^{{\tilde{B}}}i_{{B}}(V\cup W).

We have xX,xX\forall x\in X,x\leq\sum X so xX,iA~(x)iA~(X)\forall x\in X,i_{{\tilde{A}}}(x)\leq i_{{\tilde{A}}}(\sum X) and finally iA~(X)iA~(X)\sum{i_{{\tilde{A}}}(X)}\leq i_{{\tilde{A}}}(\sum X). Similarly, any vVv\in V belongs to some VαV_{\alpha} and by construction iA(v)yαxαXi_{A}(v)\leq y_{\alpha}\leq x_{\alpha}\in X so iA~(iA(v))iA~(x)iA~(X)i_{{\tilde{A}}}(i_{A}(v))\leq i_{{\tilde{A}}}(x)\leq{\sum i_{{\tilde{A}}}(X)} and we get iA~(iA(V))iA~(X)\sum i_{{\tilde{A}}}(i_{A}(V))\leq{\sum i_{{\tilde{A}}}(X)}. Thus we have

iA~(X)\displaystyle i_{{\tilde{A}}}\left(\sum X\right) =iA~(σ)iB(VW)\displaystyle={i_{{\tilde{A}}}(\sigma)}\cdot{\sum i_{{B}}(V\cup W)}
=wVWiA~(σ)iA~(iA(w))\displaystyle=\sum_{{w\in V\cup W}}{i_{{\tilde{A}}}(\sigma)\cdot i_{{\tilde{A}% }}(i_{A}(w))}
=wVWiA~(vV(iA(v)iA(w)))\displaystyle=\sum_{{w\in V\cup W}}{i_{{\tilde{A}}}\left(\sum_{{v\in V}}(i_{A}% (v)\cdot i_{A}(w))\right)}
=wVWiA~(vVδv,wiA(w))\displaystyle=\sum_{{w\in V\cup W}}{i_{{\tilde{A}}}\left(\sum_{{v\in V}}\delta% _{{v,w}}i_{A}(w)\right)}
=iA~(iA(V))\displaystyle=\sum i_{{\tilde{A}}}(i_{A}(V))
iA~(X)\displaystyle\leq\sum i_{{\tilde{A}}}(X)

Finally iA~(X)=iA~(X)i_{{\tilde{A}}}\left(\sum X\right)=\sum i_{{\tilde{A}}}(X) and iA~i_{{\tilde{A}}} is a complete embedding from A~\tilde{A} to B~\tilde{B} such that iB|A=iA~iA{i_{B}}_{{|A}}=i_{{\tilde{A}}}\circ i_{A}. Note that for any aA~a\in\tilde{A}, such a morphism ff must satisfy f(a)=f(iA(Va))=f(iA(Va))=iB(Va)f(a)=f\left(\sum i_{A}(V_{a})\right)=\sum f(i_{A}(V_{a}))=\sum i_{B}(V_{a}) and so iA~i_{{\tilde{A}}} is the unique morphism with this property.

7.32

Let BB be a complete Boolean algebra. If WW is a maximal antichain then any element bBb\in B can be written b=b1=bW=wWbwb=b\cdot 1=b\cdot\sum W=\sum_{{w\in W}}b_{w} where bw=bwBwb_{w}=b\cdot w\in B_{{w}}. Conversely, if wWbw=wWcw\sum_{{w\in W}}b_{w}=\sum_{{w\in W}}c_{w} with bw,cwBwb_{w},c_{w}\in B_{{w}} then bw=wwWbw=wwWcw=cwb_{w}=w\cdot\sum_{{w\in W}}b_{w}=w\cdot\sum_{{w\in W}}c_{w}=c_{w} and the decomposition is unique. Hence |B|=wW|B|w||B|=\prod_{{w\in W}}|B_{{|w}}|.

The case BB finite has been studied in exercise 7.21. WW was the set of the nn atoms. For any wWw\in W, B|w={0,w}B_{{|w}}=\{0,w\} and |B|=wW|B|w|=2n|B|=\prod_{{w\in W}}|B_{{|w}}|=2^{n}. Below we consider the case BB infinite and prove that |B|0=|B|{|B|}^{{\aleph_{0}}}=|B|.

First consider the case when |Ba|=|B||B_{{a}}|=|B| for all a0a\neq 0. BB is infinite so there exists some 0<u1<10<u_{1}<1. If unu_{n} is defined, then B|-unB_{{|-u_{n}}} is infinite and there exists some 0<un+1<-un0<u_{{n+1}}<-u_{n}… If i<ji<j then uiujui-ui=0u_{i}\cdot u_{j}\leq u_{i}\cdot-u_{i}=0. If we set u0=-nunu_{0}=-\sum_{{n\in\mathbb{N}}}u_{n} then W={un:n}W=\{u_{n}:n\in\mathbb{N}\} is a maximal antichain. Hence |B|=wW|B|w|=|B|0|B|=\prod_{{w\in W}}{|B_{{|w}}|}={|B|}^{{\aleph_{0}}}.

Let SS be the set of stable element i.e. for all 0<xa0<x\leq a, |B|x|=|B|a||{B_{{|x}}}|=|{B_{{|a}}}|. Let bBb\in B. Suppose that there is no 0<xb0<x\leq b such that B|xB_{{|x}} is stable then there is 0<u1<u0=b0<u_{1}<u_{0}=b such that |B|u1|<|B|u0||{B_{{|u_{1}}}}|<|{B_{{|u_{0}}}}|. Thus we could continue and construct an infinite decreasing sequence of cardinals |B|u0|>|B|u1|>|B|u2|>|B_{{|u_{0}}}|>|B_{{|u_{1}}}|>|B_{{|u_{2}}}|>.... A contradiction. So xS,xb\exists x\in S,x\leq b and SS is dense in BB. Using the technique of the exercise 7.31, we can construct a maximal antichain WSW\subseteq S such that |W|0|W|\leq\aleph_{0}.

Let sSs\in S. If ss is an atom then B|s={0,s}B_{{|s}}=\{0,s\}. Otherwise, there exists some 0<x<s0<x<s. We have |B|s|=|B|x||B_{{|s}}|=|B_{{|x}}| and B|xB|sB_{{|x}}\subsetneq B_{{|s}} so B|sB_{{|s}} is infinite. By the first case, |B|s|=|B|x|0|B_{{|s}}|={|B_{{|x}}|}^{{\aleph_{0}}}.

If wW\forall w\in W, |B|w|=2|B_{{|w}}|=2 then |B|=2|W||B|=2^{{|W|}} and so WW is infinite: |W|=0|W|=\aleph_{0}. Clearly, we have |B|0=|B|{|B|}^{{\aleph_{0}}}=|B|. Otherwise, there is some w0w_{0} such that |B|w0||B_{{|w_{0}}}| is infinite. Let TWT\subseteq W the set of atoms of BB. We have |T||W|0|T|\leq|W|\leq\aleph_{0} and finally:

|B|0=(wW|B|w|0)=wT20wST|B|w|0=20|T|wST|B|w|0=(2|B|w0|)0wS(T{w0})|B|w|=wST|B|w||B||B|0{|B|}^{{\aleph_{0}}}=\left(\prod_{{w\in W}}{|B_{{|w}}|}^{{\aleph_{0}}}\right)=% \prod_{{w\in T}}{2^{{\aleph_{0}}}}\prod_{{w\in S\setminus T}}{{|B_{{|w}}|}}^{{% \aleph_{0}}}={2^{{\aleph_{0}{|T|}}}}\prod_{{w\in S\setminus T}}{{|B_{{|w}}|}^{% {\aleph_{0}}}}={\left({2{|B_{{|w_{0}}}|}}\right)}^{{\aleph_{0}}}\prod_{{w\in S% \setminus{(T\cup\{w_{0}\})}}}{{|B_{{|w}}|}}=\prod_{{w\in S\setminus T}}{{|B_{{% |w}}|}}\leq|B|\leq{|B|}^{{\aleph_{0}}}

7.33

Let BB be a κ\kappa-complete κ\kappa-saturated Boolean algebra. Let XBX\subset B and Y={bB+:xX,bx}XY=\{b\in B^{+}:\exists x\in X,b\leq x\}\subseteq X. Let WYW\subseteq Y be a maximal subset of YY which is an antichain. BB is κ\kappa-saturated so |W|<κ|W|<\kappa and BB is κ\kappa-complete so W\sum W is well-defined.

If there exists yYy\in Y such that yWy\nleq\sum W then 0y-Wy0\neq y-\sum W\leq y. So y-WYy-\sum W\in Y. For all wWw\in W, w(y-W)W-W=0w\cdot\left(y-\sum W\right)\leq{\sum W}\cdot{-\sum W}=0. This contradicts the maximality of WW. Hence for all yYy\in Y, yWy\leq\sum W.

If MM is a upper bound of XX then for all wWYw\in W\subseteq Y there exists xXx\in X such that wxMw\leq x\leq M. So MM is an upper bound of WW and so WM\sum W\leq M. Moreover, we have seen in the previous paragraph that W\sum W is itself an upper bound of XYX\subseteq Y. Hence X\sum X is well-defined and X=W\sum X=\sum W. Using 7.26, we conclude that BB is complete.

This page is W3C-compliant - Author: Frédéric WANG
Valid XHTML 1.1 Valid MathML 2.0 Valid SVG Valid CSS