applet-magic.com
Thayer Watkins
Silicon Valley
USA

 Ordinal Numbers and Their Arithmetic

There are two related but distinct concepts of enumeration, cardinal and ordinal. A cardinal number is one of the families consisting of all sets that can be put into one-to-one correspondence with each other. Thus 2 is the family of all sets that can be put into one-to-one correspondence with {1, 2}. In a sense, 2 represents the property of two-ness. While cardinality involves only sets, ordinality involves sets and order relations on those sets. An order relation is like that of "≤" although it doesn't have to be numerical inequality. For example, the ordering can the the lexicographic (alphabetical) ordering of words; "adz" comes before "bowl" in the dictionary.

Order relations may be reflexive as is ≤ or nonreflexive as is <. For simplicity "≤" will be used for any reflexive order relation.

A set is totally ordered if for any two elements a and b from A either a≤b, b≤a, or both, which means a=b.

A set is well ordered if all of its nonempty subsets have first elements under the order relation. That is to say, if S is a subset of A then there exists an element of S, say x, such that for any element y in S, x≤y. (Here it is important that the relation is reflexive; i.e., x≤x.)

An ordinal number is a family of well-ordered sets that can be put into one-to-one correspondences that preserve the order relations; i.e., if f:A→B and a1A a2 for a1,a2 ∈ A then b1=f(a1) ≤B b2=f(a2). Thus if a is the first element of A1 ⊂ A then f(a) is the first element of the set f(A1).

The collection of well-ordered sets is partitioned into equivalence classes. Each equivalence class contains all the well-ordered sets that are similar to each other. The equivalence classes may be thought of as having labels or indices.

In a well-order set A, the initial segment s(x) of an element x belonging to A is the set of all elements which precede x in A under the order relation; i.e., )

#### s(x) = {z |z ∈ A and z≤x}.

• Theorem 1: Let S(A) be the family of all initial segments of A. S(A) is ordered by set inclusion. The function f that maps an element x to its initial segment is one-to-one and onto; i.e., f:A→S(A). Furthermore f preserves order so A is similar to S(A).

• Theorem 2: Suppose A is a well-ordered set and B is a subset of A such that there exists a similarity mapping f of A into B. Then for every element x of A, x≤f(x).

Proof: Let D={x|f(x)≤x}. If D=φ, the empty set, then the theorem is true.

Suppose D is not empty. Then, since A is a well-ordered set, D has a first element d. Since d ∈ D, f(d)≤d. But, since f is a similarity mapping which preserves order f(f(d))≤f(d) and hence f(d) ∈ D. But f(d)≤d so there is a contradiction with the assumption that d is the first element of D. Therefore D must be empty.

• The next theorem is a very useful one.

Theorem 3: A well-ordered set cannot be similar to one of its initial segments.

Proof: Let A be a well-ordered set and f a similarity mapping of A onto the initial segment s(x) for some x ∈ A. By definition all elements of s(x) are less than x. Therefore f(x)≤x. But this contradict Theorem 2. Therefore a well-ordered set cannot be similar to one of its initial segments.

• Theorem 4: If A and B are well-ordered sets then either A and B are similar or one is similar to an intial segment of the other.

Proof: Consider the elements of each set whose initial sets are similar to the initial sets of elements in the other set; i.e., let

#### S = {x|x∈A and s(x) is similar to s(y) for some y∈B} T = {y|y∈B and s(y) is similar to s(x) for some x∈A}

For example, suppose A = {1,2,3,4} and B = {a,b,c,d,e}. Then S = {1,2,3,4} and T = {a,b,c,d}.

Continuation with the proof of Theorem 4. Claim: S is similar to T.

Proof of Claim: Consider an element of x. By definition there is an element y ∈ B such that s(x) is similar it s(y). This y is unique because otherwise there would be two initial segments of B, say s(y1) and s(y2) which were both similar to s(x) and hence similar to each other. But this implies that s(y1)=s(y2) and hence y1=y2. Likewise x the element of A such that s(x) is similar to y ∈ B is unique. This correspondence defines a one-to- one relationship between the elements of S and T. Thus S and T are similar.

There are three possibilities:

• 1. If S=A and T=B then A is similar to B.
• 2. If S=A and T=s(b) for some b ∈ B, then A is similar to an intial segment of B.
• 3. If T=B and S=s(a) for some a ∈ A, then B is similar to an initial segment of A.

The fourth possibility of S=s(a) for some a ∈ A and T=s(b) for some b ∈ B cannot occur. This would imply that a ∈ S, since its initial segment is similar to the initial segment of an element (E S) of B, but since S=s(a) this would have a belonging to its own initial segment. Thus there would be a contradiction.

Definition: The order type of a well-ordered set is the family of well-ordered sets it is similar to. In other words, the order type of a well-ordered set A, denoted ord(A), is the equivalence class A belongs to. If ord(A)=λ then A ∈λ.

