[MUSIC PLAYING] You may have heard how Hercules slew the hydra in Greek mythology.

It turns out, you don't need to be a mythical hero to defeat this rapidly regenerating monster.

Just a mathematician.

In this challenge you, like Hercules, are facing off against a frightening beast, but your hydra is even scarier.

Instead of regrowing two heads for every one that gets chopped off, this hydra regrows entire sections of its body.

For starters, this mathematical hydra is not just a bunch of heads attached to a single body.

It can have heads attached to its heads.

So you might encounter a hydra that looks like this, or this, or this.

Now, you can only cut off a head that doesn't have any other heads growing out of it.

So for this hydra, there are five options.

For the sake of example, I'll just try to defeat this hydra.

For the first move, I'll chop off this head, the one attached to the body.

In that case, nothing happens.

Nothing regrows, and the hydra is one step closer to defeat.

But these heads, the ones attached directly to the body, are the only ones that won't cause something to regenerate.

If I chop off a head which is not attached to the body, then that particular head is gone, but the hydra grows two new copies of the portion that starts down the neck from the head you chopped off.

That might sound a bit complicated, but let's just see what happens in our example.

What if I chop off this head?

Go down the neck toward the body.

For clarity's sake, we'll mark that edge in blue.

Now, the hydra regrows two new copies of the blue edge and everything above it, except the heads we chopped off.

The copies of the blue edge are temporarily marked in purple, just to help show what's going on.

But that didn't seem to help anything.

The hydra looks bigger.

Now, there are seven options for which had to chop off, so I'll choose this head.

Again, we go down one edge and mark it in blue.

The hydra generates two new copies of the blue edge and everything above it, so we get this.

But that also might have been a mistake.

Maybe I'm just not doing it in the right order.

Do you think it's possible to defeat the hydra?

And if so, can you come up with a better strategy?

Now, I'm going to start to answer these questions.

It'll take a few steps.

At any point, you should feel free to pause the video and think about it on your own.

It might help clarify things to draw some pictures and work out some small examples.

Now, here's the big theorem-- no matter what order you chop off the heads, you will, in a finite number of steps, defeat the hydra.

That is, eventually-- and that might be a really long eventually-- you will chop off all the heads.

This theorem can seem totally counter-intuitive, given how quickly the hydra appears to be growing.

To begin to understand what's going on, let's try something very common in mathematics.

We'll look at examples of small, or simple, hydra.

First, the simplest kind of hydra is probably one where all the heads are attached directly to the body.

If it has four heads, it takes four chops to defeat the hydra.

And 10 heads just takes 10 chops.

Easy.

What if the hydra's just a line, as in all the heads are stacked one on top of another.

Let's try it with three heads.

There's only one option for what to cut off first, so we'll do that.

Then, there's not a whole lot of other options, so we'll just keep going.

As we chop off the forking branches, they're replaced by equally long, non-forking branches, until there are nine branches of length 2.

Then, we chop off the ends of these, until there are 27 heads connected directly to the body.

Finally, 27 chops later, we're done.

Hydra defeated.

Here's what the first 15 steps look like, if you start with a hydra that's a line of height 4.

After many more steps, this hydra will look like a spiky ball, just a body with many heads attached directly to it.

Then, you'll be able to chop off each of those heads and defeat it.

Here's a challenge question-- how many heads will be in this spiky ball if the original hydra is a line of height 4?

And how many steps will it take to finally defeat this hydra?

OK, after all those examples, what have we learned?

First, notice that the hydra never becomes taller, that is, the maximum height of heads that are stacked on top of one another never grows.

The hydra's becoming wider, but not taller.

It's kind of de-tangling itself, level by level, until it just turns into a giant spiky ball.

To prove this rigorously, like we do in mathematics, we'll need to encode the hydra's complexity.

To show that the hydra will be killed in a finite number of moves, we'll need to show that the hydra's complexity goes to zero, that is, we'll show that it eventually becomes the simplest hydra-- a single body with no heads.

Here's where it gets really weird.

The tool we're going to use is ordinals.

Here's a crash course in ordinals.

Ordinals are the numbers we use to count.

They're different than cardinals, which are the numbers we use to tell size.

If 5 apples is the third item on your grocery list, the number 5 is a cardinal.

It's about size.

And the number 3 is an ordinal.

It's about counting.

The reason they usually don't teach you about ordinals and cardinals in school is that there isn't really a difference if you're only talking about finite numbers.

But infinite ordinals and infinite cardinals are different.

Our episode A Hierarchy of Infinities was about cardinals, sizes of infinity.

This episode is about ordinals, infinities to count with.

I'm not going to go into a detailed explanation of how ordinals work.

There's plenty of other resources for that.

I'm just going to describe the part we need-- the ordering of the ordinals.

The smallest ordinals are finite-- 0, 1, 2, 3, 4, 5, and so on.

