Suslin’s Problem

04 Apr 2013

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,y\in\mathbb{Q}$ either $x<y$ or $y<x$), unbounded (for any $x\in\mathbb{Q}$ there is $y_{1},y_{2}\in\mathbb{Q}$ such that $x<y_{1}$ and $y_{2}<x$) and dense (for any $x,y\in\mathbb{Q}$ if $x<y$ we can find $z\in\mathbb{Q}$ such that $x<z<y$). It turns out that $\mathbb{Q}$ can be characterized by these order properties:

Lemma 0.1.

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

Proof.

Let $P=\{p_{n}:n\in\mathbb{N}\}$ and $\mathbb{Q}=\{q_{n}:n\in\mathbb{N}\}$ be enumerations of $P$ and $\mathbb{Q}$. We shall construct by induction a sequence $f_{0}\subseteq f_{1}\subseteq f_{2}\subseteq...$ of functions such that for all $n\in\mathbb{N}$, $\operatorname{dom}(f_{n})\supseteq\{p_{i}:i<n\}$, $\operatorname{ran}(f_{n})\supseteq\{q_{i}:i<n\}$ and $\forall x,y\in\operatorname{dom}(f_{n}),x<y\Leftrightarrow f(x)<f(y)$. Then $f=\bigcup_{n\in\mathbb{N}}f_{n}$ is a function: if $(x,y),(x,z)\in f$ then there is $n$ large enough such that $(x,y),(x,z)\in f_{n}$ and since $f_{n}$ is a function $y=z$. Moreover, $\operatorname{dom}(f)=\bigcup_{n\in\mathbb{N}}\operatorname{dom}(f_{n})=P$ and $\operatorname{ran}(f)=\bigcup_{n\in\mathbb{N}}\operatorname{ran}(f_{n})= \mathbb{Q}$. Finally, for any $x,y\in P$ there is $n$ large enough such that $x,y\in\operatorname{dom}(f_{n})$ and so $x<y\Leftrightarrow f_{n}(x)<f_{n}(y)\Leftrightarrow f(x)<f(y)$. Hence $f$ is an isomorphism between $(P,<)$ and $(\mathbb{Q},<)$.

Thus let $f_{0}=\emptyset$. If $f_{n}$ is defined, we construct $f_{n+1}\supseteq f_{n}$ as follows. Suppose $p_{n}\notin\operatorname{dom}(f_{n})$. If $\forall i<n,p_{n}>p_{i}$ then because $\mathbb{Q}$ is unbounded we can consider the least $n_{0}$ such that $\forall i<n,f(p_{i})<q_{n_{0}}$ and set $f_{n+1}(p_{n})=q_{n_{0}}$. Similarly if $\forall i<n,p_{n}<p_{i}$. Otherwise, let $i_{1},i_{2}<n$ such that $p_{i_{1}}<p_{n}<p_{i_{2}}$ with $p_{i_{1}},p_{i_{2}}$ respectively the largest and smallest possible. Because $\mathbb{Q}$ is dense we can consider the least $n_{0}$ such that $f_{n}(p_{i_{1}})<q_{n_{0}}<f_{n}(p_{i_{2}})$ and again set $f_{n+1}(p_{n})=q_{n_{0}}$. Similarly, if $n\neq n_{0}$ we use the fact that $P$ is unbounded and dense to find $m_{0}\geq n+1$ that allows to define $f_{n+1}(p_{m_{0}})=q_{n}$ and ensures $f_{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,y\in\mathbb{R}$ such that $x<y$ we can find $z\in\mathbb{Q}$ such that $x<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,<)$ be an unbounded, dense and linearly ordered set with the least upper-bound property. Suppose that $R$ has a dense countable subset $P$. Then $(R,<)$ is isomorphic to $(\mathbb{R},<)$.

Proof.

