2Well-orderings and ordinals
II Logic and Set Theory
2.2 New well-orderings from old
Given a well-ordering
X
, we want to create more well-orderings. We’ve previously
shown that we can create a shorter one by taking an initial segment. In this
section, we will explore two ways to make longer well-orderings.
Add one element
We can extend a well-ordering by exactly one element. This is known as the
successor.
Definition (Successor). Given
X
, choose some
x ∈ X
and define a well-ordering
on
X ∪ {x}
by setting
y < x
for all
y ∈ X
. This is the successor of
X
, written
X
+
.
We clearly have X < X
+
.
Put some together
More interestingly, we want to “stitch together” many well-orderings. However,
we cannot just arbitrarily stitch well-orderings together. The well-orderings must
satisfy certain nice conditions for this to be well-defined.
Definition (Extension). For well-orderings (
X, <
X
) and (
Y, <
Y
), we say
Y
extends
X
if
X
is a proper initial segment of
Y
and
<
X
and
<
Y
agree when
defined.
Note that we explicitly require
X
to be an initial segment of
Y
.
X
simply
being a subset of Y will not work, for reasons that will become clear shortly.
Definition (Nested family). We say well-orderings
{X
i
:
i ∈ I}
form a nested
family if for any i, j ∈ I, either X
i
extends X
j
, or X
j
extends X
i
.
Proposition. Let
{X
i
:
i ∈ I}
be a nested set of well-orderings. Then there
exists a well-ordering X with X
i
≤ X for all i.
Proof.
Let
X
=
S
i∈I
X
i
with
<
defined on
X
as
S
i∈I
<
i
(where
<
i
is the
ordering of
X
i
), i.e. we inherit the orders from the
X
i
’s. This is clearly a total
ordering. Since
{X
i
:
i ∈ I}
is a nested family, each
X
i
is an initial segment of
X.
To show that it is a well-ordering, let
S ⊆ X
be a non-empty subset of
X
.
Then
S ∩ X
i
is non-empty for some
i
. Let
x
be the minimum element (in
X
i
) of
S ∩X
i
. Then also for any
y ∈ S
, we must have
x ≤ y
, as
X
i
is an initial segment
of X.
Note that if we didn’t require
X
to be an initial segment of
Y
when defining
’extension’, then the above proof will not work. For example, we can take the
collection of all subsets
X
n
=
{x ≥ −n
:
x ∈ Z}
, and their union would be
Z
,
which is not well-ordered.