Blog de Frédéric

To content | To menu | To search

Tag - set theory

Entries feed - Comments feed

Saturday, April 11 2015

Exercises in Set Theory

As mentioned in a previous blog post, I've been working on the exercises of chapter 1 of Kunen's Set Theory book. I finally uploaded my solutions this morning.

Saturday, January 31 2015

The canonical well-ordering of α×α (part 2)

In a my previous blog post, I discussed the canonical well-ordering on α×α and stated theorem 0.5 below to calculate its order-type γ(α). Subsequent corollaries provided a bound for γ(α), its fixed points and a proof that infinite cardinals were among these fixed points (and so that cardinal addition and multiplication is trivial). In this second part, I’m going to provide the proof of this theorem.

First, we note that for all n<ω, there is only one order-type for n×n, since the notion of cardinal and ordinal is the same for finite sets. So indeed

n<ω,γ(n)=|n×n|=n2

and taking the limit, we get our first infinite fixed point:

γ(ω)=supn<ωγ(n)=ω

For all α the ordering on (α+1)×(α+1) is as follows: first the elements of α×α ordered as γ(α), followed by the elements (ξ,α) for 0ξ<α, followed by the elements (α,ξ) for 0ξα. Hence

α,γ(α+1)=γ(α)+α2+1

From this, we can try to calculate the next values of γ after ω:

γ(ω+1)=ω+ω2+1=ω3+1
γ(ω+2)=ω3+1+ω+1+ω+1+1=ω5+2

The important point is 1+ω=ω ; in general we will use several times the property α+ωβ=ωβ if α<ωβ. By a simple recurrence (see proposition 0.1), we can generalize the expression to arbitrary n:

γ(ω+n)=ω(2n+1)+n

and so taking the limit

γ(ω2)=ω2

which is a limit ordinal not fixed by γ. We note another point that will be used later: taking the limit “eliminates” the smallest terms. More generally, we can perform the same calculation, starting from any arbitrary αω:

Proposition 0.1.

For any limit ordinal α and 1n<ω we have

γ(α+n)=γ(α)+α2n+n
Proof.

For n=1 this is the relation for γ(α+1) explained above. If the relation is true for n then

γ(α+n+1)=γ(α+n)+(α+n)2+1
γ(α+n+1)=γ(α)+α2n+n+α+n+α+n+1

and since αω we have n+α=α and so

γ(α+n+1)=γ(α)+α(2n+1)+n+1

Which shows the result at step n+1. ∎

As above, we can take the limit and say γ(α+ω)=supn<ωγ(α+n)=γ(α)+αω which is consistent with γ(ω2)=ω+ω2=ω2. However, if we consider the Cantor Normal Form α=ωβ1n1++ωβknk, then for all n<ω we have can use the fact that “ωβ1 will eliminate smaller terms on its left” that is αn=ωβ1(n1n)+ωβ2n2++ωβknk. Then using the fact that “taking the limit eliminates the smallest terms” we get αω=supn<ωαn=ωβ1+1. So actually, we have a nicer formula where αω is put in Cantor Normal Form:

αω,γ(α+ω)=γ(α)+ωlogω(α)+1

This can be generalized by the following proposition:

Proposition 0.2.

For any αω and β1 such that logω(α)+1β we have

γ(α+ωβ)=γ(α)+ωlogω(α)+β
Proof.

We prove by induction on β that for all such α the expression is true. We just verified β=1 and the limit case is obvious by continuity of γ and of the sum/exponentiation in the second variable. For the successor step, if logω(α)+1β+1 then a fortiori 1n<ω,logω(α+ωβn)+1β+1β. We can then use the induction hypothesis to prove by induction on 1n<ω that γ(α+ωβn)=γ(α)+ωlogω(α)+βn. For n=1, this is just the induction hypothesis of β (for the same α!). For the successor step, we need to use the induction hypothesis of β (for α+ωβn) which is γ(α+ωβ(n+1))=γ(α+ωβn)+ωlogω(α)+β. Finally, γ(α+ωβ+1)=sup1n<ωγ(α+ωβn)=γ(α)+ωlogω(α)+β+1, as wanted. ∎

For all α1, logω(ωα)+1=α+1 so the previous paragraph also gives γ(ωα+1)=γ(ωα+ωα+1)=γ(ωα)+ωα2+1. Then, we find