$P$ is countable by assumption and since $P\subseteq R$ it is also linearly ordered. If $x,y\in P\subseteq R$ and $x<y$ then by density of $P$ in $R$ there is $z\in P$ such that $x<z<y$. So $P$ is actually dense. Similarly, if $x\in P\subseteq R$ then since $R$ is unbounded there is $y_{1},y_{2}\in R$ such that $y_{2}<x<y_{2}$ and again by density of $P$ in $R$ we can find $z_{1},z_{2}\in P$ such that $y_{2}<z_{2}<x<z_{1}<y_{1}$. So $P$ is unbounded. By the previous lemma, there is an isomorphism of ordered sets $f:P\rightarrow\mathbb{Q}$.

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

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

We shall prove that $f_{\star}$ is surjective. Of course $f_{\star}(P)=f(P)=\mathbb{Q}$ so let’s consider $r\in\mathbb{R}\setminus\mathbb{Q}$. Define $x=\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 $R$ has the the least upper bound property. Then for all $q<r$ such that $q\in\mathbb{Q}$ we have $f^{-1}(q)\leq x$ by definition. By density of $\mathbb{Q}$ in $\mathbb{R}$ we can actually find $q^{\prime}\in\mathbb{Q}$ such that $q<q^{\prime}<r$ and so $f^{-1}(q)<f^{-1}(q^{\prime})\leq x$. We have $x>f^{-1}(q)\in P$ and so $f_{\star}(x)\geq f(f^{-1}(q))=q$. Hence $f_{\star}(x)\geq r$. Suppose that $r<f_{\star}(x)$ and consider (by density of $\mathbb{Q}$ in $\mathbb{R}$) some $q\in\mathbb{Q}$ such that $r<q<f_{\star}(x)$ and let $p=f^{-1}(q)$. If $p<x$ then there is $q^{\prime}\in\mathbb{Q}$, $q^{\prime}<r$, such that $p\leq f^{-1}(q^{\prime})$. Then $r<q=f(p)\leq q^{\prime}<r$ a contradiction. If instead $p\geq x$ then $f_{\star}(x)\leq f_{\star}(p)=q<f_{\star}(x)$ which is again a contradiction.

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

∎

