Sometimes understanding finite numbers requires us to use infinity.

---Last episode, you learned how to slay a crazy mathematical hydra, and your victory has led you to this episode.

But there's a whole back story to that hydra that's just as wild and unbelievable as the hydra itself.

I want to talk to you about that now.

So if you haven't slain the beast yourself, I recommend you watch that episode and find out how we did it.

Then come back and join us.

Remember that every time you chopped off a head of the hydra it regenerated two new copies of the entire portion of the hydra that started one edge down from the chopped off head.

Unless you chopped off a head directly attached to the body, then nothing grows.

We used a totally unexpected tool, infinite ordinals, to show that no matter what order you chopped off the heads, you'll always defeat the hydra in a finite number of moves.

Whoa.

So, what's up with that weird infinite ordinal proof?

Who thought of it?

And why do you need something so complicated to prove that you will definitely defeat the hydra?

To understand the answer to these questions, we have to start with Goodstein sequences.

Here's how to build a Goodstein sequence.

First, you pick a number, any number to start with, like 13.

Then you rewrite 13 in hereditary base 2 notation.

OK.

Here's a brief interlude to explain what hereditary base notation is.

Plain old base, i.e.

non-hereditary notation, works like this.

To write 416 in base 3 notation, first, pick the largest power of 3 that will fit in 416.

So 416 is 3 to the fifth plus 173.

Now what's the largest power of 3 that fits into 173?

3 to the fourth, but that actually fits in twice.

So 416 is 3 to the fifth plus 2 times 3 to the fourth plus 11.

Repeat this procedure, fitting the largest power of 3 into the leftover part, until you get to 3 to 0, a.k.a.

1.

Now, we have 416 written in normal base 3 notation.

But notice that the exponents still have numbers bigger than 3 in them.

To write it in hereditary base 3 notation, we'll replace each of the exponents by their base 3 representative.

In the end, 3 is the biggest number to show up in this expansion.

Just to see one more example, it's easy to write 1,024 in base 2 notation.

But to write it in hereditary base 2 notation, we have to rewrite the exponent in base 2 notation and then write the exponent of the exponent in base 2 notation.

OK, back to Goodstein sequences.

We start with 13 written in hereditary base 2 notation, then convert all the 2s to 3s and subtract 1.

The result is 108.

Write 108 in hereditary base 3 notation, then convert all the 3s to 4s and subtract 1.

The result is 1,279.

Now write 1,279 in hereditary base 4 notation.

Can you guess what comes next?

Convert all the 4s to 5s and subtract 1.

The result is 16,092, which we write in hereditary base 5 notation.

Now we have the first four terms of this Goodstein sequence-- 13, 108, 1,279 16,092.

It would be very reasonable to conjecture that this sequence is getting bigger and bigger going to infinity.

I encourage you to pause the video right now, and make your own Goodstein sequence.

Pick any starting number.

I chose 13, but you might want to try 7 or 10, and copy the procedure just laid out.

Write in hereditary base 2, switch 2s to 3s, subtract 1, then write the result in hereditary base 3.

Switch 3s to 4s and subtract 1, and so on.

I promise, your sequence will get really big, really fast.

How fast?

Here's the Goodstein sequence that starts at 15.

By the seventh term in the sequence, we're at 150 million, and it only keeps growing.

But here's the totally amazing fact, called Goodstein's theorem.

These sequences get bigger and bigger for a long time.

But eventually, they get smaller.

And then the numbers keep shrinking.

And eventually they hit 0 and terminate.

If you start the Goodstein sequence with the number 3, it goes to 0 after only six steps.

But if you start your Goodstein sequence with 4, it takes this many steps to terminate.

And the situation gets worse if you start with bigger numbers.

So how do we prove this eventually terminates?

Infinite ordinals.

You might be having a little deja vu moment.

It should remind you of last week's hydra.

To start the proof, let's write out our Goodstein sequence, starting with the number 13 in hereditary base notation.

The first number is written in hereditary base 2, the second in hereditary base 3, and so on.

Now next to each number in the Goodstein sequence, we're going to write an ordinal.

