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
iI
X
i
with
<
defined on
X
as
S
iI
<
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.