Introduction to BEAF
this wiki
- Main article: BEAF
BEAF, or Bowers Exploding Array Function, is a googological function invented by Jonathan Bowers. This article is a walkthrough gradually introducing the function, meant to give an intuitive sense of how it works.
Arrow notation Edit
Before we can understand BEAF, we must understand the extended operators at its core. Arrow notation describes a set of operators invented by Donald Knuth:
- \(a\uparrow b = a^b\).
- \(a\uparrow\uparrow b = \underbrace{a\uparrow a\uparrow\ldots\uparrow a\uparrow a}_b = \underbrace{a^{a^{a^{.^{.^.}}}}}_b\). Googologists call this tetration; arrows should be solved from right to left.
- \(a\uparrow\uparrow\uparrow b = \underbrace{a\uparrow\uparrow a\uparrow\uparrow\ldots\uparrow\uparrow a\uparrow\uparrow a}_b\). Also known as pentation.
- etc
In general,
- \(a\uparrow^n b = \underbrace{a\uparrow^{n-1} a\uparrow^{n-1}\ldots\uparrow^{n-1} a\uparrow^{n-1} a}_b\) where \(a \uparrow^n b = a \underbrace{\uparrow\uparrow\uparrow\cdots\uparrow\uparrow\uparrow}_n b\).
Here are some examples:
- \(3\uparrow 4 = 3^4 = 81\) (3 to the power of 4)
- \(2\uparrow\uparrow 4 = 2\uparrow 2\uparrow 2\uparrow 2 = 2\uparrow 2\uparrow 4 = 2\uparrow 16 = 65536\) (2 tetrated to 4)
- \(4\uparrow\uparrow 4 = 2361022671...5261392896\) which has about \(8.0723\cdot 10^{153}\) digits (4 tetrated to 4)
- \(3\uparrow\uparrow\uparrow 3 = 3\uparrow\uparrow 3\uparrow\uparrow 3 = 3\uparrow\uparrow 3^{3^3} = 3\uparrow\uparrow 7625597484987\) (3 pentated to 3)
Operator notation Edit
Bowers developed a generalization of arrow notation that he calls operator notation:
- \(a\ \{n\}\ b = a\uparrow^n b\)
- i.e.: \(a\ \{1\}\ b = a^b\)
- and \(a\ \{n\}\ b = \underbrace{a\ \{n - 1\}\ a\ \{n - 1\}\ \ldots\ \{n - 1\}\ a\ \{n - 1\}\ a}_b\)
For example, \(3\ \{4\}\ 5 = 3\uparrow\uparrow\uparrow\uparrow 5\).
This form of operator notation is simply a shorthand for arrow notation. However, Bowers takes it a step further by wrapping n in two pairs of braces instead of one:
- \(a\ \{\{1\}\}\ b = \underbrace{a\ \{a\ \{\ldots a\ \{a}_b\}\ a\ldots\}\ a\}\ a\)
Bowers calls this a expanded to b. Here, b is the number of "layers" including the outside, or (number of a's + 1) / 2. (For the computer scientists out there, expansion is not primitive-recursive. You can't program it using only for loops with precalculated limits.)
An example:
- \(3\ \{\{1\}\}\ 3 = 3\ \{3\ \{3\}\ 3\}\ 3 = 3\ \{3\ \{2\}\ 7625597484987\}\ 3\)
If we change n to 2, we get multiexpansion.
- \(a\ \{\{2\}\}\ b = \underbrace{a\ \{\{1\}\}\ a\ \{\{1\}\}\ \ldots\ \{\{1\}\}\ a\ \{\{1\}\}\ a}_b\)
Higher values for n can be used:
- \(a\ \{\{3\}\}\ b = \underbrace{a\ \{\{2\}\}\ a\ \{\{2\}\}\ \ldots\ \{\{2\}\}\ a\ \{\{2\}\}\ a}_b\) (powerexpansion)
- \(a\ \{\{4\}\}\ b = \underbrace{a\ \{\{3\}\}\ a\ \{\{3\}\}\ \ldots\ \{\{3\}\}\ a\ \{\{3\}\}\ a}_b\) (expandotetration)
- expandopentation, expandohexation, etc.
All these operators are right-associative, and they work just like the lower hyper-operators.
Using three braces instead of two gives us explosion:
- \(a\ \{\{\{1\}\}\}\ b = \underbrace{a\ \{\{a\ \{\{\ldots a\ \{\{a\}\}\ a\ldots\}\}\ a\}\}\ a}_b\)
- \(a\ \{\{\{2\}\}\}\ b = \underbrace{a\ \{\{\{1\}\}\}\ a\ \{\{\{1\}\}\}\ \ldots\ \{\{\{1\}\}\}\ a\ \{\{\{1\}\}\}\ a}_b\) (multiexplosion)
- \(a\ \{\{\{3\}\}\}\ b = \underbrace{a\ \{\{\{2\}\}\}\ a\ \{\{\{2\}\}\}\ \ldots\ \{\{\{2\}\}\}\ a\ \{\{\{2\}\}\}\ a}_b\) (powerexplosion)
- \(a\ \{\{\{4\}\}\}\ b = \underbrace{a\ \{\{\{3\}\}\}\ a\ \{\{\{3\}\}\}\ \ldots\ \{\{\{3\}\}\}\ a\ \{\{\{3\}\}\}\ a}_b\) (explodotetration)
- explodopentation, explodohexation, etc.
Four sets of braces is detonation (multidetonation, powerdetonation, detonotetration, etc.), and five is pentonation (multipentonation, powerpentonation, pentonotetration, etc.) Then we have hexonation, heptonation, etc.
Our operator notation now has four arguments:
- \(a\ \{1\}\ b = a^b\)
- \(a\ \{1\}^d\ b = \underbrace{a\ \{a\ \{\ldots a\ \{a\}^{d - 1}\ a\ldots\}^{d - 1}\ a\}^{d - 1}\ a}_b\)
- \(a\ \{c\}^d\ b = \underbrace{a\ \{c - 1\}^d\ a\ \{c - 1\}^d\ \ldots\ \{c - 1\}^d\ a\ \{c - 1\}^d\ a}_b\)
Here, the superscript d's indicate the number of curly braces wrapped around c. For example, \(\{\ldots\}^4\) is a shorthand for \(\{\{\{\{\ldots\}\}\}\}\). This particular notation was not used by Jonathan Bowers.
Googologist Chris Bird proved that this 4-argument notation is about as powerful as chained arrow notation. We have barely scratched the surface of BEAF, however!
Linear array notation Edit
Operator notation is starting to burst at the seams. A simpler way to write \(a\ \{c\}^d\ b\) is \(\{a, b, c, d\}\). Our new notation is:
- \(\{a, b, 1, 1\} = a^b\)
- \(\{a, b, 1, d\} = \underbrace{\{a, a, \{a, a, \ldots \{a, a, a, d - 1\} \ldots, d - 1\}, d - 1\}}_b\) if \(d > 1\)
- \(\{a, b, c, d\} = \underbrace{\{a, \{a, \ldots \{a, a, c - 1, d\} \ldots, c - 1, d\}, c - 1, d\}}_b\) if \(c > 1\)
Ones are considered defaults, so we can chop off the end of an array if it consists only of ones. For example, \(\{a, b, 1, 1\}\) can just be written \(\{a, b\} = a^b\).
We can simplify rules 2 and 3 somewhat by relying on their recursive nature:
- \(\{a, b, 1, d\} = \underbrace{\{a, a, \{a, a, \ldots \{a, a, a, d - 1\} \ldots, d - 1\}, d - 1\}}_b\)
- \(= \{a, a, \underbrace{\{a, a, \ldots \{a, a, a, d - 1\} \ldots, d - 1\}}_{b - 1}, d - 1\} = \{a, a, \{a, b - 1, 1, d\}, d - 1\}\)
- \(\{a, b, c, d\} = \underbrace{\{a, \{a, \ldots \{a, a, c - 1, d\} \ldots, c - 1, d\}, c - 1, d\}}_b\)
- \(= \{a, \underbrace{\{a, \ldots \{a, a, c - 1, d\} \ldots, c - 1, d\}}_{b - 1}, c - 1, d\} = \{a, \{a, b - 1, c, d\}, c - 1, d\}\)
But you'll notice a problem with this refactoring. We've specified an inductive rule, but no base case, so in both cases \(b\) will keep decreasing forever! We supply a rule explaining what happens when \(b\) reaches \(1\):
- \(\{a, 1, c, d\} = a\)
This step is very important to the definition of BEAF. If it is not clear to you, try working it out on paper.
Five entries and more Edit
Let's recap with our current ruleset:
- \(\{a, b, 1, 1\} = \{a, b\} = a^b\)
- \(\{a, 1, c, d\} = a\)
- \(\{a, b, 1, d\} = \{a, a, \{a, b - 1, 1, d\}, d - 1\}\), \(b,d > 1\)
- \(\{a, b, c, d\} = \{a, \{a, b - 1, c, d\}, c - 1, d\}\), \(b,c > 1\)
With our new simplification, a pattern is faintly visible in the final two terms. Equipped with this knowledge, we will attempt a fifth argument:
- \(\{a, b\} = a^b\)
- \(\{a, 1, c, d, e\} = a\)
- \(\{a, b, 1, 1, e\} = ???\)
- \(\{a, b, 1, d, e\} = \{a, a, \{a, b - 1, 1, d, e\}, d - 1, e\}\), \(b,d > 1\)
- \(\{a, b, c, d, e\} = \{a, \{a, b - 1, c, d, e\}, c - 1, d, e\}\), \(b,c > 1\)
There's a gap in the third rule, but we can mend it by extrapolating back from the fourth and fifth rules:
- \(\{a, b, 1, 1, e\} = \{a, a, a, \{a, b - 1, 1, 1, e\}, e - 1\}\)
The addition of the fifth entry was mercifully simple. We can continue the pattern and add a sixth:
- \(\{a, b\} = a^b\)
- \(\{a, 1, c, d, e, f\} = a\)
- \(\{a, b, 1, 1, 1, f\} = \{a, a, a, a, \{a, b - 1, 1, 1, 1, f\}, f - 1\}\), \(b,f > 1\)
- \(\{a, b, 1, 1, e, f\} = \{a, a, a, \{a, b - 1, 1, 1, e, f\}, e - 1, f\}\), \(b,e > 1\)
- \(\{a, b, 1, d, e, f\} = \{a, a, \{a, b - 1, 1, d, e, f\}, d - 1, e, f\}\), \(b,d > 1\)
- \(\{a, b, c, d, e, f\} = \{a, \{a, b - 1, c, d, e, f\}, c - 1, d, e, f\}\), \(b,c > 1\)
We should generalize this to an arbitrary number of terms. To keep this concise, we'll introduce some terminology. The first entry \(a\) is the base, and the second \(b\) is the prime. After the prime, the first non-1 entry is the pilot; the entry immediately before it is the copilot, and all entries before that are the passengers. The value of the array is written \(v(A)\). Using these terms, we can completely describe linear array notation.
- Linear array notation
Let \(b\) be the base and \(p\) the prime.
- Base rule. If there is no pilot (that is, all entries after the prime are 1), then \(v(A) = b^p\).
- Prime rule. If the prime is 1, \(v(A) = b\).
- Catastrophic rule. Otherwise...
- Replace the copilot with a copy of the original array, but with the prime decreased by one.
- Decrease the value of the pilot by 1.
- Set all passengers to \(b\).
- (end of definition)
This is a re-creation of Bowers' classic array notation, written around 2002. The original used five rules, but we managed to slim it down to three as per the modern BEAF.
Examples Edit
We have completely solved linear arrays now, and now we'll present some examples to get a better intuitive sense.
\begin{eqnarray*} \{3,3,1,1,1,3\} &=& \{3,3,3,3,\{3,2,1,1,1,3\},2\} \\ &=& \{3,3,3,3,\{3,3,3,3,3,2\},2\} \\ &=& \{3,3,3,3,\{3,\{3,2,3,3,3,2\},2,3,3,2\},2\} \\ &=& \{3,3,3,3,\{3,\{3,\{3,1,3,3,3,2\},2,3,3,2\},2,3,3,2\},2\} \\ &=& \{3,3,3,3,\{3,\{3,3,2,3,3,2\},2,3,3,2\},2\} \\ &=& \{3,3,3,3,\{3,\{3,\{3,2,2,3,3,2\},1,3,3,2\},2,3,3,2\},2\} \\ &=& \{3,3,3,3,\{3,\{3,\{3,\{3,1,2,3,3,2\},1,3,3,2\},1,3,3,2\},2,3,3,2\},2\} \\ &=& \{3,3,3,3,\{3,\{3,\{3,3,1,3,3,2\},1,3,3,2\},2,3,3,2\},2\} \\ &=& \{3,3,3,3,\{3,\{3,\{3,3,\{3,2,1,3,3,2\},2,3,2\},1,3,3,2\},2,3,3,2\},2\} \\ &=& \{3,3,3,3,\{3,\{3,\{3,3,\{3,3,\{3,1,1,3,3,2\},2,3,2\},2,3,2\},1,3,3,2\},2,3,3,2\},2\} \\ &=& \{3,3,3,3,\{3,\{3,\{3,3,\{3,3,3,2,3,2\},2,3,2\},1,3,3,2\},2,3,3,2\},2\} \end{eqnarray*}
If all the entries in an array are the same, we can convert it to a simpler higher-order array:
Three entries converted to four:
- \(\{a,a,a\} = \{a,2,1,2\}\)
- \(\{a,a,\{a,a,a\}\} = \{a,3,1,2\}\)
- \(\{a,a,\{a,a,\{a,a,a\}\}\} = \{a,4,1,2\}\) and so on.
Four entries converted to five:
- \(\{a,a,a,a\} = \{a,2,1,1,2\}\)
- \(\{a,a,a,\{a,a,a,a\}\} = \{a,3,1,1,2\}\)
- \(\{a,a,a,\{a,a,a,\{a,a,a,\{a,a,a,\{a,a,a,a\}\}\}\}\} = \{a,6,1,1,2\}\)
Five entries converted to six:
- \(\{a,a,a,a,a\} = \{a,2,1,1,1,2\}\)
- \(\{a,a,a,a,\{a,a,a,a,a\}\} = \{a,3,1,1,1,2\}\)
- \(\{a,a,a,a,\{a,a,a,a,\{a,a,a,a,a\}\}\} = \{a,4,1,1,1,2\}\)
In general, \(\{a,b,1,1,...,1,1,2\} = \{a,a,a,...,a,a,\{a,a,a,...a,a,\{a,a,a,...,a,a,\{a,a,a,...,a,a\}\ldots\}\}\}\),with b-1 layers.
Multidimensional arrays Edit
We'll introduce a new operator, "b array of a":
- \(b \& a = \underbrace{\{a, a, ..., a, a\}}_b\)
This function "diagonalizes" through everything we've done so far. It's a sizable function; if you're familiar with the fast-growing hierarchy, then \(n \& n\) is about the level of \(f_{\omega^\omega}(n)\).
To continue extending array notation, we need to take a bit of a leap of intuition. \(b \& a\) is vaguely similar to \(a^b = \underbrace{\{a \cdot a \cdots a \cdot a\}}_b\), so let's write an "second-order array notation" with the base rule changed:
- Base rule. If there is no pilot (that is, all entries after the prime are 1), then \(v(A) = p \& b\).
To indicate second-order array notation, we'll put a subscript number 2 after the array: \(\{a, b\}_2 = p \& b\). Apart from this base rule, the other rules of array notation are left unchanged, so we still have \(\{a, b, c\}_2 = \{a, \{a, b - 1, c\}_2, c - 1\}_2\) and so forth. We might as well do order 3 while we're at it. Define \(b \&_2 a = \underbrace{\{a, a, ..., a, a\}_2}_b\), and replace \(\&\) with \(\&_2\) in the above base rule. Bam, third-order array notation.
From here the extension should be obvious and a little dull. Let's generalize and create a new ruleset with \(r\) as the order:
- Base rule. If there is no pilot and \(r = 1\), then \(v(A) = b^p\).
- Order rule. If there is no pilot and \(r > 1\), then \(v(A) = p \&_{r - 1} b\).
- The prime rule and catastrophic rule are unchanged.
So how can we take maximum advantage of this extension? By letting \(r\) be the value of an array:
- \(\{a, a, \ldots, a, a\}_{\{a, a, \ldots, a, a\}}\)
Heck, why not nest it \(b\) times?
- \(\{a, a, \ldots, a, a\}_{\{a, a, \ldots, a, a\}_{\{a, a, \ldots, a, a\}_{._{._.}}}}\) (where each array has \(a\) entries)
We'll use \(b \&_{1, 2} a\) to write this, allowing us to define "order-1,2 notation." (Hmmm...why "1,2"?) Next is \(2,2\), which is merely \(\{a, a, \ldots, a, a\}_{1,2}\). We can inductively define order-n,2 in the same way we defined order-n.
Now for 1,3:
- \(\{a, a, \ldots, a, a\}_{\{a, a, \ldots, a, a\}_{\{a, a, \ldots, a, a\}_{._{._.}},2},2}\)
and in general 1,n for n > 1:
- \(\{a, a, \ldots, a, a\}_{\{a, a, \ldots, a, a\}_{\{a, a, \ldots, a, a\}_{._{._.}},n - 1},n - 1}\)
Not bad so far. How about 1,1,2? We can see from here that \(r\) is taking on multiple entries, and can start to mirror the way ordinary arrays work. We find the first non-1 entry in \(r\), call that the "order-pilot," replace the order-copilot with a copy of the array with the prime decreased by 1, decrease the order-pilot, and set the first \(p\) entries to \(b\).
But why do we need to segregate the pilot and the order-pilot at all? We only need to care about the order when the array is just the base and the prime, as in \(\{b, p\}_{1,1,2}\). The crucial step here is saying that \(r\) is part of the array, and therefore the order-pilot is the pilot.
Let's revise our notation to put \(r\) within the curly braces. Bowers' fascination with higher dimensions let him to put \(r\) as the second row, e.g.:
\[\left\{ \begin{matrix} b,p \\ 1,1,2 \end{matrix} \right\}\]
Inline, we will write this as \(\{b, p\ (1)\ 1, 1, 2\}\), where the (1) indicates a break between rows. Again, each row is automatically filled with a (countably) infinite number of 1's, so this array is identical to \(\{b, p, 1\ (1)\ 1, 1, 2\}\) or \(\{b, p, 1, 1, 1\ (1)\ 1, 1, 2, 1, 1\}\).
Let's try our new two-row extension on the existing ruleset on, say, \(\{b, p (1) 2\}\). Immediately we see that there is no copilot! We'll need to revise the rules to accommodate copilotless cases. A less trivial problem happens here:
- \(\{b, p (1) 1, 1, 2\} = \{b, b, b, \ldots (1) b, \{b, p - 1 (1) 1, 1, 2\}\}\)
The problem is the infinite number of b's on the first row; we only want p of them. Our current definition of "passengers" has broken our system, so we'll repair it as well. In summary:
- The base is the first entry.
- The prime is the second entry.
- The pilot is the first non-1 entry after the prime.
- The copilot is the entry immediately before the pilot. It may not exist if the pilot is on the beginning of the second row.
- A previous entry is an entry before another one that's still on the same row. (So in \(\{a, b (1) c, d\}\), \(c\) is a previous entry to \(d\) but \(a\) and \(b\) are not.)
- The prime block of a row is the first \(p\) entries of that row.
- The airplane is the pilot and all previous entries. If the pilot is on the second row, the airplane also includes the prime block of the previous row.
- The passengers are all entries in the airplane except for the pilot and copilot (if it exists).
The rules are otherwise the same as linear array notation. No "order rule" is needed since what we originally called the order is now part of the array.
Here's a brief example:
\begin{eqnarray*} \{3,3,3 (1) 2\} &=& \{3,\{3,2,3 (1) 2\},2 (1) 2\} \\ &=& \{3,\{3,\{3,1,3 (1) 2\},2 (1) 2\},2 (1) 2\} \\ &=& \{3,\{3,3,2 (1) 2\},2 (1) 2\} \\ &=& \{3,\{3,\{3,2,2 (1) 2\},1 (1) 2\},2 (1) 2\} \\ &=& \{3,\{3,\{3,2,2 (1) 2\} (1) 2\},2 (1) 2\} \\ &=& \{3,\{3,\{3,\{3,1,2 (1) 2\},1 (1) 2\} (1) 2\},2 (1) 2\} \\ &=& \{3,\{3,\{3,3 (1) 2\} (1) 2\},2 (1) 2\} \\ &=& \{3,\{3,\{3,3,3 (1) 1\} (1) 2\},2 (1) 2\} \\ &=& \{3,\{3,\{3,3,3\} (1) 2\},2 (1) 2\} \\ &=& \{3,\{3,3\uparrow\uparrow\uparrow3 (1) 2\},2 (1) 2\} \\ &=& \{3,\{\underbrace{3,\cdots,3}_{3\uparrow\uparrow\uparrow3}\},2 (1) 2\} \end{eqnarray*}
More rows Edit
The smallest nontrivial three-row array is \(\{b, p (1) (1) 2\}\), where the second row is only ones. As you might expect, this is equal to \(\{b, b, \ldots, b, b (1) b, b, \ldots, b, b\}\) with \(p\) entries per row. The pilot has now moved to the third row, and we can introduce a copilot as in \(\{b, p (1) (1) 1, 2\} = \{b, p (1) (1) \{b, p - 1 (1) (1) 1, 2\}\}\). More than three rows behave pretty much the same, so let's take the opportunity to generalize.
We will need to alter our definition of the airplane again:
- The airplane is the pilot, all previous entries, and the prime blocks of all previous rows.
When the pilot is on the first row, there are no previous rows and the airplane is just the previous entries. This takes care of the ugly conditional in our previous airplane.
Now we have completely defined planar array notation. So what is there beyond a row?
Three dimensions Edit
A plane. We'll use the (2) separator to indicate a planar break. The smallest two-plane array is \(\{b, p (2) 2\} = \{b, b, \ldots, b, b (1) b, b, \ldots, b, b (1) \ldots (1) b, b, \ldots b, b (1) b, b, \ldots, b, b\}\), or a \(p \times p\) array of \(b\)'s. (We can also write this as \(p^2 \& b\), more on that later.) Eventually we'll reach multiple planes, which pretty much solve as expected.
Let's define this formally. To aid in generalization, we need to introduce some more abstract terms. One of them is a structure, which is either an entry, a row, or a plane. Now we'll define prime blocks of structures in general.
- The prime block of a row is the first \(p\) entries, and the prime block of a plane is the first \(p \times p\) square of entries (or the prime blocks of the first \(p\) rows).
- A previous entry to X is an entry before X on the same row. A previous row to X is a row before X on the same plane.
- The airplane is the pilot, all previous entries, and the prime blocks of all previous structures.
Study that last definition carefully, because it's a core part of how BEAF works.
Four and more Edit
An infinite line of planes, or a three-dimensional space, is a realm, according to Bowers. A four-dimensional space is a flune. The symbols to indicate breaks in realms and flunes are (3) and (4), respectively.
Generally, (n) indicates a break into the next n-dimensional space. A comma is short for (0), since an entry is a 0-dimensional space. A "structure" is any n-dimensional space; we'll notate an n-D structure as \(X^n\).
Let's revise our definitions of "structure," "prime block," "previous structure," and "airplane."
- A structure is an entry, row, plane, realm, flune, 5-space, ... Inductively, this is defined as an entry or an infinite row of structures.
- The prime block of a row is the first \(p\) entries; the prime block of a plane is the first \(p \times p\) square; the prime block of a realm is the first \(p \times p \times p\) cube, etc. Inductively, the prime block of of a row is the first \(p\) entries, and the prime block of an \(X^n\) structure is the prime blocks of the first \(p\) \(X^{n-1}\)-structures.
- A previous structure to A is an \(X^n\) before A on the same \(X^{n + 1}\) structure. Specifically, a previous entry to A is an entry before A on the same row, a previous row to A is a row before A on the same plane, etc.
- The airplane is the pilot, all previous entries, and the prime blocks of all previous structures.
Up to here we have completely defined dimensional array notation. Recap with full rules:
- Dimensional array notation
Definitions:
- The base \(b\) is the first entry.
- The prime \(p\) is the second entry.
- The pilot is the first non-1 entry after the prime.
- The copilot is the entry immediately before the pilot. It may not exist if the pilot is on the beginning of a row.
- A structure is an entry, row, plane, realm, flune, 5-space, ... Inductively, this is defined as an entry or an infinite row of structures.
- The prime block of a row is the first \(p\) entries; the prime block of a plane is the first \(p \times p\) square; the prime block of a realm is the first \(p \times p \times p\) cube, etc. Inductively, the prime block of of a row is the first \(p\) entries, and the prime block of an \(X^n\) structure is the prime blocks of the first \(p\) \(X^{n-1}\)-structures.
- A previous structure to A is an \(X^n\) before A on the same \(X^{n + 1}\) structure. Specifically, a previous entry to A is an entry before A on the same row, a previous row to A is a row before A on the same plane, etc.
- The airplane is the pilot, all previous entries, and the prime blocks of all previous structures.
- The passengers are all entries in the airplane excluding the pilot and copilot (if it exists).
Rules:
- Base rule. If there is no pilot (that is, all entries after the prime are 1), then \(v(A) = b^p\).
- Prime rule. If the prime is 1, \(v(A) = b\).
- Catastrophic rule. Otherwise...
- If the copilot exists, replace the copilot with a copy of the original array, but with the prime decreased by one.
- Decrease the value of the pilot by 1.
- Set all passengers to \(b\).
- (end of definition)
Whew! This is "extended array notation," developed by Bird and Bowers. The original used seven rules, but we have applied the modern BEAF definition to simplify it quite a bit.
Array of operator Edit
The array of operator, notated & (not to be confused with logical "and" operator) returns the array assigned to the structure at the left to &, filled with the number of entries at the right to &. What are these structures? First structures are numbers, and \(n\ \&\ m = \{\underbrace{m,m,m,\cdots,m,m,m}_{\text{n m's}}\}\). The structure above numbers, so called X-structure, should be evaluated to m. So, \(X\ \&\ m = m \&\ m = \{m,m (1) 2\}\).
If we want to specify other number, we can enclose it by brackets: \(X\ \&\ a[b] = b\ \&\ a[b]\). This notation hasn't been used by Bowers himself.
The structures above numbers X are X+1,X+2,X+3,...,2X,2X+1,2X+2,2X+3,...,3X,4X,...,\(X^2\), etc. X+m can be thought as a line of entries with m entries below it, 2X as two lines, 3X as three lines, nX+m as n lines of entries with m entries below it all. Here are some correspondences between our notations above and "array of":
\begin{eqnarray*} 1\ \&\ n &=& \{n\} = n \\ 2\ \&\ n &=& \{n,n\} = n^n \\ 3\ \&\ n &=& \{n,n,n\} = n \uparrow^{n} n \\ 4\ \&\ n &=& \{n,n,n,n\} = n \underbrace{ \{\{\cdots\{\{n\}\}\cdots\}\} }_{n \{\}'s} n \\ m\ \&\ n &=& \{\underbrace{n,n,n,\cdots,n,n,n}_{\text{m n's}}\} &=& \{n,m (1) 2\} \\ X\ \&\ n &=& \{\underbrace{n,n,n,\cdots,n,n,n}_{\text{n n's}}\} &=& \{n,n (1) 2\} \\ X+1\ \&\ n &=& \{\underbrace{n,n,n,\cdots,n,n,n}_{\text{n n's}} (1) n\} \\ X+2\ \&\ n &=& \{\underbrace{n,n,n,\cdots,n,n,n}_{\text{n n's}} (1) n,n\} \\ X+3\ \&\ n &=& \{\underbrace{n,n,n,\cdots,n,n,n}_{\text{n n's}} (1) n,n,n\} \\ X+m\ \&\ n &=& \{\underbrace{n,n,n,\cdots,n,n,n}_{\text{n n's}} (1) \underbrace{n,n,n,\cdots,n,n,n}_{\text{m n's}}\} \\ 2X\ \&\ n &=& \{\underbrace{n,n,n,\cdots,n,n,n}_{\text{n n's}} (1) \underbrace{n,n,n,\cdots,n,n,n}_{\text{n n's}}\} \\ 3X\ \&\ n &=& \{\underbrace{n,n,n,\cdots,n,n,n}_{\text{n n's}} (1) \underbrace{n,n,n,\cdots,n,n,n}_{\text{n n's}} (1) \underbrace{n,n,n,\cdots,n,n,n}_{\text{n n's}}\} \\ mX\ \&\ n &=& \{\underbrace{X\ \&\ n(1)X\ \&\ n(1)X\ \&\ n(1)\cdots(1)X\ \&\ n(1)X\ \&\ n(1)X\ \&\ n}_{\text{m X's}}\} &=& \{n,m (2) 2\} \\ X^2\ \&\ n &=& \{\underbrace{X\ \&\ n(1)X\ \&\ n(1)X\ \&\ n(1)\cdots(1)X\ \&\ n(1)X\ \&\ n(1)X\ \&\ n}_{\text{n X's}} &=& \{n,n (2) 2\} \end{eqnarray*}
As can be seen, last three examples can be simplified to \(\{n,3 (2) 2\}, \{n,m (2) 2\}\) and \(\{n,n (2) 2\}\) respectively. Here the last "2" is in the next plane and marks the start of 3-D arrays. Fortunately, we don't have to draw multidimensional arrays in its natural form. The main key to it is using polynomial form: the expression \(a_1X^m+a_2X^{m-1}+a_3X^{m-2}+\cdots+a_{m-1}X+a_m \&\ b[p]\) means that its array is formed by \(a_1\) sections of \(X^m\) (m-D array of b's), then \(a_2\) sections of \(X^{m-1}\), then \(a_3\) sections of \(X^{m-2}\), and so on. The total number of entries can be found by replacing every X to p and solving like normal polynomial. For example, \(X^{100}+X^{99} \&\ 3[4]\) has \(4^{100}+4^{99}\) entries.
Tetrational arrays Edit
Up to here, we have a system at the level of \(f_{\omega^{\omega^\omega}}\) for those familiar with FGH. The next step is not entirely obvious, but it's crucial for continuing the system.
- \(\{b, p (0, 1) 2\}\)
What does this even mean? This is an \(X^X\) structure, and the prime block of an \(X^X\) structure is a \(p^p\) structure, or a \(\underbrace{p \times p \times \cdots \times p \times p}_p\) hypercube. So it's a 2-by-2 square, or a 3-by-3-by-3 cube, or a 4-by-4-by-4-by-4 tesseract, etc. When we actually solve the array, we can replace (0, 1) with (p) — for example, \(\{b, 4 (0, 1) 2\} = \{b, 4 (4) 2\}\).
Technical note: the space described by an \(X^X\) structure is called a dimensional group. In a dimensional group, each coordinate is described by a row of coordinates (order type \(\omega\)) rather than a fixed finite number.
- \(\{b, p (1, 1) 2\}\)
This is an \(X^{X + 1}\) structure; its prime block is \(p^{p + 1}\). Generally, an \((n, m)\) separator creates an \(X^{mX + n}\) structure. It is a row of dimensional groups.
Linear separator arrays can describe all possible \(X^P\), where \(P\) is a polynomial in \(X\). (Here and in the rest of the article, we restrict "polynomial" to have nonnegative integer coefficients.) They do this by supplying a list of coefficients from degree 0 on:
- \((a_0, a_1, a_2, a_3, \ldots)\) describes a structure of type \(X^{a_0 + a_1X + a_2X^2 + a_3X^3 + \cdots}\)
So, for example, (0, 0, 1) describes \(X^{X^2}\) (dimensional gang), and (1, 0, 6, 1) describes \(X^{1 + 6X^2 + X^3}\). You will notice that now zeroes are the default rather than 1's; this is one of BEAF's more annoying properties.
- \(\{b, p (0 (1) 1) 2\} = \{b, p ((1) 1) 2\}\)
Of course, we have no reason to stop at linear arrays for separators. This structure is \(X^{X^X}\), a superdimensional group. (Vectors in a superdimensional group have order type \(\omega^\omega\).) In general for the second row,
- \((a_{00}, a_{01}, a_{02}, \ldots (1) a_{10}, a_{11}, a_{12}, \ldots )\) describes a structure of type \(X^{a_{00} + a_{01}X + a_{02}X^2 + a_{03}X^3 + \cdots + a_{10}X^X + a_{11}X^{X + 1} + a_{12}X^{X + 2} + \ldots}\).
The third row ((1)(1)1) describes \(X^{X^{2X}}\) (no, we're not at \(X^{X^{X^X}}\) yet!), and the (n + 1)-th row describes \(X^{X^{nX}}\). The second plane ((2)1) is \(X^{X^{X^2}}\), the second realm ((3)1) is \(X^{X^{X^3}}\), and so on and so forth. We finally reach \(X^{X^{X^X}} = X \uparrow\uparrow 4\) at the second dimensional group, ((0, 1) 1). The inner pair of parentheses describes a polynomial \(P\) in \(X\), with the outer one describing \(X^{X^{X^P}}\).
- \(\{b, p (((1) 1) 1) 2\}\)
This is \(X^{X^{X^{X^X}}} = X \uparrow\uparrow 5\).
- \(\{b, p (((0, 1) 1) 1) 2\}\) describes \(X \uparrow\uparrow 6\)
- \(\{b, p ((((1) 1) 1) 1) 2\}\) describes \(X \uparrow\uparrow 7\)
- \(\{b, p ((((0, 1) 1) 1) 1) 2\}\) describes \(X \uparrow\uparrow 8\)
- etc.
The limit of all this is the \(X \uparrow\uparrow X\) structure. If we stop here, we have tetrational array notation.
Attempt at definition Edit
Bowers never bothered to formalize tetrational arrays, but we'll give it a try. The only thing holding us back right now is the definition of prime blocks, which is specifically tailored for dimensional arrays only. Let's look at our current inductive definition:
- The prime block of an entry is an entry.
- The prime block of an \(X^{n + 1}\) structure is the prime blocks of its first \(p\) \(X^n\)-structures.
(There is a slight change here, but it can be seen that it has minimal effect.) This definition doesn't say what happens when our structure is an \(X^X\) structure, because it's not a structure of the form \(X^{n + 1}\).
Let's try to extend this definition to allow all \(X^P\) for degree-1 polynomials \(P\).
- The prime block of an entry is an entry.
- The prime block of an \(X^{P+1}\) structure is the prime blocks of its first \(p\) \(X^P\)-structures, where \(P\) is a polynomial in \(X\).
- The prime block of an \(X^{P+X}\) structure is the prime block of its first \(X^{P + p}\)-structure.
This breaks down at \(X^{X^2}\) as expected, but there is a pattern emerging.
- The prime block of an entry is an entry.
- The prime block of an \(X^{P + 1}\) structure is the prime blocks of its first \(p\) \(X^P\)-structures, where \(P\) is a polynomial in \(X\).
- The prime block of an \(X^{P + X}\) structure is the prime block of its first \(X^{P + p}\)-structure.
- The prime block of an \(X^{P + X^2}\) structure is the prime block of its first \(X^{P + pX}\)-structure.
- The prime block of an \(X^{P + X^3}\) structure is the prime block of its first \(X^{P + pX^2}\)-structure.
- In general, the prime block of an \(X^{P + X^{n + 1}}\) structure is the prime block of its first \(X^{P + pX^n}\)-structure.
This works up until \(X^{X^X}\). At this rate we'll never get to \(X \uparrow\uparrow X\)!
Second attempt Edit
Let's generalize the concept of "structure" to help out our definition.
- \(0\) is a structure.
- If \(\alpha\) is a structure, \(X^\alpha\) is also a structure.
- If \(\alpha\) and \(\beta\) are structures, \(\alpha + \beta\) is also a structure.
This allows things like \(2X\) and \(4X^X + X + 1\), and works up until our limit of \(X \uparrow\uparrow X\). Furthermore, let's define a limit structure as one of the form \(X^\alpha\) for \(\alpha > 0\) or \(\alpha+\beta\) for \(\alpha\) and \(\beta\) being limit structures, and a successor structure as one of the form \(\alpha + 1\).
Now we'll recursively define the prime block of a structure \(\alpha[p]\).
- \(0[p] = \{\}\)
- \((\alpha + 1)[p] = \alpha[p] \cup \{\text{the last entry of }\alpha + 1\}\)
- \(X[p] = p\) and \(X^{\alpha + 1}[p] = X^{\alpha} p\)
- \(X^{\alpha}[p] = X^{\alpha[p]}\) if and only if \(\alpha\) is a limit structure.
- \((X^{\alpha_1} + X^{\alpha_2} + \cdots + X^{\alpha_{k - 1}} + X^{\alpha_k})[p] = (X^{\alpha_1} + X^{\alpha_2} + \cdots + X^{\alpha_{k - 1}} )[p] \cup X^{\alpha_k}[p])\) where \(\alpha_k\) is the smallest \(\alpha_i\)
- \(X\uparrow\uparrow X[0] = 1\) and \(X\uparrow\uparrow X[p] = X^{X\uparrow\uparrow X[p-1]}\)
If you are confused by now, skip it. All you need an intuitive conception of how this works.
There's one final step. Notice how we used the word "smallest" in the definition above, but structures aren't numbers and we haven't yet defined an ordering. This is easy:
- \(\alpha < \alpha + X^0\)
- \(X^\alpha < X^\beta\) iff \(\alpha < \beta\)
- \(\alpha + \gamma < \beta + \gamma\) iff \(\alpha < \beta\)
And we're done! Tetrational arrays.
But can we make this simpler?
As ordinals (advanced) Edit
Some of our more experienced readers may notice the parallels to ordinal hierarchies. \(X\) functions a lot like \(\omega\), and our prime block definition looks like that of the Wainer hierarchy — we picked the \(\alpha[p]\) notation for a reason. We have developed a notation for ordinals up to \(\varepsilon_0\), which is also the strength of BEAF up to this point. It seems reasonable to rewrite our notation using ordinals, and we'll do just that.
We'll define an array as a function \(A : \varepsilon_0 \mapsto \mathbb{N}_+\), where the number of outputs greater than 1 is finite. (This prevents infinite arrays like {6, 6, 6, ...}.) Let \(b = A(0)\), \(p = A(1)\), \(\pi = \min\{\alpha > 1: A(\alpha) > 1\}\) (the position of the pilot), and \(\kappa = \pi - 1\) (the position of the copilot).
Define the prime block \(\Pi(\alpha)\):
- \(\Pi(0) = \{\}\)
- \(\Pi(\alpha + 1) = \{\alpha\} \cup \Pi(\alpha)\)
- \(\Pi(\alpha) = \Pi(\alpha[p])\) if \(\alpha\) is a limit ordinal
(This looks a lot like the slow-growing hierarchy.) Define the passengers as \(S = \Pi(\pi) \backslash \{\pi, \kappa\}\).
And the three rules:
- Base rule. If \(\pi\) does not exist, \(v(A) = b^p\).
- Prime rule. If \(p = 1\), \(v(A) = b\).
- Catastrophic rule. Define \(A'\) as \(A\) with the following modifications:
- Define \(B\) as \(A\), but with \(B(1) = p - 1\).
- If \(\kappa\) exists, \(A'(\kappa) := v(B)\).
- \(A'(\pi) = A(\pi) - 1\).
- \(A(\sigma) := b\) for \(\sigma \in S\).
- \(v(A) = v(A')\).
Although less accessible, this is a far simpler definition than above!
One more thing; let's define some fundamental sequences for ordinals below \(\varepsilon_0\).
- \(\omega^\alpha[n] = \omega^{\alpha[n]}\) for limit ordinals \(\alpha\)
- \(\omega^{\alpha + 1}[n] = \omega^\alpha n\)
- \((\omega^{\alpha_1} + \omega^{\alpha_2} + \cdots + \omega^{\alpha_k})[n] = \omega^{\alpha_1} + \omega^{\alpha_2} + \cdots + \omega^{\alpha_k}[n]\) where \(\alpha_1 \geq \alpha_2 \geq \cdots \geq \alpha_k\)
- \(\omega \uparrow\uparrow 0 = 1\)
- \((\omega \uparrow\uparrow (\alpha + 1))[n] = \omega^{\omega \uparrow\uparrow \alpha}[n]\)
We threw in a definition of \(\omega \uparrow\uparrow n\) to ensure that we properly mirror Bowers' \(X\) hierarchy. Indeed, after \(\varepsilon_0\) the fundamental sequences depart a bit from the usual.
Pentational arrays Edit
Pentational arrays are a bit of a mindblow. By far the worst part is that no notation has yet been devised to support them! Bowers never bothered to put one together; he just used the array of operator.
Remember the array of operator?
- \(a \& b = \{b, a (1) 2\}\)
We left it behind long ago in the single-row era. Turns out, & has an extension that allows use beyond this level.
- \(a^2 \& b = \{b, a (2) 2\}\)
It's not hard to see that the right-hand side is an a by a array of b's, or an a^{2} array of b's. Note that the expression "\(a^2\)" should not be solved first; rather it is a blueprint for the dimensions of the array.
- \(a^k \& b = \{b, a (k) 2\}\)
In general, the array-of operator lets us specify many dimensions, and even tetrational arrays such as this one:
- \(a^{a^a} \& b = a \uparrow\uparrow 3 \& b = \{b, a ((1) 1) 2\}\)
For those who understood the ordinal definition above, we can formally define \(f(a) \& b = \{0 \mapsto b, 1 \mapsto a, f(\omega) \mapsto 2\}\).
The smallest pentational array is this one:
- \((a \uparrow\uparrow a) \& b = \{b, a (???) 2\}\)
There is no notation for this array (an \(X \uparrow\uparrow X\) structure), but it's certainly definable with ordinals, where \(\omega \uparrow\uparrow \omega = \varepsilon_0\) using the fundamental sequence \(\varepsilon_0[n] = \omega \uparrow\uparrow n\). We'll take a moment to apologize to the readers who don't get ordinals yet. Skip ahead to the legion arrays if you're one of them.
At this point you may be wondering what \(X \uparrow\uparrow\uparrow X\) is, but we can't move on to that until we've defined \(X \uparrow\uparrow (X2)\) or the fundamental sequence of "\(\omega \uparrow\uparrow (\omega2)\)". Our current definition of \(\uparrow\uparrow\) over the ordinals would make \(\omega \uparrow\uparrow (\omega2) = \omega \uparrow\uparrow \omega\), so we need to repair that.
If we amend our definition to \(\omega \uparrow\uparrow (1 + \alpha) = \omega^{\omega \uparrow\uparrow \alpha}\), we can clearly see that \(\omega \uparrow\uparrow (1 + \omega) = \omega \uparrow\uparrow \omega\) is the fixed point of the function \(\alpha \mapsto \omega^\alpha\).
\(\omega \uparrow\uparrow (\omega2)\) should be the next fixed point, i.e. \(\varepsilon_1\). One particularly clean definition of \(\varepsilon_1\) is the limit of \(\varepsilon_0, \varepsilon_0^{\varepsilon_0}, \varepsilon_0^{\varepsilon_0^{\varepsilon_0}}, \ldots\), so why not make \(\varepsilon_1 = \varepsilon_0 \uparrow\uparrow \omega = (\omega \uparrow\uparrow \omega) \uparrow\uparrow \omega\)? This seems slightly odd at first, since in general \(a \uparrow\uparrow a2 \neq (a \uparrow\uparrow a) \uparrow\uparrow a\). Ordinals work in mysterious ways.
The next fixed point is \(\omega \uparrow\uparrow (\omega3) = \varepsilon_1 \uparrow\uparrow \omega = \varepsilon_2\), and in general \(\omega \uparrow\uparrow (\omega n) = \varepsilon_{n - 2} \uparrow\uparrow \omega = \varepsilon_{n-1}\) for finite \(n > 0\). Understandably, the limit of all these is \(\omega \uparrow\uparrow (\omega^2) = \varepsilon_\omega\).
Yada yada yada. Nothing too interesting here until \(\varepsilon_{\varepsilon_0} = \omega \uparrow\uparrow (\omega \uparrow\uparrow \omega) = \omega \uparrow\uparrow\uparrow 3\) an \(\varepsilon_{\varepsilon_{\varepsilon_0}} = \omega \uparrow\uparrow\uparrow 4\). The triple arrows are quite promising, and indeed the limit of all this is \(\zeta_0 = \omega \uparrow\uparrow\uparrow \omega\). Boom. Done.
Formal definition Edit
Good news: formalizing this is just a matter of defining some functions over the ordinals and the fundamental sequences they create. Arrow notation is not part of standard ordinal arithmetic, so we have to define it ourselves:
- \(\alpha \uparrow\uparrow 0 = 1\)
- \(\alpha \uparrow\uparrow (n + 1) = \alpha^{\alpha \uparrow\uparrow n}\) for \(n < \omega\)
- \(\alpha \uparrow\uparrow \beta = \bigcup\{\gamma < \beta : \alpha \uparrow\uparrow \gamma\}\) for limit ordinals \(\beta\)
- \(\alpha \uparrow^{k} (\beta + \omega) = lim\{(\alpha \uparrow^k \beta),(\alpha \uparrow^k \beta)^{(\alpha \uparrow^k \beta)},(\alpha \uparrow^k \beta)^{(\alpha \uparrow^k \beta)^{(\alpha \uparrow^k \beta)}},...\}\) for \(\beta \geq \omega\)
- \((\alpha \uparrow\uparrow \beta)[n] = \alpha \uparrow\uparrow \beta[n]\)
Further sublegion arrays Edit
We ended the last section with \(\zeta_0 = \omega \uparrow\uparrow\uparrow \omega\). We can also write \(\omega \uparrow\uparrow\uparrow \omega = \{\omega, \omega, 3\}\), and what's to stop us from defining \(\{\omega, \omega, 4\}\)? Or \(\{\omega, \omega, 1, 2\}\)? Or \(\{\omega, \omega (0, 1) 2\}\)?
The only barrier is formality: we need to define BEAF for ordinals. We'll start off with arrow notation for a finite number of arrows:
- \(\alpha \uparrow \beta = \alpha^\beta\)
- \(\alpha \uparrow^k 0 = 1\)
- \(\alpha \uparrow^{k + 1} (n + 1) = \alpha \uparrow^k (\alpha \uparrow^{k + 1} n)\) for \(n < \omega\)
- \(\alpha \uparrow^k \beta = \sup\{\gamma < \beta : \alpha \uparrow^k \gamma\}\) for limit ordinals \(\beta\)
- \(\alpha \uparrow^{k} (\beta + \omega) = lim\{(\alpha \uparrow^k \beta),(\alpha \uparrow^k \beta)\uparrow^{k-1}(\alpha \uparrow^k \beta),(\alpha \uparrow^k \beta)\uparrow^{k-1}(\alpha \uparrow^k \beta))\uparrow^{k-1}(\alpha \uparrow^k \beta),...\} \) for \(\beta \geq \omega\)
- \((\alpha \uparrow^k \beta)[n] = \alpha \uparrow^k \beta[n]\)
It's not hard to see that ordinal arrow notation is similar to the Veblen function, and the differences are mostly in the fundamental hierarchies. Analogous to the Veblen unction, \(\alpha \mapsto \omega \uparrow^{k + 1} (\omega + \alpha)\) enumerates the fixed points of \(\alpha \mapsto \omega \uparrow^k \alpha\).
Already this definition is mildly annoying due to the sheer number of rules. Anyways, let's try \(k = \omega\):
- \(\alpha \uparrow^\omega \beta = \sup\{k < \omega : \alpha \uparrow^k \beta\}\)
- \((\alpha \uparrow^\omega \beta)[n] = \alpha \uparrow^n \beta\)
Take note that \(\omega \uparrow^\omega \omega = \phi_\omega(0)\). Our existing framework works for successor ordinals \(k\), but we need some limits here:
- \(\alpha \uparrow^\kappa \beta = \sup\{\gamma < \kappa : \alpha \uparrow^\gamma \beta\}\)
- \((\alpha \uparrow^\kappa \beta)[n] = \alpha \uparrow^{\kappa[n]} \beta\)
Putting it all together:
- \(\alpha \uparrow \beta = \alpha^\beta\)
- \(\alpha \uparrow^\kappa 0 = 1\)
- \(\alpha \uparrow^{\kappa + 1} (n + 1) = \alpha \uparrow^\kappa (\alpha \uparrow^{\kappa + 1} n)\) for \(n < \omega\)
- \(\alpha \uparrow^\kappa (\beta + 1) = (\alpha \uparrow^\kappa \beta) \uparrow^\kappa \alpha\) for \(\beta \geq \omega\)
- \(\alpha \uparrow^\kappa \beta = \sup\{\gamma < \kappa : \alpha \uparrow^\gamma \beta\}\) for limit ordinals \(\kappa\)
- \(\alpha \uparrow^\kappa \beta = \sup\{\gamma < \beta : \alpha \uparrow^\kappa \gamma\}\) for limit ordinals \(\beta\)
- \((\alpha \uparrow^\kappa \beta)[n] = \alpha \uparrow^{\kappa[n]} \beta\) for limit ordinals \(\kappa\)
- \((\alpha \uparrow^\kappa \beta)[n] = \alpha \uparrow^\kappa \beta[n]\) for limit ordinals \(\beta\)
This definition works okay, but the last two pairs of rules have identical conditions. In the case of \((\omega \uparrow^\omega \omega)[n]\), we'd rather have \(\omega \uparrow^n \omega\), so if \(\kappa\) and \(\beta\) are limit ordinals, we should focus on \(\kappa\) first.
In the meantime, let's write this out as three-entry array notation. This is ordinary three-entry notation with some limit ordinal cases. To simplify things, we won't allow any of the entries to be 0 as with ordinary array notation.
- \(\{a, b, 1\} = a^b\)
- \(\{a, 1, c\} = a\)
- \(\{a, b + 1, c + 1\} = \{a, \{a, b, c + 1\}, c\}\) for \(b < \omega\)
- \(\{a, b + 1, c\} = \{\{a, b, c\}, a, c\}\) for \(b \geq \omega\)
- \(\{a, b, c\} = \sup\{x < c: \{a, b + 1, x\}\}\) for \(c \in \text{Lim}\)
- \(\{a, b, c + 1\} = \sup\{x < b: \{a, b + 1, c + 1\}\}\) for \(b \in \text{Lim}\)
- \(\{a, b, c\}[n] = \{a, b, c[n]\}\) for \(c \in \text{Lim}\)
- \(\{a, b, c + 1\}[n] = \{a, b[n], c + 1\}\) for \(b \in \text{Lim}\)
Where \(\text{Lim}\) is set of all limit ordinals.
We can also remove the fourth and fifth rules if we define them as the limits of the sixth and seventh rules, respectively.
Now for four entries:
- \(\{a, b, 1, 1\} = a^b\)
- \(\{a, 1, c, d\} = a\)
- \(b < \omega:\)
- \(\{a, b + 1, 1, d + 1\} = \{a, \{a, b, 1, d + 1\}, 1, d\}\)
- \(\{a, b + 1, c + 1, d\} = \{a, \{a, b, c + 1, d\}, c, d\}\)
- \(b > \omega:\)
- \(\{a, b + 1, c, d\} = \{\{a, b, c, d\}, a, c, d\}\)
- \(\{a, b, c, d\}[n] = \{a, b, c, d[n]\}\) for \(d \in \text{Lim}\)
- \(\{a, b, c, d + 1\}[n] = \{a, b, c[n], d + 1\}\) for \(c \in \text{Lim}\)
- \(\{a, b, c + 1, d + 1\}[n] = \{a, b[n], c + 1, d + 1\}\) for \(b \in \text{Lim}\)
Generalization is easy from here.
- Linear ordinal array notation
Definitions are unchanged — the first entry is the base \(b\), the second entry is the prime \(p\), the first non-1 entry after the prime is the pilot, the entry before it is the copilot, and the passengers are all entries before the copilot. In addition, we'll define the limiter \(l\) as the last limit ordinal after the base; it may not exist if there are only successor ordinals from the prime on.
All entries are between zero and \(\omega_1\) exclusive.
- Base rule. If there is no pilot, \(v(A) = b^p\).
- Prime rule. If \(p = 1\), \(v(A) = b\).
- Catastrophic rule. If there is no limiter and \(p < \omega\)...
- Replace the copilot with a copy of the array with the prime decreased by 1.
- Decrease the pilot by 1. (The pilot must be a successor ordinal or a finite cardinal, otherwise there would be a limiter.)
- Set all the passengers to \(b\).
- Infinite catastrophic rule. If there is no limiter and \(p \geq \omega\)...
- Replace the base with a copy of the array with the prime decreased by 1. (The prime must be a successor ordinal, otherwise there would be a limiter.)
- Set the prime to the original value of \(b\).
- Limit rule. Otherwise...
- Let \(v(A)[n]\) be the value of the array with the limiter changed to \(l[n]\).
- \(v(A) = \sup\{1 \leq n < \omega : v(A)[n]\}\).
- (end of definition)
Of course, we have no reason to stop at linear arrays. Our tetrational BEAF easily extends to ordinals; we just need to throw in the limit rule, and expand the domain of \(A\) from \(\varepsilon_0\) to \(\omega_1\), the first ordinal without a fundamental sequence with countable length. We'll prohibit ourselves from just plugging in any large countable ordinal, since we're building from the ground up and using BEAF to define the ordinals as we go along.
By the way, what ordinals have we defined? Quite a few.
- \(\Gamma_0 = \{\omega, \omega, 1, 2\}\) (expandal arrays)
- \(\vartheta(\Omega^2) = \{\omega, \omega, 1, 1, 2\}\)
- \(\vartheta(\Omega^\omega) = \{\omega, \omega (1) 2\}\)
- \(\vartheta(\Omega^\Omega) = \{\omega, \omega, 2 (1) 2\}\)
- \(\vartheta(\varepsilon_{\Omega + 1}) = \{\omega, \omega (\varepsilon_0) 2\}\)
The limit of our notation at the moment is \(\vartheta(\Omega_\omega)\). This is quite an accomplishment!
Legion arrays Edit
Thank you, non-ordinal readers, for waiting this long! Up to now we have what could be called "sublegion BEAF." Bowers called everything up to this point "L-space."
We're resurrecting the array of operator & again. As our notations get more and more powerful, so does &: by now we have a good definition for things such as {3, 3, 3}&3 (triakulus), a pentational array. The array of operator will always be able to diagonalize over our most powerful notations.
Note that we can also write triakulus as (3&3)&3, and we'll make the operator left-associative so we can get rid of parentheses as in 3&3&3. This naturally invites an operator, b♦p = b&b&...&b&b p times. This operator expresses the limit of sublegion BEAF; it's the most powerful function we've defined so far. Note that the ♦ notation hasn't been used by Bowers himself.
\(b♦p\) reminds us a bit of \(b^p\), so let's use the same trick we did far back in two-row arrays. We can make this "second-order sublegion BEAF" by redefining the base rule to \(b♦p\).
As we did with two-row array notation, we could keep expanding higher-order sublegion BEAF until we need to merge the order into the array. We'll cut to the chase and immediately put the order into the array.
- \(\{b, p / 2\} = b♦p\)
The slash separator marks off a new kind of space called legion space. The pilot 2 is in the second legion, in the same way that we moved the pilot to the second row way back in planar array notation. The prime block of a legion is \(b♦p\), so for example \(\{b, p / 3\} = \{b♦p / 2\}\).
- \(\{b, p / 1, 2\} = \{b♦p / \{b, p - 1 / 2\}\}\)
Legions form a larger space than rows, planes, or any structure we've defined so far, so we can put multiple entries in the second legion.
- \(\{b, p / 1 / 2\} = \{b♦p / b♦p\}\)
We can also throw in more than two legions...
- \(\{b, p (/1) 2\} = \{b♦p / b♦p / \ldots / b♦p / b♦p\}\) with \(p\) legions
- \(\{b, p (/0,1) 2\} = \{b♦p / b♦p / \ldots / b♦p / b♦p\}\) where the legions form a \(p^p\) structure
...and the legions themselves can take on dimensional structures of any size.
Another notation for \(\{b, p (/1) 2\} = \{b♦p / b♦p / \ldots / b♦p / b♦p\}\) is \(p \&\& b\), or p legion array of b. Similarly, \(\{b, p (/(1)1) 2\} = p^p \&\& b\), so the && operator works similarly to & but with legions instead of entries. We'll use b♦♦p to mean b&&b&&..&&b&&b p times, and we'll introduce "legion legion space" using the separator \(//\).
- \(\{b, p // 2\} = b♦♦p = b \&\& b \&\& \ldots \&\& b \&\& b\)
- \(\{b, p (//1) 2\} = \{b♦♦p / b♦♦p / \ldots / b♦♦p / b♦♦p\} = b \&\&\& p\)
- \(\{b, p /^n 2\} = b♦^np = b \&^n b \&^n \ldots \&^n b \&^n b\)
- \(\{b, p (/^n1) 2\} = \{b♦^np / b♦^np / \ldots / b♦^np / b♦^np\} = b \&^{n + 1} p\)
Extension is straightforward.
- \(\{b, p (1)/ 2\} = \{b, p /^p 2\} = b (1)\& p\)
- \(\{b, p ///(1)///(1)/// 2\}\)
Why not give the legions a multidimensional structure themselves? Trouble is, we need to define this. Let L be a legion structure, which is greater than all structures up to but not including legions. (So L is a legion in the same way that X is a row.) We could say that L = {X, X / 2}, but that's uncomfortably circular. Anyways, the prime block of a legion is \(b♦p\).
Two legions is a \(2L\) structure, a row of legions is an \(XL\) structure, a legion legion // is an \(L^2\) structure. From here we can put L inside an array the same way we wrote things such as {X, X, X}. We can write \(\{L, L\}\) or \(\{L, L, L\}\) or \(\{L, X (1) 2\} = X\&L\). Unfortunately, by this time we have no notation for separators, but Bowers supplied the notation \(\{L, L\}_{b, p}\) (say) to mean an \(\{L, L\}\) structure solved with b as the base and p as the prime.
We continue to drop L into larger and larger arrays until we reach the landmark \(\{L, L / 2\}\), or lugion space. Bowers also writes this \(L2\) using the separator \ and the operator \(a@b\), or a legiattic array of b.
Formalization Edit
We will quickly catch up on the definition of legion arrays with ordinals. First, we'll notice that the array-of operator has three parts: a base, prime, and structure type. For example, \(3\&4\) has base 4, prime 3, and structure type X, and \(3 \uparrow\uparrow\uparrow 4 \& 5\) has base 5, prime 3, and structure type \(X \uparrow\uparrow\uparrow 4\). Bowers' minor abuse of notation can be mended with a three-argument array-of operator:
- \(\lambda(b, p, \xi) = \{(0, b), (1, p), (\xi, 2)\}\)
That is, base \(b\), prime \(p\), and the number 2 in position \(\xi\). Normally \(\xi\) is a limit ordinal, but our new function allows any \(\xi > 1\).
The ordinal for legion space is the unnamed ordinal \(\vartheta(\Omega_\omega) = \{\omega, \omega / 2\}\), and its fundamental sequence is \(\vartheta(\Omega_\omega)[1] = \omega,\,\vartheta(\Omega_\omega)[2] = \lambda(\omega, \omega, \omega),\,\vartheta(\Omega_\omega)[3] = \lambda(\omega, \omega, \lambda(\omega, \omega, \omega)),\) and so and so forth. This defines the prime block of a \(\vartheta(\Omega_\omega)\) structure as defined before.