CHAP10 Ordinal Numbers

10.
ORDINAL NUMBERS
§10.1 Transitive Sets
We turn our attention to ordinal numbers. With finite numbers the cardinal
numbers, apart from zero, are 1, 2, 3, … while the ordinal numbers are 1st, 2nd, 3rd, …
There is really very little difference. For infinite sets there’s a big difference. While
cardinal numbers simply measure the size of a set, ordinal numbers describe the structure
of a well-ordered set.
Consider the well-ordered set {1, 2, 3, … , 0}. As a set this is no bigger than
{1, 2, 3, …}. But as well-ordered sets the ordering is quite different. One set has a
largest while the other does not.
A set x is transitive if x  x, that is, if every element of an element of x is

itself an element of x.
Example 1: Recall that (1, 2) = {{1}, {1, 2}}.

x = {0, 1, 2, {2}, {1, 2}, (1, 2)} is not transitive since x = {0, 1, 2, {1}, {1, 2}}  x.
However y = {0, 1, 2, {2}, {1, 2}, (2, 1)} is since y = {0, 1, 2, {2}, {1, 2}}  x.
The natural numbers are transitive, and the set of natural numbers itself is
transitive.
Theorem 1: A set x is transitive if and only if x x.

Proof: Suppose x is transitive. We must show that x  x, that is, every element of x is
a subset of x. Let y  x. If z  y then z  x and so z  x. Hence y  x, as required.
Now suppose x  x. Let y  x. Then for some z, y  z and z  x.
Since x  x, z  x, that is, z  x. Since y  z, y  x. We have therefore shown that
x  x.
Example 1 (continued): Observe that every element of y is a subset of y, since

y = {0, {0}, {0, 1}, {2}, {1, 2}, {{2}, {1, 2}}}.
Theorem 2: If the elements of x are transitive then so are x and x.

Proof: Suppose that the elements of x are transitive.
(1) Let y  x. We must show that y  x, that is y  u for all u  x.
Let u  x. Then u is transitive. Since y  x, y  z for some z  x.
 z  u. Since y  z  u, y  u.
(2) Let y  x. Then for some z, y  z  x. Then z  u for some u  x.
Since y  z  u and u is transitive, y  u. Thus y  x. Hence x is transitive.
Example 2: The sets x = {{1, {1}}, {1}, 0, 1, 2} and y = {{2, {1}}, {1}, 0, 1, 2} are
transitive. Let u = {x, y}.
Then u = x  y = {{1}, 0, 1, 2} and x = {{1, {1}}, {2, {1}},{1}, 0, 1, 2}, both of
which are transitive.
73
§10.2 Ordinal Numbers
An ordinal number is a transitive set that is well-ordered by the relation
“ or =”. So, for ordinals, < and  are equivalent. We denote the class of ordinals by
Ord.
Examples 2: Ordinal numbers include all the natural numbers, as well as  and +.
If (X, ) is a well-ordered set X and is similar to the ordinal  we say that  is its
ordinal number. We shall show that this is uniquely defined. We denote the ordinal of
X by ord (X, ). If the ordering is understood we can write ord(X).
Theorem 3: If  is an ordinal number, then so is +.
Theorem 4: Elements of ordinals are ordinals.

Proof: Elements of ordinals are subsets and so are well-ordered. Let x  y  z  ,
where  is an ordinal. Then since  is transitive, x, y, z are elements of . Since  is
transitive on , x  z.
Theorem 5: Similar ordinals are equal.

Proof: Let f:  be a similarity. Suppose x is the smallest element of  such that
f(x)  x. If y < x then y = f(y) < f(x), whence x  f(x). Now suppose y < f(x).
Then, since f1 is a similarity, f1(y) < x. Hence y = f(f1(y)) = f f1(y) < x. So f(x)  x, a
contradiction. Hence there is no such x.
Theorem 6: If  and  are ordinal numbers and    then  is an element of .

Proof: Suppose ,  are ordinals such that   . Let x be the least element of   .
Since x   and  is transitive, x  .
Since (  )  x = 0, x  . Let y  . Then y  .
Since {x, y} has a least, either x  y or x = y or y  x. If x  y or x = y, then x  ,
contradicting the fact that x    . Thus y  x and so   x. But x  . Hence x = .
As x  ,   .
Theorem 7: Transitive subsets of ordinals are ordinals.