γ(ω2)=ω+ω3=ω3
γ(ω3)=ω3+ω5=ω5

And more generally by induction on n<ω, we can show that

γ(ωn+1)=ω2n+1

Then we deduce another fixed point

γ(ωω)=sup1n<ωγ(ωn)=ωω

The following proposition tries to generalize the expression of γ(ωα+1).

Proposition 0.3.

For any α,β1 such that logω(α)>logω(β) we have

γ(ωα+β)=γ(ωα)+ωα2+β
Proof.

This is done by induction on β<α for a fixed α. We already verified the case β=1 in the previous paragraph and the limit case is obvious by continuity of γ and of the sum/exponentiation in the second variable. For the successor step, we have γ(ωα+β+1)=γ(ωα+β)+ω(α+β)2+1 and by induction hypothesis, γ(ωα+β)=γ(ωα)+ωα2+β. Since logω(α)>logω(β+1)=logω(β) we have (α+β)2+1=α+β+α+β+1=α2+β+1>α2+β and so ωα2+β+ωα2+β+1=ωα2+β+1. Finally, γ(ωα+β+1)=γ(ωα+β)+ωα2+β+1 as wanted. ∎

For any 1n<ω and α1, if 1β<ωα then logω(β)<α=logω(ωαn). Hence proposition 0.3 gives γ(ωωαn+β)=γ(ωωαn)+ωωα2n+β Then by continuity of γ and of the sum/exponentiation in the second variable, we can consider the limit βωα to get γ(ωωα(n+1))=γ(ωωαn)+ωωα(2n+1). So continuing our calculation we have

γ(ωω2)=ωω+ωω3=ωω3
γ(ωω3)=ωω3+ωω5=ωω5

and taking the limit we find another fixed point

γ(ωω2)=ωω2

then again

γ(ωω22)=ωω2+ωω23=ωω23
γ(ωω23)=ωω23+ωω25=ωω25

and taking the limit we find another fixed point

γ(ωω3)=ωω3

More generally, we have the following proposition:

Proposition 0.4.

For any ordinal α and 1n<ω we have

γ(ωωαn)=ωωα(2n-1)
Proof.

From the relation γ(ωωα(n+1))=γ(ωωαn)+ωωα(2n+1), we deduce by induction on n that

n2,γ(ωωαn)=γ(ωωα)+ωωα(2n-1)

Taking the limit nω,we obtain

γ(ωωα+1)=γ(ωωα)+ωωα+1

We can then show by induction that all the ωωα are actually fixed points, using the previous relation at successor step, the continuity of γ at limit step and the fact that γ(ω)=ω. This means

γ(ωωα)=ωωα=ωωα(2×1-1)

Then for n2, we get

γ(ωωαn)=γ(ωωα)+ωωα(2n-1)=ωωα+ωωα(2n-1)=ωωα(2n-1)

Equipped with these four propositions, we have a way to recursively calculate γ. We are ready to prove the main theorem:

Theorem 0.5.

For all ordinal α, we denote γ(α) the order-type of the canonical ordering of α×α. Then γ can be calculated as follows:

  1. (1)

    Finite Ordinals: For any n<ω we have

    γ(n)=n2
  2. (2)

    Limit Ordinals: For any limit ordinal α,

    1. (a)

      If ωlogω(logω(α)) does not divide logω(α) then

      γ(α)=ωlogω(α)α
    2. (b)

      Otherwise, we write α=ωlogω(α)n+ρ for some n1. If n2 then

      γ(α)=ωlogω(α)(ωlogω(α)(n-1)+ρ)

      (like the first case but we “decrement n in the second factor”)

    3. (c)

      Otherwise, α=ωlogω(α)+ρ and we write logω(α)=ωlogω(logω(α))m for some m1. We have

      γ(α)=ωlogω(α)(ωωlogω(logω(α))(m-1)+ρ)

      (like the first case but we “decrement m in the second factor”)

  3. (3)

    Infinite Successor Ordinals: For any limit ordinal α and 1n<ω we have

    γ(α+n)=γ(α)+α2n+n

    where γ(α) is determined as in the previous point.

Proof.

