ordinal.h

This is a header made to allow the creaton, comparison and arithmetic of ordinal numbers up to ε₀.

What is an ordinal number?

An ordinal number is a generalization of the natural numbers used to describe the ordering of well-ordered sets.

What is a well-ordered set?

A totally-ordered set is a set where any element can be described as either "less than" or "greater than" any other element. A well-ordered set is a totally-ordered set such that any non-empty subset has a "least" element.

The Natural Numbers

The de-facto definition of the Natural numbers is known as the Von Neumann ordinals, which is as follows:

• Define '0' as the empty set ∅ = {}.
• Define the successor function S(x) = x ∪ {x}.
• Define '1' as S(0) = {0}, '2' as S(1) = {0,1}, '3' as S(2) = {0,1,2}, and so on.

This definition has two useful properties:

1. The natural number 'n' has n elements inside it.

   This property makes defining the size or 'cardinality' of a set easy in set theory. A set has size 'n' if every element can be mapped one-to-one to an element in 'n'. The set is sometimes said to be 'bijective' with n.

2. A natural number is the set of all naturals preceding it.

   This property makes defining the order between numbers easy. n < m if n is an element of m; equivalently if n is a subset of m. It also helps in defining certain functions

   • max(a,b) = a ∪ b
   • sup{ a_i | i ∈ I } = ∪_{i ∈ I} a_i

Transfinite Ordinals

The set of natural numbers ℕ is thus defined as {0,1,2,3,...}. The definition of size for the natural numbers also applies to ℕ itself. A set that is 'bijective' with ℕ is called 'countably infinite'.

If the successor function is applied to ℕ, we get S(ℕ) = {0,1,2,...,ℕ}. This is where the concept of ordinals begins to show use. S(ℕ) actually has the same cardinality as ℕ, as ℕ in S(ℕ) can be mapped to 0 in ℕ and n in S(ℕ) can be mapped to S(n) in ℕ. S(ℕ) and ℕ cannot be mapped together in a way that preserves order however, as S(ℕ) has a 'greatest' element while ℕ does not. This is refered to as the order type. The successor function can be applied to ℕ repeatedely to get different 'countably infinite' sets with different order types. These sets are called 'transfinite ordinals'. From here on, the set ℕ is referred to as ω.

• ω = {0,1,2,...}
• ω+1 = {0,1,2,...,ω}
• ω+2 = {0,1,2,...,ω,ω+1}

The initial definition of order for naturals holds in general for ordinals.

Limit Ordinals and Induction

There are two types of natural numbers: '0', and successor naturals. Every natural number that is not zero is preceded by another natural. This is not the case when generalizing to ordinals however, as the ordinal ω is not preceded by anything. An ordinal that is not zero and not a successor to another ordinal is called a limit ordinal.

Induction

There are two versions of induction.

• Weak induction

  This is the induction you would be taught in secondary school. Given a property P(n), if P(0) and P(n)⇒P(n+1) then P holds for all n.

• Strong induction

  Given a property P(n), if P(0) and (∀m<n P(m))⇒P(n) then P holds for all n.

The Weak and Strong forms of induction are equivalent when only working with natural numbers, but Weak induction cannot prove P(ω). Strong induction is required if induction on the ordinals (Transfinite induction) is to be attempted.

Arithmetic

Addition, Multiplication, and Exponentiation (but not subtraction, division, roots or logarithms) can be defined recursively on the ordinals similar to how they are recursively defined on the naturals, however they lose certain properties once you transcend the naturals.

Addition

Addition is defined as follows:

• For zero, a+0 = a
• For successors, a+S(b) = S(a+b)
• For limit ordinals, a+b = sup{ a+c | c < b }

Ordinal addition retains associativity ((a+b)+c = a+(b+c)) but loses commutivity. For example, 2+ω = sup{ 2+n | n∈ℕ } = ω ≠ ω+2. Imagine taking the two sets, placing them next to each other and ordering them such that elements on the right set are greater than elements on the left set.

ω + 2 = {0,1,...} + {0,1} = {0,1,...,0',1'} = ω+2

2 + ω = {0,1} + {0,1,...} = {0,1,0',1',...} ≡ {0,1,2,3,...} = ω

ω+ω = {0,1,...,ω,ω+1,...} = sup{ ω+n | n∈ℕ }

Multiplication

Multiplication is defined as follows:

• For zero, a*0 = 0
• For successors, a*S(b) = a*b + a
• For limit ordinals, a*b = sup{ a*c | c < b }

Ordinal multiplication retains associativity, but loses commutivity and right-distributivity.

Examples:

• ω*2 = ω*1 + ω = ω+ω
• 2*ω = sup{ 2*n | n∈ℕ } = ω
• ω*ω = sup{ ω*n | n∈ℕ }

Exponentiation

Exponentiation is defined as follows:

• For zero, a⁰ = 1
• For successors, a^S(b) = a^b * a
• For limit ordinals, a^b = sup{ a^c | c < b }

Ordinal exponentiation loses the property (a*b)^c = a^c*b^c

Examples:

• (ω*2)² = (ω*2)*(ω*2) = ω²*2
• (ω)²*(2)² = ω²*4
• a^ω = sup{ aⁿ | n∈ℕ } = ω
• ω^ω = sup{ ωⁿ | n∈ℕ }

Epsilon zero and the Cantor Normal Form

As addition is defined by repeated succession, multiplication by repeated addition, and exponentation by repeated multiplication, a function can be defined by repeated exponentiation. This function is called tetration. Repeated tetration will give what is called pentation, repeated pentation gives hexation, and so on. These are not standard operations however, and so the tetration of ω with itself is given a new name entirely:

ε₀ = sup{ ω, ω^ω, ω^ωω, ...}

Given only ω, ε₀ cannot be reached without the use of tetration. With only addition, multiplication, and exponentiation, the ordinals you can compute can be represented in "Cantor Normal Form": a sum of ω terms raised to the power of strictly decreasing ordinal terms multiplied by a natural coefficient in a manner similar to a polynomial or n-base representation.