"Infinity!" "Infinity plus 1!" "Infinity plus a hundred!" "Infinity times ten!" "Infinity times infinity!" Remember playing this game as a child? Trying to compete to name the biggest infinity? What happens when pure research mathematicians play this game?
A few quarters back, standing outside an auditorium before giving a calculus final exam, some of my students asked what I was reading. It was "The Higher Infinite", a very advanced tome of mathematics by Akihiro Kanamori. My students were understandably pretty interested to hear about the idea of more than one kinds of infinity. In fact, there are infinitely many levels of infinity. And that's even pretty well-known, at least among people who read about math. What Kanamori writes about, in rather difficult mathematical language (the book is meant for advanced graduate students or math PhDs), are some lesser-known infinities, which are so big that they literally bend the basic facts of mathematics. It's some pretty trippy stuff.
WHAT IS INFINITY?
In formal set theory, there is no single entity called "infinity". In mathematics, when we say that the answer to some question is "infinity", we really mean that any finite answer would be too small. The "entity" of infinity is just a kind of shorthand for expressing this idea. But there are infinite sets-- that is, collections which are infinite. When we talk about multiple "levels of infinity", we're really talking about collections of different, infinite, sizes.
Here's an example. Take the collection of all natural numbers (the natural numbers are the numbers 0, 1, 2, 3, 4, and so on; the numbers you use to count). How big is this collection? Any finite answer, is too small. For example, if we guess that the collection of natural numbers has size one million, then that's too small because there are more than a million counting numbers. Since any finite answer is too small, we say the collection is infinite.
What about the set of all real numbers, with any number of decimal places, including infinitely many non-repeating decimal places, like in the number pi=3.1415...? If we look at this "continuum" of real numbers, again it's infinite, because any finite size would be too small. It turns out, that the set of all real numbers, is actually larger than the set of all counting numbers. And that's the prototypical example to show that there are more than one sizes of infinity. But, what does it mean to say that one infinite collection is larger than another?
To understand how the sizes of infinite collections can be compared, it's first necessary to understand how the sizes of finite collections are compared. One way to compare the sizes of finite collections, is to just count them and compare the numbers. But that doesn't generalize to infinite collections, because we can't count an infinite collection-- if we could, it would not be infinite.
A better way-- or at least, a more generalizable way-- to compare the sizes of finite collections, is to check whether we can marry their elements up together in a nice one-to-one way. If two finite collections have the same size, then we can think of one collection as being the collection of "males", think of the other as being the collection of "females", and marry them up so everyone has exactly one partner. If the collections had different sizes, we couldn't do this, someone would be left out.
This "marriage" idea is referred to in mathematics as a "bijection". A bijection is just a fancy, smart-sounding way of saying, you assign each member of the first collection to a unique member of the other, so that nothing is left out and nothing is matched up twice. If two collections have a bijection between them, then they have the same size, and if not, then they have different sizes.
You can think of counting small (smaller than size eleven) sets as establishing a bijection between the set and between a certain subset of your fingers. You count "one, two, three, four," holding up a finger with each utterance, and you're implicitly "marrying" a certain set of your fingers to elements of the set you're counting.
The bijection idea naturally generalizes to infinite sets with no extra work. Two sets, whether they be finite or infinite, are said to have the same size if there's some way to link their elements together bijectively, so that each element of the first gets associated with exactly one element of the second.
Right away, some trippy examples come up. For example, the set of all even counting numbers (0,2,4,6,8,...) has the same size as the set of all counting numbers. That's because if you take any even counting number and divide it in half, you get a counting number, and the result is unique and no other even number gives the same result. The act of dividing in half, is a bijection from the set of even counting numbers, to the set of all counting numbers.
THERE ARE MORE THAN ONE SIZES OF INFINITY
The famous example which first shows that there are more than one sizes of infinity, is the fact that there are more real numbers than there are counting numbers. A real number being, any number, positive or negative, with any number of decimal places. Including numbers like pi or the square root of two, where there are infinitely many non-repeating decimal places.
The fact that there are more real numbers than counting numbers was a big surprise to mathematicians; after all, both sets have infinitely many elements, so a mathematician back in the old times might have said both sets have size infinity.
Saying that there are more reals than naturals comes down to saying that there aren't enough naturals to associate with the reals; if we try to marry each real number to a unique natural number, with no naturals getting married twice, then there won't be enough natural numbers to go around and some (in fact, most) of the reals will be left out. In other words, there is no bijection from the naturals to the reals. Since the naturals are a subset of the reals, that is, every natural is a real, there are at least as many real numbers as there are natural numbers; so if there's no bijection between them, then the set of real numbers must be strictly bigger.
Georg Cantor, the mathematician who discovered a lot of this stuff about different infinities, published a famous proof that there's no bijection between the naturals and the real numbers. You can read his proof, the famous "diagonal argument", at Wikipedia. I'll give a different proof, one which is in my opinion more acid-trippy and fun. Anyway the diagonal argument has been beaten into the ground by a million other people so it's better to give a less well-known proof anyway.
My proof uses a certain infinite sum which is related to one of the Zeno's paradoxes, if you've ever read about those. Basically, in order to walk across a distance of size 1 meter, first you have to walk one half meter. Then, you have to walk one fourth meter. Then, you have to walk one eighth meter, then one sixteenth meter, and so on. Adding up all those partial walks, each one half as long as the previous, you get the total distance of one meter. This gives the infinite sum, 1/2+1/4+1/8+...=1. What does this have to do with proving there are more reals than naturals? Hold onto your hat...
Suppose that there was a bijection from the naturals to the reals. Then we could "count" the reals, saying, this real number is the first real; this real number is the second real; this real number is the third real; and so on. Using the association from the counting numbers, to the reals. And it would hit every real number, since, according to the assumption, each real number has a natural number associated with it.
Now I'm gonna show a way that you can cover the entire real number line, with a covering of length 1. That's ridiculous, because the real number line is infinitely long. There's no way to cover it with just a covering of length one. For instance the real line contains the interval from -1 to 1, which has length 2 just by itself.
Well, take the "first" real number (i.e., the number which is associated to the counting number 0). Cover it with a cover of length 1/2. Next, take the "second" real number, and cover it with a cover of length 1/4. Take the "third" real number, and cover it with a cover of length 1/8, then cover the "fourth" real number with a cover of length 1/16, and so on. Even if none of these covers overlapped, the total area of the cover would be at most 1/2+1/4+1/8+...=1. In fact, the covers overlap a lot, so the total area of these covers ends up being less than 1. But every real number is the nth real number for some n; that's the assumption we made, that we had a bijection between counting numbers and reals. So, every real number gets covered. I've covered the whole real line, with a covering scheme where the covers have a total length no longer than 1. Impossible, that's not even enough to cover just the part of the real line from -1 to 1.
I started out assuming there was a bijection from the naturals to the reals. Then, I showed that the assumption allows me to do something ridiculous. So the assumption must be wrong, and there is no bijection between the naturals and the reals. They have different sizes, and the reals contain the naturals, so there are more reals than naturals.
(Actually the proof is missing a little detail, since I'm assuming some common sense notions about how lengths work. The details are filled in in an advanced branch of math called "measure theory", but I figured it'd be worth the reduced details to post this alternate proof that there's no bijection.)
THERE ARE INFINITELY MANY LEVELS OF INFINITY
I just established there are more than one levels of infinity, by showing that the set of real numbers is bigger than the set of natural numbers. But the infinitudes get much, much bigger, and there are far more sizes of infinity than just the size of the set of naturals and the size of the set of reals.
If you take any collection of objects, it makes sense to talk about subsets of that collection. Like, the set of even numbers is a subset of the set of all numbers. Well, once you have the notion of subsets, you can ask about the collection of all subsets of a set. For example, you can ask about the set of all subsets of the natural numbers. This set-of-all-subsets is called the power set. The power set of the natural numbers is the set of all sets of natural numbers.
Here's the big breakthrough which leads to infinitely many levels of infinity. It's a fundamental truth discovered by Georg Cantor, and it totally turned mathematics on its head. Cantor showed: if you have any set whatsoever-- empty, finite, or any level of infinite-- then the power set is even bigger.
For example, the power set of the natural numbers-- the set of all sets of natural numbers-- is bigger than the set of natural numbers. So that gives another proof that there are more than one levels of infinity. (Incidentally, which set is bigger, the power set of the natural numbers, or the set of real numbers? Or are they the same size? It turns out this question is unanswerable. Read more at Continuum Hypothesis)
To get infinitely many levels of infinity, you can just repeat the process. You can take the power set of the power set of the set of naturals, and get something even bigger. And then you can take the power set of that. The process never ends, and it provides infinitely many levels of infinity.
SO HOW MANY LEVELS OF INFINITY ARE THERE?
I've shown you how there are infinitely many different levels of infinity, and a natural question which you might ask is, what is the size of the set of all levels of infinity? So far, I've showed how to get infinitely many different levels of infinity, but the infinities we can create using just power set, can be placed into a natural association with the natural numbers. I can say that the 0th infinity corresponds to the number of natural numbers. And then I can say the 1st infinity is the power set of the 0th. And the 2nd is the power set of the 1st, and so on. This hits all the infinities we get with just repeated power setting of the naturals. If we just look at repeated power sets, we get as many levels of infinity as there are natural numbers.
But is that all of them?
No. There are infinities so big that no matter how many times I apply the power set operation, I'll never reach them. Here's an example. What if we take the set of naturals, and then the power set of that, and combine them into one big set. And then, we throw in everything in the power set of the power set of the naturals. And then, throw in everything in the power set of that. And keep going, forever. So, in other words, we get the set of all things which show up anywhere in any of the repeated power sets starting with the naturals. Since this set contains all those power sets as subsets, it must be bigger than all of them. It's one mind-bendingly, insanity-destroyingly huge set! (But, it'll turn out it's still "tiny" in the world of mathematical logic)
Ok, but I'm beating around the bush. The question is, how many infinities are there? The answer is unsettling. It turns out, there are so many levels of infinity, that no level of infinity is enough to answer the question. No matter how hard anyone tries, to come up with some incomprehendably large level of infinity, there are more levels of infinity than that.
LARGE CARDINALS
Congratulations, if you've read this far, you know just about as much about building really-big-freaking-infinities as the average mathematician. Now strap yourself in, I'm gonna talk about how to go to a whole new level, making the infinities we've talked about so far look like tiny insects. This is actually cutting-edge stuff I'm sharing with you, and is mostly only known by people who actually specialize in mathematical logic.
Logicians use the term "LARGE CARDINAL" to refer to some levels of infinity so big that they literally transcend math. These levels of infinity are so awesomely, divinely, insanely huge, the term LARGE CARDINAL must always be written in all capitals, because a LARGE CARDINAL is that freakin' ginormous.
In order to get an idea what a LARGE CARDINAL is, you have to understand a little of the very foundations of modern mathematics. You already know there is no absolute truth and no absolute provable theorem, because all proofs must ultimately call upon some unprovable assumptions. Usually those assumptions are so "obvious" that noone would ever question them, but nevertheless they can't be proven (and if they could somehow be proven, it would only be by relying on even more unprovable assumptions). It's kind of how a dictionary can't really define every word, without eventually falling into circular definitions (try defining the word "the", using only words which can be defined without using "the").
In modern mathematics, the "unprovable assumptions" have been very neatly organized into a system called ZFC. Basically, mathematicians know deep down that their proofs have holes in them, that math would fail if ZFC fails. But that's okay, because if ZFC fails, then unicorns are real and dreams come true and everyone has a million dollars.
One of the things about ZFC, proved by Godel in his famous "Incompleteness Theorem", is that you can't prove ZFC using ZFC. It is possible to prove ZFC, if you make other assumptions above and beyond ZFC. But then, your proof is in some extended system, and you can't prove that system, unless you make even more assumptions, and so on.
ZFC is really a "statement about the existence of a universe". It doesn't say outright that "math is true", so much as it says, "there exists a universe in which math is true". Then we prove theorems about such a universe. Presumably, math is true in the real universe, so these theorems become true in the real universe. But if ZFC fails, it really means there's no universe where math is true, and all the theorems proved from ZFC are vacuous.
One thing about universes, is that you can have universes within universes. For example, going philosophical for a moment, suppose the Real Life universe is made up of two parts, a "close" part which humans can navigate, see, or in some way detect. And a "far" part which humans can never reach, see, or even detect. Then if we looked at the "close" part of the universe, even though it would not be all of the "Real Universe", it would be a universe by itself. There'd be no way for us to tell that the "close universe" wasn't the entire universe.
The "close universe" in my example is closed and consistent because the non-close part of the Real universe is undetectable, and so if humans assumed the "close universe" was the entire universe, they'd never reach any contradiction. (If they could reach a contradiction, they'd have detected the far universe, but by definition the far universe is undetectable)
Now, suppose we assume that there's a universe which contains certain sets of objects, and that these sets satisfy ZFC. Ok, so far we just have vanilla math. But let's also assume that among those sets, there's a set which, by itself, satisfies ZFC. In otherwords, the elements of this set are themselves sets, and ZFC holds among them if we pretend they're all the sets in the universe. Then we've gone beyond ZFC itself into an extended system, and this extended system proves ZFC, because the set in which ZFC holds can be taken as a "close universe" where ZFC is true.
In this extended assumption system, the set where ZFC is true is a LARGE CARDINAL. It's a set so big that people "living inside it" and following normal rules of math can't detect that there's anything else in the universe.
What's more, normal math (ie, math in ZFC) cannot itself prove that the LARGE CARDINAL exists. Because, if ZFC proved the LARGE CARDINAL exists, then ZFC would prove ZFC, since ZFC is true inside the LARGE CARDINAL. And ZFC can't prove itself.
All the levels of infinity which we can possibly conceive using normal math, must exist within the LARGE CARDINAL, because ZFC-- and thus, all of "normal math"-- exists within the LARGE CARDINAL. Consequently, the LARGE CARDINAL is bigger than any level of infinity that we can construct using modern mathematics.
(And yet, I just constructed it! Isn't that a contradiction? No, because the construction steps outside conventional mathematics by assuming things outside ZFC)
Let's give a name to this new system, the system where we assumed ZFC together with the existence of a set where ZFC is true. Let's call it ZFC+. Then we can repeat the process: assume there exists some universe, with certain sets of objects, and that ZFC+ holds in this universe, and assume further that among those sets, there's a set which, by itself, satisfies ZFC+. Then that set is another LARGE CARDINAL, and this time, it's so big that it can't even be constructed with all the supernatural powers of ZFC+. It can only be constructed in the even more ridiculous system, ZFC++ if you will.
This process can be continued on and on. By going to new systems of math, we can build levels of infinity which transcend the old systems of math, and then we can repeat the process, as often as you like.
These LARGE CARDINALS I've talked about are just one type of large cardinal. The general process is: take ZFC (normal modern math) and extend it with some new assumption, strong enough to prove ZFC. Since ZFC is really a statement of the form "a universe exists in which math is true", and since the enhanced system proves ZFC, the enhanced system must prove that a universe exists where ZFC-math is true. But ZFC-math isn't provable in ZFC-math, so that universe where ZFC-math is true, must be larger than anything that can be built in the un-enhanced system of ZFC.
IS THERE ANYTHING BIGGER THAN LARGE CARDINALS?
Yes, it's possible to go even bigger than LARGE CARDINALS! All throughout the article so far, I keep talking about "sets". So far, I've just been doing "naive set theory", treating sets intuitively as "collections of objects", but this naive treatment actually leads to certain paradoxes.
The most prototypical example of a paradox of naive set theory, goes like this. Let X be the set of all sets which don't contain themselves. That is, if you look at any set, it lies in X if and only if it does not lie in itself. The question is, is X an element of itself? If X is an element of itself, then by definition, it's NOT an element of itself. Ridiculous. But if X is not an element of itself, then by definition, it IS an element of itself. If we assume X is in itself, we get that X is not in itself, and if we assume X is not in itself, we get that it IS in itself. ARRGH, brain explode!
That paradox is known as "Russel's Paradox". It basically says we have to be more careful with what "sets" are allowed to exist. The system of ZFC I discussed above is basically a code of laws specifying which sets actually exist. Under ZFC, it's impossible to construct "the set of all sets which don't contain themselves", so the paradox is avoided.
In real world applications, noone really cares about "the set of all sets that don't contain themselves", so we're not missing out on much by not having it. However, there are some useful "collections" which it's nice to talk about, which are also un-constructable using ZFC. The most obvious example is, the set of all sets. Since mathematicians and logicians spend so much time talking about sets, it would certainly be nice to talk about the set of all sets, just to organize our work. And, unfortunately, you can't build the set of all sets using ZFC. (In fact, you can show that if you could build the set of all sets, then you could build the set of all sets which don't contain themselves, and then you'd get Russel's paradox)
Mathematicians get around this in a kind of cheating way, by introducing "classes". What's a class? It's a collection of objects. How is that different than a set? Well, the only difference is that a set is restricted by ZFC. A class is also restricted by different assumptions, but the restrictions are less stringent, so that it's possible to talk about the class of all sets.
Classes are just a linguistic trick to let us talk about "the set of all sets" (in essence), without invoking paradoxes. If we had a set of all sets, we could use ZFC assumptions to reach a paradoxical contradiction. But ZFC assumptions don't say anything about classes-- they can't "touch" classes, and so even though we have the class of all sets, we can't pull a paradox from it.
So what's the size of the class of all sets? It must be infinite, since there are infinitely many sets. If the class of all sets had the same size as any particular set, then that would give us a foothold to "touch" the class with ZFC assumptions, and we could get a paradox. The class of all sets is bigger than any particular set, it's even bigger than a LARGE CARDINAL.
Whereas the LARGE CARDINALS are awesome and stupefying in their size, the "proper classes", such as the class of all sets, are bigger but somehow they feel like cheating, like we got them through some linguistic tricks. To a realist mathematician who believes that math "exists" somewhere out there, the LARGE CARDINALS are actual "existent" entities, whereas the proper classes are just linguistic formality. In some sense, they only "exist" because of Russel's Paradox, and some mathematicians don't like to think about Russel's Paradox, since it's the closest we've ever been to the Death of Math. Nevertheless, proper classes are an example of something even bigger than LARGE CARDINALS.
CONCLUSION
Next time you're in a contest to name the biggest infinity, after your enemy says "infinity times infinity plus a million", you can say "smallest LARGE CARDINAL", or "size of the class of all sets". Of course, they can just counter by saying, "power set of what you said!"...
Here are some other things I wrote. Soon, glowingfaceman.com will contain infinity+1 articles!
Ergative Verbs
Introduction To Toastmasters
The Evolution Of Handwriting / Penmanship / Shorthand
Researching English On Books.google.com
A few quarters back, standing outside an auditorium before giving a calculus final exam, some of my students asked what I was reading. It was "The Higher Infinite", a very advanced tome of mathematics by Akihiro Kanamori. My students were understandably pretty interested to hear about the idea of more than one kinds of infinity. In fact, there are infinitely many levels of infinity. And that's even pretty well-known, at least among people who read about math. What Kanamori writes about, in rather difficult mathematical language (the book is meant for advanced graduate students or math PhDs), are some lesser-known infinities, which are so big that they literally bend the basic facts of mathematics. It's some pretty trippy stuff.
WHAT IS INFINITY?
In formal set theory, there is no single entity called "infinity". In mathematics, when we say that the answer to some question is "infinity", we really mean that any finite answer would be too small. The "entity" of infinity is just a kind of shorthand for expressing this idea. But there are infinite sets-- that is, collections which are infinite. When we talk about multiple "levels of infinity", we're really talking about collections of different, infinite, sizes.
Here's an example. Take the collection of all natural numbers (the natural numbers are the numbers 0, 1, 2, 3, 4, and so on; the numbers you use to count). How big is this collection? Any finite answer, is too small. For example, if we guess that the collection of natural numbers has size one million, then that's too small because there are more than a million counting numbers. Since any finite answer is too small, we say the collection is infinite.
What about the set of all real numbers, with any number of decimal places, including infinitely many non-repeating decimal places, like in the number pi=3.1415...? If we look at this "continuum" of real numbers, again it's infinite, because any finite size would be too small. It turns out, that the set of all real numbers, is actually larger than the set of all counting numbers. And that's the prototypical example to show that there are more than one sizes of infinity. But, what does it mean to say that one infinite collection is larger than another?
To understand how the sizes of infinite collections can be compared, it's first necessary to understand how the sizes of finite collections are compared. One way to compare the sizes of finite collections, is to just count them and compare the numbers. But that doesn't generalize to infinite collections, because we can't count an infinite collection-- if we could, it would not be infinite.
A better way-- or at least, a more generalizable way-- to compare the sizes of finite collections, is to check whether we can marry their elements up together in a nice one-to-one way. If two finite collections have the same size, then we can think of one collection as being the collection of "males", think of the other as being the collection of "females", and marry them up so everyone has exactly one partner. If the collections had different sizes, we couldn't do this, someone would be left out.
This "marriage" idea is referred to in mathematics as a "bijection". A bijection is just a fancy, smart-sounding way of saying, you assign each member of the first collection to a unique member of the other, so that nothing is left out and nothing is matched up twice. If two collections have a bijection between them, then they have the same size, and if not, then they have different sizes.
You can think of counting small (smaller than size eleven) sets as establishing a bijection between the set and between a certain subset of your fingers. You count "one, two, three, four," holding up a finger with each utterance, and you're implicitly "marrying" a certain set of your fingers to elements of the set you're counting.
The bijection idea naturally generalizes to infinite sets with no extra work. Two sets, whether they be finite or infinite, are said to have the same size if there's some way to link their elements together bijectively, so that each element of the first gets associated with exactly one element of the second.
Right away, some trippy examples come up. For example, the set of all even counting numbers (0,2,4,6,8,...) has the same size as the set of all counting numbers. That's because if you take any even counting number and divide it in half, you get a counting number, and the result is unique and no other even number gives the same result. The act of dividing in half, is a bijection from the set of even counting numbers, to the set of all counting numbers.
THERE ARE MORE THAN ONE SIZES OF INFINITY
The famous example which first shows that there are more than one sizes of infinity, is the fact that there are more real numbers than there are counting numbers. A real number being, any number, positive or negative, with any number of decimal places. Including numbers like pi or the square root of two, where there are infinitely many non-repeating decimal places.
The fact that there are more real numbers than counting numbers was a big surprise to mathematicians; after all, both sets have infinitely many elements, so a mathematician back in the old times might have said both sets have size infinity.
Saying that there are more reals than naturals comes down to saying that there aren't enough naturals to associate with the reals; if we try to marry each real number to a unique natural number, with no naturals getting married twice, then there won't be enough natural numbers to go around and some (in fact, most) of the reals will be left out. In other words, there is no bijection from the naturals to the reals. Since the naturals are a subset of the reals, that is, every natural is a real, there are at least as many real numbers as there are natural numbers; so if there's no bijection between them, then the set of real numbers must be strictly bigger.
Georg Cantor, the mathematician who discovered a lot of this stuff about different infinities, published a famous proof that there's no bijection between the naturals and the real numbers. You can read his proof, the famous "diagonal argument", at Wikipedia. I'll give a different proof, one which is in my opinion more acid-trippy and fun. Anyway the diagonal argument has been beaten into the ground by a million other people so it's better to give a less well-known proof anyway.
My proof uses a certain infinite sum which is related to one of the Zeno's paradoxes, if you've ever read about those. Basically, in order to walk across a distance of size 1 meter, first you have to walk one half meter. Then, you have to walk one fourth meter. Then, you have to walk one eighth meter, then one sixteenth meter, and so on. Adding up all those partial walks, each one half as long as the previous, you get the total distance of one meter. This gives the infinite sum, 1/2+1/4+1/8+...=1. What does this have to do with proving there are more reals than naturals? Hold onto your hat...
Suppose that there was a bijection from the naturals to the reals. Then we could "count" the reals, saying, this real number is the first real; this real number is the second real; this real number is the third real; and so on. Using the association from the counting numbers, to the reals. And it would hit every real number, since, according to the assumption, each real number has a natural number associated with it.
Now I'm gonna show a way that you can cover the entire real number line, with a covering of length 1. That's ridiculous, because the real number line is infinitely long. There's no way to cover it with just a covering of length one. For instance the real line contains the interval from -1 to 1, which has length 2 just by itself.
Well, take the "first" real number (i.e., the number which is associated to the counting number 0). Cover it with a cover of length 1/2. Next, take the "second" real number, and cover it with a cover of length 1/4. Take the "third" real number, and cover it with a cover of length 1/8, then cover the "fourth" real number with a cover of length 1/16, and so on. Even if none of these covers overlapped, the total area of the cover would be at most 1/2+1/4+1/8+...=1. In fact, the covers overlap a lot, so the total area of these covers ends up being less than 1. But every real number is the nth real number for some n; that's the assumption we made, that we had a bijection between counting numbers and reals. So, every real number gets covered. I've covered the whole real line, with a covering scheme where the covers have a total length no longer than 1. Impossible, that's not even enough to cover just the part of the real line from -1 to 1.
I started out assuming there was a bijection from the naturals to the reals. Then, I showed that the assumption allows me to do something ridiculous. So the assumption must be wrong, and there is no bijection between the naturals and the reals. They have different sizes, and the reals contain the naturals, so there are more reals than naturals.
(Actually the proof is missing a little detail, since I'm assuming some common sense notions about how lengths work. The details are filled in in an advanced branch of math called "measure theory", but I figured it'd be worth the reduced details to post this alternate proof that there's no bijection.)
THERE ARE INFINITELY MANY LEVELS OF INFINITY
I just established there are more than one levels of infinity, by showing that the set of real numbers is bigger than the set of natural numbers. But the infinitudes get much, much bigger, and there are far more sizes of infinity than just the size of the set of naturals and the size of the set of reals.
If you take any collection of objects, it makes sense to talk about subsets of that collection. Like, the set of even numbers is a subset of the set of all numbers. Well, once you have the notion of subsets, you can ask about the collection of all subsets of a set. For example, you can ask about the set of all subsets of the natural numbers. This set-of-all-subsets is called the power set. The power set of the natural numbers is the set of all sets of natural numbers.
Here's the big breakthrough which leads to infinitely many levels of infinity. It's a fundamental truth discovered by Georg Cantor, and it totally turned mathematics on its head. Cantor showed: if you have any set whatsoever-- empty, finite, or any level of infinite-- then the power set is even bigger.
For example, the power set of the natural numbers-- the set of all sets of natural numbers-- is bigger than the set of natural numbers. So that gives another proof that there are more than one levels of infinity. (Incidentally, which set is bigger, the power set of the natural numbers, or the set of real numbers? Or are they the same size? It turns out this question is unanswerable. Read more at Continuum Hypothesis)
To get infinitely many levels of infinity, you can just repeat the process. You can take the power set of the power set of the set of naturals, and get something even bigger. And then you can take the power set of that. The process never ends, and it provides infinitely many levels of infinity.
SO HOW MANY LEVELS OF INFINITY ARE THERE?
I've shown you how there are infinitely many different levels of infinity, and a natural question which you might ask is, what is the size of the set of all levels of infinity? So far, I've showed how to get infinitely many different levels of infinity, but the infinities we can create using just power set, can be placed into a natural association with the natural numbers. I can say that the 0th infinity corresponds to the number of natural numbers. And then I can say the 1st infinity is the power set of the 0th. And the 2nd is the power set of the 1st, and so on. This hits all the infinities we get with just repeated power setting of the naturals. If we just look at repeated power sets, we get as many levels of infinity as there are natural numbers.
But is that all of them?
No. There are infinities so big that no matter how many times I apply the power set operation, I'll never reach them. Here's an example. What if we take the set of naturals, and then the power set of that, and combine them into one big set. And then, we throw in everything in the power set of the power set of the naturals. And then, throw in everything in the power set of that. And keep going, forever. So, in other words, we get the set of all things which show up anywhere in any of the repeated power sets starting with the naturals. Since this set contains all those power sets as subsets, it must be bigger than all of them. It's one mind-bendingly, insanity-destroyingly huge set! (But, it'll turn out it's still "tiny" in the world of mathematical logic)
Ok, but I'm beating around the bush. The question is, how many infinities are there? The answer is unsettling. It turns out, there are so many levels of infinity, that no level of infinity is enough to answer the question. No matter how hard anyone tries, to come up with some incomprehendably large level of infinity, there are more levels of infinity than that.
LARGE CARDINALS
Congratulations, if you've read this far, you know just about as much about building really-big-freaking-infinities as the average mathematician. Now strap yourself in, I'm gonna talk about how to go to a whole new level, making the infinities we've talked about so far look like tiny insects. This is actually cutting-edge stuff I'm sharing with you, and is mostly only known by people who actually specialize in mathematical logic.
Logicians use the term "LARGE CARDINAL" to refer to some levels of infinity so big that they literally transcend math. These levels of infinity are so awesomely, divinely, insanely huge, the term LARGE CARDINAL must always be written in all capitals, because a LARGE CARDINAL is that freakin' ginormous.
In order to get an idea what a LARGE CARDINAL is, you have to understand a little of the very foundations of modern mathematics. You already know there is no absolute truth and no absolute provable theorem, because all proofs must ultimately call upon some unprovable assumptions. Usually those assumptions are so "obvious" that noone would ever question them, but nevertheless they can't be proven (and if they could somehow be proven, it would only be by relying on even more unprovable assumptions). It's kind of how a dictionary can't really define every word, without eventually falling into circular definitions (try defining the word "the", using only words which can be defined without using "the").
In modern mathematics, the "unprovable assumptions" have been very neatly organized into a system called ZFC. Basically, mathematicians know deep down that their proofs have holes in them, that math would fail if ZFC fails. But that's okay, because if ZFC fails, then unicorns are real and dreams come true and everyone has a million dollars.
One of the things about ZFC, proved by Godel in his famous "Incompleteness Theorem", is that you can't prove ZFC using ZFC. It is possible to prove ZFC, if you make other assumptions above and beyond ZFC. But then, your proof is in some extended system, and you can't prove that system, unless you make even more assumptions, and so on.
ZFC is really a "statement about the existence of a universe". It doesn't say outright that "math is true", so much as it says, "there exists a universe in which math is true". Then we prove theorems about such a universe. Presumably, math is true in the real universe, so these theorems become true in the real universe. But if ZFC fails, it really means there's no universe where math is true, and all the theorems proved from ZFC are vacuous.
One thing about universes, is that you can have universes within universes. For example, going philosophical for a moment, suppose the Real Life universe is made up of two parts, a "close" part which humans can navigate, see, or in some way detect. And a "far" part which humans can never reach, see, or even detect. Then if we looked at the "close" part of the universe, even though it would not be all of the "Real Universe", it would be a universe by itself. There'd be no way for us to tell that the "close universe" wasn't the entire universe.
The "close universe" in my example is closed and consistent because the non-close part of the Real universe is undetectable, and so if humans assumed the "close universe" was the entire universe, they'd never reach any contradiction. (If they could reach a contradiction, they'd have detected the far universe, but by definition the far universe is undetectable)
Now, suppose we assume that there's a universe which contains certain sets of objects, and that these sets satisfy ZFC. Ok, so far we just have vanilla math. But let's also assume that among those sets, there's a set which, by itself, satisfies ZFC. In otherwords, the elements of this set are themselves sets, and ZFC holds among them if we pretend they're all the sets in the universe. Then we've gone beyond ZFC itself into an extended system, and this extended system proves ZFC, because the set in which ZFC holds can be taken as a "close universe" where ZFC is true.
In this extended assumption system, the set where ZFC is true is a LARGE CARDINAL. It's a set so big that people "living inside it" and following normal rules of math can't detect that there's anything else in the universe.
What's more, normal math (ie, math in ZFC) cannot itself prove that the LARGE CARDINAL exists. Because, if ZFC proved the LARGE CARDINAL exists, then ZFC would prove ZFC, since ZFC is true inside the LARGE CARDINAL. And ZFC can't prove itself.
All the levels of infinity which we can possibly conceive using normal math, must exist within the LARGE CARDINAL, because ZFC-- and thus, all of "normal math"-- exists within the LARGE CARDINAL. Consequently, the LARGE CARDINAL is bigger than any level of infinity that we can construct using modern mathematics.
(And yet, I just constructed it! Isn't that a contradiction? No, because the construction steps outside conventional mathematics by assuming things outside ZFC)
Let's give a name to this new system, the system where we assumed ZFC together with the existence of a set where ZFC is true. Let's call it ZFC+. Then we can repeat the process: assume there exists some universe, with certain sets of objects, and that ZFC+ holds in this universe, and assume further that among those sets, there's a set which, by itself, satisfies ZFC+. Then that set is another LARGE CARDINAL, and this time, it's so big that it can't even be constructed with all the supernatural powers of ZFC+. It can only be constructed in the even more ridiculous system, ZFC++ if you will.
This process can be continued on and on. By going to new systems of math, we can build levels of infinity which transcend the old systems of math, and then we can repeat the process, as often as you like.
These LARGE CARDINALS I've talked about are just one type of large cardinal. The general process is: take ZFC (normal modern math) and extend it with some new assumption, strong enough to prove ZFC. Since ZFC is really a statement of the form "a universe exists in which math is true", and since the enhanced system proves ZFC, the enhanced system must prove that a universe exists where ZFC-math is true. But ZFC-math isn't provable in ZFC-math, so that universe where ZFC-math is true, must be larger than anything that can be built in the un-enhanced system of ZFC.
IS THERE ANYTHING BIGGER THAN LARGE CARDINALS?
Yes, it's possible to go even bigger than LARGE CARDINALS! All throughout the article so far, I keep talking about "sets". So far, I've just been doing "naive set theory", treating sets intuitively as "collections of objects", but this naive treatment actually leads to certain paradoxes.
The most prototypical example of a paradox of naive set theory, goes like this. Let X be the set of all sets which don't contain themselves. That is, if you look at any set, it lies in X if and only if it does not lie in itself. The question is, is X an element of itself? If X is an element of itself, then by definition, it's NOT an element of itself. Ridiculous. But if X is not an element of itself, then by definition, it IS an element of itself. If we assume X is in itself, we get that X is not in itself, and if we assume X is not in itself, we get that it IS in itself. ARRGH, brain explode!
That paradox is known as "Russel's Paradox". It basically says we have to be more careful with what "sets" are allowed to exist. The system of ZFC I discussed above is basically a code of laws specifying which sets actually exist. Under ZFC, it's impossible to construct "the set of all sets which don't contain themselves", so the paradox is avoided.
In real world applications, noone really cares about "the set of all sets that don't contain themselves", so we're not missing out on much by not having it. However, there are some useful "collections" which it's nice to talk about, which are also un-constructable using ZFC. The most obvious example is, the set of all sets. Since mathematicians and logicians spend so much time talking about sets, it would certainly be nice to talk about the set of all sets, just to organize our work. And, unfortunately, you can't build the set of all sets using ZFC. (In fact, you can show that if you could build the set of all sets, then you could build the set of all sets which don't contain themselves, and then you'd get Russel's paradox)
Mathematicians get around this in a kind of cheating way, by introducing "classes". What's a class? It's a collection of objects. How is that different than a set? Well, the only difference is that a set is restricted by ZFC. A class is also restricted by different assumptions, but the restrictions are less stringent, so that it's possible to talk about the class of all sets.
Classes are just a linguistic trick to let us talk about "the set of all sets" (in essence), without invoking paradoxes. If we had a set of all sets, we could use ZFC assumptions to reach a paradoxical contradiction. But ZFC assumptions don't say anything about classes-- they can't "touch" classes, and so even though we have the class of all sets, we can't pull a paradox from it.
So what's the size of the class of all sets? It must be infinite, since there are infinitely many sets. If the class of all sets had the same size as any particular set, then that would give us a foothold to "touch" the class with ZFC assumptions, and we could get a paradox. The class of all sets is bigger than any particular set, it's even bigger than a LARGE CARDINAL.
Whereas the LARGE CARDINALS are awesome and stupefying in their size, the "proper classes", such as the class of all sets, are bigger but somehow they feel like cheating, like we got them through some linguistic tricks. To a realist mathematician who believes that math "exists" somewhere out there, the LARGE CARDINALS are actual "existent" entities, whereas the proper classes are just linguistic formality. In some sense, they only "exist" because of Russel's Paradox, and some mathematicians don't like to think about Russel's Paradox, since it's the closest we've ever been to the Death of Math. Nevertheless, proper classes are an example of something even bigger than LARGE CARDINALS.
CONCLUSION
Next time you're in a contest to name the biggest infinity, after your enemy says "infinity times infinity plus a million", you can say "smallest LARGE CARDINAL", or "size of the class of all sets". Of course, they can just counter by saying, "power set of what you said!"...
Here are some other things I wrote. Soon, glowingfaceman.com will contain infinity+1 articles!
Ergative Verbs
Introduction To Toastmasters
The Evolution Of Handwriting / Penmanship / Shorthand
Researching English On Books.google.com
Posts
4 comments:
it makes me happy that you're a teacher. this article is great.
Does an infinity of things that are not numbers really stand to be counted and sized along with infinities that are?
It seems like the very largest, most mindboggling varieties of infinities there are really just semantic gamesmanship rather than concept with real mathematical merit. I mean, it's kind of interesting to think about it, but it really does sound like kids saying "infinity + 1!"
(Incidentally, which set is bigger, the power set of the natural numbers, or the set of real numbers? Or are they the same size? It turns out this question is unanswerable. Read more at Continuum Hypothesis)
They are the same size. The Continuum Hypothesis states instead that their cardinality is the second smallest infinite cardinaly (i.e., there is no cardinality between that of the naturals and that of the continuum).
The Generalized Continuum Hypothesis states that if X is infinite, then P(X) has the next bigger cardinality. (This is clearly not true in the finite case).
I stumbled on your article by something not directly related.
I noticed several words that do not apply properly to the concept of infinite, such as "big" or "size", or the fact that there are more sizes to infitity. This is probably related to the concept of cardinality, but not when it comes to infinity. To speak of "size" or "big" one needs a limit, a boundary. Infinity, by definition has neither, and thus although thinking of infinity as an ever growing concept is somewhat common, it is not the right way to think about it. In order to grow, you cannot be infinite.
Post a Comment