Direct continuation of: Large Numbers, Part 2: Graham and Conway

In the first post of this series, we built a basic understanding of magnitude through the use of exponentiation and Knuth up-arrows that was then thrown out the window in the second post when we started going through Graham’s Number and Conway chained-arrows.

Now we’re going to start all over again, and build an even larger number. But to do this, we’re going to start at the most basic unit — the function.

The Basics of Growing a Function

A function is something like “y = f(x)” where x is an input and y is an output — it turns every input into a unique output. A function like f(x) = x+1 will take every input, add one to it, and turn that into the output. It does this for every x, ever.

Our first function will be just that: f(x) = x+1, and we’re only interested in integers 0 and larger. Therefore, the first output will be 0+1 = 1, the second will be 1+1 = 2, the third will be 2+1 = 3, etc. Continuting this, we get 4, 5, 6, 7, 8, 9, …

Functional Powers

Obviously, this function alone isn’t going to get us anywhere. So we need to do yet another step. The next step is to plug the function back into itself, so we look for f(f(x)), not f(x). This means that every input will be (x+1)+1, or x+2. Then we can repeat this again and try for f(f(f(x))), and then try for f(f(f(f(x)))), and onward.

The amount of nested functions can be written in something called functional powers, written with a superscript to denote how many copies of a function there will be.

The First Diagonalization Function

Then we can make a function and call it f[1](x) that is f^x(x), or f(f(f(…f(f(x)))…))) with x nested functions.

f[1](x) produces values that look like this: f(1), f(f(2)), f(f(f(3))), f(f(f(f(4)))), f(f(f(f(f(5))))), f(f(f(f(f(f(6)))))), …

Or, once evaluated: 2, 4, 6, 8, 10, 12, …

This function has changed from adding one to doubling the function. f₁(x) = x + x = 2x

This function is also the first thing of what we call a diagonalization function. Diagonalization functions take the “x”th value from the “x”th function in a previous series of functions. “f(x), f(f(x)), f(f(f(x))), …” is a series of functions, with each function individually having an infinite amount of values.

By combining them into a diagonalization function (a process called diagonalization), we get a new function that will grow faster than all the functions in the series.

How Diagonalization Works

So all those words were just said… but how do they make sense? What is a diagonalization? Well, in order to diagonalize, you first make an infinite list of functions, such as “f(x), f(f(x)), f(f(f(x))), f(f(f(f(x)))), …”. Then you take the 1st value from the 1st function, f(1) = 2; the 2nd value from the 2nd function, f(f(2)) = 4; the 3rd value from the 3rd function, f(f(f(3))) = 6; and so on, constructing a new function by taking all of the values on the diagonal. We will call this f₁(x):

Growing “Faster”

So what does it mean for f₁(x) to grow faster? Since f¹⁰⁰⁰(2) = 1002 and f₁(2) = 4, why is f₁(2) considered the “larger” function? Well, it all has to do with this thing called growth rate.

The growth rate is a measure of how much the output of a function changes as the input changes. In the example of f(x), as x is increased by 1, f(x) is increased by 1; f(a+1) = f(a) + 1. This means the function has a growth rate of “1″.

Generally, if you have a function g(x) and a function h(x), if g(x) is the “faster function”, then “g(a) – g(b)” will be greater than “h(a) – h(b)” for more values of a and b than it is false, provided “a > b”. In layman’s terms, the “faster function” is the one that, in the end, produces the larger numbers.

For example, consider “g(x) = 1000x” and “h(x) = x^x”. g(x) starts out growing larger, since the difference between g(0) and g(1) is 1000, whereas the difference between h(0) and h(1) is only 1. However, in the end, h(x) grows larger, since the difference between g(1000) and g(1001) is 1000, whereas the difference between h(1000) and h(1001) is about 10^3003.

h(x) = x^x in blue eventually grows much faster than g(x) = 1000x in purple.

Many More Diagonalizations

So now that we have f₁(x), we can look for f₁(f₁(x)), and then f₁(f₁(f₁(x))), and then f₁⁴(x), and then we can diagonalize over that and find a brand new function f₂(x), which equals f₁^x(x).

f₂(x) produces the values “f₁(1), f₁(f₁(2)), f₁(f₁(f₁(3))), f₁(f₁(f₁(f₁(4)))), f₁(f₁(f₁(f₁(f₁(5))))), …”; or “2, 8, 24, 32, 80, …”.

f₂(x) = f₁^x(x) = x * 2^x

But it gets better. Just like we have f₁(x) = f^x(x) and f₂(x) = f₁^x(x) we can have an f₃(x) = f₂^x(x) and a f₄(x) = f₃^x(x)…

All the way to a rule for infinitely many of these functions: f_k(x) = f_k-1^x(x)

So we can ask ourselves: “what’s f₄₂₀₉(685)?”

Easy. Follow the rule:

And while it doesn’t match up exactly, f_k(x) will be on the same level of huge as 10→x→k using Conway Chained Arrows.

Following the Recursion

Now, we should also be able to notice a pattern with each increase in the subscript:

f(x) = x, add one.
f₁(x) = x, add one, x times = x + x = 2x
f₂(x) = (x, add one, x times), x times = x doubled, x times = x * 2^x
f₃(x) = ((x, add one, x times), x times), x times = (x doubled, x times), x times = (x * 2^x) * 2^(x * 2^x) ≈ x↑↑x
f₄(x) = … ≈ x↑↑↑x
f₅(x) = … ≈ x↑↑↑↑x
…
f_n(x) = … ≈ hyper(x, x, n) ≈ x→x→(n-2)

Diagonalizing the Diagonalizations

Where do we go from here? Well, the next step is to take a diganonalization of all the functions, and create a function from “f₁(1), f₂(2), f₃(3), f₄(4), …” that grows faster than any of the infinite functions in that series. But what do we call it?

We call it f_ω(x).

What is that? The little funny ω is the Greek letter Omega. But why? Turns out that ω is actually an ordinal number, something a bit complicated, but not too bad. Hold on to your stomach, and let’s explain.

The Most Basic Ordinal

ω is a set, specifically the set of all positive integers. ω = [0, 1, 2, 3, 4, 5, 6, ..., 8091380, 8091381, ..., 3↑↑↑↑3, ..., G, ...]; every number that is a positive integer is in there, no matter how large. There are an infinite number of numbers contained in ω. ω itself has a value, namely infinity — the smallest number larger than all finite numbers.

Don’t worry about the infinity bit. For now, the way we define f_ω(x) is to find the “x”th number in the ω set, and replace the “ω” symbol with that entry. More simply, f_ω(x) = f_x(x).

We now have our next step. And we can do this for any ordinal, and there are more to come — if there is an ordinal in the subscript, find the “x”th entry in the set the ordinal represents, and replace that ordinal with it. Don’t worry — we’ll explain in more detail as we go on.

Adding to Ordinals

Now we can do something a bit more complicated with another rule. We define f_ω+1(x). It looks weird, and “ω+1″ is not an addition problem we can do. Instead, this is simply a notation for this, which we’ve seen before:

And we can now do that for any number:

For example:

Comparing to Conway

Even the tiny f_ω+1(2) ends up making large numbers, generating f₈(8), which is roughly 8↑↑↑↑↑↑↑↑8.

However, our other notations made big numbers too. While f_ω+1(10) is big, it’s still small compared to what Conway notation can do. f_ω+1(10) is about 10→10→10→2 and f_ω+2(10) is about 10→10→10→3. f_ω+10(10) is about 10→10→10→11, and we can see an obvious pattern.

However, if we keep on going with ordinals, we can go even larger than even 10→_10→10→1010. It will just take a little bit of work to get there…

Multiplying Ordinals

So what happens if we do to ω what ω did to the natural numbers? What if we made a function that was the diagonalization of “f_ω+1(1), f_ω+2(2), f_ω+3(3), f_ω+4(4), …”.

It’s time to introduce yet another ordinal we’ll be working with: ω2.

f_ω2(x) = f_ω+x(x)

Now, ω2 itself is a set that contains ω + every positive integer: [ω, ω+1, ω+2, ω+3, ω+4, ..., ω+1000000, ω+1000001, ω+1000002, ..., ω+(10→10→10), ...]

You can figure this out because ω2 is not just written like “ω2″ to be silly… it is actually “ω*2″, or “ω+ω”. You then replace the rightmost ω with x when calculating f_ω2(x). Note that “2ω” is not the same, since that’s 2*2*2*2*2*…*2 an infinite amount of times, or just infinity, or ω.

It’s weird, but 2ω = ω. If that hurts your head, we can just ignore it. It’s not really that critical to understanding how these functions work.

Adding to the Multiplying

Just like how you can add to ω, creating “ω+1″ and a “ω+2″, you can add to ω2. And then that “ω2+1, ω2+2, ω2+3, ω2+4, …” can all be diagonalized in ω3. And then that pattern continues for ω times any number, ωn. That’s a lot of work we just did in one step, and we now have massively larger numbers. Let’s see what we just did.

Every ωn is a set [ω(n-1), ω(n-1) + 1, ω(n-1) + 2, ω(n-1) + 3, ω(n-1) + 4, ...]

ω67, for example is a set [ω66, ω66 + 1, ω66 + 2, ω66 + 3, ...].

And just like before, we select the “x”th member from the set, and replace ωn with that member.

Here’s everything we’ve learned in five easy rules, and the first one doesn’t even count. Remember these:

1. f₀(x) = x+1
2. f_a(x) = f_a-1^x(x)
3. f_ω(x) = f_x(x)
4. f_ωa(x) = f_ω(a-1)+x(x)
5. f_ωa+b(x) = f_ωa+(b-1)^x(x)

So using our new knowledge, what is f_ω14+2(3)?