Now consider a totally ordered set $(R,<)$. For any $a,b$ we define the open interval $(a,b)=\{x\in R:a<x<b\}$. Suppose $P=\{p_{n}:n\in\mathbb{N}\}$ is a dense subset of $R$. If ${\left((a_{i},b_{i})\right)}_{i\in I}$ is a family of pairwise disjoint open intervals then we can associate to any $(a_{i},b_{i})$ the least $n_{i}\in\mathbb{N}$ such that $p_{n_{i}}\in(a_{i},b_{i})$ (by density of $P$ in $R$). Since the family is disjoint the function $i\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,<)$ be an unbounded, dense and linearly ordered set with the least upper-bound property. Suppose that any family of disjoint open intervals in $R$ is at most countable. Is $(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 $\mathrm{MA}_{\aleph_{1}}$ and on the Diamond Principle $\Diamond$, that we define here:

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

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

• •

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

• •

  $D$ is dense in $P$ if for any $p\in P$ there is $d\in D$ such that $d\leq p$.

• •

  $G\subseteq P$ is a filter if:

  • –

    $G\neq\emptyset$

  • –

    For any $p,q\in P$ such that $p\leq q$ and $p\in G$ we have $q\in G$

  • –

    Any $p,q\in G$ there is $r\in G$ such that $r\leq p,q$.

• •

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

• •

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

  • –

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

  • –

    It is closed for the order topology, or equivalently if for any $\gamma<\omega_{1}$ and any $\gamma$-sequence $\alpha_{0}<\alpha_{1}<...<\alpha_{\xi}<...$ of elements of $C$, $\lim_{\xi\rightarrow\gamma}\alpha_{\xi}$ is in $C$.

• •

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

• •

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

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

Theorem 0.2.

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

Proof.

Suppose $(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_{\alpha}\subseteq R$ by induction on $\alpha<\omega_{1}$. If $I_{\beta}=[a_{\beta},b_{\beta}]$ is defined for all $\beta<\alpha$ then the set $C=\{a_{\beta}:\beta<\alpha\}\cup\{b_{\beta}:\beta<\alpha\}$ is countable and thus is not dense in $R$. Then there is $a_{\alpha}<b_{\alpha}$ such that $I_{\alpha}=[a_{\alpha},b_{\alpha}]$ is disjoint from $C$. We define the set $S=\{I_{\alpha},\alpha<\omega_{1}\}$. Clearly, $|S|=\aleph_{1}$ and $(S,\subsetneq)$ is partially ordered. We note that if $\beta<\alpha<\omega_{1}$ then by construction $a_{\beta},b_{\beta}\notin I_{\alpha}$ and so either $I_{\alpha}\cap I_{\beta}=\emptyset$ or $I_{\alpha}\subsetneq I_{\beta}$. In particular, comparable is the same as compatible in $S$ and any family of pairwise incomparable/incompatible elements of $S$ is a family of pairwise disjoint intervals of $R$ so at most countable.

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

For any $I\in S$, define $S_{I}=\{J\in S:J\subseteq I\}$ and let $T=\{I\in S:|S_{I}|=\aleph_{1}\}$. Let $\alpha<\omega_{1}$ and suppose that $L_{\alpha}\cap T=\emptyset$. Then $S=\bigcup_{\beta<\alpha}L_{\beta}\cup\bigcup_{I\in L_{\alpha}}S_{I}$ and since the $L_{\beta}$ are at most countable for $\beta<\omega_{1}$ and the $S_{I}$ are at most countable for $I\in L_{\alpha}$ we would have $S$ at most countable, a contradiction. So for each $\alpha<\omega_{1}$, there is $I\in T\cap L_{\alpha}$ and in particular $|T|=\aleph_{1}$. We note that if $I\in T$ and $J\supseteq I$ then $S_{I}\subseteq S_{J}$ and so $J\in T$. In particular, $P_{I}=\{J\in T:J\supsetneq I\}$ and thus without loss of generality we may assume that $S=T$.

For any $\alpha<\omega_{1}$ let $D_{\alpha}=\{I\in D_{\alpha}:o(I)>\alpha\}$. For any $I\in S$, $|S_{I}|=\aleph_{1}$ and $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_{\alpha}$ is a dense subset of $S$.

Using $\mathrm{MA}_{\aleph_{1}}$, we find $G\subseteq S$ a filter that intersects each $D_{\alpha}$. By definition, elements of a filter are pairwise compatible and so pairwise comparable. Let us construct by induction on $\alpha<\omega_{1}$, some sets $J_{\alpha}\in G$. If $J_{\beta}$ is constructed for any $\beta<\alpha$ then $\gamma=\sup_{\beta<\alpha}o(J_{\beta})<\omega_{1}$ and we can pick $J_{\alpha}\in G\cap D_{\gamma}$. We obtain a decreasing $\omega_{1}$-sequence of intervals $J_{0}\supsetneq J_{1}\supsetneq...\supsetneq J_{\alpha}\supsetneq...$. If $J_{\alpha}=[x_{\alpha},y_{\alpha}]$ then this gives an increasing sequence $x_{0}<x_{1}<x_{2}<...<x_{\alpha}<...$. The sets $(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,<)$ 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.

Proof.

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

Each $(T_{\alpha},\prec)$ will be a tree i.e. for any $x$ in the tree the set $P_{x}=\{y:y\prec x\}$ is well-ordered. As in the proof of 0.2 we can define $o(x)$ the order-type of $P_{x}$. The level $\alpha$ is the set of elements such that $o(x)=\alpha$. The height of a tree is defined as the supremium of the $o(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_{\alpha}$ is constructed such that its height is $\alpha$ and for each $x\in T_{\alpha}$ there is some $y\succ x$ at each higher level less than $\alpha$.

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

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

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

We note that $T_{1}=\{0\}\geq 1$. If $T_{\alpha}\geq\alpha$ then $T_{\alpha+1}$ is obtained by adding at least one element at the end of the initial segment $T_{\alpha}$ and so $T_{\alpha+1}\geq\alpha+1$. Finally if $\lambda>0$ is limit and $T_{\alpha}\geq\alpha$ for each $\alpha<\lambda$ then $T_{\lambda}=\bigcup_{\alpha<\lambda}T_{\alpha}\geq\sup_{\alpha<\lambda}\alpha=\lambda$. Moreover by definition, each $T_{\alpha}$ is at most countable. Let’s come back to the closed set $C$ above. Let $\alpha_{0}<\omega_{1}$ be arbitrary. For each $n<\omega$, we let $\alpha_{2n+1}$ be the limit of the sequence $\alpha_{0}\leq T_{\alpha_{0}}\leq T_{T_{\alpha_{0}}}\leq T_{T_{T_{\alpha_{0}}} }...$. By definition, $T_{\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 $A$ is a maximal antichain in $T$, for each $x\in T_{\alpha_{2n+1}}$ we can find some $\alpha_{x}\geq\alpha_{2n+1}$ and $a_{x}\in A_{\alpha_{x}}$ that is comparable with $x$. Because $T_{\alpha_{2n+1}}$ is countable we can define $\alpha_{2n+2}=\sup_{x\in T_{\alpha_{2n+1}}}\alpha_{x}<\omega_{1}$. Then any $x\in T_{\alpha_{2n+1}}$ is comparable with some element of $a_{x}\in A\cap T_{\alpha_{2n+2}}$. Let $\lambda=\lim_{n<\omega}\alpha_{n}$. With the same method as to prove the fact that $C$ is closed, the equality $\lambda=\lim_{n<\omega}\alpha_{2n+1}$ shows that $T_{\lambda}=\lambda$ while the equality $\lambda=\lim_{n<\omega}\alpha_{2n+2}$ shows that $A\cap T_{\lambda}$ is a maximal antichain in $T_{\lambda}$. So $\lambda\in C$ and $C$ is closed unbounded.

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

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

Finally, we define $S$ the set of all branches of $T$. By construction, each $x\in T$ has countably many immediate successors and we order them as $\mathbb{Q}$. Let $B_{1},B_{2}$ be two branches and $\alpha$ the least level where they differ. The level 0 is $T_{1}=\{0\}$ so $\alpha>0$. If $\alpha$ is limit then the restriction of the branches $B_{1},B_{2}$ to $T_{\alpha}$ is the same branch $b$ and $T_{\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 $\beta+1$. Hence if $B_{1}(\alpha)\in B_{1}$ and $B_{2}(\alpha)\in B_{2}$ are the immediate successors of the point in $B_{1}\cap B_{2}$ at level $\beta$, we order $B_{1},B_{2}$ according to whether $B_{1}(\alpha)<B_{2}(\alpha)$ or $B_{1}(\alpha)>B_{2}(\alpha)$, using the $\mathbb{Q}$-isomorphic order we just defined. Clearly, this gives a linear ordering $<_{S}$. It is also unbounded: for any $B\in S$, if $B(1)\in B$ is the element at level 1 pick $x$ greater (or smaller) than for the $\mathbb{Q}$-isomorphic order on successors of $B(0)=0$ and consider a branch extending $0\prec x$.

Now consider two branches $B_{1}<_{S}B_{2}$. Let $\alpha=\beta+1$ be as above. We can find $x$ an immediate successor of $B_{1}(\beta)$ such that $B_{1}(\alpha)<x<B_{2}(\alpha)$ for the $\mathbb{Q}$-isomorphic order on immediate successors of $B_{1}(\beta)$. Let $I_{x}=\{B\in S:x\in B\}$. Any $B\in I_{x}$ contains $\{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(\alpha)$ and so $B_{1}<B<B_{2}$. $I_{x}$ is nonempty (we can extend $\{y\in T:y\preceq x\}$ to a maximal branch) and so $S$ is dense. If $I_{x}\cap I_{y}=\emptyset$ then $x,y$ are incomparable. So from any collection of disjoint open intervals ${(B_{1i},B_{2i})}_{i\in I}$ we get an antichain $\{x_{i}:i\in I\}$ and so $I$ is at most countable.

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

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

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

∎

The $\Diamond$ principle holds in the model $L$ of constructible sets. Using iterated forcing, we can construct a model of ZFC in which $\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 $\omega_{1}$-tree are at most countable then so are its branches).

• •

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