First, the set of rationals
is well-known to be countable. It is
linearly ordered (for any either or ),
unbounded (for any there is such that
and ) and dense (for any if we
can find such that ). It turns out that can
be characterized by these order properties:
be enumerations of and .
We shall construct by induction a sequence
of functions such that
for all ,
Then is a function:
if then there is large enough such that
and since is a function .
for any there is large enough such that
and so . Hence is an isomorphism between
Thus let . If is defined, we construct
as follows. Suppose . If
then because is unbounded we can consider
the least such that and set
. Similarly if . Otherwise,
let such that
with respectively the largest and smallest possible.
Because is dense we can consider the least such that
and again set
. Similarly, if we use the fact that
is unbounded and dense to find that allows to define
and ensures is order-preserving.
We now notice that is linearly ordered, unbounded, dense and has the
least upper-bound property (that is any nonempty bounded subset of has
a least upper-bound). Moreover, the subset is countable and dense in
(that is for any such that we can find
such that ). Using the previous lemma, we deduce again that these
order properties give a characterization of the set of reals:
is countable by assumption and since it is also
linearly ordered. If and then by density
of in there is such that . So is actually
dense. Similarly, if then since is unbounded
there is such that and again
by density of in we can find such that
. So is unbounded. By the previous lemma,
there is an isomorphism of ordered sets .
We define for all ,
. Because is dense in and
has the least upper bound property this is well-defined.
If then for all such that we have
and so . If
we could find (by density of in ) an element such
that . For we get and so
. A contradiction. So .
Let such that . Because is increasing we
get . By density of in we can
find such that . Again, we get
. Hence we actually have
. In particular, is one-to-one.
We shall prove that is surjective. Of course
so let’s consider
This is well-defined because is dense in and has the
the least upper bound property. Then for all such that
we have by definition.
By density of in we can actually find such that
and so . We have
. Hence .
Suppose that and consider
(by density of in ) some
such that and let .
If then there is , , such that
. Then a contradiction.
If instead then
which is again a
Finally, let such that . Because
is totally ordered either or . But the latter is
impossible since we saw above that it implied .
Hence is an isomorphism between and .
Now consider a totally ordered set . For any we define
the open interval . Suppose
is a dense subset of .
is a family of pairwise disjoint open intervals
then we can associate to any the least such that
(by density of in ). Since the family is
disjoint the function 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:
We have seen how this problem arises from a natural generalization of
a characterization of . 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 and on the
Diamond Principle , that we define here:
Suppose is not isomorphic to and in particular
does not have any countable dense subset (otherwise we could apply
We define closed intervals by induction on
is defined for all
then the set is countable and thus is not dense in .
Then there is such that
is disjoint from . We define the set
and is partially ordered.
We note that if then by construction
and so either
In particular, comparable is the same as compatible in and
any family of pairwise incomparable/incompatible elements of
is a family of pairwise disjoint intervals of so at most countable.
Let and define . Let
nonempty. Let the least ordinal such that . If
. Hence by
the previous remark . So
is well-ordered by and
we define the order-type of .
We note that the set can be enumerated by
for some and so .
Moreover for any ,
is an initial segment of and so
Hence for each the set
has pairwise incomparable
elements and so is at most countable.
For any , define
and let . Let
and suppose that . Then
are at most countable for and the
are at most countable for we would
have at most countable, a contradiction. So for each
, there is and in particular
. We note that if and then
and so . In particular,
and thus without loss of generality
we may assume that .
For any let
. For any ,
. The first term is at most countable and so the
second is uncountable and a fortiori nonempty. So is a dense
subset of .
Using , we find a filter that
intersects each . By definition, elements of a filter are
pairwise compatible and so pairwise comparable.
Let us construct by induction
on , some sets . If is
constructed for any then
and we can pick
. We obtain a decreasing -sequence
If then this gives an increasing sequence
. The sets
form an uncountable family of disjoint open
intervals. A contradiction.
Let be a -sequence.
We first construct a partial ordering of .
We define for all an ordering
on initial segments
and obtain the ordering on
Each will be a tree i.e. for any in the tree the set
is well-ordered. As in the proof of
0.2 we can define the order-type of .
The level is the set of elements such that .
The height of a tree is defined as the supremium of the .
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.
is constructed such that its height is
and for each there is some at each higher level
less than .
We let . If is a limit ordinal then
is the union of for .
If is a successor ordinal, then the highest level
of is .
is obtained by adding immediate
successors to each element of
. These successors are taken from in a way that
is an initial segment of .
Let is a limit ordinal. Let if it is a maximal
antichain in and take an arbitrary maximal
antichain of otherwise. Then for each
there is such that either or
. Let be a branch that contains . We construct
for each branch some that is greater than all the elements of
. We can choose in way that it contains an element of
each level less than and so and the height
of is . We note that
each is either in (so comparable with some
element of ) or greater than (a fortiori comparable with) one element of
. So is an antichain in .
Now consider a maximal antichain and
the set of ordinals such that
‘‘ is a maximal antichain in and
() be a sequence of elements in and consider
the limit ordinal
By construction, . If , there is such that
and so is comparable with some
is a maximal antichain in . Finally and is
We note that . If then
is obtained by adding at least one element at the end
of the initial segment and so .
Finally if is limit and
then . Moreover by definition,
each is at most countable.
Let’s come back to the closed set above.
Let be arbitrary. For each , we let
be the limit of the sequence
By definition, .
Because is a maximal antichain in , for each we
can find some and that is
comparable with . Because is countable we can define
any is comparable with some element of
. Let .
With the same method as to prove the fact that is closed,
the equality shows that
is a maximal antichain in .
So and is closed unbounded.
Using the Diamond principle,
If is in the intersection, then
is a maximal antichain in .
By construction, it is also a maximal antichain in .
Each element of is at level .
Any is comparable with some element of
. Moreover, by contruction any
has some predecessor at level and
there is that is comparable with .
Necessarily, and so .
Thus is maximal
in and is at most
Let be a branch in . It is clear that is nonempty. Actually
it is infinite: otherwise there is some limit ordinal
and by construction we can find some
contradicting the maximality of .
By construction, each has infinitely many
successors at the next level and so these successors are
Hence if then we can pick one among these
succcessors. Let be two elements of . Then
impossible. Suppose . We also have by definition.
If then we would have because is a branch.
If we would get .
Hence are incomparable (in particular distinct) and the set
is an antichain in and so is countable.
Finally, we define the set of all branches of . By construction, each
has countably many immediate successors and we order them
as . Let be two branches and
the least level where they differ. The level 0 is
so . If is limit then the restriction of the
branches to is the same branch and
has been contructed in a way that there is only one possible element at level
to extend this branch and this is a contradiction.
So is actually a successor
ordinal . Hence if and
are the immediate successors of the
point in at level , we order
according to whether
or , using the -isomorphic order we just
defined. Clearly, this gives a linear ordering .
It is also unbounded: for any
, if is the element at level 1 pick greater
(or smaller) than for the -isomorphic order on successors
of and consider a branch extending .
Now consider two branches . Let be as above.
We can find an immediate successor of such that
for the -isomorphic order on immediate
successors of .
Let . Any contains
. Moreover and so
. is nonempty (we can extend
to a maximal branch) and so is dense.
If then are incomparable.
So from any collection of disjoint open intervals
we get an antichain and so is at most countable.
Let be a countable set of branches in . Since
these branches are countable, we can find larger
than the length of any branches in . If is at level greater
than then for all , so .
Finally and is not dense.
Now let be the Dedekind-MacNeille completion of .
It is unbounded, linearly ordered, has
the least upper-bound property and is dense in .
Using the fact that is dense in we deduce that is dense.
Similarly, if is any collection
of disjoint open intervals in we can find
such that . Then
is a collection of disjoint open intervals in
and so is at most countable.
Finally, it remains to prove that is not isomorphic to and it
suffices to show that does not have any countable dense subset .
If is a countable subset of , then for any elements
in we pick such that . This gives a
countable subset of . If are elements of , we can find
such that and so such that
. Thus would be a countable dense subset of .