The “Finite Ordinals” has been discussed at the beginning and the “Infinite Successor Ordinals” is proposition 0.1. Now let’s consider the Cantor Normal Form ωβ1n++ωβknk of a limit ordinal αω (so βk1 and β1=logω(α)). First, from proposition 0.2 we can make successively extract the nk terms ωβk (by left-multiplying them by ωβ1), then the nk-1 terms ωβk-1, … then the n2 terms ωβ2 and finally n-1 terms ωβ1. We obtain:

γ(α)=γ(ωβ1)+ωβ1(ωβ1(n-1)+ωβ2n2++ωβknk)

We now write β1=ωδm+σ where δ=logωβ1 and m,σ are the quotient and remainder of the Euclidean division of β1 by ωδ. We can then use proposition 0.3 to extract σ:

σ=0γ(ωβ1)=γ(ωωδm)
σ0γ(ωβ1)=γ(ωωδm)+ωωδ(2m)+σ

Finally, using proposition 0.4 we obtain

γ(ωωδm)=ωωδ(2m-1)

σ0 means that ωδ=ωlogω(logω(α)) does not divide β1=logω(α). In that case, ωωδ(2m)+σ>ωωδ(2m-1) and so γ(ωβ1)=ωωδ(2m)+σ. We note that β12=ωδm+σ+ωδm+σ=ωδ(2m)+σ since the remainder σ is less than ωδ. So actually γ(ωβ1)=ωβ1ωβ1. Coming back to the expression of γ(α), this term can be grouped with ωβ1(n-1) to recover the Cantor Normal Form of α and we finally get γ(α)=ωβ1α.

Otherwise, σ=0, β1=ωδm and

γ(ωβ1)=γ(ωωδm)=ωωδ(2m-1)=ωβ1ωωδ(m-1)

But then β1=ωδm>ωδ(m-1) and so ωβ1ωβ1>ωβ1ωωδ(m-1). Hence if n2, the term γ(ωβ1) is eliminated in the expression of γ(α) and it remains

γ(α)=ωβ1(ωβ1(n-1)+ρ)

where ρ=ωβ2n2++ωβknk. If instead n=1, then the term ωβ1(n-1) is zero and it remains

γ(α)=ωβ1(ωωδ(m-1)+ωβ2n2++ωβknk)

Friday, January 30 2015

The canonical well-ordering of α×α

It is well-known that the cartesian product of two infinite sets of cardinality α is also of cardinality α. Equivalently, the set ωα×ωα can be well-ordered in order-type ωα. However, the standard ordering on ωα×ωα does not work, since it is always of order type ωα2. Instead, we introduce for each ordinal α the canonical well-ordering of α×α as follows: (ξ1,ξ2)(η1,η2) if either max(ξ1,ξ2)<max(η1,η2) or max(ξ1,ξ2)=max(η1,η2) but (ξ1,ξ2) precedes (η1,η2) lexicographically. If we note γ(α) the ordinal isomorphic to that well-ordering ordering, then we can prove that γ(ωα)=ωα as wanted (see Corollary 0.4).

Jech’s Set Theory book contains several properties of γ. For example, γ is increasing : for any ordinal α, α×α is a (proper) initial segment of (α+1)×(α+1) and of λ×λ for any limit ordinal λ>α. As a consequence, α,αγ(α) which can also trivially be seen by the increasing function ξ(ξ,0) from α to α×α. Also, α,γ(α)<γ(λ) implies supα<λγ(α)γ(λ). This can not be a strict equality, or otherwise the element (ξ,η)λ×λ corresponding to supα<λγ(α) via the isomorphism between λ×λ and γ(λ) would be an element larger than all (α,α) for α<λ. Hence γ is continuous and by exercise 2.7 of the same book, γ has arbitrary large fixed points. Exercise 3.5 shows that γ(α)ωα and so γ does not increase cardinality (see Corollary 0.2 for a much better upper bound). Hence starting at any infinite cardinal κ the construction of exercise 2.7 provides infinitely many fixed points of γ having cardinality κ. Hence the infinite fixed points of γ are not just cardinals and we can wonder what they are exactly…

