II Logic and Set Theory - Well-orderings and ordinals

2Well-orderings and ordinals

II Logic and Set Theory

2.3 Ordinals

We have already shown that the collection of all well-orderings is a total order.

But is it a well-ordering itself? To investigate this issue further, we first define

ourselves a convenient way of talking about well-orderings.

Definition (Ordinal). An ordinal is a well-ordered set, with two regarded as

the same if they are isomorphic. We write ordinals as Greek letters α, β etc.

We would want to define ordinals as equivalence classes of well-orders under

isomorphism, but we cannot, because they do not form a set. We will provide a

formal definition of ordinals later when we study set theory.

Definition (Order type). If a well-ordering

has corresponding ordinal

, we

say X has order type α, and write otp(X) = α.

Notation. For each

k ∈ N

, we write

for the order type of the (unique)

well-ordering of size k. We write ω for the order type of N.

Example. In R, {2, 3, 5, 6} has order type 4. {

, ···} has order type ω.

Notation. For ordinals

α, β

, write

α ≤ β

X ≤ Y

for some

of order type

. This does not depend on the choice of

and

(since any

two choices must be isomorphic).

Proposition. Let

be an ordinal. Then the ordinals

< α

form a well-ordering

of order type α.

Notation. Write I

= {β : β < α}.

Proof.

Let

have order type

. The well-orderings

< X

are precisely (up to

isomorphism) the proper initial segments of

(by uniqueness of subset collapse).

But these are the

for all

x ∈ X

. So we can biject

with the well-orderings

< X by x 7→ I

Finally, we can prove that the ordinals are well-ordered.

Proposition. Let

be a non-empty set of ordinals. Then

has a least element.

Proof. Choose α ∈ S. If it is minimal, done.

If not, then

S ∩ I

is non-empty. But

is well-ordered. So

S ∩ I

has a

least element, β. Then this is a minimal element of S.

However, it would be wrong to say that the ordinals form a well-ordered set,

for the very reason that they don’t form a set.

Theorem (Burali-Forti paradox). The ordinals do not form a set.

Proof.

Suppose not. Let

be the set of ordinals. Then

is a well-ordering.

Let its order-type be

. Then

is isomorphic to

, a proper initial subset of

X. Contradiction.

Recall that we could create new well-orderings from old via adding one

element and taking unions. We can translate these into ordinal language.

Given an ordinal

, suppose that

is the corresponding well-order. Then

we define α

to be the order type of X

If we have a set

{α

i ∈ I}

of ordinals, we can stitch them together to form

a new well-order. In particular, we apply “nested well-orders” to the initial

segments

i ∈ I}

. This produces an upper bound of the ordinals

. Since

the ordinals are well-ordered, we know that there is a least upper bound. We

call this the supremum of the set

{α

i ∈ I}

, written

sup{α

i ∈ I}

. In fact,

the upper bound created by nesting well-orders is the least upper bound.

Example. {2, 4, 6, 8, ···} has supremum ω.

Now we have two ways of producing ordinals: +1 and supremum.

We can generate a lot of ordinals now:

0 ω · 2 + 1 ω

+ 1 ω

· 3 ω

ω+2

+ 1

1 ω · 2 + 2 ω

+ 2 ω

· 4

2 ω · 2 + 3 ω

+ 3 ω

· 5 ω

ω·2

· 2

ω ω · 3 ω

+ ω ω

ω + 1 ω · 4

ω + 2 ω · 5 ω

+ ω · 2 ω

ω + ω = ω · 2 ω · ω = ω

· 2 ω

ω+1

= ε

Here we introduced a lot of different notations. For example, we wrote

+ 1 to

mean

, and

ω ·

2 =

sup{ω, ω

+ 1

, ω

+ 2

, ···}

. We will formally define these

notations later.

We have written a lot of ordinals above, some of which are really huge.

However, all the ordinals above are countable. The operations we have done so

far is adding one element and taking countable unions. So the results are all

countable. So is there an uncountable ordinal?

Theorem. There is an uncountable ordinal.

Proof.

This is easy by looking at the supremum of the set of all countable

ordinals. However, this works only if the collection of countable ordinals is a set.

Let

{R ∈ P

(

N × N

) :

R is a well-ordering of a subset of N}

. So

A ⊆

(

N × N

). Then

{order type of R

R ∈ A}

is the set of all countable

ordinals.

Let

sup B

. Then

is uncountable. Indeed, if

were countable, then

it would be the greatest countable ordinal, but

+ 1 is greater and is also

countable.

By definition,

is the least uncountable ordinal, and everything in our

previous big list of ordinals is less than ω

There are two strange properties of ω

(i) ω

is an uncountable ordering, yet for every

x ∈ ω

, the set

y < x}

countable.

(ii)

Every sequence in

is bounded, since its supremum is a countable union

of countable sets, which is countable.

In general, we have the following theorem:

Theorem (Hartogs’ lemma). For any set

, there is an ordinal that does not

inject into X.

Proof. As before, with B = {α : α injects into X}.

Notation. Write

(

) for the least ordinal that does not inject into

. e.g.

γ(ω) = ω