f_ω14+2(3) = f_ω14+1³(3) = f_ω14+1(f_ω14+1(f_ω14+1(3))) = f_ω14+1(f_ω14+1(f_ω14³(3))) = f_ω14+1(f_ω14+1(f_ω14(f_ω14(f_ω14(3))))) = f_ω14+1(f_ω14+1(f_ω14(f_ω14(f_ω13+3(3))))) = f_ω14+1(f_ω14+1(f_ω14(f_ω14(f_ω13+2³(3))))) = …

That’s probably good enough — it will be some huge number. Time to move on.

Squaring Ordinals

Whoa. First we were adding them, ω+n. Then when we got to ω+ω, we made that ω2. Then we continued multiplying, going to ωn. Now what? Well, eventually we go to ωω, which we just write as ω^2. ω^2 is where the number in the function actually defines the n for ωn.

More specifically, ω^2 is another infinite set, containing all of the ωn’s: [ω, ω2, ω3, ω4, ω5, ω6, ω7, ..., ω9009, ...]

We then can make a function to select the “x”th value, and evaluate: f_ω^2(x) = f_ω*ω(x) = f_ωx(x).

Tacking on Continuations

And one of the reasons ordinals are powerful for making large numbers is that you can extend f_ω^2(x) through all the means we’ve already made…

f_ω^2+1(x) = f_ω^2^x(x)
f_ω^2+ω(x) = f_ω^2+x(x)
f_ω^2+ω+1(x) = f_ω^2+ω^x(x)
f_ω^2+ω2(x) = f_ω^2+ω+x(x)
f_ω^2+ω3(x) = f_ω^2+ω2+x(x)
f_(ω^2)*2(x) = f_ω^2+ω^2(x) = f_ω^2+ωx(x)
f_(ω^2)2+1(x) = f_(ω^2)2^x(x)
…

And you can probably see that we’re heading toward ω^3, a set [ω^2, (ω^2)2, (ω^2)3, (ω^2)4, (ω^2)5, ...], where f_ω^3(x) = f_(ω^2)x(x).

Magnitude Comparsion

So as we surmised in Part 1, magnitude is going to be intuitively impossible to understand at this scale. However, we can still compare it to the large notations that were built in part 2.

Where would we find Graham’s Number, for example?

Well Graham’s Number itself is a recursive function. If g(x) = 3→3→x = 3↑↑…↑↑3 (with x Knuth up-arrows), then Graham’s Number would be g⁶⁴(4). Since g(x) is approximately f_x(x) = f_ω(x), that means Graham’s Number would be approximately f_ω⁶⁴(4), which is smaller than f_ω+1(64).

Extended Conway Chained-Arrow Notation

Where would we find something like the basic extended arrow notation, say 10→₂10, which equals 10→10→10→10→10→10→10→10→10→10→10?

Well, we were able to get this pattern:
f_ω(10) ≈ 10→10→10
f_ω2(10) ≈ 10→10→10→10
f_ω3(10) ≈ 10→10→10→10→10
f_ω4(10) ≈ 10→10→10→10→10→10
…

So we find 10→₂10 being approximately f_ω10(10), or f_ω^2(10). What about something more advanced, like 10→₁₀10?

Well, this same pattern helps a little:
f_ω^2+ω(10) ≈ 10→₂10→₂10
f_ω^2+ω2(10) ≈ 10→₂10→₂10→₂10
f_ω^2+ω3(10) ≈ 10→₂10→₂10→₂10→₂10
f_ω^2+ω4(10) ≈ 10→₂10→₂10→₂10→₂10→₂10
…
f_(ω^2)2(10) ≈ 10→₃10

And then again:
f_(ω^2)2+ω(10) ≈ 10→₃10→₃10
f_(ω^2)2+ω2(10) ≈ 10→₃10→₃10→₃10
f_(ω^2)2+ω3(10) ≈ 10→₃10→₃10→₃10→₃10
…
f_(ω^2)3(10) ≈ 10→₄10

It doesn’t take much work to realize you’ll eventually find 10→₁₀10 at approximately f_(ω^2)10(10), or f_ω^3(10).

And that’s as far as we get with ω^3. The C(a) function remains undefeated. …For now. In the next post, we’ll move past ω^3 and defeat it.

For now, here’s all twelve rules we’ve learned so far, in one reference location:

1. f₀(x) = x+1
2. f_a(x) = f_a-1^x(x)
3. f_ω(x) = f_x(x)
4. f_ωa(x) = f_ω(a-1)+x(x)
5. f_ωa+b(x) = f_ωa+(b-1)^x(x)
6. f_ω^2(x) = f_ωx(x)
7. f_ω^2+b(x) = f_ω^2+(b-1)^x(x)
8. f_(ω^2)a(x) = f_{(ω^2)*(a-1) + ωx}(x)
9. f_(ω^2)a+b(x) = f_{(ω^2)a+(b-1)}^x(x)
10. f_(ω^2)a+ωb(x) = f_{(ω^2)a + ωb + x}(x)
11. f_{(ω^2)a+ωb+c}(x) = f_{(ω^2)a + ωb + c-1}^x(x)
12. f_ω^3(x) = f_(ω^2)x(x)

Continued in: Large Numbers, Part 4: Epsilon and Phi

Be Sociable, Share!

•