I recently tried to solve Exercise I.11.7 of Kunen’s Set Theory book which suggests a nice characterization of infinite fixed points of γ: they are the ordinals of the form ωωα. However, I could not find a simple proof of this statement so instead I tried to determine the explicit expression of γ(α), from which the result becomes obvious (see Corollary 0.3). My final calculation is summarized in Theorem 0.1, which provides a relatively nice expression of γ(α). Recall that any α1 can be written uniquely as α=ωβq+ρ where β is (following Kunen’s terminology) the “logarithm in base ω of α” (that we will denote logωα for αω) and q,ρ are the quotient and remainder of the Euclidean division of α by ωβ. Alternatively, this can be seen from Cantor’s Normal Form: β and q are the exponent and coefficient of the largest term while ρ is the sum of terms of smaller exponents.

Theorem 0.1.

For all ordinal α, we denote γ(α) the order-type of the canonical ordering of α×α. Then γ can be calculated as follows:

  1. (1)

    Finite Ordinals: For any n<ω we have

      γ(n)=n2  
  2. (2)

    Limit Ordinals: For any limit ordinal α,

    1. (a)

      If ωlogω(logω(α)) does not divide logω(α) then

        γ(α)=ωlogω(α)α  
    2. (b)

      Otherwise, we write α=ωlogω(α)n+ρ for some n1. If n2 then

        γ(α)=ωlogω(α)(ωlogω(α)(n-1)+ρ)  

      (like the first case but we “decrement n in the second factor”)

    3. (c)

      Otherwise, α=ωlogω(α)+ρ and we write logω(α)=ωlogω(logω(α))m for some m1. We have

        γ(α)=ωlogω(α)(ωωlogω(logω(α))(m-1)+ρ)  

      (like the first case but we “decrement m in the second factor”)

  3. (3)

    Infinite Successor Ordinals: For any limit ordinal α and 1n<ω we have

      γ(α+n)=γ(α)+α2n+n  

    where γ(α) is determined as in the previous point.

Proof.

In a future blog post ;-) ∎

From this theorem, we deduce several corollaries:

Corollary 0.2.

For any ordinal α, we have

  αγ(α)ωlogω(α)(α-r)+α2rα(α+r)  

where r=αmodω is the remainder in the Euclidean division of α by ω (i.e. the constant term in the Cantor Normal Form).

Proof.

The “Limit Ordinals” case is r=0 i.e. αγ(α)ωlogω(α)α, which is readily seen by the previous theorem. Then we deduce for the “Infinite Successor Ordinals” case: γ(α+n)=γ(α)+α2n+nωlogω(α)α+(α+n)2n where logω(α+n)=logω(α) and n=(α+nmodω). Since ωlogω(α)α we can write ωlogω(α)(α-r)+α2rα(α-r+2r)=α(α+r). ∎

Hence the order type of the canonical ordering of α×α (i.e. γ(α)α(α+ω)) is never significantly bigger than the one of the standard lexical ordering (i.e. α2), and even never larger for limit ordinals. Moreover, for many ordinals α the canonical ordering is of order type α:

Corollary 0.3.

The fixed points of γ are 0,1 and ωωα for all ordinals α.

Proof.

For the “Finite Ordinals” case, we have γ(n)=n2=n iff n=0 or n=1. For the “Infinite Successor Ordinals” case, we have α2n>α if n1 so γ(α+n)>α+n. Now we look at the three subcases of the “Limit Ordinals” case. For the first one, we have logω(α)1 and so ωlogω(α)αωα>α. For the second one, we note that logω(α)2>logω(α) and so ωlogω(α)2>α (compare the Cantor Normal Form). Since n-11 by assumption, we have γ(α)>α. Similarly in the third case, if we expand the parenthesis the first term is ω raised to the power ωlogω(logω(α))(2m-1) which is stricly greater than logω(α)=ωlogω(logω(α))m if m2. Now if m=1, we obtain γ(α)=ωlogω(α)+ωlogω(α)ρ and α=ωlogω(α)+ρ. Hence γ(α)>α if ρ>0 and γ(α)=α if ρ=0. Finally for αω, γ(α)=α iff α=ωωlogω(logω(α)) iff α=ωωβ for some ordinal β. ∎

Finally, now that we know that infinite fixed points of γ are of the form α=ωωβ we only need to verify that infinite cardinals κ are of this form to prove that |κ×κ|=κ. This provides an alternative (less straightforward) proof of Theorem 3.5 from Jech’s Set Theory book.

Corollary 0.4.

