How is it possible that some infinities can be bigger than others? Seems like it contradicts the concept of infinity! Or something.
If it helps, try not to think of infinity as meaning “everything.” What it really means is “if you tried to count it, it would take forever.”
So, take the set of even positive integers, E: { 2, 4, 6, 8 … } Obviously, it’s infinite. If we tried to count them, it would take forever. It’s also a subset of the set of all positive integers, P, and there are positive integers which aren’t even. Therefore, P must have more items in it than E, even though we already know that E is infinitely big. Wacky.
For the purposes of basic algebra and calculus, this doesn’t matter. Infinity can be treated as just a really big limit. It starts to matter when you study set theory and other topics, and learn about aleph numbers and such. That stuff is beyond me, though.
First, realize that your common sense notions of one thing being “bigger” than another don’t really apply to infinities. Your common sense is based on your experiences with finite sets, so you’re going to have rules and concepts that don’t really apply when you talk about infinite sets.
It’s kind of like how your common sense ideas of physics don’t always apply in circumstances you don’t have experience with, like a vacuum. It makes perfect sense to say that a heavier object will fall faster than a lighter one in air, because that’s generally what does happen in your everyday experiences (all of which include air, at least for most people). That doesn’t mean that that’s what will happen in a different set of circumstances (like in a vacuum).
Except P doesn’t have more items in it than E.
When you’re comparing infinite sets, the question to ask isn’t “are all the items in E also in P, and are there also items in P that are not in E?” The right question to ask is “can you come up with a one-to-one function that maps all members of E onto members of P?”
What you’re trying to do is find some way to match each member of E to each member of P. It’s just like matching socks after doing laundry, really (assuming each pair of socks that you have is different from every other pair)- each left sock matches to only one right sock, and each right sock matches to only one left sock.
We do this by trying to come up with an equation that says how to match items from E to items from P. With the sets E (even integers) and P (all integers), the equation y = 2x will work, where x is a member of P and y is a member of E. For every x in P, that equation gives you exactly one y which is a member of E. For every y in E, that equation matches it to exactly one x which is a member of P. Every even integer is 2 times some integer, in other words. You could make a list that shows how they match up:
- 2
- 4
- 6
- 8
and so on. Every member of P will have a corresponding member of E, and every member of E will appear somewhere in this list.
From the sock example, though, that must mean that the sets are the same size- if you can match one right sock to every left sock, that means you must have the same number of left and right socks. So E and P are the same size, even though there are items in P that aren’t in E. Yes, it’s freaky, but that’s infinite sets for you.
Using a different equation, you can also match up the set of all positive integers plus zero (all non-negative integers) to the set of all positive integers (the equation here is y = x + 1). (Yes, a set that your common sense tells you has one more member than another set is the same size.) You can also match up the set of all positive and negative integers to the set of all positive integers. Any set that you can match up to the set of positive integers this way is said to have a size of aleph-null.
There are infinite sets that don’t have a size of aleph-null. The set of all real numbers is one of them. There’s a rather clever proof of that that Georg Cantor came up with:
Suppose you did have a one-to-one equation that connected the integers and the real numbers. For simplicity’s sake, let’s say you had a one-to-one equation that mapped the integers to the real numbers between 0 and 10 (that has to be the same size as the set of all real numbers or smaller). If you did, you could make a list of the real numbers. It might look something like this:
- 0.00000…
- 3.14159…
- 2.71725…
- 0.77777…
- 1.29975…
and so on. But I can prove that there is at least one real number that isn’t anywhere in your list. For each number in your list, this number is 1 bigger than the number in your list in the decimal place corresponding to its place in the list. For the list I’ve got there, the number would be 1.2288… The first digit is one different from the zero in the first position of real number #1, the second is one different from the one in the first decimal place of #2, the third is one different from the one in the second decimal place of #3, and so on.
If you try to say, “But that number is in the list, it’s #137 in the list”, I can say, “No, it isn’t- it’s one different from #137 in the list in the 136th decimal place.” That proves that you can’t match the set of all real numbers to the set of integers the way you could match the set of integers to the set of even integers. You’ve got at least one right sock (real number) that doesn’t match up with any left sock (integer), so you must have more right socks than left socks. There are more real numbers than there are integers.
There’s a name for the size of the set of all real numbers- it’s called aleph-one. It’s also sometimes called the continuum. The question of whether there is any “aleph-one-half”, or is there any infinite set that is bigger than the set of integers and smaller than the set of real numbers, is an unsolved problem in modern mathematics. Nobody knows, in other words. Cantor suspected that there isn’t, but he couldn’t prove it, and nobody since him (he died in 1918) has been able to prove or disprove it.
It may or may not help if you think of a lace doily that’s two inches wide, but whose length is infinite. Put the doily on top of a 2x4 with infinite length, and you can see 2x4 through the gaps in the doily, even though both go on forever. However if you put the 2x4 on top, you can’t see the doily at all. Therefore the 2x4 represents a larger infinity.
Now imagine a 2 x infinity plane. Put the doily and the 2x4 on top of it. You can see plane sticking out from under both the doily and the 2x4. But if the plane was on top, you couldn’t see either. The plane is therefore a larger infinity than either the 2x4 or the doily.
I see the doily as representing sequences and the plank and plane as representing continua, but that may be because of a weakness in my math. Feel free to slam, debunk, or correct the doily/plank explanation in any way it needs to be slammed, debunked, or corrected.
But the presence of gaps doesn’t correlate to one infinity being greater than the other. Anne Neville showed this: she matched one sparse set if integers with the full set of integers. Even though the doily (the even integers) allows the full set of integers to peek through, they can be matched one to one since the set never ends.
I have heard of a similar trick used to match points on a line with points on a plane: you can express the point in the plane as an X,Y pair of real numbers. Then all you need to do is make a new single real number by using the digits of X for the odd digits and the digits of Y for the even digits.
1.234
5.678
maps to
15.263748
Now that’s where my memory of this ends. I vaguely recall that the integers and the real numbers are different forms of infinity, as Anne pointed out, but that points on a line (the real numbers) vs. points on a plane are the same, using the trick above.
I recall a mention that the number of different curves in a plane is a higher kind of infinity than the real numbers, but I can’t quite get my head around that statement, so I never went any further.
I read your question a little differently than Anne Neville (whose post was quite informative):
Basically, math only incidentally has any kind of relationship to “reality”. You make up some definitions, some assumptions, some rules of inference and then you play the game and see where it all gets you – that’s math. Of course it would be a complete waste of time if it wasn’t useful, so mathemeticians try to start out with definitions and assumptions that correspond in some ways to what we know is true already.
Long story short: “Bigger” in this instance means “can’t be put into one-to-one correspondence with”; that’s all it means. It is useful because in real life one-to-one correspondence is often how we tell which member of a set is bigger. When I’m at the roulette table for instance, I have one stack of twenty chips that I measure all my other stacks of chips against in just this way.
I kind of disagree with the notion that our “common sense” just can’t handle infinities; it’s that the definitions involved mean different things than they do in the context of finite numbers simply because that’s the only way they’ll make any sense at all.
You have to make some adjustments to your common sense ideas to deal with a situation (like infinite sets) that you don’t have experience with. Common sense says that, if you can match sets A and B in a one-to-one correspondence, that means that A can’t contain everything in B plus some additional things- you’d match up the members of A and B that are the same, and have the additional members of A left over, and there’d be no way to match them all up one-to-one. That common-sense logic works for finite sets, but not for infinite ones. You could call it a change in the definition of “bigger” for infinite sets, or that infinite sets don’t work the way that common sense tells you sets work. It’s two ways of looking at the same thing.
You have your notation wrong. Aleph-One is the cardinality of the set of all countable ordinal numbers. Cantor’s Continuum Hypothesis says that the cardinality of the set of all real numbers(let’s call it c) is equal to Aleph-One(well, it does with the Axiom of Choice), but that has not been proven.
Both the integers and the even integers would be doilies. You can manipulate any one doily to cover any other doily. To be a 2x4, a continuum is required.
I think you meant Aleph-Null there.
Good post, but there are a couple errors in this paragraph. As mentioned, the cardinality of the naturals is aleph[sub]0[/sub]. The cardinality of the reals is 2[sup]aleph[sub]0[/sub][/sup]. The equality of 2[sup]aleph[sub]0[/sub][/sup] and aleph[sub]1[/sub] is independent of the standard axiomatization of mathematics. Wikipedia has a pretty good article discussing this and its generalization.
No. Aleph Null is the cardinality of the set of integers.
Thanks All. You’ve given me plenty to think about. Please keep up the discussion.
It’s a bit misleading to say that this is an unsolved problem. The question has been completely resolved: We know for an absolute fact that it cannot be answered. For the continuum hypothesis to be false is exactly as consistent as for it to be true.
This is Cantor’s famous ‘diagonal shift’ proof of infinities distinct from aleph null. However, it’s flawed.
(1) It is based on being able to create, construct or write a list of the real numbers. However, if we accept the concept of infinity, you can’t do this. There is no way to create such a list. Note that you have done what Cantor and every other writer has done. You have given a few lines of this supposed list and then added ‘and so on’. You have also used an ellipsis at the right-hand end of every line to indicate ‘and so on’. However, ‘and so on’ is only meaningful if the omitted sections could be constructed, written or depicted, but are omitted for reasons of simplicity or saving time. This is not the case here. There is no way to create this list. You can define what items would be on the list, but that’s not the same as actually listing them. The former is possible, the latter is not. It’s a subtle distinction, but an important one.
Writing a few lines of this supposed list and then adding ‘and so on’ is a kind of mathematical three card trick. It gets past the critical thinking gate for most readers, but it is flawed. This list could never be written, constructed or depicted. If you doubt me, then I challenge you to do a simple thing that can be done with any list: reverse the order of its constituent elements. Tell me what number is now at the top. You can’t. This should give us a clue that to refer to this ‘list’ is actually meaningless.
(2) You cannot draw a diagonal line through the numbers in this list. Not only is it impossible for anyone to create this list, you cannot produce, draw or define a ‘diagonal’ line which passes through the nth digit of the nth member of the list (as Cantor suggested). If you don’t appreciate this, ask yourself where the other end of the diagonal line is. We know it starts at what would be graph co-ordinates 0,0. But where is the other end? Give me the co-ordinates, and I will accept it can be drawn. But it can’t. So the idea of a ‘diagonal shift’ is also flawed.
‘Diagonal’ as a concept is only meaningful if we can define end points. It is easy to define the ‘diagonal’ of a square or a chess board. But the ‘list of numbers’ you have presented cannot have a ‘diagonal’ because there is no way to define what this ‘diagonal’ would be or consist of. It only has one co-ordinate. If you feel tempted to reply that the other end lies at a co-ordinate defined by infinity along the x axis and infinity along the y axis, then tell me its co-ordinates when rotated 90 degrees. You can do this (define the result when the diagonal is rotated 90 degress) for a square or a chess board, because ‘diagonal’ is meaningful in these cases. You cannot do this for the list of numbers, which should provide a clue to the fact that ‘diagonal’ in meaningless in this context.
The whole crux of the proof is that you can’t do it. That’s how the proof works. However, the reason you can’t do it isn’t just that the list is infinite. You can construct a list of all of the integers.
The diagonal is likewise perfectly well-defined. We don’t need to be able to specify the “other endpoint”; we just need to be able to specify every element of it, which we can do.
Here’s Cantor’s argument in something closer to formal detail:
Assume that we have a function f which is a bijection between the positive natural numbers and decimal representations of real numbers in the interval [0, 1). Since f is a bijection, we know two things:[ol][li]If f(m) = f(n), m = n.[]For every decimal representation d, there is a natural number n[sub]d[/sub] such that f(n[sub]d[/sub]) = d.[/ol]Denote by d[sub]i[/sub] the ith digit to the right of the decimal point in the representation d. We construct a new representation k such that k[sub]i[/sub] = 1 if f(i)[sub]i[/sub] = 0 and 0 otherwise. By property 2 above, there is a positive natural n[sub]k[/sub] such that f(n[sub]k[/sub]) = k. But by our construction, k[sub]n[sub]k[/sub][/sub] is not equal to f(n[sub]k[/sub])[sub]k[/sub], and it follows that f(n[sub]k[/sub]) is not equal to k. This implies that there is no bijection f between the positive natural numbers and decimal representations of real numbers in the interval [0, 1).[/li]
To establish that the reals are larger than the naturals we have to show three additional facts:[ol][][0, 1) has the same cardinality as the entire real line: Consider the function g defined by g(x) = (arctan(x) + 1)/2. This is a bijection between [0, 1) and the real line. I’ll leave the details of the proof to the reader.[]There is some subset of [0, 1) which has the same cardinality as the positive natural numbers: Let n be a positive natural number, and let d(n) be the least integer not less than log[sub]10/sub. The function h defined by h(n) = n/10[sup]d(n)[/sup] is a bijection between the positive naturals and some subset of [0, 1).[]The positive naturals have the same cardinality as the naturals including zero: The bijection here is obvious.[/ol]
The diagrammatic nature of the proof is an aid to understanding and guide to intuition, not the crux of the proof. Not being able to physically draw an infinite line is neither here nor there.
Of course, Cantor’s theorem and his diagonal argument aren’t just idle intellectual curiosities. Diagonalisation is used all over theoretical computer science, for instance, and was instrumental in Turing’s proof of the existence of undecideable numbers.
Please demonstrate, or show me where someone has managed to do this. I wold be fascinated.
Please do so, or show me where someone has managed to do this. Also, please respond to my earlier point and tell me where either end point of this diagonal may be found once you have rotated it through 90 degrees.
Here is what is meant by the claim that “you can construct a list of all the integers.” What you are able to do is specify a way of writing out a sequence of integers such that, given any particular integer N, you are guaranteed eventually to write the number N in a finite amount of time. I give you the way of writing a sequence. You give me the number. And I will always (given enough time) be able to show you exactly where in my sequence your number ends up showing up.
What is meant, then, by the claim that you can’t construct a list of the real numbers is the following. There is no way to specify any way of writing a sequence of real numbers such that, given any particular real number N, you are guaranteed eventually to write the number N in a finite amount of time. In other words, given any way of writing out a sequence of real numbers, there will always be at least one number N (*) which will not appear anywhere in that sequence in any amount of time, neither in any finite amount of time or in an infinite amount of time if there were such a thing.
That is what Cantor proved, paraphrased.
-FrL-
(*)Actually, for any way of sequencing real numbers, there are always an infinite number of such Ns. How big an infinity? The same size as the infinity of real numbers.