ordinal

Sbiis Saibian's

!!! FORBIDDEN LIST !!!

of

Recursive Ordinals

Introduction

Googology is mainly the study of very large finite numbers. However one can play an analogous game with large infinities. I call this transfinite googology, as opposed to the more usual finite googology. The existence of large infinities does not mean that finite googology is obsolete however. This is because the real driving forces behind all forms of googology are curiosity and challenge. Knowing about the larger infinities still does not give us any sense nor understanding of the infinite depth of complexity that lies hidden within the finite numbers, nor does it make the challenge of defining large finite numbers trivial. So the challenge and mystery of finite googology remains.

Why then as googologists should we be interested in the infinite? The reason is because Cantor's theory of infinity provides a great framework to study the order-types of transfinite sequences of fast growing functions, or googological notations. With "ordinals" we can measure the strengths of various functions and notations and compare them by simply determining which ordinal is larger. We can even use this system of ordinals to conveniently demarcate vast regions (which I call Epochs) of the finite numbers. Therefore some familiarity with the transfinite ordinals and ordinal notations is essential for any googologist.

In this Appendix, I will provide a list of several ordinals important to googologist's. I will describe them from the googologist's point of view, as measures of strength.

Briefly the ordinals may be obtained in this way. Begin with the empty set , { } , and denote it by 0. By definition this is an ordinal. We define an ordinal as the set of all smaller ordinals. Since there is no ordinal smaller than "0" it naturally contains no members.

Next every ordinal , α , has a successor defined as α+1 = α U {α}. That is, the successor of an ordinal includes it's predecessor as an element in addition to all the elements of it's predecessor. Thus the successor of the empty set is , { { } } , the set containing only the empty set, which can alternatively be written {0}, and denoted by 1. We can continue ... for every time we obtain a new ordinal we can form yet another one by finding it's successor. So the successor of {0} is the set {0,{0}} or {0,1}, which can be denoted by 1+1 or more commonly 2. In this way we can generate all the so called "finite ordinals" which are isomorphic to the non-negative integers.

To continue we introduce a new means of generation. Any "set" of ordinals can be used to generate a new ordinal. Let S be a set of ordinals. There is always a least ordinal , λ , which is greater than every member of S. Notice that in the case where we take a finite set of finite ordinals, this will always produce a finite ordinal. In fact, it will always produce the successor of the largest element of the set. What if the set of ordinals is infinite? Take for example the set {0,1,2,3,...}. This set has no largest member. This set however is guaranteed to generate another ordinal by our second principle of generation. Cantor denoted this ordinal by ω, and it is called omega. It is the smallest infinite ordinal. It is not however, the largest ordinal. There is in fact, no largest ordinal, because we can always keep generating new ones. To create an ordinal after ω we simply create the set ωU{ω}, denoted ω+1, which can be conveniently written as the set {ω,0,1,2,3,...}. Here we have used the first principle of generation to create a new ordinal after ω. With ω+1 in hand we can of course generate ω+2 , ω+3, and so on ... in this way we can form the set {0,ω,1,ω+1,2,ω+2,3,ω+3,...}. The smallest ordinal larger than every member of this set is called ω*2.

The collection of all ordinals is generated by simply continuing these two principles of generation indefinitely. With that basic primer let's now explore the ordinals as order-types of fast growing functions...

Ordinals

0

zero

Zero is the very smallest ordinal. As the beginning of the sequence it holds the unique distinction of neither being a "successor ordinal" nor a "limit ordinal".

As an order-type this represents the "base-case" for a particular Hierarchy of Fast-growing functions, or the simplest case for some googological notation. Conventionally the successor function, S(n) = n + 1, is by definition of order-type 0. We can define the order-type of any function or notation as the smallest order-type in FGH which is equivalent or exceeds the growth rate of the function or any function definable with the given notation. By this definition almost no functions are of order-type 0. Some examples would include the Constant functions which always return the same value, the projection function , R(n) = n, as well as all functions of the form f(n) = n + k , for some constant k. Functions this slow are of no major interest to googology except as theoretical foundations.

1

One

One is the very first Successor ordinal. This is also a unique distinction.

An order-type of 1 is typically the first primitive recursion (or something roughly equivalent) of the base case. If the base case is sufficiently weak, primitive recursions may not produce faster growing functions. Typically however an order-type of 1 represents (n)[1] in the fast-growing hierarchy. This is equivalent to the function 2n. There are very few functions with an order type this low. Any linear equation , mx+b, where the slope is equal to or less than 2, will have an order type of 1, if it is not dominated by an order-type of zero. So for example 3n/2 will have an order-type of 1, but "n" will have an order type of 0, and 3n will have an order type greater than 1.

ω

omega

ωαλ