There is a particular sequence of ordered sets that are appropriate to use to represent order types. For finite sets the following are "standard" order types:

#### φ, {φ, {φ}}, {φ,{φ},{φ, {φ}}}, …

where φ is used to denote the empty set.

Because this gets tedious to write the following labels are adopted:

Thus

#### φ → 0 {0} → 1 {0, 1} → 2 {0, 1, 2} → 3

The order type of the natural numbers, {0, 1, 2, 3, … } is denoted as omega, ω.

## The Ordering of Ordinals

The ordering of ordinal numbers is achieved through the following construction. If λ and μ are ordinal numbers and A and B are well-ordered sets such that ord(A)=λ and ord(B)=μ then:

λ < μ if A is similar to an initial segment of B
λ = μ if A is similar to B
λ > μ if B is similar to an initial segment of A
λ ≤ μ if λ ≤ μ or λ = μ
λ ≥ μ if λ > μ or λ = μ.

• Theorem 5: Any set of ordinals is well-ordered by ≤.

• Theorem 6: Let s(λ ) be the set of all ordinals less than λ . Then ord(s(λ ))=λ .

• Theorem 7: Every ordinal has an immediate successor.

• Definition of a limit element: An element of a well-ordered set is a limit element if it does not have an immediate predecessor and it is not the first element. A limit number is an ordinal which is a limit element of the ordinals.

• Theorem 8: For any infinite ordinal λ there exists ordinal numbers μ and n such that μ is a limit number and n is a finite ordinal.

## Addition of Ordinals

Definition of concatenation of well-ordered sets: Let A and B be well-ordered sets. Then (A ; B) is the union of A and B ordered by the relation R where any two elements x and y are ordered according their relation in A or B if they both belong to A or both belong to B and x Definition of addition of ordinals: For any two ordinals λ and μ let A and B be well-ordered sets such that ord(A)=λ and ord(B)=μ . Then

#### λ +μ = ord((A ; B)).

For this definition to be proper it must be established that λ+μ is independent of the representative A and B used in the construction.

Addition is not necessarily commutative; λ+μ is not necessarily the same as μ+λ . For example, 1+ω is not the same as ω+1; i.e., ω+1 = ord({0,1,2,...; 0}) but 1+ω is ord({0,0,1,2,3,...})=ω.

Addition is associative; (λ +μ)+ ν = λ +(μ + ν). There also exists an additive identity; i.e., the empty set φ.

• Theorem 9: The immediate successor of any ordinal λ is λ +1.

## Multiplication of Ordinals

### Definition of the cartesian product of well-ordered sets:

Let A and B be well-ordered sets. Then (A X B) is the cartesian product of A and B, order pairs (a,b) where a ∈ A and b ∈ B, ordered by the relation R where any two elements (x,y) and (z,w) are ordered according to

#### (x,y) ≤ (z,w) if y≤w in B or y=w and x≤z in A.

This is called a reverse lexicographic ordering.

Definition of multiplication of ordinals:

Definition of multiplication of ordinals: For any two ordinals λ and μ let A and B be well-ordered sets such that ord(A)=λ and ord(B)=μ . Then

#### λ*μ= ord((A × B)).

Again, for this definition to be proper it must be established that λ*μ is independent of the representative A and B used in the construction.

Multiplication is not commutative. For example, 2*ω is not the same as ω*2; i.e., 2=ord({a,b}) and ω=ord({1,2,..}) so

#### 2*ω = ord({(a,1),(b,1),(a,2),(b,2),...}) = ω but ω*2 = ord({(1,a),(2,a)...; (1,b),(2,b),...})

However, multiplication is associative.

In the folowing let card(A) stand for the cardinality of a set A.

• Theorem 10: Let A and B be well ordered sets. Then card(A)≤card(B) implies that ord(A)≤ord(B), and ord(A)≤ord(B) implies that card(A)≤card(B).

The order of the ordinals is 0,1,2,3,..., then ω,ω+1,ω+2,... then ω22+1, ω2+2,... to ω3 and so on to ωω.

From there the sequence goes on to ω to the power of ωω.

Next comes (ω to the power of ωω) to the power of ω
and on to (ω to the power of ω to the power of ω … .

But there is always a successor to any ordinal.

## Definition of Exponentiation of Ordinals

Definition of functions from one well-ordered set to another: Let A and B be well-ordered sets. Then AB is the set of all functions from A to B.

The Burali-Forti Paradox: The concept of the set of all ordinal numbers is contradictory.

Proof not given.

Modeling ordinal arithmetic in the programming language LISP is convenient because a list is exactly a well-ordered set. For any list one can construct the corresponding ordinal by creating a list that begins with "0" and ends with a cardinal that is one less than the length of the list. The middle of the ordinal list is just the ellipsis "…". Infinite ordinals are ones in which the … has no successor (other than the delimiters ";" and ")".