intro
4.2.1
Introduction to the Fast Growing Hierarchy
Introduction
The Fast Growing Hierarchy (FGH for short) is the de-facto standard large number notation in professional mathematical circles. What it is, in fact, is an infinite set of unary functions, each building on all the previous ones, resulting in a hierarchy of recursion. The fast growing hierarchy easily outranks anything presented in Sections I,II and III, and it is just as powerful a method for defining fast growing functions as Jonathan Bower's Array Notation. Better yet it is in some respects easier to define and more versatile than BEAF.
The reason it is of interest to us here, is because in professional mathematics it is used as the standard benchmark for any functions growth rate. It also exemplifies all of the main features of a googological function.
FGH is rather unique in that it's the one place in professional mathematics where you'll see googologically large numbers! Of course, FGH isn't just for the purpose of making large numbers (what self-respecting mathematician would want that!). For mathematicians it's a way to measure the computational strength of various mathematical subsystems. Basically a mathematical system can be measured by the largest set of FGH it can accommodate, that to say, the largest set it can prove are "terminating". For example, Peano Arithmetic is often cited as having strength epsilon-zero (the same strength as Jonathan Bowers' tetrational arrays). What this means is that we can define and prove closure on FGH below the epsilon-zero level, but not any higher. An interesting upshot of this is that Jonathan Bowers' tetrational arrays could actually be defined within Peano Arithmetic! Note however that Peano Arithmetic is a rather primitive mathematical system, and consequently the epsilon-zero level is not actually that far reaching. Mathematicians have gone much further, so we'll have to explore FGH well beyond the epsilon-zero level to gain a fuller appreciation of just how powerful this system is.
To do this will require some grounding in theory however. FGH uses a very different (though similar) conceptual framework than BEAF. Rather than discuss one master function which takes on spaces of entries, FGH is considered an entire family of unary functions, which have a well-defined order determined by their growth rate such that for any two members a faster growing member can always be determined. These functions are all indexed using a system known as Ordinal Notation. For this reason we will be spending a lot of time building up the theory of Ordinals. Originally ordinals were first invented in set theory as an attempt to "count" the members of infinite ordered sets, and therefore are usually interpreted as different orders of infinity. However, just like Bowers' use of spaces proves superfluous and merely as an interpretation of the basic mechanisms, we'll find that the infinitiary interpretation is also not strictly necessary and is only one of several possible interpretations, another popular one being to treat the ordinals as sets of smaller ordinals, a definition we'll be making ample use of. In this sense an ordinal is not so much an "infinite number" as a set, possibly but not necessarily, containing an infinite number of elements. The ordinals of greatest interest to us will be the "countable ordinals". That is the ordinals whose elements can be put in one-to-one correspondence with some subset of the natural numbers.
Brief History
Georg Cantor, the founder of set theory, invented the concept of transfinite numbers to measure the cardinality of sets. That is, to measure, in some sense, the size of the set concerned. For unordered sets, for which for any given element we can either say it is a member of the set or not, Cantor developed the Cardinal numbers. The Cardinality of the natural numbers was denoted aleph-zero, and the Cardinality of the real numbers was denoted aleph-one. Cantor asked the question: Is there any cardinality between aleph-zero and aleph-one? He believed there wasn't, but a proof eluded him. So he invented the ordinal numbers to measure the sizes of ordered sets, in an attempt to answer this question. Cantor used the symbol "w" , the greek lower case omega, to represent the ordinal size of the ordered set of natural numbers from least to greatest. He went on to develop an ordinal notation for ordinals we'll past w, up to the Cantorian Limit Ordinal (which I'll denote by "c"), which is the limit to his epsilon ordinal sequence. After this ordinal notations took on a life of their own, being further developed by others, such as Veblen, and also finding many new applications besides counting the length of well-ordered sets.
Around the same time computability theory was emerging. It was found that hierarchies of very fast growing functions could be created by diagonalization, and could be notated using ordinals. These functions would quickly surpass the elementary functions, and then even the primitive recursive functions. FGH, and variants on it emerged as a simple way to measure the strength of various types of recursive functions. The upshot for googologist's, who turn making recursive functions into a hobby in it's own right, is that we too can use FGH to measure the strength of the variously invented googological notations. For this reason we will spend a lot of time developing FGH. Ultimately we'll want to use FGH as a ranking system for all the other googological notations.
http://plato.stanford.edu/entries/recursive-functions/