Any infinite cardinal κ is a fixed point of γ. Hence for any infinite cardinal κ1,κ2 we have

  κ1+κ2=κ1κ2=max(κ1,κ2)  
Proof.

For any cardinal infinite cardinal μ that is a fixed point of γ, the canonical well-ordering provides a bijection between μ and μ×μ i.e. μ2=μ. Hence if μ1μ2 are two fixed points, we have

  μ2μ1+μ2μ1μ2μ22=μ2  

Suppose that there is a cardinal κ which is not a fixed point of γ and consider the smallest one. Then any infinite cardinal below κ is a fixed point of γ and the previous equality is still true below κ.

Suppose κ>ωlogωκ and write κ=ωlogωκ+ρ where ρ<κ corresponds to the remaining terms in Cantor Normal Form. Then 0μ1=|ωlogωκ|<κ, μ2=|ρ|<κ and μ1+μ2=κ. But the two first relations imply μ1+μ2=max(μ1,μ2)<κ which contradicts the third one. Hence κ=ωlogωκ.

Now suppose logωκ>ωlogωlogωκ and write logωκ=ωlogωκ+ρ where ρ<logωκ corresponds to the remaining terms in Cantor Normal Form. Then we have

  κ=ωlogωκ=ωωlogωlogωκωρ  

where ωωlogωlogωκ<ωlogωκ=κ and ωρ<ωlogωκ=κ since αωα is strictly increasing. Then 0μ1=|ωωlogωlogωκ|<κ, μ2=|ωρ|<κ and μ1μ2=κ. But again, the two first relations imply μ1μ2=max(μ1,μ2)<κ which contradicts the third one.

Finally, κ=ωωlogωlogωκ and so is a fixed point of γ, a contradiction. Hence all the infinite cardinals are fixed point of γ and so the property stated at the beginning is true for arbitrary infinite cardinals μ1,μ2. ∎

Wednesday, July 24 2013

Exercises in Set Theory: Large Cardinals

New solutions to exercises from Thomas Jech’s book “Set Theory”:

Saturday, June 1 2013

Exercises in Set Theory: Iterated Forcing and Martin’s Axiom

New solutions to exercises from Thomas Jech’s book “Set Theory”:

Last November, I tried to provide some details of the proof given in chapter 7, regarding the fact that the continuum hypothesis implies the existence of a Ramsey ultrafilter. Peter Krautzberger pointed out that the proof could probably work assuming only Martin’s Axiom. This was indeed proved by Booth in 1970 and the missing argument is actually given in exercise 16.16. For completeness, I copy the details on this blog post.

Remember that the proof involves contructing a sequence (Xα)α<20{(X_{\alpha})}_{{\alpha<2^{{\aleph_{0}}}}} of infinite subsets of ω\omega. The induction hypothesis is that at step α<20\alpha<2^{{\aleph_{0}}}, for all β1,β2<α\beta_{1},\beta_{2}<\alpha we have β1<β2Xβ2Xβ1\beta_{1}<\beta_{2}\implies X_{{\beta_{2}}}\setminus X_{{\beta_{1}}} is finite. It is then easy to show the result for the successor step, since the construction satisfies Xα+1XαX_{{\alpha+1}}\subseteq X_{\alpha}. However at limit step, to ensure that XαXβX_{\alpha}\setminus X_{\beta} is finite for all β<α\beta<\alpha, the proof relies on the continunum hypothesis. This is the only place where it is used.

Assume instead Martin’s Axiom and consider a limit step α<20\alpha<2^{{\aleph_{0}}}. Define the forcing notion Pα={(s,F):s[ω]<ω,F[α]<ω}P_{\alpha}=\{(s,F):s\in{[\omega]}^{{<\omega}},F\in{[\alpha]}^{{<\omega}}\} and (s,F)(s,F)(s^{{\prime}},F^{{\prime}})\leq(s,F) iff sss\subseteq s^{{\prime}}, FFF\subseteq F^{{\prime}} and ssXβs^{{\prime}}\setminus s\subseteq X_{\beta} for all βF\beta\in F. It is clear that the relation is reflexive and antisymmetric. The transitivity is almost obvious, just note that if (s3,F3)(s2,F2)(s_{3},F_{3})\leq(s_{2},F_{2}) and (s2,F2)(s1,F1)(s_{2},F_{2})\leq(s_{1},F_{1}) then for all βF1F2\beta\in F_{1}\subseteq F_{2} we have s3s1s3s2s2s1Xβs_{3}\setminus s_{1}\subseteq s_{3}\setminus s_{2}\cup s_{2}\setminus s_{1}% \subseteq X_{\beta}.