Proof: Suppose there is an ordinal  having a transitive subset which is not itself an
ordinal, and suppose  is the least element of + which has such a subset. Then there is
some X   which is transitive but not an ordinal. Then X is not well-ordered by . Let
0  Y  X have no least. Now the elements of Y are elements of the ordinal  and so are
ordinals, and hence transitive. Hence Y is transitive.
Let y  Y. Then Y  y  Y  X  . Hence y  . Thus y is an ordinal, and
being less than , the transitive subset Y must be an ordinal. By Theorem 6, Y  Y.
But clearly Y is the least element of Y, a contradiction.
74
Theorem 8: If X is a set of ordinals then X is an ordinal.
Proof: Suppose X is a set of ordinals. Then X is transitive. Let 0  Y  X. Then the
elements of Y are ordinals and so Y is transitive. Let   Y. Then Y  . Thus Y
is an ordinal. Hence Y   or Y =   Y. Hence if Y  Y, Y  Y, a
contradiction. Thus Y is the least element of Y. Hence X is well-ordered by . Thus
X is an ordinal.
Theorem 9 (Burali-Forti Paradox): The class of ordinals is not a set.

Proof: Suppose Ord is a set. Then Ord  Ord and so Ord  (Ord)+  Ord so
Ord  Ord, a contradiction.
§10.3 Transfinite Induction

The method of Proofs by Induction is very useful in mathematics. It works
because every non-empty set of natural numbers has a least, that is, the set of natural
numbers is well-ordered by the usual ordering. Finite induction can be extended to
infinite sets, provided we can well-order them.
Theorem 10 (Proof by Transfinite Induction): Suppose W is a well-ordered set and X

is a subset of W. Suppose that X has the property that whenever all the predecessors of
x are in X then so is x. Then X = W.
Proof: Suppose X  W. Then m = min(W  X)  C!
We can also define things by transfinite induction. The following is a special case.
Theorem 11: Suppose G is a generalized function whose domain is S, a subset of Ord

with no maximum. Then there exists a unique function f on S such that f(x +) = G(f(x))
for all x  S and f(x) = {f(y) | y < x} if x has no predecessor.
§10.4 The Arithmetic of Ordinal Numbers

A non-zero ordinal is a limit ordinal if it has no immediate predecessor. An
obvious example is .
We define addition of ordinals by transfinite induction as follows:
(A0)  + 0 = ;
(A1)  + + = ( + )+;
(A2)  +  =  { +  |  < } if  is a limit ordinal.
Example 3: Successively adding 1 to  we get the sequence  + 1,  + 2, …
We define multiplication of ordinals by transfinite induction as follows:

(M0) 0 = 0;
(M1) + = () + ;
(M2)  =  { |  < } if  is a limit ordinal.
We define exponentiation of ordinals by transfinite induction as follows:
75
(E0) 0 = 1;
(E1)  = .;
+
(E2)  = { +  |  < } if  is a limit ordinal and   0;

(E3) 0 = 0 if  is a limit ordinal.
Examples 4:
 + 1 =  + 0+ = ( + 0)+ by (A1) = + by (A0)  .
1 +  = {1 + n | n < } = .
2 = {2n | n < } by (M2) = .
2 = 1+ = 1 +  by (M1) = 0+ +  = (0 + ) +  by (M1)
= (0 + ) +  by (M0) = {0 + n | n < } +  =  +  =  { + n | n < } by (A2).
2 = {2n | n < } by (E2) = 
§10.5 Further Arithmetic of Cardinal Numbers

Theorem 12:If a, b are cardinal numbers and a is finite and b is infinite then a + b = b.
Proof: Choose A, B disjoint so #A = a, #B = b.
Let C  B such that #C = 0 and let D = B  C. Let #D = d.
Then b = 0 + d so a + b = a + 0 + d = 0 + d = b.
Theorem 13: If a is an infinite cardinal number then a + a = a.

