Transfinite Induction

\maketitle

1. Introduction

This is supposed to be a primer inspired by a piece by Hilbert Levitz. The theory of transfinite ordinals is a part of set theory. While the concept is tied up with the completed infinite and high cardinalities, we’ll emphasize more constructive aspects of the theory. There have been applicatons of constructive aspects of the theory. There have been applications of constructive treatments of ordinals to recursive function theory, and proof theory. Pretty much everything we need to know about ordinals follows from the following three properties of the class of all ordinals O.

2. Basic Properties of the System of Ordinal Numbers.

1. O has a well ordering, which will be denoted by .
2. Any well ordered set whatsoever is order isomorphic to (a unique) initial segment of O. The ordinal determining the segment is called the ordinal of the set. This makes the system of ordinals in some sense the “mother of all well ordered sets”
3. Any set of members of O has a strict upper bound (and therefore by well ordering, a least upper bound) in O. Warning: The collection of all ordinals itself is not a “set”. You’ll get hit with a famous paradox if you treat it like one. Sub-collections of initial segments of the ordinals are sets, and these are all we use. As a consequence of the well ordering, we see easily that:
   • One can do arguments by induction over the ordinals, or over any initial segment of them, if we use the form of the induction principle. Recall that for natural numbers we also have induction in the to form, but that fails as soon as one has an object greater than every natural number. Induction in the form frequently goes under the fancy name “transfinite induction”
   • We let 0 denote the smallest ordinal. Every ordinal has an immediate successor, so by taking repeated successors of zero, we generate all the natural numbers as an initial segment of the system of ordinals. Not all non-zero ordinals have an immediate predecessor. Those without an immediate predecessor are called limit ordinals. The smallest number is to follow all the natural numbers is denoted by and it is a limit ordinal. Each limit ordinal is the least upper bound (‘supremum’) of the set of smaller ordinals.
   • On account of the well ordering we can define by recursion operations of addition, multiplication, and exponentiation. The only added feature over recursion on natural numbers is that we need to specify what to do at limit ordinals.

   when is a limit ordinal.

   when is limit ordinal.

   when is a limit ordinal. It turns out that:

   • Addition an Multiplication are associative. Neither is commutative. Multiplication distributes from the left over addition; that is Right distributivity fails, but we do have the inequality
   • Addition, multiplication and exponetiation are (with trivial exceptions): i)Continuous strictly increasing function of the right argument. ii) Weakly monotone increasing functions of the left argument.

3. Cantor Normal Form

The theorem of ordinary number theory that justifies writing any non-zero number to a number base, like base 10 or base 2, applies to transfinite ordinals as well.

Theorem 1 Any non-zero ordinal can be written uniquely as a polynomial to any base greater than 1 with descending exponents and coefficients less than the base. The coefficients are written to the right of the base. Such a representation is called a Cantor normal form.

It’s common to use as the base the number , in which case the coefficients are natural numbers, thus a typical normal formlooks like:

where

• The rule for comparing two normal forms to see which represents the bigger ordinal is as follows: One first looks to see which has the highest leading exponent, if they are the same then you look to see which has the highest leading coefficient, etc. Such a method could go into an infinite regress on account of the fact (shown in the next section) that some ordinals can equal their own leading exponent.
• Numbers of the form determine initial segments closed under addition, and numbers of the form determine initial segments of the ordinals closed under multiplication.

4. Definition of the ordinal

• The limit of the sequence was named by Cantor. We can see that it’s a solution of the equation by the following simple argument: Consider the recursively defined sequence

  then Another way to say that a number is a solution of is to say that it’s a fixed point of the function .

• is the smallest ordinal bigger than that determines an initial segment closed under ordinal addition, multiplication, and exponetiation. From this it follows that you can’t denote it just using symbols 0, , plus, times, and exponetiation. One can show using Cantor Normal Form that anything smaller can be so represented.
• Actually a similar argument can be used to show additional fixed points and they run clear through the ordinals. They can be arranged in a transfinite sequence as

Next time we will consider computation with Ordinals on Real Computers. ;