The forcing notion satisfies ccc or even property (K): since [ω]<ω{[\omega]}^{{<\omega}} is countable, for any uncountable subset WW there is t[ω]<ωt\in{[\omega]}^{{<\omega}} such that Z={(s,F)W:s=t}Z=\{(s,F)\in W:s=t\} is uncountable. Then any (t,F1),(t,F2)Z(t,F_{1}),(t,F_{2})\in Z have a common refinement (t,F1F2)(t,F_{1}\cup F_{2}).

For all n<ωn<\omega, define Dn={(s,F):|s|n}D_{n}=\{(s,F):|s|\geq n\}. Let β1>β2>>βk\beta_{1}>\beta_{2}>...>\beta_{k} the elements of FF. We show by induction on 1mk1\leq m\leq k that i=1mXβi\bigcap_{{i=1}}^{m}X_{{\beta_{i}}} is infinite. This is true for m=1m=1 by assumption. If it is true for m-1m-1 then

i=1m-1Xβi=i=1mXβii=1mXβiXβm\bigcap_{{i=1}}^{{m-1}}X_{{\beta_{i}}}=\bigcap_{{i=1}}^{m}X_{{\beta_{i}}}\cup% \bigcap_{{i=1}}^{m}X_{{\beta_{i}}}\setminus X_{{\beta_{m}}}

The left hand side is infinite by induction hypothesis. The second term of the right hand side is included in Xβ1XβmX_{{\beta_{1}}}\setminus X_{{\beta_{m}}} and thus is finite. Hence the first term is infinite and the result is true for mm. Finally, for m=km=k, we get that βFXβ\bigcap_{{\beta\in F}}X_{\beta} is infinite. Pick x1,x2,,xnx_{1},x_{2},...,x_{n} distinct elements from that set and define (s,F)=(s{x1,xn},F)(s^{{\prime}},F^{{\prime}})=(s\cup\{x_{1},...x_{n}\},F). We have (s,F)Dn(s^{{\prime}},F^{{\prime}})\in D_{n}, sss\subseteq s^{{\prime}}, FFF\subseteq F^{{\prime}} and for all βF\beta\in F, ss={x1,xn}Xβs^{{\prime}}\setminus s=\{x_{1},...x_{n}\}\subseteq X_{\beta}. This shows that DnD_{n} is dense. For each β<α\beta<\alpha, the set Eβ={(s,F):βF}E_{\beta}=\{(s,F):\beta\in F\} is also dense: for any (s,F)(s,F) consider (s,F)=(s,F{β})(s^{{\prime}},F^{{\prime}})=(s,F\cup\{\beta\}).

By Martin’s Axiom there is a generic filter GG for the family {Dn:n<ω}{Eβ:β<α}\{D_{n}:n<\omega\}\cup\{E_{\beta}:\beta<\alpha\} of size |α|<20|\alpha|<2^{{\aleph_{0}}}. Let Xα={n<ω:(s,F)G,ns}X_{\alpha}=\{n<\omega:\exists(s,F)\in G,n\in s\}. For all n<ωn<\omega, there is (s,F)GDn(s,F)\in G\cap D_{n} and so |Xα||s|n|X_{\alpha}|\geq|s|\geq n. Hence XαX_{\alpha} is infinite. Let β<α\beta<\alpha and (s1,F1)GEβ(s_{1},F_{1})\in G\cap E_{\beta}. For any xXαx\in X_{\alpha}, there is (s2,F2)G(s_{2},F_{2})\in G such that xs2x\in s_{2}. Hence there is (s3,F3)G(s_{3},F_{3})\in G a refinement of (s1,F2),(s2,F2)(s_{1},F_{2}),(s_{2},F_{2}). We have xs2s3x\in s_{2}\subseteq s_{3} and s3s1Xβs_{3}\subseteq s_{1}\subseteq X_{\beta}. Hence XαXβs1X_{\alpha}\setminus X_{\beta}\subseteq s_{1} is finite and the induction hypothesis is true at step α\alpha.

- page 1 of 4