Analysis_Hyper-E

3.3.2

An Analysis of Hyper-E Notation

Introduction

In Chapter 3.2 I introduced my Hyper-E and Extended Hyper-E notations.

Measuring Hyper-E Against Conway Chained Arrows

John Conway's Chained Arrow notation was introduced to the public in 1996 in "The Book of Numbers". It quickly gained popularity on the web as the next notation after Knuth Up-arrows for large numbers. They have achieved a certain notoriety for those whose interest in large numbers is more passive than academic. It is not difficult to find reasons for the popularity of chained arrows. Firstly, it is easy to use and understand. Secondly, it is extremely powerful in any casual discussion of large numbers and can easily express numbers vastly larger than Graham's Number. Thirdly, it can not be doubted that Conway's high profile and reputation played a large role in proliferating and popularizing the notation.

Yet from an academic standpoint, chain-arrows are not especially recursive or noteworthy. Notational systems such as Jonathan Bower's array notation, and the fast growing hierarchy go much much further, but are generally esoteric and difficult to explain to the laymen. To make matters worse, in the full set of recursive functions, chained-arrows are really just one amongst many possible alternatives in the same recursive range and are not necessarily the most natural choice. Some features of the notation can be awkward. The inability to specify an arbitrary starting integer for the beginning of a new chain length makes it difficult to match up with other notations in the same range.

Still there is something appealing about the notations simplicity and power. For most people "Chained-arrows" represent the end of the line for "officially recognized" large number notations. The truth is however that there is so authoritative body that decides what the standards of large number notation is, and in fact mathematicians would probably never institute such a thing. Mathematicians are less interested in the specifics of notations, and more interested in the general properties. Many alternative notations abound in mathematics, and some of these are even equivalent, rendering them redundant. However mathematicians generally adopt a "flavor" of notation that suits their fancy, and this is true to some extent in the large number field. There are several varieties of notations describing tetration, the hyper-operator hierarchy, and the fast-growing hierarchy, but no one seems to be complaining.

While Chained-arrows are certainly impressive, and already completely incomprehensible to our lowly exponential geared minds, it must be said that Conway never took the notation seriously himself. It occupies but 3 pages in the "Book of Numbers", and then only to provide some way to bound Graham's Number and describe an even faster sequence than the so called "Ackermann Numbers". It was by all accounts meant to amuse the laymen, but was never meant as a serious go at large numbers, because even by then, some mathematicians had extended the Grzegorczyk hierarchy to ordinals past e₀ back in the 1970s.

That being said however, due to the notoriety of Chained-arrows they have often been adopted as a kind of "standard of measure" in googology. Showing that a notation grows faster than chained-arrows is a simple way to show that the notation goes beyond what goes for "large" in laymen circles. Jonathan Bower's was quick to claim that even small numbers in his array notation were much larger than Graham's Number and those that could be expressed using Chained-arrow notation. Chris Bird added substance to this claim by proving that 4-argument arrays are already comparable to arbitrary length chains and that 5-arguments vastly exceed the notation. The implication seems to have been that array notation had gone much further than anything in "professional mathematics". It is therefore sobering to learn that professional mathematicians such as Harvey Friedman have studied even larger numbers in Ramsey theory than Graham's Number that reach much higher into the fast-growing hierarchy, surpassing even such Bowerian giants as a gongulus or goppatoth (More on these numbers in Section IV). Graham's Number no longer holds the title for largest number in a serious mathematical proof, and the fast-growing hierarchy represents a quasi-standard (in several varieties) for very large numbers that has implicitly (if not explicitly) been extended to all the countable ordinal notations effectively making it on par with array notation. So it turns out that professional mathematicians hold their own and it is a misconception to think that "Chained arrows" represent the best that they have for the representation of large numbers.