And then, after all that, comes omega, the first infinite ordinal.

Then comes omega plus 1, omega plus 2, omega plus 3, and so on.

Then comes 2 times omega, then 2 times omega plus 1, 2 times omega plus 2, and so on.

Then there's three 3 omega, 4 times omega, and so on.

After all that, there's omega times omega, a.k.a.

omega squared.

Then omega cubed, omega to the fourth, and so on.

After all that, there is omega to the omega.

And it kind of just keeps going.

Omega to the omega to the omega, and so on.

Luckily, the ordering is pretty intuitive.

You just have to think about the normal order of the natural numbers, and then just add a new thing that's bigger than all the natural numbers-- omega.

So omega to the omega plus 2 is bigger than omega to the 100, but smaller than omega to the 3 times omega.

Now, how do ordinals help us encode the hydra's complexity?

Well, we're going to assign each hydra an ordinal number.

Each time we chop off a hydra's head, the associated ordinal will decrease.

There's a helpful theorem called the well-ordering theorem, which implies that any decreasing sequence of ordinals eventually goes to zero.

This means that our hydra will be defeated, no matter what order one chops off the heads.

But how do we assign the ordinal to the hydra?

First, label all the leaves with a 0.

Then, moving down the hydra, we'll label each head according to the ones that are above it.

If a head has N heads coming out that are labeled L1, L2, up to LN, then we label it omega to the L1 plus omega to the L2, up to omega to the LN.

We keep doing this all the way down the tree.

The label on the bottom-- the body-- is the important one.

It's the ordinal that we assign to the entire hydra.

To get the hang of this, let's label this hydra.

It's the one that came about when we first chopped off the lower head.

Here's the way we labeled this hydra to get its ordinal.

Then, we chopped off another head, and this hydra was the result.

Here's the ordinal for that one.

Finally, we tried for a third chop, and got this hydra.

Here's the ordinal for that hydra.

Each time we chop a head off a hydra, the associated ordinal gets smaller.

It doesn't matter which head we chop off, the new hydra will always have a smaller ordinal.

Let's see one more example-- the line of three heads stacked on top of each other.

The starting hydra has ordinal omega to the omega.

After one chop, it's omega cubed.

By the sixth step, it's 9 times omega, and by the 15th step, it's 27.

Finally, after 41 steps, the hydra is just its body, so it is assigned the ordinal 0.

And that's the big point.

As we chop off heads, the ordinal assigned to the hydra keeps getting smaller and smaller, until the assigned ordinal is 0.

And when it's 0, that means the hydra has been defeated.

It's just a body.

The hydra we just defeated grows two new copies of the part below the chopped off head.

What if it grew three new copies, or four, or 10?

Amazingly, not much changes.

It's still true that, no matter what order you chop off the hydra's heads, you'll still defeat it in a finite number of moves.

No matter how many heads grow each time, the proof technique that involved encoding the hydra in an infinite ordinal still shows that the hydra will be defeated.

The ordinals will still be decreasing and, therefore, must eventually be zero.

But here's the part that totally blows my mind.

Let's say the hydra grows one copy after the first chop, two copies after the second chop, 10 copies after the 10th chop, and so on.

With each chop, it's regenerating faster.

Still-- even still-- you'll eventually chop off all the hydra's heads, and the same proof technique shows it.

There's a really crazy story behind this hydra, how and why mathematicians developed it, and why the proof is so unexpected.

We'll explore this in next week's episode-- the prequel to our Slay the Hydra Adventure.

Hello.

I want to address some of the comments on our Singularities episode from last week.

So Lucid Moses asked if anyone knows of something in reality that is really infinite, not just a really big number.

This is kind of what's at the heart of the episode, and so I was excited that his comment got so many responses.

Some people talked about, maybe time is infinite, or maybe space is infinite, or maybe space is infinitely divisible.

But a lot of people thought that those things weren't true, that there were physical theories that said none of those helped.

So maybe those aren't examples of real infinities.

Then, people gave examples of math things, like the number of digits in the decimal expansion of pi, or the square root of 2, or the number of sides of a fractal.

Maybe those are infinity, but I kind of doubt that they're real in the same sense that space is real.

They're different.

Lorenz Zahn said that a way out of the time zone singularity was that he uses UTC, which is coordinated universal time.

So everybody used coordinated universal time, then there would be no time zone singularity.

That's true.

But it would be pretty weird.

Like, here in Los Angeles, where I am right now, the sun would rise at 3:00 PM, which might feel a little strange.

A couple folks mentioned the residue theorem, which is a powerful theorem from complex analysis.

And it basically says that singularities are the only things that matter when you're doing certain computations.

This is really important, and it's a huge idea that would be really fun to tackle in a future episode.

That's all for now.

See you next week.

[MUSIC PLAYING]