Blog de Frédéric

To content | To menu | To search

Tag - set theory

Entries feed - Comments feed

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

  2. (2)

    Limit Ordinals: For any limit ordinal α,

    1. (a)

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

    2. (b)

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


      (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


      (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


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


In a future blog post ;-) ∎

From this theorem, we deduce several corollaries:

Corollary 0.2.

For any ordinal α, we have


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


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


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


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


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


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.

Friday, May 3 2013

Exercises in Set Theory: Applications of Forcing

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

The exercises from this chapter was a good opportunity to play a bit more with the forcing method. Exercise 15.15 seemed a straightforward generalization of Easton’s forcing but turned out to be a bit technical. I realized that the forcing notion used in that exercise provides a result in ZFC (a bit like Exercises 15.31 and 15.32 allow to prove some theorems on Boolean Algebras by Forcing).

Remember that 0=0,1=20,2=21,ω=supn,,α+1=2α,\beth_{0}=\aleph_{0},\beth_{1}=2^{{\beth_{0}}},\beth_{2}=2^{{\beth_{1}}}...,% \beth_{\omega}=\sup\beth_{n},...,\beth_{{\alpha+1}}=2^{{\beth_{{\alpha}}}},... is the normal sequence built by application of the continuum function at successor step. One may wonder: is α\beth_{\alpha} regular?

First consider the case where α\alpha is limit. The case α=0\alpha=0 is clear (0=0\beth_{0}=\aleph_{0} is regular) so assume α>0\alpha>0. If α\alpha is an inacessible cardinal, it is easy to prove by induction that for all β<α\beta<\alpha we have β<α\beth_{\beta}<\alpha: at step β=0\beta=0 we use that α\alpha is uncountable, at successor step that it is strong limit and at limit step that it is regular. Hence α=α\beth_{\alpha}=\alpha and so is regular. If α\alpha is not a cardinal then cf(α)=cf(α)|α|<αα\operatorname{cf}(\beth_{\alpha})=\operatorname{cf}(\alpha)\leq|\alpha|<\alpha% \leq\beth_{\alpha} so α\beth_{\alpha} is singular. If α\alpha is a cardinal but not strong limit then there is β<α\beta<\alpha such that 2βα2^{\beta}\geq\alpha. Since β<αα\beta<\alpha\leq\beth_{\alpha} there is γ<α\gamma<\alpha such that γ>β\beth_{\gamma}>\beta. Then αγ+1=2γ>2βα\beth_{\alpha}\geq\beth_{{\gamma+1}}=2^{{\beth_{\gamma}}}>2^{\beta}\geq\alpha. So cf(α)=cf(α)α<α\operatorname{cf}(\beth_{\alpha})=\operatorname{cf}(\alpha)\leq\alpha<\beth_{\alpha} and α\beth_{\alpha} is singular. Finally, if α\alpha is a singular cardinal, then again cf(α)=cf(α)<αα\operatorname{cf}(\beth_{\alpha})=\operatorname{cf}(\alpha)<\alpha\leq\beth_{\alpha} and α\beth_{\alpha} is singular.

What about the successor case i.e. α+1\beth_{{\alpha+1}}? By Corollary 5.3 from Thomas Jech’s book any α\alpha, we can show that α+1\aleph_{{\alpha+1}} is a regular cardinal. The Generalized Continuum Hypothesis says that α,α=α\forall\alpha,\aleph_{\alpha}=\beth_{\alpha}. Since it holds in LL we can not prove in ZFC that for some α\alpha, α+1\beth_{{\alpha+1}} is singular.

The generic extension V[G]VV[G]\supseteq V constructed in exercise 15.15 satisfies GCH and so it’s another way to show that α+1\beth_{{\alpha+1}} can not be proved to be singular for some α\alpha. However, it provides a better result: by construction, V[G]α+1V=(αV)+V[G]\models\beth_{{\alpha+1}}^{V}={(\beth_{{\alpha}}^{V})}^{+} and so V[G][α+1V is a regular cardinal]V[G]\models[\beth_{{\alpha+1}}^{V}\text{ is a regular cardinal}]. Since ‘‘regular cardinal’’ is a Π1\Pi_{1} notion we deduce that α+1\beth_{{\alpha+1}} is a regular cardinal in VV.

Now the question is: is there any ‘‘elementary’’ proof of the fact that α+1\beth_{{\alpha+1}} is regular i.e. without using the forcing method?

--update: of course, I forgot to mention that by König’s theorem, 2α=α+1cf(α+1)=cf(2α)(α)+2^{{\beth_{{\alpha}}}}=\beth_{{\alpha+1}}\geq\operatorname{cf}(\beth_{{\alpha+% 1}})=\operatorname{cf}(2^{{\beth_{{\alpha}}}})\geq{(\beth_{{\alpha}})}^{+} so the singularity of α+1\beth_{{\alpha+1}} would imply the failure of the continuum hypothesis for the cardinal α\beth_{\alpha} and this is not provable in ZFC.

Thursday, April 4 2013

Suslin’s Problem

In a previous blog post, I mentioned the classical independence results regarding the Axiom of Choice and the Generalized Continuum Hypothesis. Here, I’m going to talk about a slightly less known problem that is undecidable in ZFC. It is about a characterization of the set of reals \mathbb{R} and its formulation does not involve at all cardinal arithmetics or the axiom of choice, but only properties of ordered sets.

First, the set of rationals (, <)(\mathbb{Q},<) is well-known to be countable. It is linearly ordered (for any x,yx,y\in\mathbb{Q} either x<yx<y or y<xy<x), unbounded (for any xx\in\mathbb{Q} there is y1,y2y_{1},y_{2}\in\mathbb{Q} such that x<y1x<y_{1} and y2<xy_{2}<x) and dense (for any x,yx,y\in\mathbb{Q} if x<yx<y we can find zz\in\mathbb{Q} such that x<z<yx<z<y). It turns out that \mathbb{Q} can be characterized by these order properties:

Lemma 0.1.

Let (P, <)(P,<) be a countable, dense, unbounded linearly ordered set. Then (P, <)(P,<) is isomorphic to (, <)(\mathbb{Q},<).


Let P={pn:n}P=\{p_{n}:n\in\mathbb{N}\} and ={qn:n}\mathbb{Q}=\{q_{n}:n\in\mathbb{N}\} be enumerations of PP and \mathbb{Q}. We shall construct by induction a sequence f0f1f2f_{0}\subseteq f_{1}\subseteq f_{2}\subseteq... of functions such that for all nn\in\mathbb{N}, dom(fn){pi:i<n}\operatorname{dom}(f_{n})\supseteq\{p_{i}:i<n\}, ran(fn){qi:i<n}\operatorname{ran}(f_{n})\supseteq\{q_{i}:i<n\} and x,ydom(fn),x<yf(x)<f(y)\forall x,y\in\operatorname{dom}(f_{n}),x<y\Leftrightarrow f(x)<f(y). Then f=nfnf=\bigcup_{{n\in\mathbb{N}}}f_{n} is a function: if (x,y),(x,z)f(x,y),(x,z)\in f then there is nn large enough such that (x,y),(x,z)fn(x,y),(x,z)\in f_{n} and since fnf_{n} is a function y=zy=z. Moreover, dom(f)=ndom(fn)=P\operatorname{dom}(f)=\bigcup_{{n\in\mathbb{N}}}\operatorname{dom}(f_{n})=P and ran(f)=nran(fn)=\operatorname{ran}(f)=\bigcup_{{n\in\mathbb{N}}}\operatorname{ran}(f_{n})=% \mathbb{Q}. Finally, for any x,yPx,y\in P there is nn large enough such that x,ydom(fn)x,y\in\operatorname{dom}(f_{n}) and so x<yfn(x)<fn(y)f(x)<f(y)x<y\Leftrightarrow f_{n}(x)<f_{n}(y)\Leftrightarrow f(x)<f(y). Hence ff is an isomorphism between (P, <)(P,<) and (, <)(\mathbb{Q},<).

Thus let f0=f_{0}=\emptyset. If fnf_{n} is defined, we construct fn+1fnf_{{n+1}}\supseteq f_{n} as follows. Suppose pndom(fn)p_{n}\notin\operatorname{dom}(f_{n}). If i<n,pn>pi\forall i<n,p_{n}>p_{i} then because \mathbb{Q} is unbounded we can consider the least n0n_{0} such that i<n,f(pi)<qn0\forall i<n,f(p_{i})<q_{{n_{0}}} and set fn+1(pn)=qn0f_{{n+1}}(p_{n})=q_{{n_{0}}}. Similarly if i<n,pn<pi\forall i<n,p_{n}<p_{i}. Otherwise, let i1,i2<ni_{1},i_{2}<n such that pi1<pn<pi2p_{{i_{1}}}<p_{n}<p_{{i_{2}}} with pi1,pi2p_{{i_{1}}},p_{{i_{2}}} respectively the largest and smallest possible. Because \mathbb{Q} is dense we can consider the least n0n_{0} such that fn(pi1)<qn0<fn(pi2)f_{{n}}(p_{{i_{1}}})<q_{{n_{0}}}<f_{{n}}(p_{{i_{2}}}) and again set fn+1(pn)=qn0f_{{n+1}}(p_{n})=q_{{n_{0}}}. Similarly, if nn0n\neq n_{0} we use the fact that PP is unbounded and dense to find m0n+1m_{0}\geq n+1 that allows to define fn+1(pm0)=qnf_{{n+1}}(p_{{m_{0}}})=q_{n} and ensures fn+1f_{{n+1}} is order-preserving.

We now notice that \mathbb{R} is linearly ordered, unbounded, dense and has the least upper-bound property (that is any nonempty bounded subset of \mathbb{R} has a least upper-bound). Moreover, the subset \mathbb{Q} is countable and dense in \mathbb{R} (that is for any x,yx,y\in\mathbb{R} such that x<yx<y we can find zz\in\mathbb{Q} such that x<z<yx<z<y). Using the previous lemma, we deduce again that these order properties give a characterization of the set of reals:

Theorem 0.1.

Let (R, <)(R,<) be an unbounded, dense and linearly ordered set with the least upper-bound property. Suppose that RR has a dense countable subset PP. Then (R, <)(R,<) is isomorphic to (, <)(\mathbb{R},<).


PP is countable by assumption and since PRP\subseteq R it is also linearly ordered. If x,yPRx,y\in P\subseteq R and x<yx<y then by density of PP in RR there is zPz\in P such that x<z<yx<z<y. So PP is actually dense. Similarly, if xPRx\in P\subseteq R then since RR is unbounded there is y1,y2Ry_{1},y_{2}\in R such that y2<x<y2y_{2}<x<y_{2} and again by density of PP in RR we can find z1,z2Pz_{1},z_{2}\in P such that y2<z2<x<z1<y1y_{2}<z_{2}<x<z_{1}<y_{1}. So PP is unbounded. By the previous lemma, there is an isomorphism of ordered sets f:Pf:P\rightarrow\mathbb{Q}.

We define for all xRx\in R, f(x)=supyP;y<xf(y)f_{\star}(x)=\sup_{{y\in P;y<x}}f(y). Because PP is dense in RR and \mathbb{R} has the least upper bound property this is well-defined. If xPx\in P then for all y<xy<x such that yPy\in P we have f(y)<f(x)f(y)<f(x) and so f(x)f(x)f_{\star}(x)\leq f(x). If f(x)<f(x)f_{\star}(x)<f(x) we could find (by density of \mathbb{Q} in \mathbb{R}) an element qq\in\mathbb{Q} such that f(x)<q<f(x)f_{\star}(x)<q<f(x). For p=f-1(q)p=f^{{-1}}(q) we get p<xp<x and so q=f(p)f(x)q=f(p)\leq f_{\star}(x). A contradiction. So f|P=f{f_{\star}}_{{|P}}=f.

Let x,yRx,y\in R such that x<yx<y. Because ff is increasing we get f(x)f(y)f_{\star}(x)\leq f_{\star}(y). By density of PP in RR we can find p1,p2Pp_{1},p_{2}\in P such that x<p1<p2<yx<p_{1}<p_{2}<y. Again, we get f(x)f(p1)=p1f_{\star}(x)\leq f_{\star}(p_{1})=p_{1} and p2=f(p2)f(y)p_{2}=f_{\star}(p_{2})\leq f_{\star}(y). Hence we actually have f(x)<f(y)f_{\star}(x)<f_{\star}(y). In particular, ff_{\star} is one-to-one.

We shall prove that ff_{\star} is surjective. Of course f(P)=f(P)=f_{\star}(P)=f(P)=\mathbb{Q} so let’s consider rr\in\mathbb{R}\setminus\mathbb{Q}. Define x=supq<r:qf-1(q)Rx=\sup_{{q<r:q\in\mathbb{Q}}}f^{{-1}}(q)\in R. This is well-defined because \mathbb{Q} is dense in \mathbb{R} and RR has the the least upper bound property. Then for all q<rq<r such that qq\in\mathbb{Q} we have f-1(q)xf^{{-1}}(q)\leq x by definition. By density of \mathbb{Q} in \mathbb{R} we can actually find qq^{{\prime}}\in\mathbb{Q} such that q<q<rq<q^{{\prime}}<r and so f-1(q)<f-1(q)xf^{{-1}}(q)<f^{{-1}}(q^{{\prime}})\leq x. We have x>f-1(q)Px>f^{{-1}}(q)\in P and so f(x)f(f-1(q))=qf_{\star}(x)\geq f(f^{{-1}}(q))=q. Hence f(x)rf_{\star}(x)\geq r. Suppose that r<f(x)r<f_{\star}(x) and consider (by density of \mathbb{Q} in \mathbb{R}) some qq\in\mathbb{Q} such that r<q<f(x)r<q<f_{\star}(x) and let p=f-1(q)p=f^{{-1}}(q). If p<xp<x then there is qq^{{\prime}}\in\mathbb{Q}, q<rq^{{\prime}}<r, such that pf-1(q)p\leq f^{{-1}}(q^{{\prime}}). Then r<q=f(p)q<rr<q=f(p)\leq q^{{\prime}}<r a contradiction. If instead pxp\geq x then f(x)f(p)=q<f(x)f_{{\star}}(x)\leq f_{{\star}}(p)=q<f_{\star}(x) which is again a contradiction.

Finally, let x,yRx,y\in R such that f(x)<f(y)f_{\star}(x)<f_{\star}(y). Because RR is totally ordered either x<yx<y or y<xy<x. But the latter is impossible since we saw above that it implied f(y)<f(x)f_{\star}(y)<f_{\star}(x). Hence ff_{\star} is an isomorphism between (R, <)(R,<) and (, <)(\mathbb{R},<).

Now consider a totally ordered set (R, <)(R,<). For any a,ba,b we define the open interval (a,b)={xR:a<x<b}(a,b)=\{x\in R:a<x<b\}. Suppose P={pn:n}P=\{p_{n}:n\in\mathbb{N}\} is a dense subset of RR. If ((ai,bi))iI{\left((a_{i},b_{i})\right)}_{{i\in I}} is a family of pairwise disjoint open intervals then we can associate to any (ai,bi)(a_{i},b_{i}) the least nin_{i}\in\mathbb{N} such that pni(ai,bi)p_{{n_{i}}}\in(a_{i},b_{i}) (by density of PP in RR). Since the family is disjoint the function inii\mapsto n_{i} obtained is one-to-one and so the family is at most countable. One naturally wonders what happens if we replace in theorem 0.1 the existence of a countable dense subset by this weaker property on open intervals:

Problem 0.1 (Suslin’s Problem).

Let (R, <)(R,<) be an unbounded, dense and linearly ordered set with the least upper-bound property. Suppose that any family of disjoint open intervals in RR is at most countable. Is (R, <)(R,<) isomorphic to (, <)(\mathbb{R},<)?

We have seen how this problem arises from a natural generalization of a characterization of \mathbb{R}. We note that we did not use the Axiom of Choice in the above analysis and that the problem can be expressed using only definitions on ordered sets. However, in order to answer Suslin’s Problem we will need to introduce more concepts. We will assume familiarity with basic notions of Set Theory like ordinals, cardinals or the Axiom of Choice. The first five chapters of Thomas Jech’s book ‘‘Set Theory’’ should be enough. In addition, we will rely on the axiom MA1\mathrm{MA}_{{\aleph_{1}}} and on the Diamond Principle \Diamond, that we define here:

Definition 0.1 (Martin’s Axiom 1\aleph_{1}, Diamond Principle).

MA1\mathrm{MA}_{{\aleph_{1}}} and \Diamond are defined as follows:

  • Let (P, <)(P,<) be a partially ordered set. Two elements x,yx,y are compatible if there is zz such that zxz\leq x and zyz\leq y. Note that comparable implies compatible.

  • DD is dense in PP if for any pPp\in P there is dDd\in D such that dpd\leq p.

  • GPG\subseteq P is a filter if:

    • GG\neq\emptyset

    • For any p,qPp,q\in P such that pqp\leq q and pGp\in G we have qGq\in G

    • Any p,qGp,q\in G there is rGr\in G such that rp,qr\leq p,q.

  • MA1\mathrm{MA}_{{\aleph_{1}}}: Let (P, <)(P,<) be a partially ordered set such that any subset of paiwise incompatible elements of PP is at most countable. Then for any family of at most 1\aleph_{1} dense subsets there is a filter GPG\subseteq P that has a nonempty intersection with each element of this family.

  • A set Cω1C\subseteq\omega_{1} is closed unbounded if

    • It is unbounded in the sense that for any α<ω1\alpha<\omega_{1} there is βC\beta\in C such that α<β\alpha<\beta

    • It is closed for the order topology, or equivalently if for any γ<ω1\gamma<\omega_{1} and any γ\gamma-sequence α0<α1<<αξ<\alpha_{0}<\alpha_{1}<...<\alpha_{\xi}<... of elements of CC, limξγαξ\lim_{{\xi\rightarrow\gamma}}\alpha_{\xi} is in CC.

  • A set Sω1S\subseteq\omega_{1} is stationary if for any CC closed unbounded, SCS\cap C\neq\emptyset.

  • \Diamond: There is an ω1\omega_{1}-sequence of sets SααS_{\alpha}\subseteq\alpha such that for every Xω1X\subseteq\omega_{1} the set {α<ω1:Xα=Sα}\{\alpha<\omega_{1}:X\cap\alpha=S_{\alpha}\} is stationary.

First we show that if MA1\mathrm{MA}_{{\aleph_{1}}} holds, then we get a positive answer to Suslin’s problem:

Theorem 0.2.

Assume Martin’s axiom MA1\mathrm{MA}_{{\aleph_{1}}} holds. Let (R, <)(R,<) be an unbounded, dense and linearly ordered set with the least upper-bound property. Suppose that any disjoint family of open intervals in RR is at most countable. Then (R, <)(R,<) is isomorphic to (, <)(\mathbb{R},<).


Suppose (R, <)(R,<) is not isomorphic to (, <)(\mathbb{R},<) and in particular does not have any countable dense subset (otherwise we could apply theorem 0.1). We define closed intervals IαRI_{\alpha}\subseteq R by induction on α<ω1\alpha<\omega_{1}. If Iβ=[aβ,bβ]I_{\beta}=[a_{\beta},b_{\beta}] is defined for all β<α\beta<\alpha then the set C={aβ:β<α}{bβ:β<α}C=\{a_{\beta}:\beta<\alpha\}\cup\{b_{\beta}:\beta<\alpha\} is countable and thus is not dense in RR. Then there is aα<bαa_{\alpha}<b_{\alpha} such that Iα=[aα,bα]I_{\alpha}=[a_{\alpha},b_{\alpha}] is disjoint from CC. We define the set S={Iα,α<ω1}S=\{I_{\alpha},\alpha<\omega_{1}\}. Clearly, |S|=1|S|=\aleph_{1} and (S, )(S,\subsetneq) is partially ordered. We note that if β<α<ω1\beta<\alpha<\omega_{1} then by construction aβ,bβIαa_{\beta},b_{\beta}\notin I_{\alpha} and so either IαIβ=I_{\alpha}\cap I_{\beta}=\emptyset or IαIβI_{\alpha}\subsetneq I_{\beta}. In particular, comparable is the same as compatible in SS and any family of pairwise incomparable/incompatible elements of SS is a family of pairwise disjoint intervals of RR so at most countable.

Let α<ω1\alpha<\omega_{1} and define PIα={IS:IIα}P_{{I_{\alpha}}}=\{I\in S:I\supsetneq I_{\alpha}\}. Let XPIαX\subseteq P_{{I_{\alpha}}} nonempty. Let β\beta the least ordinal such that IβXI_{\beta}\in X. If IγXI_{\gamma}\in X then βγ\beta\leq\gamma and IγIβIαI_{\gamma}\cap I_{\beta}\supseteq I_{\alpha}\neq\emptyset. Hence by the previous remark IβIγI_{\beta}\supseteq I_{\gamma}. So PIαP_{{I_{\alpha}}} is well-ordered by \supseteq and we define o(Iα)o(I_{\alpha}) the order-type of PIαP_{{I_{\alpha}}}. We note that the set PIαP_{{I_{\alpha}}} can be enumerated by Iα1Iα2IαI_{{\alpha_{1}}}\supsetneq I_{{\alpha_{2}}}\supsetneq...\supsetneq I_{\alpha} for some αξα\alpha_{\xi}\leq\alpha and so o(Iα)<ω1o(I_{\alpha})<\omega_{1}. Moreover for any α,β<ω\alpha,\beta<\omega, if IαIβI_{{\alpha}}\supsetneq I_{{\beta}} then PIαP_{{I_{\alpha}}} is an initial segment of PIβP_{{I_{\beta}}} and so o(Iα)<o(Iβ)o(I_{\alpha})<o(I_{\beta}). Hence for each α<ω1\alpha<\omega_{1} the set Lα={IS:o(I)=α}L_{\alpha}=\{I\in S:o(I)=\alpha\} has pairwise incomparable elements and so is at most countable.

For any ISI\in S, define SI={JS:JI}S_{I}=\{J\in S:J\subseteq I\} and let T={IS:|SI|=1}T=\{I\in S:|S_{I}|=\aleph_{1}\}. Let α<ω1\alpha<\omega_{1} and suppose that LαT=L_{\alpha}\cap T=\emptyset. Then S=β<αLβILαSIS=\bigcup_{{\beta<\alpha}}L_{\beta}\cup\bigcup_{{I\in L_{\alpha}}}S_{I} and since the LβL_{\beta} are at most countable for β<ω1\beta<\omega_{1} and the SIS_{I} are at most countable for ILαI\in L_{\alpha} we would have SS at most countable, a contradiction. So for each α<ω1\alpha<\omega_{1}, there is ITLαI\in T\cap L_{\alpha} and in particular |T|=1|T|=\aleph_{1}. We note that if ITI\in T and JIJ\supseteq I then SISJS_{I}\subseteq S_{J} and so JTJ\in T. In particular, PI={JT:JI}P_{I}=\{J\in T:J\supsetneq I\} and thus without loss of generality we may assume that S=TS=T.

For any α<ω1\alpha<\omega_{1} let Dα={IDα:o(I)>α}D_{\alpha}=\{I\in D_{\alpha}:o(I)>\alpha\}. For any ISI\in S, |SI|=1|S_{I}|=\aleph_{1} and SI=(βαSILβ)SIDαS_{I}=\left(\bigcup_{{\beta\leq\alpha}}S_{I}\cap L_{\beta}\right)\cup S_{I}% \cap D_{\alpha}. The first term is at most countable and so the second is uncountable and a fortiori nonempty. So DαD_{\alpha} is a dense subset of SS.

Using MA1\mathrm{MA}_{{\aleph_{1}}}, we find GSG\subseteq S a filter that intersects each DαD_{\alpha}. By definition, elements of a filter are pairwise compatible and so pairwise comparable. Let us construct by induction on α<ω1\alpha<\omega_{1}, some sets JαGJ_{\alpha}\in G. If JβJ_{\beta} is constructed for any β<α\beta<\alpha then γ=supβ<αo(Jβ)<ω1\gamma=\sup_{{\beta<\alpha}}o(J_{\beta})<\omega_{1} and we can pick JαGDγJ_{\alpha}\in G\cap D_{\gamma}. We obtain a decreasing ω1\omega_{1}-sequence of intervals J0J1JαJ_{0}\supsetneq J_{1}\supsetneq...\supsetneq J_{\alpha}\supsetneq.... If Jα=[xα,yα]J_{\alpha}=[x_{\alpha},y_{\alpha}] then this gives an increasing sequence x0<x1<x2<<xα<x_{0}<x_{1}<x_{2}<...<x_{\alpha}<.... The sets (xα,xα+1)(x_{\alpha},x_{{\alpha+1}}) form an uncountable family of disjoint open intervals. A contradiction.

Finally, we show that the \Diamond principle provides a negative answer to Suslin’s problem:

Theorem 0.3.

Assume the \Diamond principle holds. Then there is a linearly ordered set (R, <)(R,<) not isomorphic to (, <)(\mathbb{R},<), unbounded, dense, that has the least upper-bound property and such that any family of disjoint open intervals is at most countable.


Let (Sα)α<ω1{(S_{\alpha})}_{{\alpha<\omega_{1}}} be a \Diamond-sequence. We first construct a partial ordering \prec of T=ω1T=\omega_{1}. We define for all 1α<ω11\leq\alpha<\omega_{1} an ordering (Tα, )(T_{\alpha},\prec) on initial segments Tαω1T_{\alpha}\subseteq\omega_{1} and obtain the ordering \prec on ω1=T=α<ω1Tα\omega_{1}=T=\bigcup_{{\alpha<\omega_{1}}}T_{\alpha}.

Each (Tα, )(T_{\alpha},\prec) will be a tree i.e. for any xx in the tree the set Px={y:yx}P_{x}=\{y:y\prec x\} is well-ordered. As in the proof of 0.2 we can define o(x)o(x) the order-type of PxP_{x}. The level α\alpha is the set of elements such that o(x)=αo(x)=\alpha. The height of a tree is defined as the supremium of the o(x)+1o(x)+1. In a tree, a branch is a maximal linearly ordered subset and an antichain a subset of pairwise incomparable elements. A branch is also well-ordered and so we can define its length as its order-type. TαT_{\alpha} is constructed such that its height is α\alpha and for each xTαx\in T_{\alpha} there is some yxy\succ x at each higher level less than α\alpha.

We let T1={0}T_{1}=\{0\}. If α\alpha is a limit ordinal then (Tα, )(T_{\alpha},\prec) is the union of (Tβ, )(T_{\beta},\prec) for β<α\beta<\alpha. If α=β+1\alpha=\beta+1 is a successor ordinal, then the highest level of TαT_{\alpha} is Lβ={xTα:o(x)=β}L_{\beta}=\{x\in T_{\alpha}:o(x)=\beta\}. Tα+1T_{{\alpha+1}} is obtained by adding 0\aleph_{0} immediate successors to each element of LβL_{\beta}. These successors are taken from ω1\omega_{1} in a way that Tα+1T_{{\alpha+1}} is an initial segment of ω1\omega_{1}.

Let α\alpha is a limit ordinal. Let A=SαA=S_{\alpha} if it is a maximal antichain in (Tα, )(T_{\alpha},\prec) and take AA an arbitrary maximal antichain of TαT_{\alpha} otherwise. Then for each tTαt\in T_{\alpha} there is aAa\in A such that either ata\prec t or tat\prec a. Let btb_{t} be a branch that contains a,ta,t. We construct (Tα+1, )(T_{{\alpha+1}},\prec) by adding for each branch btb_{t} some xbtx_{{b_{t}}} that is greater than all the elements of btb_{t}. We can choose btb_{t} in way that it contains an element of each level less than α\alpha and so o(xbt)=αo(x_{{b_{t}}})=\alpha and the height of Tα+1T_{{\alpha+1}} is α+1\alpha+1. We note that each tTα+1t\in T_{{\alpha+1}} is either in TαT_{\alpha} (so comparable with some element of AA) or greater than (a fortiori comparable with) one element of AA. So AA is an antichain in (Tα+1, )(T_{{\alpha+1}},\prec).

Now consider a maximal antichain AT=ω1A\subseteq T=\omega_{1} and CC the set of ordinals α<ω1\alpha<\omega_{1} such that ‘‘ATαA\cap T_{\alpha} is a maximal antichain in TαT_{\alpha} and Tα=αT_{\alpha}=\alpha’’. Let α0<α1<<αξ<\alpha_{0}<\alpha_{1}<...<\alpha_{\xi}<... (ξ<γ<ω1\xi<\gamma<\omega_{1}) be a sequence of elements in CC and consider the limit ordinal λ=limξ<γαξ\lambda=\lim_{{\xi<\gamma}}\alpha_{\xi}. By construction, Tλ=α<λTα=ξ<γTαξ=ξ<γαξ=λT_{\lambda}=\bigcup_{{\alpha<\lambda}}T_{\alpha}=\bigcup_{{\xi<\gamma}}T_{{% \alpha_{\xi}}}=\bigcup_{{\xi<\gamma}}\alpha_{\xi}=\lambda. If xTλx\in T_{\lambda}, there is ξ<γ\xi<\gamma such that xTαξx\in T_{{\alpha_{\xi}}} and so xx is comparable with some yATαξATλy\in A\cap T_{{\alpha_{\xi}}}\subseteq A\cap T_{\lambda}. So ATλA\cap T_{\lambda} is a maximal antichain in TλT_{\lambda}. Finally λC\lambda\in C and CC is closed.

We note that T1={0}1T_{1}=\{0\}\geq 1. If TααT_{\alpha}\geq\alpha then Tα+1T_{{\alpha+1}} is obtained by adding at least one element at the end of the initial segment TαT_{\alpha} and so Tα+1α+1T_{{\alpha+1}}\geq\alpha+1. Finally if λ>0\lambda>0 is limit and TααT_{\alpha}\geq\alpha for each α<λ\alpha<\lambda then Tλ=α<λTαsupα<λα=λT_{\lambda}=\bigcup_{{\alpha<\lambda}}T_{\alpha}\geq\sup_{{\alpha<\lambda}}% \alpha=\lambda. Moreover by definition, each TαT_{\alpha} is at most countable. Let’s come back to the closed set CC above. Let α0<ω1\alpha_{0}<\omega_{1} be arbitrary. For each n<ωn<\omega, we let α2n+1\alpha_{{2n+1}} be the limit of the sequence α0Tα0TTα0TTTα0\alpha_{0}\leq T_{{\alpha_{0}}}\leq T_{{T_{{\alpha_{0}}}}}\leq T_{{T_{{T_{{% \alpha_{0}}}}}}}.... By definition, Tα2n+1=ξ<α2n+1Tξ=α0Tα0TTα0=α2n+1T_{{\alpha_{{2n+1}}}}=\bigcup_{{\xi<\alpha_{{2n+1}}}}T_{\xi}=\alpha_{0}\cup T_% {{\alpha_{0}}}\cup T_{{T_{{\alpha_{0}}}}}...=\alpha_{{2n+1}}. Because AA is a maximal antichain in TT, for each xTα2n+1x\in T_{{\alpha_{{2n+1}}}} we can find some αxα2n+1\alpha_{x}\geq\alpha_{{2n+1}} and axAαxa_{x}\in A_{{\alpha_{x}}} that is comparable with xx. Because Tα2n+1T_{{\alpha_{{2n+1}}}} is countable we can define α2n+2=supxTα2n+1αx<ω1\alpha_{{2n+2}}=\sup_{{x\in T_{{\alpha_{{2n+1}}}}}}\alpha_{x}<\omega_{1}. Then any xTα2n+1x\in T_{{\alpha_{{2n+1}}}} is comparable with some element of axATα2n+2a_{x}\in A\cap T_{{\alpha_{{2n+2}}}}. Let λ=limn<ωαn\lambda=\lim_{{n<\omega}}\alpha_{n}. With the same method as to prove the fact that CC is closed, the equality λ=limn<ωα2n+1\lambda=\lim_{{n<\omega}}\alpha_{{2n+1}} shows that Tλ=λT_{\lambda}=\lambda while the equality λ=limn<ωα2n+2\lambda=\lim_{{n<\omega}}\alpha_{{2n+2}} shows that ATλA\cap T_{\lambda} is a maximal antichain in TλT_{\lambda}. So λC\lambda\in C and CC is closed unbounded.

Using the Diamond principle, {α<ω1:Aα=Sα}C\{\alpha<\omega_{1}:A\cap\alpha=S_{\alpha}\}\cap C\neq\emptyset. If α\alpha is in the intersection, then Sα=ATαS_{\alpha}=A\cap T_{\alpha} is a maximal antichain in TαT_{\alpha}. By construction, it is also a maximal antichain in Tα+1T_{{\alpha+1}}. Each element of aATα+1a\in A\cap T_{{\alpha+1}} is at level o(a)αo(a)\leq\alpha. Any tTα+1t\in T_{{\alpha+1}} is comparable with some element of ATα+1A\cap T_{{\alpha+1}}. Moreover, by contruction any tTTα+1t^{{\prime}}\in T\setminus T_{{\alpha+1}} has some predecessor tTα+1t\in T_{{\alpha+1}} at level α\alpha and there is aATα+1a\in A\cap T_{{\alpha+1}} that is comparable with tt. Necessarily, o(a)<o(t)=αo(a)<o(t)=\alpha and so atta\prec t\preceq t^{{\prime}}. Thus ATα+1A\cap T_{{\alpha+1}} is maximal in TT and A=ATα+1Tα+1A=A\cap T_{{\alpha+1}}\subseteq T_{{\alpha+1}} is at most countable.

Let BB be a branch in TT. It is clear that BB is nonempty. Actually it is infinite: otherwise there is some limit ordinal α>0\alpha>0 such that BTαB\subseteq T_{\alpha} and by construction we can find some ymaxBy\succ\max B contradicting the maximality of BB. By construction, each xTx\in T has infinitely many successors at the next level and so these successors are pairwise incomparable. Hence if xBx\in B then we can pick one zxBz_{x}\notin B among these succcessors. Let xyx\prec y be two elements of BB. Then o(zx)=o(x)+1>o(y)+1=o(zy)o(z_{x})=o(x)+1>o(y)+1=o(z_{y}) so zxzyz_{x}\preceq z_{y} is impossible. Suppose zyzxz_{y}\prec z_{x}. We also have xzxx\prec z_{x} by definition. If zyxz_{y}\preceq x then we would have zyBz_{y}\in B because BB is a branch. If xzyx\prec z_{y} we would get o(x)<o(zy)=o(y)+1o(x)o(x)<o(z_{y})=o(y)+1\leq o(x). Hence zx,zyz_{x},z_{y} are incomparable (in particular distinct) and the set {zx:xB}\{z_{x}:x\in B\} is an antichain in TT and so BB is countable.

Finally, we define SS the set of all branches of TT. By construction, each xTx\in T has countably many immediate successors and we order them as \mathbb{Q}. Let B1,B2B_{1},B_{2} be two branches and α\alpha the least level where they differ. The level 0 is T1={0}T_{1}=\{0\} so α>0\alpha>0. If α\alpha is limit then the restriction of the branches B1,B2B_{1},B_{2} to TαT_{\alpha} is the same branch bb and Tα+1T_{{\alpha+1}} has been contructed in a way that there is only one possible element at level α\alpha to extend this branch and this is a contradiction. So α\alpha is actually a successor ordinal β+1\beta+1. Hence if B1(α)B1B_{1}(\alpha)\in B_{1} and B2(α)B2B_{2}(\alpha)\in B_{2} are the immediate successors of the point in B1B2B_{1}\cap B_{2} at level β\beta, we order B1,B2B_{1},B_{2} according to whether B1(α)<B2(α)B_{1}(\alpha)<B_{2}(\alpha) or B1(α)>B2(α)B_{1}(\alpha)>B_{2}(\alpha), using the \mathbb{Q}-isomorphic order we just defined. Clearly, this gives a linear ordering <S<_{S}. It is also unbounded: for any BSB\in S, if B(1)BB(1)\in B is the element at level 1 pick xx greater (or smaller) than for the \mathbb{Q}-isomorphic order on successors of B(0)=0B(0)=0 and consider a branch extending 0x0\prec x.

Now consider two branches B1<SB2B_{1}<_{S}B_{2}. Let α=β+1\alpha=\beta+1 be as above. We can find xx an immediate successor of B1(β)B_{1}(\beta) such that B1(α)<x<B2(α)B_{1}(\alpha)<x<B_{2}(\alpha) for the \mathbb{Q}-isomorphic order on immediate successors of B1(β)B_{1}(\beta). Let Ix={BS:xB}I_{x}=\{B\in S:x\in B\}. Any BIxB\in I_{x} contains {yT:yx}={yT:yB1(β)}={yT:yB2(β)}\{y\in T:y\prec x\}=\{y\in T:y\prec B_{1}(\beta)\}=\{y\in T:y\prec B_{2}(\beta)\}. Moreover x=B(α)x=B(\alpha) and so B1<B<B2B_{1}<B<B_{2}. IxI_{x} is nonempty (we can extend {yT:yx}\{y\in T:y\preceq x\} to a maximal branch) and so SS is dense. If IxIy=I_{x}\cap I_{y}=\emptyset then x,yx,y are incomparable. So from any collection of disjoint open intervals (B1i,B2i)iI{(B_{{1i}},B_{{2i}})}_{{i\in I}} we get an antichain {xi:iI}\{x_{i}:i\in I\} and so II is at most countable.

Let CC be a countable set of branches in TT. Since these branches are countable, we can find α<ω1\alpha<\omega_{1} larger than the length of any branches in CC. If xTx\in T is at level greater than α\alpha then for all BCB\in C, xBx\notin B so BIxB\notin I_{x}. Finally CIx=C\cap I_{x}=\emptyset and CC is not dense.

Now let RR be the Dedekind-MacNeille completion of SS. It is unbounded, linearly ordered, has the least upper-bound property and SS is dense in RR. Using the fact that SS is dense in RR we deduce that RR is dense. Similarly, if (ai,bi)iI{(a_{i},b_{i})}_{{i\in I}} is any collection of disjoint open intervals in RR we can find ci,diSc_{i},d_{i}\in S such that ai<ci<di<bia_{i}<c_{i}<d_{i}<b_{i}. Then (ci,di)iI{(c_{i},d_{i})}_{{i\in I}} is a collection of disjoint open intervals in SS and so II is at most countable.

Finally, it remains to prove that RR is not isomorphic to \mathbb{R} and it suffices to show that RR does not have any countable dense subset CC. If CC is a countable subset of RR, then for any elements a<ba<b in CC we pick cSc\in S such that a<c<ba<c<b. This gives a countable subset CC^{{\prime}} of SS. If a<ba<b are elements of SS, we can find c,dCc,d\in C such that a<c<d<ba<c<d<b and so eCe\in C^{{\prime}} such that a<c<e<d<ba<c<e<d<b. Thus CC^{{\prime}} would be a countable dense subset of SS. A contradiction.

The \Diamond principle holds in the model LL of constructible sets. Using iterated forcing, we can construct a model of ZFC in which MA1\mathrm{MA}_{{\aleph_{1}}} holds. Using theorems 0.2 and 0.3 we deduce that both the positive and negative answers to Suslin’s problem are consistent with ZFC and so Suslin’s problem is undecidable in ZFC. It’s remarkable that a problem that only involves linearly ordered set can be solved using sophisticated methods from Set Theory. The above proofs follow chapters 4, 9, 15 and 16 from Thomas Jech’s book ‘‘Set Theory’’. In particular:

  • Lemma 0.1 and theorem 0.1 are based on the sketch given in theorem 4.3.

  • Theorem 0.2 is based on the proofs of theorem 16.16 and lemma 9.14 (a).

  • Theorem 0.3 is based on the proofs of lemma 15.24, lemma 15.25, theorem 15.26, lemma 15.27 and lemma 9.14 (b).

  • Theorem 0.2 implicitely uses theorem 4.4 about the Dedekind-MacNeille completion of a dense unbounded linearly ordered.

  • In addition, theorem 0.2 also contains the proof of lemma 8.2 (the intersection of two closed unbounded sets is closed unbounded) the solutions to exercise 2.7 (any normal sequence has arbitrarily large fixed points) and exercise 9.7 (if all the antichains of a normal ω1\omega_{1}-tree are at most countable then so are its branches).

  • Finally, \Diamond and MA1\mathrm{MA}_{{\aleph_{1}}} are proved to be consistent with ZFC in theorems 13.21 and 16.13.

- page 1 of 3