Proof: Choose A so that #A = a.
Let F = {bijections f : X  2  X | X  A}.
F  0 (take X with #X = 0).
F is partially ordered by extension.
By Zorn’s Lemma  maximal f: X  2  X for some X  A.
If A  X is infinite we contradict the maximality of f so A  X is finite.
#X + #X = #X and #A = #X + #(A  X) so
#A + #A = #X + #X + 2#(A  X)
= #A + #(A  X)
= #A.
Theorem 14: If a  b are cardinal numbers and b is infinite then a + b = b.

Proof: Choose A, B with #A = a, #B = b.
Since a  b, a + b  b + b = b.
But b  a + b so a + b = b.
Theorem 15: If a is an infinite cardinal number then a.a = a.

Proof: Choose A so #A = a.
Let F = {bijections f : X  X  X | X  A}.
F  0 (take X with #X = 0).
F is partially ordered by extension.
By Zorn’s Lemma  maximal f: X  X  X for some X  A.
Let #X = x. Then x.x = x.
Suppose x < a.
76
Then #(A  X) = a and so A  X has a subset, Y with #Y = x.
Then #[(X  Y) + (Y  X) + (Y  Y)] = 3x.x
= x so
there exists a bijection from (X  Y) + (Y  X) + (Y  Y) to Y.
We can thus extend f to a bijection g: (X + Y)  (X + Y)  X + Y, a contradiction.
Hence x = a and so a.a = a.
At long last we can define a cardinal number as a set. A cardinal number is

simply an ordinal number that is not equivalent to any of its predecessors.
Theorem 16: The class of ordinals, C, equivalent to a set S is itself a set.

Proof: Well order (S) and let  be the corresponding ordinal.
Then   C   <     .
So C = {   |   S}.
Now that we have established that the set of ordinals equivalent to S is a set we
can define, for any set S #S to be the smallest ordinal equivalent to S. Clearly it is a
cardinal number.
We are now in a position to properly define the alephs, that is, to write every
infinite cardinal as  for some ordinal . Let  be an infinite cardinal number.
Let S be the set of infinite cardinal numbers that are less than  (less than in the sense
of cardinal numbers). S is well-ordered by .
Let  be the ordinal number of this well-ordered set.
Then we denote  by .
Example 5: Let  = . Then S = {0, 1, 2, …} with

0 < 1 < 2 < …
The ordinal number of this well-ordered set is , which justifies the use of the notation
.
Example 6: Let  = +1. Then S = {0, 1, 2, …, } with

0 < 1 < 2 < … < 
The ordinal number of this well-ordered set is  + 1, which justifies the use of the
notation +1.
Theorem 17: If  is an ordinal number and # =  then    < +1.

Proof:    by definition of cardinals.
If +1   then +1  , a contradiction.
Theorem 18:  = { |  < } is a cardinal number.

Proof:  is an ordinal number.
Suppose  = # and  < .
Then   , so    for some  < .
Then  <   , a contradiction.
77
Theorem 19: { |  < +} = .
Proof: If  < + then    and so   .
Theorem 20: If  has no predecessor then { |  < } = .

Proof: Let  = { |  < }.
For all  < ,    and so   .
Hence   .
If  < ,  + 1 <  so +1  , a contradiction.
78

CHAP10 Ordinal Numbers

Uploaded by

Copyright:

Available Formats

CHAP10 Ordinal Numbers

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

CHAP10 Ordinal Numbers

Uploaded by

Copyright:

Available Formats

10.

A set x is transitive if x  x, that is, if every element of an element of x is

Example 1: Recall that (1, 2) = {{1}, {1, 2}}.

Theorem 1: A set x is transitive if and only if x x.

Example 1 (continued): Observe that every element of y is a subset of y, since

Theorem 2: If the elements of x are transitive then so are x and x.

Theorem 3: If  is an ordinal number, then so is +.

Theorem 4: Elements of ordinals are ordinals.

Theorem 5: Similar ordinals are equal.

Theorem 6: If  and  are ordinal numbers and    then  is an element of .

Theorem 7: Transitive subsets of ordinals are ordinals.

Theorem 9 (Burali-Forti Paradox): The class of ordinals is not a set.

§10.3 Transfinite Induction

Theorem 10 (Proof by Transfinite Induction): Suppose W is a well-ordered set and X

Theorem 11: Suppose G is a generalized function whose domain is S, a subset of Ord

§10.4 The Arithmetic of Ordinal Numbers

Example 3: Successively adding 1 to  we get the sequence  + 1,  + 2, …

We define multiplication of ordinals by transfinite induction as follows:

We define exponentiation of ordinals by transfinite induction as follows:

(E2)  = { +  |  < } if  is a limit ordinal and   0;

§10.5 Further Arithmetic of Cardinal Numbers

Theorem 13: If a is an infinite cardinal number then a + a = a.

Theorem 14: If a  b are cardinal numbers and b is infinite then a + b = b.

Theorem 15: If a is an infinite cardinal number then a.a = a.

At long last we can define a cardinal number as a set. A cardinal number is

Theorem 16: The class of ordinals, C, equivalent to a set S is itself a set.

Example 5: Let  = . Then S = {0, 1, 2, …} with

Example 6: Let  = +1. Then S = {0, 1, 2, …, } with

Theorem 17: If  is an ordinal number and # =  then    < +1.

Theorem 18:  = { |  < } is a cardinal number.

Theorem 20: If  has no predecessor then { |  < } = .

You might also like