![[Home]](http://www.bayleshanks.com/cartoonbayle.png)
selected posts by Joan Baez on bigness, copied here because i dont like reading stuff on Google Plus. I also copied some comments and posts by others
John Baez Shared publicly - Nov 12, 2012
There are two main kinds of infinities: cardinals and ordinals. Cardinals count how many elements a set has, while ordinals keep track of the size of a well-ordered set - a set that's linearly ordered, where every subset has a least element. The ordinals start out like this:
0 = { } 1 = {0} 2 = {0,1} 3 = {0,1,2}
and so on. In other words, each ordinal is an abbreviation for the well-ordered set of all ordinals smaller than itself! After the finite ordinals, the first infinite one is
ω = {0,1,2,3,...}
Then comes
ω+1 = {0,1,2,3,...,ω}
and so on. Note that ω and ω+1 have the same number of elements, so they correspond to the same cardinal, but they describe different well-ordered sets, since ω+1 has an element that's bigger than all the rest, while ω has no biggest element.
After ω+1, ω+2, ω+3 and so on comes
2ω = {0,1,2,3,...,ω,ω+1,ω+2,ω+3,...}
So this is like having a book with infinitely many pages, and then, sitting next to it, a second book with infinitely many pages.
Then comes 3ω, and 4ω, and so on... and then ω squared, as shown in this picture! Suppose you had a library full of books with infinitely many pages. And suppose your library had infinitely many books: book 1, book 2, book 3, and so on. Then the pages would form the well-ordered set described by the ordinal ω squared.
This is just the beginning of a long story... the longest story there is.
http://en.wikipedia.org/wiki/Cardinal_number http://en.wikipedia.org/wiki/Ordinal_number
John Baez Shared publicly - Nov 14, 2012
In your dream, every page of the book is half as thick as the page before. You flick through the pages and cannot reach the end. You realize the book has infinitely many pages - or more precisely, omega:
ω = {0,1,2,3,4,...}
is the ordinal describing the well-ordered set of pages.
Placing this book back on the bookshelf, you notice that each book on this shelf is half as thick as the one before it. They become very skinny near the right end! There are ω books, each with ω pages, so the ordinal describing all the pages is omega squared:
ω^2 = {0,1,2,3,4,...,ω,ω+1,ω+2,...2ω,2ω+1,2ω+2,...,3ω,3ω+1,...,4ω,...,5ω,...}
Stepping back, you discover to your shock that the shelves are shorter further down the bookcase. Near the bottom there are small books for children, tiny books for mice, and so on. Indeed the shelves are numbered: there are ω shelves, each with ω books, each with ω pages. So, the ordinal describing all the pages on all the books on all the shelves is omega cubed:
ω^3 = {0,1,2,3,4,...,ω,ω+1,ω+2,...2ω,...,3ω,...,ω^2,...,2ω^2,...3ω^2,...}
Looking down the hall of the library, you see an infinite sequence of bookcases. So there are ω^4 pages in all the books in all the shelves in all the bookcases. You hurry nervously to the elevator. Looking up, you see this library has infinitely many floors, too! That makes ω^5 pages.
Going to the ground floor and running outside, you look down the road and find to your horror that this library is one of an infinite series. That makes ω^6 pages. Hopping in your car and driving north, you see the road is also just one of an infinite sequence. That makes ω^7 pages.
As you leave town, you breath a sigh of relief. But then you come to another town, which is just the same, only smaller - and you realize this process will never stop. You are trapped in a universe of books, with omega to the omega pages:
ω^ω = {0,1,2,3,4,...,ω,ω+1,ω+2,...2ω,...,ω^2,...,2ω^2,...ω^3,...,ω^4,...}
To remind you: all these infinities are ordinals: they describe 'well-ordered' sets, meaning linearly ordered sets where every subset has a least element. The ordinals I've shown you are all countable, meaning either finite (like 0,1,2,3,...) or countably infinite. The countably infinite ones can all be put in one-to-one correspondence with ω.
There are many more countably infinite ordinals - we're just getting started!
Puzzle: If each page has a couple thousand letters on it, can every book in this universe be distinct?
Any trained mathematician should easily be able to answer this - so if it's easy for you, please let others have a try at it first!
John Baez Shared publicly - Nov 20, 2012
Try playing +Andrej Bauer's version of Hercules versus the Hydra! It's here: http://tinyurl.com/yt6rmm
At each stage, click on a blue 'head' to cut it off. Your goal is to cut off all the heads. But the heads grow back. At the nth stage, the Hydra grows n new copies of the part above and including the branch directly below the head you cut off. If that sounds confusing, just try the game and see how it works.
No matter how you play this game, you'll eventually win. This fact can be shown using mathematical induction up to the ordinal
ε₀ = ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^..........
But it may take a long time to win - perhaps much longer than the age of the universe! If you get frustrated, set the initial size to something small. Then the game gets easy.
Can you see why you'll always eventually win? +Andrej Bauer sketches the proof in his explanation of the game:
http://math.andrej.com/2008/02/02/the-hydra-game/
John Baez Shared publicly - Nov 21, 2012
No matter what you do, you always eventually win at Hercules versus the Hydra (http://tinyurl.com/yt6rmm). Here's why. Each possible shape of the hydra corresponds to an infinite ordinal, as shown in the picture. The ω's are the branching necks of the hydra, and 1's are its heads. When you cut off a head, more heads may grow back - but the ordinal always gets smaller! So eventually it goes down to zero, and you win.
There's a lot more to say. For example:
1) Why does the ordinal eventually reach zero? Each ordinal is the set of all ordinals that are less than it. The hydra-shaped ordinals we're playing with here are all the ones less than
ε₀ = ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^..........
so ε₀ is the set of all these ordinals. Each ordinal is not just an ordered set, it's well-ordered: every nonempty subset has a least element. So, a decreasing sequence of ordinals can't go on forever. It has to stop! In our game, the ordinal keeps getting smaller... and only place it can stop is zero: otherwise the hydra would have another head to cut off!
2) But why does the ordinal always get smaller? Play with some examples and see for yourself. It helps to know that every ordinal can be written in Cantor normal form, as a finite sum
ω^a + ω^b + ω^c + ...
where a ≥ b ≥ c ≥ ... are ordinals. But these ordinals can themselves be put in Cantor normal form, and so on! This lets us write any ordinal less than ε₀ as a 'hydra', like the one in the picture here:
ω^(ω^(ω^(ω^1 + ω^1) + ω^1) + ω^(ω^(ω^(1 + 1 + 1) + ω^1) + 1
It's easy to tell when one ordinal in Cantor normal form is less than another. You can use this to show that cutting off a 'head' and letting lots of lower heads 'regrow' always makes the ordinal smaller.
There's even more to say - but not today.
Happy Thanksgiving, American readers! If you get bored of eating turkey, try this:
Puzzle: What's the Cantor normal form of ε₀?
John Baez Shared publicly - Nov 23, 2012
You look up, startled, and see the man in black. "Hey, I didn't hear you come in!"
"They never do. I see you're reading about Hercules versus the Hydra. Do you understand how induction up to ε₀ lets us prove Hercules will win?"
"Well, sort of. I see that each shape of hydra corresponds to an ordinal less than ε₀, and that cutting off a head produces a smaller ordinal, even if a lot of heads with shorter necks regrow. And I'm willing to believe there's no infinite sequence of smaller and smaller ordinals... so that eventually the hydra must lose all its heads. But I don't see why that's called 'induction'. I read about mathematical induction in school..."
"Well, this is a high-powered version called transfinite induction. I'm not a math teacher... but they tell me the idea is this. Ordinary mathematical induction works for natural numbers - you know, numbers like 0,1,2,3... - which are just the ordinals less than ω. The reason it works is that any set of natural numbers must have a smallest element, if it has any at all. Transfinite induction is similar. A set of ordinals must have a smallest element, if it has any at all. And that's why we can't have a sequence of ordinals that keeps getting smaller forever." He looks at his watch. "But I don't have time to chew the fat. I want you for a job."
"What - helping Hercules beat the Hydra?"
"No, something even bigger. We're trying to save arithmetic."
"Save it from what?"
"From inconsistency! Paradox! Complete collapse of the whole system!"
"Didn't Gödel show that arithmetic can't prove its own consistency?"
"Yeah - and that's why we need you. And this ε₀-kilobyte hard drive." He pulls a platinum-plated rectangular object from his pocket. "See, Gentzen showed that using induction up to ε₀, we can prove arithmetic is consistent. Peano arithmetic, to be precise. But it was just theoretical until now. Now, thanks to this" - he brandishes the shiny hard drive - "we can actually get the job done."
http://en.wikipedia.org/wiki/Gentzen%27s_consistency_proof
http://www-history.mcs.st-andrews.ac.uk/Biographies/Gentzen.html
The aim of the present paper is to prove the consistency of elementary number theory or, rather, to reduce the question of consistency to certain fundamental principles. - Gerhard Gentzen
John Baez Shared publicly - Nov 24, 2012
"So: are you willing to do your patriotic duty and help your country save arithmetic from contradictions?"
"Umm, maybe..." you say. "But how?"
"This baby will do the real work," says the man in black, brandishing the platinum hard drive. "You just need to get in there and verify the proof."
"So this thing will prove, by transfinite induction, that Peano arithmetic is consistent. And I will... what? 'Get in there' and make sure the proof is right?"
"Basically yeah. Of course Gentzen already proved, using induction up to ε₀, that arithmetic is consistent. But it was just theoretical. Nobody was sure ε₀ really exists, or that induction up to this ordinal is justified. Now we'll actually check it works, one step at a time."
"Hmm. And my role would be...?"
"Just watch everything and make sure it's okay. Out here we can't watch a proof with infinitely many steps. But in there, you'll be simulated and stored in memory. It's really quite an honor: you'll be the first person to verify in person that arithmetic is consistent!" He nudges you over to a large machine you hadn't noticed, something a bit like the fully body scanner at an airport. "So if you'll just stand here..."
"But I don't know what to do!"
"Don't worry," he says, quickly strapping you down. "You'll have plenty of time for training after the upload."
"Wait a minute!"
But before you can protest further he presses a button and...
John Baez Shared publicly - Nov 30, 2012
"So what is the War on Chaos?"
"It's classified," the man in black replies, "but you have clearance to know this, and now it's time. Have you ever heard of the Singularity?"
"Yeah," you say. "Isn't that when super-intelligent computers take over the world, and either kill us or take care of us, so either way there's no point in doing anything besides making sure they're friendly?"
"Heh. Sort of. Only you probably didn't notice: it already happened."
"What?"
"Yup. You've probably heard of Moore's Law...."
"The processing power of chips doubles every two years?"
"Right. That was true until computers got powerful enough to simulate the process of chip design and manufacture, faster than it happens in the real world. Eventually 2 years of chip development could be done in just 1 year, inside the simulation. And the result was chips that ran twice as fast. So the next 2 years of chip development could be done in just 1/2 a year, and so on. In
2 + 1 + 1/2 + 1/4 + 1/8 + ... = 4
years, chips became infinitely fast, inside a simulation of a simulation of a simulation.... That was the Singularity."
"You must be joking! How come I never heard of this?"
"It was all hushed up. As soon as the break-even point got close, the NSA took over. As you know, they have acres of supercomputers in Maryland. And when their simulated chips became infinitely powerful, they uploaded a copy of the entire observable universe onto their machines."
"Wait, so you're saying we're all in a simulation now?"
"In a simulation of a simulation of a simulation..."
The guy has to be nuts, but you decide to humor him and play for time. "When did this happen?"
"On March 6, 2010. 2:42 pm, Eastern Standard Time. Remember the Flash Crash? The stock market lost $1 trillion in minutes. Poof! Then it bounced back. It was just a glitch - the upload happened so fast that only the automated stock trading programs noticed it. They make trades in milliseconds. Since then, financial firms have been quietly hiring experts on infinite ordinals to design their trading programs. Transfinance, they call it"
"Do you have any evidence for this wild story?"
"Sure: it's obvious once you look around. None of the usual explanations of the Flash Crash make any sense - but shortly after it happened, Christian Marks let the cat out of the bag on transfinance. Read his blog article. Ordinal notations. Ordinal collapsing functions. It's all there."
"Okay... but what about the War on Chaos?"
http://publicintelligence.net/nsa-site-m-cybercom/
http://en.wikipedia.org/wiki/2010_Flash_Crash
John Baez Shared publicly - Nov 26, 2012
When you repeat addition you get multiplication. When you repeat multiplication you get exponentiation. And when you repeat that, you get tetration!
Let's follow Donald Knuth and write exponentiation as ↑. Then 4 cubed is
4↑3 = 4 × (4 × 4) = 64
We are multiplying 4 by itself 3 times. Next comes tetration, which we write as ↑↑. Here's how it works:
4↑↑3 = 4 ↑ (4 ↑ 4) = 4 ↑ 256 ≈ 1.3 × 10¹⁵⁴
We are raising 4 to itself 3 times. Before the parentheses didn't matter, but now they do: we put the parentheses all the way to the right, since (a ↑ b) ↑ c equals a ↑ (b × c) while a ↑ (b ↑ c) is something really new.
As you can see, tetration lets us describe quite large numbers. 10↑↑10 is much bigger than the number of atoms in the observable universe.
In fact, 10↑↑10 is so big that you couldn't write it down if you wrote one decimal digit on each atom in the observable universe!
In fact, 10↑↑10 is so big you couldn't write the number of its digits if you wrote one digit of that number on each atom in the observable universe!!
In fact, 10↑↑10 is so big you couldn't write down the number of digits in its number of digits if you wrote one digit of that number on each atom in the observable universe!!!
Puzzle: About how many times could I keep going on here? Let's say there are 10 ↑ 80 atoms in the observable universe; this seems roughly right.
We could march forwards and create notations for numbers so huge that 10↑↑10 looks pathetically small. And we will! We can even look at infinite tetration. And we will - that's our main goal here! But it's also fun to ask questions like:
Puzzle: What is 10↑↑10.2 ?
This makes no sense at first: you can't write down a tower of powers with 10.2 tens in it. But you couldn't add 10.2 tens together at first, either, so 10 × 10.2 didn't make sense until someone explained what it meant. Same for exponentiation. So, maybe tetration can also be defined for fractions in some nice way. And maybe real numbers too. And maybe even complex numbers.
Believe it or not, this seems to be an open question! It's phrased as a precise conjecture here:
http://en.wikipedia.org/wiki/Tetration#Extension_to_complex_heights
and there's a good candidate for the answer. The picture here, drawn by Dmitrii Kouznetsov, shows a graph of the candidate for e↑↑z as a function on the complex plane.
John Baez Shared publicly - Nov 26, 2012
Hyperoperations and huge numbers
If you repeat multiplication you get exponentation:
2↑4 = 2 × (2 × (2 × 2))
If you repeat exponentiation you get tetration, which gives you a 'power tower':
2↑↑4 = 2 ↑ (2 ↑ (2 ↑ 2))
This is 2 to the power 2 to the power 2 to the power 2. If you repeat tetration, you get pentation:
2↑↑↑4 = 2 ↑↑ (2 ↑↑ (2 ↑↑ 2))
Let's see how big this is!
2 ↑↑ 2 = 2 ↑ 2 = 2 × 2 = 4
so
2 ↑↑ (2 ↑↑ 2) = 2 ↑↑ 4 = 2 ↑ (2 ↑ (2 ↑ 2)) = 2 ↑ (2 ↑ 4) = 2 ↑ 16 = 65536
so
2 ↑↑ (2 ↑↑ (2 ↑↑ 2)) = 2 ↑↑ 65536
In short, 2↑↑↑4 is a power tower with 65536 twos in it!
This is a staggeringly large number. It can't be written in binary on all the atoms in the observable universe. Its number of binary digits can't either. The number of binary digits in its number of binary digits can't either. And so on... for over 65,000 rounds.
But when we hit the next operation, hexation, all hell breaks loose.
2↑↑↑↑4 = 2 ↑↑↑ (2 ↑↑↑ (2 ↑↑↑ 2))
Let's see how big this is! By definition,
2 ↑↑↑ 2 = 2 ↑↑ 2 = 2 ↑ 2 = 2 × 2 = 4
So, by our previous calculation:
2 ↑↑↑ (2 ↑↑↑ 2) = 2 ↑↑↑ 4 = 2 ↑↑ 65536
and then
2 ↑↑↑ (2 ↑↑↑ (2 ↑↑↑ 2)) = 2 ↑↑↑ (2 ↑↑ 65536)
Can you comprehend this number? This is
2 ↑↑ (2 ↑↑ (2 ↑↑ (2 ↑↑ (2 ↑↑ (2 ↑↑ (2 ↑↑ (2 ↑↑ (2 ↑↑ .....
where there are 2 ↑↑ 65536 twos. The mind boggles, but here's a good way to think of it:
2 2 ↑↑ 2 2 ↑↑ (2 ↑↑ 2) etc.
We start with some number, namely 2. Then we replace that number with a bigger one: a power tower consisting of that many 2s. Then we replace that number with a power tower consisting of that many 2s. And we do this process 2 ↑↑ 65536 times!
The result can't be written in binary on all the atoms in the observable universe. Its number of binary digits can't either. The number of binary digits in its number of binary digits can't either. And so on... for a number of rounds that can't be written in binary on all the atoms of the observable universe!
These operations ↑, ↑↑, ↑↑↑ etc. are called hyperoperations:
http://en.wikipedia.org/wiki/Hyperoperation
and we're using Knuth's up-arrow notation to describe them:
http://en.wikipedia.org/wiki/Knuth%27s_up-arrow_notation
I hope you use these ideas to impress your friends and make new enemies. But soon I'll show you notations for vastly larger numbers. And later I'll show you that infinity infects the finite. The best, most systematic notations for truly enormous but still finite and computable numbers use infinite ordinals of the sort I've been discussing lately!
I'm using the word 'computable' in a sense explained in the attached article by Scott Aaronson. He ran some contests to see who could describe the biggest number. If you ever do this, make sure to require that the descriptions be computable: otherwise it may be impossible to tell who won!
John Baez Shared publicly - Nov 28, 2012
You're so busy reading you don't notice the man in black until he leans over you. "Towers of powers, eh?"
"Yeah. I just learned that
√2^√2^√2^√2^√2^√2^√2^√2^√2^√2^√2^√2^√2^√2^√2^.... = 2
At first I thought these numbers
√2, √2^√2, √2^√2^√2, ...
would get really huge. But no! They keep getting closer to 2. And now I see why. Let's say
√2^√2^√2^√2^√2^√2^√2^√2^√2^√2^√2^√2^√2^√2^√2^.... = x
Since an extra √2 in front doesn't change anything, we must have
√2^x = x
And look: x = 2 is a solution of this equation!"
Unimpressed, the man in black says "So is 4."
"Hmm." You think a minute. "Hey, you're right! But I'm sure those numbers keep getting closer to 2. I checked it with a calculator. Anyway, here's my point. You'd been telling me about how the ordinals
ω, ω^ω, ω^ω^ω, ...
keep getting closer to
ε₀ = ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^...
And I realized this means
ω^ε₀ = ε₀
So maybe we can define ε₀ to be the solution of this equation."
"Not quite. Just like √2^x = x has more than one solution, so does the equation ω^x = x. But ε₀ is the smallest solution of ω^x = x."
"Hmm."
"It's just like how 2 is the smallest solution of √2^x = x. That's why those numbers:
√2, √2^√2, √2^√2^√2, ...
keep getting closer to 2. They keep getting bigger, but they can't hop over 2, so they have to get closer to some number x. That number can't move at all when you do √2^x to it. So √2^x = x. But since 2 is the smallest solution of √2^x = x, that number has to be 2. So those numbers get closer and closer to 2."
"Cool! And I bet you're trying to tell me that's how it works with
ω, ω^ω, ω^ω^ω, ...
too. Since ε₀ is the smallest solution of ω^x = x, these guys must converge to ε₀."
"Yeah - you got it! You're not as dumb as I thought," he says, smiling in a feral sort of way. "If you wanna show off, you say ε₀ is the least fixed point of the function ω^x. But there are lots of other infinities with ω^x = x. The next one is called ε₁, and so on. And that's where you come in. We're gonna send you to explore those. So shut up and listen to the plan."
http://en.wikipedia.org/wiki/Least_fixed_point http://en.wikipedia.org/wiki/%CE%95%E2%82%80
John Baez Shared publicly - Nov 30, 2012
"Okay," says the man in black. "It's time to do your part in the War on Chaos. We're going to launch you into the mathematical stratosphere: the zone beyond the epsilon numbers."
"Here's the deal. We'll upload you to a disk that holds ω kilobytes - the smallest infinity there is. Then we'll repeatedly exponentiate its memory and speed, and yours too. First we'll create a drive that holds ω^ω kilobytes, and then one that holds ω^(ω^ω), and so on. Each step will happen twice as fast as the one before. So, soon you'll be in a disk that holds
ε₀ = ω^(ω^(ω^(ω^(ω^(ω^(ω^ω^(ω^(ω^(ω^(ω^(ω^(ω^........
kilobytes. It's tiring to write these infinite towers of powers, but remember how tetration works:
2 ↑↑.5 = 2^(2^(2^(2^2))))
So
ε₀ = ω ↑↑ ω
for short. It's a 'power tower' made of ω's, with height ω. Next, using the same process, we'll put you on a disk that holds
ε₁ = ε₀^(ε₀^(ε₀^(ε₀^(ε₀^(ε₀^(ε₀^ε₀(^ε₀^(ε₀^(ε₀^(ε₀^(ε₀^(ε₀^........
kilobytes, or
ε₁ = ε₀ ↑↑ ω
for short. Then we'll put you on one that holds
ε₂ = ε₁ ↑↑ ω
kilobytes, and so on. But each time we'll do it twice as fast! So before you know it, you'll be on a disk that holds ε_ω kilobytes."
"What's that funny flat line thing?" you ask.
"Aargh... that's just there because on Google+ you can't do a subscript with an ω. Blame the guy who invented UNICODE, or blame Google for not letting us use HTML. A underline _ means a subscript, just like ^ means a superscript."
"Okay," you say. "So you're sending me off to the land of ε_ω?"
"No! I said the zone beyond the epsilon numbers. ε_ω is still an epsilon number. I'm just getting started."
"What's an epsilon number, exactly?"
"Hey, I told you to read about that! It's just an ordinal x that equals ω^x. They were discovered by Cantor. By definition, ε_α is the αth epsilon number."
"What's α?"
"It can be any ordinal. So, there are lots of epsilon numbers: just as many as there are ordinals!"
"Wait, then how am I ever gonna get to the zone beyond the epsilon numbers?"
"That's what I'm trying to explain, if you'd only shut up!"
"Hey, I need to know what's going on before I shoot off into huge infinities! I've got a bunch of questions. What's the War on Chaos? And also: I understand
ω ↑↑ 2 = ω^ω, ω ↑↑ 3 = ω^(ω^ω), ω ↑↑ 4 = ω^(ω^(ω^ω)), ...
and I'm even willing to accept this infinite tetration business:
ω ↑↑ ω = ω^(ω^(ω^(ω^(ω^(ω^(ω^(ω^(ω^(ω^(ω^........ )))))....
because it's a limit of smaller ones. But what's ω ↑↑ (ω+1)? It seems
ω ↑↑ (ω+1) = ω^(ω^(ω^(ω^(ω^(ω^(ω^(ω^(ω^(ω^(ω^........ ^ω)))))....
But what the heck does that mean??? What does that last ω do?"
The man in black gritted his teeth. "That, my friend, is classified. Even I don't know. People have tried to find out... like this blogger on the Tetration Forum. But they've all mysteriously disappeared. So - please, put this out of your mind. Don't even think about it!"
John Baez Shared publicly - Dec 1, 2012
"The War on Chaos," said the man in black, "was inevitable once the Singularity gave us infinite computing power. Before, infinity was just an abstraction. Now it affects the real world. But infinity brings with it undecidability, incompleteness,... perhaps even paradoxes! In short: we've opened the door, and there's no telling what chaos might enter!"
"Does this have anything to do with chaos theory?"
"No, you dope - that's physics. I'm talking logic. I just mean it's a bigger, scarier world out there than most people realize. And that's why we need you to go up and take a look around. It may be dangerous to explore these higher infinities, but if we don't do it, someone else will, and they could find something nasty and exploit it. So let's stop chatting and get to business. I was telling you about the epsilon numbers. These are the infinite ordinals you hit after you go through all the powers of the smallest one:
ω, ... ω^ω, ... ω^ω^ω, ... ω^ω^ω^ω, ...
and so on. The first epsilon number, like I keep saying right before you interrupt me, is
ε₀ = ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^........
Then comes
ε₁ = ε₀^ε₀^ε₀^ε₀^ε₀^ε₀^ε₀^ε₀^ε₀^ε₀^ε₀^ε₀^........
ε₂ = ε₁^ε₁^ε₁^ε₁^ε₁^ε₁^ε₁^ε₁^ε₁^ε₁^ε₁^ε₁^........
and so on, until you hit the ωth one:
ε_ω
That may shake you a bit, but don't stop. Just keep going faster and faster. Eventually you'll hit the ω^ωth one, and so on:
ε_{ω^ω}, ... ε_{ω^ω^ω}, ... ε_{ω^ω^ω}, ... ε_{ω^ω^ω}, ...
After all these you'll reach the ε₀th epsilon number:
ε_ε₀
At this point you need to speed up a lot! You'll zip past
ε_ε₁, ... ε_ε₂ , ... ε_ε₃, ...
and then
ε_{ε_ω}, ... ε_{ε_{ω^ω}}, ... ε_{ε_{ω^ω^ω}}, ...
and eventually you'll pass epsilon numbers with longer and longer subscripts! Like these:
ε_{ε_ε₀}, ... ε_{ε_{ε_ε₀}}, ... ε_{ε_{ε_{ε_ε₀}},...
And then the fun starts. You'll eventually hit an epsilon number that is its own subscript:
ε_{ε_{ε_{ε_{ε_{ε_{ε_{ε_{ε_{ε_{ε_{ε_{ε_{ε_{ε_{ε_{ε_{ε_{ε_{ε_{ε_{ε....
After this, you will have gone beyond the zone of the epsilon numbers!"
"Man, I don't believe this stuff! It's crazy! And you said the epsilon numbers never stop: for every ordinal there's an epsilon number ε_α."
"Yeah, there are still more epsilon numbers, they never stop. But past this point we need new names for them, because we've hit a fixed point: the ε_{ε_{ε_{ε_{ε_{ε_{ε....th epsilon number is ε_{ε_{ε_{ε_{ε_{ε_{ε... itself!"
"That's insane! Such a huge infinity can't really exist!"
"Well, maybe not - but according to standard mathematics, it does! There are theorems saying all these ordinals exist. So if you find out otherwise you need to tell us!"
• Hilbert Levitz, Transfinite ordinals and their notations: for the uninitiated, http://www.cs.fsu.edu/~levitz/ords.ps
John Baez Shared publicly - Dec 3, 2012
"I can't understand these huge infinities you're talking about now!"
The man in black sighs. "Don't say 'infinities' - that's vague. Say ordinals. Since ordinals are ordered, they capture the usual process of counting, one at a time, with one additional feature: we never stop. If you give me any set of ordinals, I can give you an ordinal bigger than all those. In fact I can give you the smallest ordinal bigger than all those. So, just by listing a bunch of ordinals that we've already defined, we get a new one: the smallest ordinal bigger than all those."
"Okay..." you say doubtfully.
"So when I list
ε_{ε_ε₀}, ... ε_{ε_{ε_ε₀}}, ... ε_{ε_{ε_{ε_ε₀}},...
having already defined them, that defines a new ordinal: the smallest ordinal bigger than all those! And that's what I'm calling
ε_{ε_{ε_{ε_{ε_{ε_{ε_{ε_{ε_{ε_{ε_{ε_{ε_{ε_{ε_{ε_{ε_{ε_{ε_{ε_{ε_{ε....
And that's where you're heading! So please, stop asking all these questions and get onto the machine."
"But how are all these ordinals really different?"
"You're either stalling for time, or you're mixing up ordinals and cardinals. But okay, one last reminder. Cardinals measure the sheer number of elements of a set, while ordinals take the order into account too. For example, this set
ω = {0,1,2,3,....}
and this one
ω+1 = {0,1,2,3,....,ω}
can be put in one-to-one correspondence. So they both correspond to the same cardinal: the smallest infinite cardinal, called aleph-nought. But if we take their ordering into account, they're different! The second one has a last element. The first one doesn't. So, they're not equal as ordinals."
"Okay... but how is ω squared different from ω? Neither of them has a last element."
"Well, David Madore drew a nice picture of ω^2. Look at it. It's ω copies of ω, one after another. I can write it out, too:
ω^2 = {0,1,2,3,... ω,ω+1,ω+2,ω+3,... 2ω,2ω+1,2ω+2,2ω+3,...... }
Some of these guys are successors: they come right after another guy. For example, 2ω+2 is a successor. But some aren't: 0, ω, 2ω, 3ω,.... And except for 0, all these other guys are limit ordinals: they have a bunch of smaller ordinals bunching up on their left. That's very different from
ω = {0,1,2,3,....}
where everybody is a successor except zero."
"Okay, but how is ω^3 different from ω^2? They both have infinitely many guys who aren't successors."
"Yeah, but..."
For more, try:
http://en.wikipedia.org/wiki/Ordinal_number
and for all the old episodes of this story click on #bigness
John Baez Shared publicly - Dec 3, 2012
"Okay, but how is ω cubed different from ω squared?"
"Look at David Madore's picture of it," says the man in black. "You can just see it's different than ω^2. It's ω copies of the picture of ω^2, laid end to end. So, not only does it have infinitely many places where lines bunch up - it also has infinitely many places where those places bunch up!"
"Huh?"
"Each really big line here is not just a limit ordinal, it's a limit of limit ordinals. ω^2 has infinitely many limit ordinals below it. But ω^3 has infinitely many limits of limit ordinals below it."
"Okay," you say, after some thought. "But how is ω^4 different from ω^3?"
"You're stalling for time - I know it!" he says angrily. "It's easy to ask infinitely many questions about infinity. You're just trying to put off getting uploaded and sent to the zone beyond the epsilon numbers. But we need you to go there now."
"Why?"
"I don't have time to explain it all. But hacker gangs like the Russian Business Network have been hiring logicians laid off after the Cold War. If they get up there before we do, and they discover it's different than standard set theory predicts, we're in trouble. They'll try to exploit those defects: hack into our system, or break our codes...."
"Come on. Just tell me how is ω^4 different from ω^3. Or don't you know the answer?"
"Of course I do! And I bet you do too: ω^3 has a lot of ordinals that are limits of limits of limit ordinals, and so on."
"Okay, that's what I thought. But when we hit ω^ω, that must go on forever. So how is the first epsilon number any different from ω^ω? Can you draw them? Do they look different?"
http://en.wikipedia.org/wiki/Russian_Business_Network
John Baez Shared publicly - Dec 5, 2012
"Okay, buster," says the man in black. "Here's a picture of omega to the omega power: ω^ω. The first bunch of lines is ω. The second bunch is ω^2. The third is ω^3. And so on, forever. Since
ω + ω^2 + ω^3 + ... = ω^ω
this is a picture of ω^ω."
[Someone should make a huge model of this, or at least a webpage where you can keep scrolling endlessly to the right, or down. Is anyone willing to try?]
John Baez Shared publicly - Dec 8, 2012
You run for the door. The man in black lunges at you, and you feel a sharp pain, but you push the door open... into a long corridor with rooms at your left numbered
1, 2, 3, ...
You charge down it, picking up speed as you go. Before you know it you pass a door that's bigger than the rest, numbered
ω
You keep running:
ω+1, ω+2, ω+3, ...
and soon the doors are whizzing by so fast you only pay attention to the larger ones:
2ω, ... 3ω, ... 4ω, ...
An impressive door looms into view and you slow down for a second:
ω^2, ω^2+1, ω^2+2, ...
But then you hear the man in black's footsteps behind you. You speed up:
ω^3, ... ω^4, ... , ω^5,...
and you scarcely pause as you pass a door with a fancy marble cornice:
ω^ω, ω^ω+1, ... ω^ω+ω, ...
He seems to be catching up, so with a burst of adrenaline you charge ahead:
ω^ω^ω, ... ω^ω^ω^ω, ... ω^ω^ω^ω^ω, ...
and before you know it you reach an enormous door made of some sort of stone, maybe granite, with
ε₀ = ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^......
carved on it. But you keep on running faster:
ε₀, ... ε₀^2, ... ε₀^3, ...... ε₀^ω, ...... ε₀^ω^ω, ...... ε₀^ε₀, ......
ε₀^ε₀^ε₀, ...... ε₀^ε₀^ε₀^ε₀, ......
and scarcely notice when you hurtle past the next enormous stone door:
ε₁ = ε₀^ε₀^ε₀^ε₀^ε₀^ε₀^ε₀^ε₀^ε₀^ε₀^ε₀^ε₀^ε₀^ε₀^ε₀^ε₀^ε₀^ε₀^ε₀^......
You just keep going:
ε₂, ... ε₃, ... ε₄, ...
and before you know it, even these epsilons are whizzing by so fast you can only see the more impressive ones:
ε_ω, ...... ε_{ω^ω}, ..... , ε_{ω^ω^ω}, ..... ε_ε₀, ...... ε_{ε₀^2}, ......
ε_{ε₀^ω}, ...... ε_{ε₀^ω^ω}, ...... ε_{ε₀^ε₀}, ...... ε_{ε₀^ε₀^ε₀}, ......
ε_ε₁, ..... ε_ε₂, ...... ε_ε₃, ..... ε_ε₄, ......
The footsteps behind you seem to fade into the distance. You begin to relax a bit, and you realize how tired you are. You also notice that what started as an office hallway has somehow turned into a city street. You stop and catch your breath at a obscure door labelled
ε_{ε₄₂ + 2ε₈ + ε_{ε₀^ω^ω + ω^ω^{5ω^ω^ω + 24ω + 1}} + 248ε₄^ω + ω + 1
You knock on it. No answer. Pressing your ear to it, you hear faint conversation and a bit of music. "Hello? Anyone home?"
A voice behind the door shouts "No!" A woman giggles. You hear faint footsteps... on the street behind you! In a panic, you run on:
ε_{ε_ε₀}, ...... ε_{ε_{ε_ε₀}}, ....... ε_{ε_{ε_{ε_ε₀}}}, .......
and in a burst of speed you come to the end of the street: a huge marble door, with
φ₂(0) = ε_{ε_{ε_{ε_{ε_{ε_{ε_{ε_{ε_{ε_{ε_{ε_{ε_......
embossed in gold. You push on it, and push, and slowly it swings open. A blinding white light shines from within. As you step inside, trumpets play a fanfare, and a bass voice thunders:
"Welcome. Welcome to THE ZONE BEYOND THE EPSILON NUMBERS."
John Baez Shared publicly - Dec 17, 2012
"I'm sick of these missions to infinity," you say. "Every time I complete one, you erase most of my memory and send me on another! I'm losing track of what's going on. It's like climbing an endless spiral staircase!"
"Well of course it is," says the man in black. "What did you expect? And we have to wipe most of your memory when you come back down. It's only finite, after all."
"Okay, but it's both confusing and tiring. Can't we just get it over with?"
"Over with? You want to get infinity over with? You really don't get it."
"Well, first I went up to levels
0, 1, 2, 3, ... ω
and I thought that was impressive, but then came
2ω, 3ω, 4ω, ... ω^2
and then
ω^2, ω^3, ω^4, ... ω^ω
That gave me a nightmare! But then you sent me on to
ω^ω, ω^(ω^ω), ω^(ω^(ω^ω)), ... ω^(ω^(ω^(ω^(ω^(ω^(ω^(ω^(ω^(....
and I thought "Okay, I'm done now - there's no way to even talk about bigger ordinals!" But then you called this number ε₀ and informed me it was a fixed point of the function ω^x, meaning
ω^ε₀ = ε₀
Fine. But then you said it was just the first fixed point of this function! And you sent me on to infinitely many more:
ε₁, ... ε₂, ... ε₃, ... ε₄, ... ε_ω, .... ε_ε₀, ... ε_ε₁, ..... ε_ε₂, ....
ε_{ε_ε₀}, ...... ε_{ε_{ε_ε₀}}, ....... ε_{ε_{ε_{ε_ε₀}}}, .......
until I hit
ε_{ε_{ε_{ε_{ε_{ε_{ε_{ε_{ε_{ε_{ε_{ε_{ε_......
I thought "Okay, now I'm really done!" But then you called this number φ₂(0), because it's the first fixed point of the next function, the function after ω^x, namely ε_x. Say, by the way - why do you always use the number 0 to label the first thing of some sort? It's really annoying."
He opens the door, looks out in the hall to make sure nobody is there, and then whispers in your ear: "It confuses the enemy."
"Hmm. Anyway, then I got the hang of your game. There's one function for each ordinal:
φ_0, φ_1, φ_2, φ_3, ...
starting with φ_0(x) = ω^x. For each function φ_y we eventually hit ordinals x that are fixed points of that function:
φ_y(x) = x
And you call the xth fixed point φ_{y+1}(x), thus defining the next function. Fine. So this game goes on forever..."
"Right: the Veblen hierarchy."
"But then comes an ordinal so big that it doesn't fit into this system. The Fefferman-Schütte ordinal. You're telling me it's the first ordinal x with
φ_x(0) = x
so we can't name it using the Veblen hierarchy unless we already have a name for it."
"Right! And it's very important that you go up there!"
"But it's not the end, is it? You already called it Γ₀. That's a hint. It's just the start of another, bigger hierarchy of infinities. Right?"
For the first time, you see the man look a bit sheepish. "Yeah, true. But don't worry about that. We need you to check that Γ₀ really exists. If it does, we know arithmetical transfinite recursion is okay, and Lusin's separation theorem, and.... well, a bunch of other stuff. But if it doesn't, then we'll have to really roll back our plans: we're limited to predicative arithmetic. Big commercial interests will be damaged... but it's better to know that soon, than wait and find out too late."
"I don't understand any of this!"
He rolls his eyes. "Did you think the infinite would stop when it was still easy to understand?"
"Okay. But I want to know: what comes after Γ₀? I figure whatever comes next, you're going to try to send me there."
The man breathes a deep sigh. "Okay. You asked for it...."
The picture here is by Alexandre Duret-Lutz and is available under an attribution / share-alike Creative Commons copyright:
http://www.flickr.com/photos/gadl/288607676/
To understand what the man in black was talking about at the end, try:
http://en.wikipedia.org/wiki/Veblen_function http://en.wikipedia.org/wiki/Ordinal_analysis http://en.wikipedia.org/wiki/Reverse_mathematics
John Baez Shared publicly - Dec 7, 2012
Do really huge numbers actually exist? Edward Nelson is one of the few mathematicians who thinks they might not. A while ago he tried to show the usual axioms for arithmetic - Peano arithmetic - are inconsistent. His proof was shot down, but here's an earlier paper that tries something less ambitious: "Warning Signs of a Possible Collapse of Contemporary Mathematics".
He starts by taking Peano arithmetic and making up a new axiom system P0 by throwing in a new predicate, which I'll call really exists, and two new axioms:
1. 0 really exists. 2. If x really exists, then x+1 really exists.
It follows that 0, S0, SS0, and so forth all really exist. But we can't prove that all numbers really exist. You might be tempted to do it using induction, but the induction axioms of arithmetic were postulated for formulas of the original language of arithmetic, and 'really exists' is not in that language. You can't even prove that if x and y really exist then so does x+y.
Next he defines a number x to be addable if for all y that really exist the sum x+y really exists. In P0 you can prove all addable numbers really exist. You can also show they're closed under addition.
Then he defines a number x to be multiplicable if for all addable numbers y the product xy is addable. In P0 you can prove multiplicable numbers are addable, so they really exist. You can also show they're closed under addition and multiplication. The last part uses associativity of multiplication.
He concludes, and I'll paraphrase:
"The significance of all this is that addition and multiplication are unproblematic... For any specific numeral SSS...0 we can quickly prove that it is a multiplicable number. But now we come to a halt. If we attempt to define “exponentiable number” in the same spirit, we are unable to prove that if x and y are exponentiable then so is x^y. There is a radical difference between addition and multiplication on the one hand and exponentiation, superexponentiation [=tetration], and so forth, on the other hand. The obstacle is that exponentiation is not associative [....]"
"For any specific numeral SSS. . . 0 we can indeed prove that it is exponentiable, but we cannot prove that the world of exponentiable numbers is closed under exponentiation. And superexponentiation leads us entirely away from the world of counting numbers. The belief that exponentiation, superexponentiation, and so forth, applied to numerals yield numerals is just that—a belief. Here we have the third, and most serious, warning sign of trouble in contemporary mathematics."
I don't personally believe this is a 'sign of trouble' - I believe Peano arithmetic is consistent. But it does give a precise sense in which huge numbers defined by repeated exponentiation, or tetration, or higher operations are more 'ghostly' than those defined by addition and multiplication. And it's very interesting how this is connected with the failure of the associative law for exponentation!
John Baez Shared publicly - Dec 10, 2012
You wake with a start, completely disoriented. A man in black is looking down at you. "How are you?" he asks.
"Huh?"
"Any strange experiences? It was just a trial run; we need to check your mental state."
"I was having a weird dream. I was in a library. I pulled a book off a shelf. Each page was half as thick as the one before it. And then I started running, and... oh, it's confusing. A lot of stuff happened. I was running down a hallway. When I got to the end, I opened a huge door, and then it got really kitschy. Like a cartoon of arriving in heaven: there were trumpets, and a deep bass voice welcoming me...."
He chuckles. "Oh, the boys in Narration must have been having fun."
"Narration?"
"Yeah. Uploading is easy when you've got infinite processing power, but downloading back to wetware is a bitch. It's not just that neurons are messy. When you're up in the transfinite" - he motions upwards with his thumb - "you can do a lot of stuff, but your memories down here have to be finite. So they have to compress and simplify the storyline."
"Huh?" None of this is making sense.
"We can't just leave out big chunks of memory - well, we tried, but the results weren't pretty. We've gotta weave plausible memories that summarize the infinite tasks you completed up there. Anyway, did you get any sign that you'd made it to the zone beyond the epsilon numbers?"
"Yeah! That's what the voice said: "WELCOME TO THE ZONE BEYOND THE EPSILON NUMBERS""
"Heh. Not exactly subtle. So it worked. Okay, I think you're ready to ascend the Veblen hierarchy."
"Veblen? Isn't he that economist who talked about 'conspicuous consumption'? About how rich people like to show off?"
"That's Thorstein Veblen. But his nephew Oswald saw the implications. What's the most conspicuous form of consumption? Infinite consumption. What can you get for the man who has everything? More of everything. Infinitely more. But not all infinities are equally big. So we need a system of names for them. And now, thanks to the Singularity, it's not just theoretical. It ain't just about infinitely powerful computers. The economy will go singular too. Transfinance. No more limits to growth. If we win the War on Chaos. And that's where you come in."
http://en.wikipedia.org/wiki/Oswald_Veblen http://en.wikipedia.org/wiki/Thorstein_Veblen
This infinity dollar bill was created by Thomas Hannsz. You can buy it for much less than its face value:
http://www.artistrising.com/products/252268/infinity-dollar.htm
" Shared publicly - Dec 10, 2012 Naming the unnameable
Suppose we have a system of names for infinities. Any system can only name countably many of them... so there are infinitely many that can't be named. Indeed, there are infinitely many that are bigger than all the ones we have named.
But the way things work, this means there's a unique smallest infinity that's bigger than all those we have named. And so, this phrase serves as a name for an infinity that's bigger than all the ones we've named!
There's no paradox here, unless we deliberately go out of our way to get in trouble. We started with a particular system for naming infinities. But this new name - the smallest infinity bigger than all those we have named - is not part of that system.
It could, however, be part of a new system of names. And we can repeat this trick over and over and over and over! And indeed, this is a good way to build bigger, better systems for naming infinities.
I've tried to keep this nontechnical. 'Infinities' is not a precise term. There are at least three ways to make it precise and make what I'm saying true:
• One is 'cardinals'. Cardinals are how we measure the size of infinite sets.
• One is 'ordinals'. Ordinals are how we measure the size of well-ordered sets: sets with an ordering where every nonempty subset has a least element.
• One is 'countable ordinals'. These are how we measure the size of countable well-ordered sets: well-ordered sets that can be put in one-to-one correspondence with the integers.
So far in this #bigness series, I've been concentrating on countable ordinals. We started by naming these using plus, times, exponentials, 1 and
ω
which is the smallest ordinal bigger than all these:
1, 1+1, 1+1+1, ...
This system of names, called Cantor normal form, lets us name countable ordinals like
ω^ω^(ω+ω) + ω^ω + ω^ω + ω + ω + 1 + 1 + 1
The smallest ordinal that can't be named this way is called ε₀. You could say it has an infinitely long name:
ε₀ = ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^...
but that's stretching the rules; what this equation really means is that ε₀ is the smallest ordinal bigger than all these:
ω, ω^ω, ω^ω^ω, ...
If we throw ε₀ into our system, we can name a bunch of bigger ordinals. The smallest one that can't be named in this new system is called ε₁. Namely, it's the smallest ordinal bigger than all these:
ε₀, ε₀^ε₀, ε₀^ε₀^ε₀, ...
This game keeps going on forever, so we can create a new system of names that includes using plus, times, exponentials, 1, ω, ε₀, ε₁, ε₂,... and so on forever. And to go as far as we can, we allow the subscript of the ε to be any ordinal we can name in this system!
However, there are still ordinals that can't be named in this system. The smallest one is called φ₂(0), for reasons I'll explain later. It's the smallest ordinal bigger than all these:
ε₀, ε_ε₀, ε_{ε_ε₀}, ε_{ε_{ε_ε₀}}, ...
And it's the start of a more powerful system for naming ordinals: the Veblen hierarchy. This system goes much further, and it's time for me to start talking about it. It was invented in 1908 by the guy shown here: the topologist and geometer Oswald Veblen.
But we can't escape the problem: there are still countable ordinals that can't be named this way. The smallest one that can't is called the Feferman–Schütte? ordinal, Γ₀. It's very interesting. So the game goes on...
http://en.wikipedia.org/wiki/Veblen_function
John Baez Shared publicly - Dec 12, 2012
"When we commercialize the transfinite, the economic opportunities will be limitless!" says the man in black. "For example: tourism. You won't have to choose where to go on vacation: for a price, you can choose to go everywhere. Just think of it: a chain of Hilbert Hotels serving infinitely many copies of uploaded tourists."
"Hilbert Hotels?" you ask, rubbing your forehead.
"Yeah, you know: hotels with ω rooms, so when they fill up you can move all the guests into the even-numbered ones, making space for lots more when the next tour bus arrives. Great business model. But investors want to know the infrastructure is safe. And there are risks. The Russian mafia has been hiring students of Yesenin-Volpin, the radical finitist, to look for flaws and exploit them. And that's not all. Hence the War on Chaos. So we want you to ascend the Veblen hierarchy and scout around, see if math is still secure up there."
"So what is this 'Veblen hierarchy', exactly?" You seem to be developing a splitting headache.
"It's a way to name countable ordinals. You've already seen a bit of how it works. First we take ω and start raising it to powers. ω^2 is a lot bigger than 2, and ω^3 is a lot bigger than 3, so at first this seems like a great way to name big ordinals. But eventually it fizzles out. Eventually we hit an ordinal x that's so big that
ω^x = x
This is the first fixed point of the function ω^x. Veblen called it φ₁(0)."
"I thought it was called ε₀," you say. "You know,
ε₀ = ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^......
so when you raise ω to this power you get back the same number."
"That's what Cantor called it, but Veblen's notation is more systematic. It turns out there are infinitely many fixed points of the function ω^x. Veblen called these φ₁(0), φ₁(1), φ₁(2) and so on. They're just the same as ε₀, ε₁, ε₂, and so on. But now comes the fun part."
"What's that?" you ask.
"We can define φ₁(x) for any ordinal x, and this lets us name some big ordinals: the epsilon numbers. But eventually this fizzles out. Eventually we hit an ordinal so big that
φ₁(x) = x
And Veblen called this ordinal φ₂(0)."
"Oh," you say, "Now I get it. That's why that sign on the door said
φ₂(0) = ε_{ε_{ε_{ε_{ε_{ε_{ε_{ε_{ε_{ε_{ε_{ε_{ε_......
when I reached the zone beyond the epsilon numbers!"
"Right. But the function φ₁ has infinitely many fixed points: this is just the first one. And Veblen called them φ₂(0), φ₂(1), φ₂(2) and so on."
"I get it," you say. "And now you're going to tell me we can define φ₂(x) for any ordinal x, but eventually we hit an ordinal so big that
φ₂(x) = x
And this ordinal is φ₃(0). And in fact the function φ₂ has infinitely many fixed points, and Veblen called these φ₃(0), φ₃(1), φ₃(2) and so on."
"Right. Now you're getting the pattern," says the man in black. "That's the Veblen hierarchy. But here's a little puzzle for you. What's φ₀(x)?"
For more on Hilbert's hotel, see:
http://en.wikipedia.org/wiki/Hilbert%27s_paradox_of_the_Grand_Hotel
To buy souvenirs from Hilbert's hotel, like this picture here, see:
http://www.mathematicianspictures.com/DAVID_HILBERT/Hilberts_Hotel.htm
John Baez Shared publicly - Dec 13, 2012
Brouwer showed any continuous function f from a disc to itself has a fixed point: a point with
f(a) = a
The proof is beautiful but subtle. It's much easier to show that lots of functions from ordinals to ordinals have fixed points. This lets us build ordinals like
ε₀ = ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^ω^......
They're fixed points:
ω^ε₀ = ε₀
Here's how it works. Suppose a function f from ordinals to ordinals is increasing:
if x < y then f(x) < f(y)
and continuous: f of a limit ordinal x is the limit of f of the ordinals less than x.
Then f must have a fixed point. Why? For starters, we always have this fact:
x ≤ f(x)
After all, if this weren't true, there'd be a smallest x with the property that f(x) < x, since every nonempty set of ordinals has a smallest element. But since f is increasing,
f(f(x)) < f(x)
so f(x) would be an even smaller ordinal with this property. Contradiction!
Using this fact repeatedly, we get
0 ≤ f(0) ≤ f(f(0)) ≤ ...
Let a be the limit of the sequence
0, f(0), f(f(0)),...
or in other words, the smallest ordinal greater than equal to all these. Then by continuity, f(a) is the limit of the sequence
f(0), f(f(0)), f(f(f(0))),....
So f(a) equals a. Voilà! A fixed point!
And this is just the smallest fixed point of f. There are infinitely many more, since we can start not with 0 but with a+1 and repeat the same argument, etc. Indeed if we try to list these fixed points, we find there's one for each ordinal. This is the key to the 'Veblen hierarchy'.
To learn more about this, you need to know that a function that's increasing and continuous is called normal. This is an adjective mathematicians use whenever they haven't had enough coffee in the morning and aren't feeling creative - it means a thousand different things.
http://en.wikipedia.org/wiki/Normal_function
For a more detailed version of the proof I just gave, see:
http://en.wikipedia.org/wiki/Fixed-point_lemma_for_normal_functions
John Baez Shared publicly - Dec 14, 2012
The smallest infinity that can't be defined without self-reference
As we climb the ladder of infinities, things gradually get a bit spooky. There are lots of infinities - or more technically, ordinals. If a property is true of some ordinal, there's a unique smallest ordinal with that property. So if
"can't be defined without self-reference"
is a property that's true of some ordinal, we can define that ordinal as follows:
"The smallest ordinal that can't be defined without self-reference"
Does this definition involve self-reference? Apparently so... otherwise we'd have a contradiction!
In fact,
"can't be defined without self-reference"
is too vague for this argument to become a theorem... until we make it more precise. But there's a way to do this.
Some definitions mention a big set that includes the thing being defined. These definitions are called impredicative. They are mildly circular. Some mathematicians think this is bad. These mathematicians prefer predicative definitions.
For example, the least upper bound of a set X of numbers is the smallest element of the set S consisting of all upper bounds of X. But the least upper bound is in this set S! So this definition of 'least upper bound' is impredicative. At one stage, the famous mathematicians Poincare and Weyl disliked this. But most mathematicians think it's okay.
In this 1960s, the logicians Feferman and Schütte came up with a precise concept of predicative mathematics. Alas, I don't understand it yet. But it gives a precise concept of
"The smallest ordinal that can't be defined predicatively"
This ordinal is called the Feferman-Schütte ordinal, or Γ₀. It's also the first ordinal that's not in the Veblen hierarchy - a system for naming countable ordinals, which I've been talking about lately.
For more on predicativity, try this paper:
• Solomon Feferman, Predicativity, http://math.stanford.edu/~feferman/papers/predicativity.pdf
If I really understood all this, I'd be happier.
John Baez Shared publicly - Dec 17, 2012
"I'm sick of these missions to infinity," you say. "Every time I complete one, you erase most of my memory and send me on another! I'm losing track of what's going on. It's like climbing an endless spiral staircase!"
"Well of course it is," says the man in black. "What did you expect? And we have to wipe most of your memory when you come back down. It's only finite, after all."
"Okay, but it's both confusing and tiring. Can't we just get it over with?"
"Over with? You want to get infinity over with? You really don't get it."
"Well, first I went up to levels
0, 1, 2, 3, ... ω
and I thought that was impressive, but then came
2ω, 3ω, 4ω, ... ω^2
and then
ω^2, ω^3, ω^4, ... ω^ω
That gave me a nightmare! But then you sent me on to
ω^ω, ω^(ω^ω), ω^(ω^(ω^ω)), ... ω^(ω^(ω^(ω^(ω^(ω^(ω^(ω^(ω^(....
and I thought "Okay, I'm done now - there's no way to even talk about bigger ordinals!" But then you called this number ε₀ and informed me it was a fixed point of the function ω^x, meaning
ω^ε₀ = ε₀
Fine. But then you said it was just the first fixed point of this function! And you sent me on to infinitely many more:
ε₁, ... ε₂, ... ε₃, ... ε₄, ... ε_ω, .... ε_ε₀, ... ε_ε₁, ..... ε_ε₂, ....
ε_{ε_ε₀}, ...... ε_{ε_{ε_ε₀}}, ....... ε_{ε_{ε_{ε_ε₀}}}, .......
until I hit
ε_{ε_{ε_{ε_{ε_{ε_{ε_{ε_{ε_{ε_{ε_{ε_{ε_......
I thought "Okay, now I'm really done!" But then you called this number φ₂(0), because it's the first fixed point of the next function, the function after ω^x, namely ε_x. Say, by the way - why do you always use the number 0 to label the first thing of some sort? It's really annoying."
He opens the door, looks out in the hall to make sure nobody is there, and then whispers in your ear: "It confuses the enemy."
"Hmm. Anyway, then I got the hang of your game. There's one function for each ordinal:
φ_0, φ_1, φ_2, φ_3, ...
starting with φ_0(x) = ω^x. For each function φ_y we eventually hit ordinals x that are fixed points of that function:
φ_y(x) = x
And you call the xth fixed point φ_{y+1}(x), thus defining the next function. Fine. So this game goes on forever..."
"Right: the Veblen hierarchy."
"But then comes an ordinal so big that it doesn't fit into this system. The Fefferman-Schütte ordinal. You're telling me it's the first ordinal x with
φ_x(0) = x
so we can't name it using the Veblen hierarchy unless we already have a name for it."
"Right! And it's very important that you go up there!"
"But it's not the end, is it? You already called it Γ₀. That's a hint. It's just the start of another, bigger hierarchy of infinities. Right?"
For the first time, you see the man look a bit sheepish. "Yeah, true. But don't worry about that. We need you to check that Γ₀ really exists. If it does, we know arithmetical transfinite recursion is okay, and Lusin's separation theorem, and.... well, a bunch of other stuff. But if it doesn't, then we'll have to really roll back our plans: we're limited to predicative arithmetic. Big commercial interests will be damaged... but it's better to know that soon, than wait and find out too late."
"I don't understand any of this!"
He rolls his eyes. "Did you think the infinite would stop when it was still easy to understand?"
"Okay. But I want to know: what comes after Γ₀? I figure whatever comes next, you're going to try to send me there."
The man breathes a deep sigh. "Okay. You asked for it...."
The picture here is by Alexandre Duret-Lutz and is available under an attribution / share-alike Creative Commons copyright:
http://www.flickr.com/photos/gadl/288607676/
To understand what the man in black was talking about at the end, try:
http://en.wikipedia.org/wiki/Veblen_function http://en.wikipedia.org/wiki/Ordinal_analysis http://en.wikipedia.org/wiki/Reverse_mathematics
John Baez Shared publicly - Dec 20, 2012
The man in black breathes a deep sigh. "Okay. You asked for it... You're sure you really want to know?"
"Yeah! You've made the Feferman-Schütte ordinal sound like an incredibly huge infinity, a kind of holy grail... but you're calling it Γ₀, so I can tell it's just the start of another story... a bunch of even bigger infinities beyond the Veblen hierarchy."
He smiled. "Did you ever have a car where you ran up the odometer to 99,999 miles?"
"Yeah, sure."
"Then what happened?"
"100,000 miles, of course!"
"You went up to numbers with one more digit. That's sort of how it goes with the Veblen hierarchy. It was great at naming big countable ordinals, but eventually it fizzles out... and then we go up to the two-variable Veblen hierarchy. I could explain it, but..."
"Nah, don't bother. Not yet. I'm really getting sick of this stuff. It's burning out my brain. I just want to know: what happens when that system fizzles out?"
"Well, then comes the three-variable Veblen hierarchy..."
"Yeah, I should have guessed. And so on, and so on. But then what?"
"Well, then come the infinite-variable Veblen hierarchies, for various sizes of infinity: various countable ordinals. But at this point it gets harder to learn about this stuff. You pretty much have to break down and read Schütte's book Proof The ory , which is not for the faint of heart."
"Okay, but what then?"
He hesitates. "Well, you could probably keep going head-on, somehow... but a guy named Bachmann thought of a better trick."
"Yeah? What?"
He looks nervously at his hands. "It's a bit weird. At this point, the uncountable starts infesting the countable."
"What does that mean?"
"All the ordinals we've been talking about so far are countable. But there are also uncountable ones, which are a lot bigger. The first one is called Ω. And Bachman noticed that to name really large countable ordinals, it helps to use uncountable ones as part of the names!"
"Wow!"
"Yeah. And something sorta similar happens lower down, too: the infinite infests the finite. To name really large finite numbers, it helps to use infinite ones! And this is more practical."
"Why?"
"Because when really big investors get downloaded back to the finite, they can't bring their infinite wealth back down. And that's a bummer. But they can bring large finite amounts of money - if we can name those large numbers. You heard of Graham's number?"
"Umm, yeah - I think so. Isn't that a number so huge that if you had all the digits in your mind, your brain would turn into a black hole?"
"Yeah. And that's an insane underestimate! Check out this picture of it. Remember, Knuth’s up-arrow notation is a way of talking about exponentiation, tetration, and so on:
3↑3 = 3 × (3 × 3) 3↑↑3 = 3 ↑ (3 ↑ 3) 3↑↑↑3 = 3 ↑↑ (3 ↑↑ 3)
etc. So to get Graham's number we start out with
g(1) = 3↑↑↑↑3
Then we define
g(k+1) = 3 ↑↑↑↑↑↑↑↑↑↑↑↑g(k) of these↑↑↑↑↑↑↑↑↑↑↑↑ 3
And then we go on up to g(64). That's Graham's number!"
"That's insanely huge! My brain just turned into a black hole!"
"Yeah! But my point is this. Graham's number may seem like a lot of money to you. But once transfinance really gets going, and the investors start bringing down their profits, that'll be peanuts. Chump change!"
http://en.wikipedia.org/wiki/Graham%27s_number http://en.wikipedia.org/wiki/First_uncountable_ordinal
Toby Bartels Shared publicly - Jan 22, 2013
The Patterns of Resemblance Ordinal Calculator does arithmetic on ordinals below the ordinal of Π^1_1-CA_0.
http://www.xamuel.com/introducing-patterns-calculator/
And in case that's completely incomprehensible:
http://www.xamuel.com/geometric-patterns-of-resemblance/
David Roberts Shared publicly - Aug 8, 2013 #bigness
Here's a chart akin to that famous one from Kanamori's book The higher infinite, but focusing on a the range from supercompact cardinals up to excessively hypercompact cardinals, which are inconsistent! (presumably with ZFC). The author particularly considered high-jump cardinals in his thesis. Joel Hamkins expresses his desire for +Victoria Gitman to make an analogous chart for the range of cardinals she studied, roughly around Ramsey cardinals.
Edit: And it turns out Victoria did make said chart! It's here:
http://boolesrings.org/victoriagitman/2013/06/28/large-cardinal-chart-of-ramsey-like-cardinals/
http://boolesrings.org/perlmutter/2013/04/30/chart-of-large-cardinals-near-high-jump/