Here's how.

The first number in the Goodstein sequence is written in hereditary base 2.

So we replace all the 2s with omegas to get an infinite ordinal.

The second number in the Goodstein sequence is written in hereditary base 3.

So we replace all the 3s with omegas.

Keep doing this to get a sequence of infinite ordinals.

What do you notice about this sequence?

It's decreasing.

It's pretty obvious that the second term is smaller than the first.

But why is the third term smaller than the second?

Well, omega to the fourth is way smaller than omega to the omega.

So even 3 times omega to the fourth is still way smaller.

And then the sequence just keeps decreasing.

Remember the big fact about sequences of decreasing ordinals from last time?

They always drop to 0 in a finite number of terms.

So eventually our ordinal sequence will be 0.

Let's go really far down the ordinal sequence until we finally get to the one that's 0.

The entire ordinal sequence, including this 0 term, is constructed from the Goodstein sequence.

So what does this say about the corresponding term of the Goodstein sequence?

It must also be 0.

We constructed the ordinal sequence by substituting numbers in the Goodstein sequence with infinite ordinals.

So in order for the ordinal sequence to be 0, the Goodstein sequence that it came from must also have been 0.

That's the proof that the Goodstein sequence also eventually drops to 0, even if that eventually takes a very, very long time.

When I first encountered Goodstein sequences and their wild hydra counterpart, and learned about the proof that shows they eventually go to zero, my initial reaction was, why are there all these infinities in the proof.

It seems so unnecessarily complicated.

All the Goodstein sequences are finite.

So why should we need to reason about infinity in order to prove that they terminate?

That's not usually the way math works.

Amazingly, the Kirby-Paris theorem shows that the infinities in the proof are necessary in the following sense.

Peano arithmetic is a set of basic rules or axioms that describe the behavior of the natural numbers.

Pretty much all the ordinary arithmetic and properties that you know and love about the natural numbers can be proved using Peano arithmetic.

And it sort of seems like Goodstein's theorem, which is only about natural numbers, should also be provable in Peano arithmetic.

But the Kirby-Paris theorem shows that it's not.

The incredibly surprising thing about this theorem is that in order to prove something about finite numbers, we had to move out of the domain of Peano arithmetic and into the world of infinite ordinals.

While writing this episode, I realized that these huge Goodstein sequences are pretty hard to calculate.

I wonder how hard it would be to write a program that computed the first few terms of a Goodstein sequence for reasonably small numbers.

Maybe one of you can meet me now.

We'll see you next week on "Infinite Series."

I want to respond to the challenge from last week's hydra episode.

Just as a reminder, here are the questions.

First, if you start with a hydra that's made up of a body with four heads stacked on top of one another, you'll eventually get to a point where the hydra is just a body with a bunch of heads coming out of it.

How many heads will there be?

And second question, how many total chops will it take to defeat this hydra?

Well, we saw that if you start chopping away at the hydra, the 15th step looks like a body with one head coming out of it and 27 heads coming out of that head.

This is where things get complicated.

So we'll focus on that hydra.

Let's say you have a hydra that's a body with one head coming out of it and k heads coming out of that head.

Here's my claim.

After 3 to the k minus 1 all divided by 2 steps, you'll end up with a hydra with 3 to the k heads coming directly out have a body.

So to defeat the entire hydra, including chopping off all the heads directly attached to the body, will take 3 to the k plus 1 minus 1 all divided by 2 steps.

Let's apply this to our hydra where k equals 27.

The answer to the first question is that it'll end up with 3 to the 27 or 7,625,597,484,987 heads.

And the answer to the second question is that it'll take 15 steps plus 3 to the 28 minus 1 divided by 2 steps before the hydra is defeated.

Which means it will finally be done at step 11,438,396,227,495.

I started labeling the hydra at 1, so if you counted the number of chops instead of the number of steps, your answer might differ by 1.

It's still totally correct.

Thanks to the handful of folks who responded in the comments.

You guys rock.

By the way, we'll be taking the next week off so we'll see you in two weeks for the next "Infinite Series."