Now that I've given some explanation of the proper place that chained-arrows occupies in the whole grand scheme of googology, I will now develop a proof that shows that my own Extended Hyper-E Notation already is strong enough to exceed it, and in fact already surpasses it quickly after the introduction of the trito-hyperion separator (###). The interesting thing is that Extended Hyper-E notation is still quite simple and easy to use and yet is significantly more powerful and general than chain arrows. In fact, I will later show that Extended Hyper-E is on par with linear array notation, but first let's prove that trito-hyperions are already enough to exceed Conway's infamous chained-arrow notation.

Recall the following results:

b-->p-->c = b^^^ ... ^^^p w/c ^s

E_ba₁#a₂#a₃# ... #a_n >= b^^^...^^^a_n w/n ^s

It immediately follows that:

Lemma 1

E_ba₁#a₂#a₃# ... #a_n >= b-->a_n-->n

So at very least we can say that ordinary Hyper-E notation is on par with chains of length 3. We will call this observation lemma 1 or L1 and use it as the basis of our proof.

With this established we can now investigate the beginnings of Extended Hyper-E notation. Firstly observe that:

E_bb##a_n = E_bb#b#b# ... #b#b#b w/a_n b's >= b-->b-->a_n [via lemma 1]

We thereby establish lemma 2:

Lemma 2

E_bb##a_n >= b-->b-->a_n

This is really just an extension of our first result, but in this form we can now extend to the next stage of Extended Hyper-E notation. Note that:

E_bb##1#2 = E_bb##(E_bb##1#1) = E_bb##(E_bb) = E_bb##(b-->b)

>= b-->b-->(b-->b) [via Lemma 2] = b-->b-->2-->2 [def. of chained-arrows]

If the relation here is not already apparent the next stage should make it clear:

E_bb##1#3 = E_bb##(E_bb##1#2) >= E_bb##(b-->b-->2-->2) [via L2]

>= b-->b-->(b-->b-->2-->2) [via L2] = b-->b-->3-->2

As I've emphasized by highlighting the 3's above, there seems to be a clear correlation here. We could of coarse continue with such examples ad infinitum but this would not prove any general principle at work. To formally prove that we would need to use mathematical induction. To prove the general result:

E_bb##1#a_n >= b-->b-->a_n-->2

We will need to use what I'll call "induction order w". This kind of induction can prove something for an infinite sequence of cases. We begin by assuming there exists at least one k such that:

E_bb##1#k >= b-->b-->k-->2

Actually we needn't presuppose the existence of k, because I've already shown it for k=2 and k=3. (k=1 is trivially true since E_bb##1#1 = E_bb = b-->b = b-->b-->1-->2). Next we must use this assumption to prove that the successive case follows:

E_bb##1#(k+1) >= b-->b-->(k+1)-->2

Proving this is as simple as expanding out the left and applying L2 as necessary:

E_bb##1#(k+1) = E_bb##(E_bb##1#k) >= E_bb##(b-->b-->k-->2) [by assumption]

>= b-->b-->(b-->b-->k-->2) [L2] = b-->b-->(k+1)-->2 [def.of Chains]

Thus we can see that each case must imply it's successor, so that k=1 implies k=2 implies k=3, ad infinitum. Thus we establish Lemma 3:

Lemma 3

E_bb##1#a_n >= b-->b-->a_n-->2

So Extended Hyper-E goes at least as far as 4-argument chains ending in 2. Of coarse we've really only gotten started with either notation so it still remains to be seen which will out last the other. We now want to establish a chain-arrow equivalent for the next level of the Extended Hyper-E notation. We begin by observing that:

E_bb##1#1#2 = E_bb##1#(b-->b) >= b-->b-->(b-->b)-->2 [L3] = b-->b-->2-->3 [def.of Chains]

Furthermore:

E_bb##1#1#3 = E_bb##1#(E_bb##1#1#2) >= E_bb##1#(b-->b-->2-->3)

>= b-->b-->(b-->b-->2-->3)-->2 [L3] = b-->b-->3-->3 [def.of Chains]

Again a correlation can be seen between the 2nd to last argument in the chain, and the last argument in the Extended Hyper-E notation (xE#). Again induction order w can be used to prove the general case.