2Well-orderings and ordinals
II Logic and Set Theory
2.1 Well-orderings
We start with a few definitions.
Definition ((Strict) total order). A (strict) total order or linear order is a pair
(X, <), where X is a set and < is a relation on X that satisfies
(i) x < x for all x (irreflexivity)
(ii) If x < y, y < z, then x < z (transitivity)
(iii) x < y or x = y or y < x (trichotomy)
We have the usual shorthands for total orders. For example,
x > y
means
y < x and x ≤ y means (x < y or x = y).
It is also possible for a total order to be defined in terms of ≤ instead of <.
Definition ((Non-strict) total order). A (non-strict) total order is a pair (
X, ≤
),
where X is a set and ≤ is a relation on X that satisfies
(i) x ≤ x (reflexivity)
(ii) x ≤ y and y ≤ z implies x ≤ z (transitivity)
(iii) x ≤ y and y ≤ x implies x = y (antisymmetry)
(iv) x ≤ y or y ≤ x (trichotomy)
Example.
(i) N, Z, Q, R with usual the usual orders are total orders.
(ii)
On
N
+
(the positive integers), ‘
x < y
if
x | y
and
x
=
y
’ is not trichotomous,
and so not a total order.
(iii)
On
P
(
S
), define ‘
x ≤ y
’ if
x ⊆ y
. This is not a total order since it is not
trichotomous (for |X| > 1).
While there can be different total orders, the particular kind we are interested
in is well-orders.
Definition (Well order). A total order (
X, <
) is a well-ordering if every (non-
empty) subset has a least element, i.e.
(∀S ⊆ X)[S = ∅ ⇒ (∃x ∈ S)(∀y ∈ S) y ≥ x].
Example.
(i) N with usual ordering is a well-order.
(ii) Z, Q, R
are not well-ordered because the whole set itself does not have a
least element.
(iii) {x ∈ Q
:
x ≥
0
}
is not well-ordered. For example,
{x ∈ X
:
x >
0
}
has no
least element.
(iv)
In
R
,
{
1
−
1
/n
:
n
= 2
,
3
,
4
, ···}
is well-ordered because it is isomorphic to
the naturals.
(v) {
1
−
1
/n
:
n
= 2
,
3
,
4
, ···} ∪ {
1
}
is also well-ordered, If the subset is only
1, then 1 is the least element. Otherwise take the least element of the
remaining set.
(vi) Similarly, {1 − 1/n : n = 2, 3, 4, ···} ∪ {2} is well-ordered.
(vii) {
1
−
1
/n
:
n
= 2
,
3
,
4
, ···}∪{
2
−
1
/n
:
n
= 2
,
3
,
4
, ···}
is also well-ordered.
This is a good example to keep in mind.
There is another way to characterize total orders in terms of infinite decreasing
sequences.
Proposition. A total order is a well-ordering if and only if it has no infinite
strictly decreasing sequence.
Proof. If x
1
> x
2
> x
3
> ···, then {x
i
: i ∈ N} has no least element.
Conversely, if non-empty
S ⊂ X
has no least element, then each
x ∈ S
have
x
′
∈ S with x
′
< x. Similarly, we can find some x
′′
< x
′
ad infinitum. So
x > x
′
> x
′′
> x
′′′
> ···
is an infinite decreasing sequence.
Like all other axiomatic theories we study, we identify two total orders to be
isomorphic if they are “the same up to renaming of elements”.
Definition (Order isomorphism). Say the total orders
X, Y
are isomorphic if
there exists a bijection
f
:
X → Y
that is order-preserving, i.e.
x < y ⇒ f
(
x
)
<
f(y).
Example.
(i) N and {1 − 1/n : n = 2, 3, 4, ···} are isomorphic.
(ii) {
1
−
1
/n
:
n
= 2
,
3
,
4
, ···}∪{
1
}
is isomorphic to
{
1
−
1
/n
:
n
= 2
,
3
,
4
, ···}∪
{2}.
(iii) {
1
−
1
/n
:
n
= 2
,
3
,
4
, ···}
and
{
1
−
1
/n
:
n
= 2
,
3
,
4
, ···} ∪ {
1
}
are not
isomorphic because the second has a greatest element but the first doesn’t.
Recall from IA Numbers and Sets that in
N
, the well-ordering principle is
equivalent to the principle induction. We proved that we can do induction simply
by assuming that
N
is well-ordered. Using the same proof, we should be able to
prove that we can do induction on any well-ordered set.
Of course, a general well-ordered set does not have the concept of “+1”, so
we won’t be able to formulate weak induction. Instead, our principle of induction
is the form taken by strong induction.
Proposition (Principle by induction). Let
X
be a well-ordered set. Suppose
S ⊆ X has the property:
(∀x)
(∀y) y < x ⇒ y ∈ S
⇒ x ∈ S
,
then S = X.
In particular, if a property P (x) satisfies
(∀x)
(∀y) y < x ⇒ P (y)
⇒ P (x)
,
then P (x) for all x.
Proof.
Suppose
S
=
X
. Let
x
be the least element of
X \S
. Then by minimality
of x, for all y, y < x ⇒ y ∈ S. Hence x ∈ S. Contradiction.
Using proof by induction, we can prove the following property of well-orders:
Proposition. Let
X
and
Y
be isomorphic well-orderings. Then there is a unique
isomorphism between X and Y .
This is something special to well-orders. This is not true for general total
orderings. For example,
x 7→ x
and
x 7→ x −
13 are both isomorphisms
Z → Z
. It
is also not true for, say, groups. For example, there are two possible isomorphisms
from Z
3
to itself.
Proof.
Let
f
and
g
be two isomorphisms
X → Y
. To show that
f
=
g
, it is
enough, by induction, to show f(x) = g(x) given f (y) = g(y) for all y < x.
Given a fixed
x
, let
S
=
{f
(
y
) :
y < x}
. We know that
Y \ S
is non-empty
since
f
(
x
)
∈ S
. So let
a
be the least member of
Y \ S
. Then we must have
f
(
x
) =
a
. Otherwise, we will have
a < f
(
x
) by minimality of
a
, which implies
that
f
−1
(
a
)
< x
since
f
is order-preserving. However, by definition of
S
, this
implies that a = f (f
−1
(a)) ∈ S. This is a contradiction since a ∈ Y \ S.
By the induction hypothesis, for
y < x
, we have
f
(
y
) =
g
(
y
). So we have
S = {g(y) : y < x} as well. Hence g(x) = min(Y \ S) = f(x).
If we have an ordered set, we can decide to cut off the top of the set and
keep the bottom part. What is left is an initial segment.
Definition (Initial segment). A subset
Y
of a totally ordered
X
is an initial
segment if
x ∈ Y, y < x ⇒ y ∈ Y,
Y
X
Example. For any
x ∈ X
, the set
I
x
=
{y ∈ X
:
y < x}
is an initial segment.
However, not every initial segment of
X
need to be in this form. For example,
{x
:
x ≤
3
} ⊆ R
and
{x
:
x <
0
or x
2
<
2
} ⊆ Q
are both initial segments not of
this form.
The next nice property of well-orders we have is that every proper initial
segment is of this form.
Proposition. Every initial segment
Y
of a well-ordered set
X
is of the form
I
x
= {y ∈ X : y < x}.
Proof.
Take
x
=
min X \ Y
. Then for any
y ∈ I
x
, we have
y < x
. So
y ∈ Y
by
definition of x. So I
x
⊆ Y .
On the other hand, if
y ∈ Y
, then definitely
y
=
x
. We also cannot have
y > x
since this implies
x ∈ Y
. Hence we must have
y < x
. So
y ∈ I
x
. Hence
Y ⊆ I
x
. So Y = I
x
.
The next nice property we want to show is that in a well-ordering
X
, every
subset S is isomorphic to an initial segment.
Note that this is very false for a general total order. For example, in
Z
, no
initial segment is isomorphic to the subset
{
1
,
2
,
3
}
since every initial segment
of
Z
is either infinite or empty. Alternatively, in
R
,
Q
is not isomorphic to an
initial segment.
It is intuitively obvious how we can prove this. We simply send the minimum
element of
S
to the minimum of
X
, and the continue recursively. However, how
can we justify recursion? If we have the well-order
{
1
2
,
2
3
,
3
4
, ··· ,
1
}
, then we will
never reach 1 if we attempt to write down each step of the recursion, since we
can only get there after infinitely many steps. We will need to define some sort
of “infinite recursion” to justify our recursion on general well-orders.
We first define the restriction of a function:
Definition (Restriction of function). For
f
:
A → B
and
C ⊆ A
, the restriction
of f to C is
f|
C
= {(x, f(x)) : x ∈ C}.
In this theorem (and the subsequent proof), we are treating functions as
explicitly a set of ordered pairs (
x, f
(
x
)). We will perform set operations on
functions and use unions to “stitch together” functions.
Theorem (Definition by recursion). Let
X
be a well-ordered set and
Y
be any
set. Then for any function
G
:
P
(
X ×Y
)
→ Y
, there exists a function
f
:
X → Y
such that
f(x) = G(f|
I
x
)
for all x.
This is a rather weird definition. Intuitively, it means that
G
takes previous
values of
f
(
x
) and returns the desired output. This means that in defining
f
at
x
, we are allowed to make use of values of
f
on
I
x
. For example, we define
f(n) = nf(n − 1) for the factorial function, with f(0) = 1.
Proof.
We might want to jump into the proof and define
f
(0) =
G
(
∅
), where 0
is the minimum element. Then we define
f
(1) =
G
(
f
(0)) etc. But doing so is
simply recursion, which is the thing we want to prove that works!
Instead, we use the following clever trick: We define an “
h
is an attempt” to
mean
h : I → Y for some initial segment I of X, and h(x) = G(h|
I
x
) for x ∈ I.
The idea is to show that for any
x
, there is an attempt
h
that is defined at
x
.
Then take the value
f
(
x
) to be
h
(
x
). However, we must show this is well-defined
first:
Claim. If attempts h and h
′
are defined at x, then h(x) = h
′
(x).
By induction on
x
, it is enough to show that
h
(
x
) =
h
′
(
x
) assuming
h
(
y
) =
h
′
(y) for all y < x. But then h(x) = G(h|
I
x
) = G(h
′
|
I
x
) = h
′
(x). So done.
Claim. For any x, there must exist an attempt h that is defined at x.
Again, we may assume (by induction) that for each
y < x
, there exists an
attempt
h
y
defined at
y
. Then we put all these functions together, and take
h
′
=
S
y<x
h
y
. This is defined for all
y < x
, and is well-defined since the
h
y
never disagree.
Finally, add to it (
x, G
(
h
′
|
I
x
)). Then
h
=
h
′
∪
(
x, G
(
h
′
|
I
x
)) is an attempt
defined at x.
Now define
f
:
X → Y
by
f
(
x
) =
y
if there exists an attempt
h
, defined at
x, with h(x) = y.
Claim. There is a unique such f.
Suppose
f
and
f
′
both work. Then if
f
(
y
) =
f
′
(
y
) for all
y < x
, then
f
(
x
) =
f
′
(
x
) by definition. So by induction, we know for all
x
, we have
f
′
(x) = f(x).
With the tool of recursion, we can prove that every subset of a well-order.
Lemma (Subset collapse). Let
X
be a well-ordering and let
Y ⊆ X
. Then
Y
is
isomorphic to an initial segment of
X
. Moreover, this initial segment is unique.
Proof.
For
f
:
Y → X
to be an order-preserving bijection with an initial segment
of X, we need to map x to the smallest thing not yet mapped to, i.e.
f(x) = min(X \{f (y) : y < x}).
To be able to take the minimum, we have to make sure the set is non-empty, i.e.
{f
(
y
) :
y < x}
=
X
. We can show this by proving that
f
(
z
)
< x
for all
z < x
by
induction, and hence x ∈ {f(y) : y < x}.
Then by the recursion theorem, this function exists and is unique.
This implies that a well-ordered
X
can never be isomorphic to a proper
initial segment of itself. This is since
X
is isomorphic to itself by the identity
function, and uniqueness shows that it cannot be isomorphic to another initial
segment.
Using the idea of initial segments, we can define an order comparing different
well-orders themselves.
Notation. Write X ≤ Y if X is isomorphic to an initial segment of Y .
We write
X < Y
if
X ≤ Y
but
X
is not isomorphic to
Y
, i.e.
X
is isomorphic
to a proper initial segment of Y .
Example. If X = N, Y = {
1
2
,
2
3
,
3
4
, ···} ∪ {1}, then X ≤ Y .
We will show that this is a total order. Of course, we identify two well-orders
as “equal” when they are isomorphic.
Reflexivity and transitivity are straightforward. So we prove trichotomy and
antisymmetry:
Theorem. Let X, Y be well-orderings. Then X ≤ Y or Y ≤ X.
Proof. We attempt to define f : X → Y by
f(x) = min(Y \ {f(y) : y < x}).
By the law of excluded middle, this function is either well-defined or not.
If it is well-defined, then it is an isomorphism from
X
to an initial segment
of Y .
If it is not, then there is some
x
such that
{f
(
y
) :
y < x}
=
Y
and we cannot
take the minimum. Then
f
is a bijection between
I
x
=
{y
:
y < x}
and
Y
. So
f
is an isomorphism between Y and an initial segment of X.
Hence either X ≤ Y or Y ≤ X.
Theorem. Let
X, Y
be well-orderings with
X ≤ Y
and
Y ≤ X
. Then
X
and
Y are isomorphic.
Proof.
Since
X ≤ Y
, there is an order-preserving function
f
:
X → Y
that
bijects
X
with an initial segment of
Y
. Similarly, since
Y ≤ X
, we get an
analogous
g
:
Y → X
. Then
g ◦ f
:
X → X
defines a bijection between
X
and
an initial segment of X.
Since there is no bijection between
X
and a proper initial segment of itself,
the image of g ◦ f must be X itself. Hence g ◦ f is a bijection.
Similarly,
f ◦ g
is a bijection. Hence
f
and
g
are both bijections, and
X
and
Y are isomorphic.