Cantor’s diagonal argument proves that there is not a one-to-one correspondence between the rationals and reals (actually between reals and all countably infinite sets), but how does he get from there to concluding that there are more reals than rationals?
The simple answer is because the theorem shows that any attempt to put the two sets into a one-to-one correspondence has left over reals.
The slightly more complicated answer is that this is essentially the definition of “more” being used since you can’t count them and say “Oh yes the number of reals is larger then the number of rationals.” because you can’t count the former.
Let me sum up my understanding of the proof:
Assume that there IS a one-to-one correspondence. If that is so, then we can count them, like this (Even though they are out of order, we’re assuming the list contains all the reals, remember?):
1 : 0.2231…
2 : 0.4378…
3 : 0.7729…
4 : 0.6290…
…
Now, we can construct another real number, by taking one digit from each row and changing it. So the first digit would be NOT 2, and the second digit would be NOT 3, and so on. We can see that this real number isn’t on the list, because it is different in at least one digit from every other number, based on how we constructed it.
So, since we’ve found a contradiction, we’ve disproved the assumption, namely that there is a one-to-one correspondence between the reals and a countably infinite set.
Okay, the sets aren’t the same size. We just proved that. But how do we tell which one is bigger?
Okay, I can see that. It’s just the definition of “more” as “having leftover elements, after putting them in a one-to-one correspondence with the other set”.
But I’m not 100% sure there isn’t a construction that shows there are more rationals when we line them up with reals.
I guess what I’m thinking is, when the assumptions are false, you can make 1=2. So, since we’ve already proven the assumption is false, how can we then say “see, when we pair them up one-to-one, there’s more reals leftover” when we’ve already established you can’t pair them up at all?
It’s because two sets A and B are defined to have the same size (|A| = |B|) if and only if there is a function f:A –> B such that f is both one-to-one and onto (i.e., a one-to-one correspondence). Additionally, the standard definition is that the size of B is at least as big as A (|B| >= |A|) if there is a one-to-one function g: A–> B, (or, equivalently, there is an onto function h: B –> A). The first version of this definition says that if we try to use members of A to label things in B, we don’t ever run out of things to label. The second version says that if we try to do the reverse, and use labels from B and stick them on items in A, then everything in A gets labeled.
Now, the list is a one-to-one function N –> R. Since it’s one-to-one, we know that |N| <= |R|. Diagonalization then says that |N| != |R|. We conclude that |N| < |R|, as desired.
The diagonalization theorem says to start with any possible method to pair the rationals (actually, the naturals, but the conclusion is still valid) with the reals. No such pairing can be complete.
Even the ancient Greeks knew that there were real numbers that were not rational numbers. But all rational numbers are real numbers, so it seems obvious that there are more real numbers.
But it also seems obvious that there are more rationals than integers. So maybe it’s more important that Cantor showed that the latter is not true, i.e. there are as many integers as rationals. He “merely” verified that there are more reals than rationals.
It only seems obvious in hindsight.
It’s not actually obvious at all, as the 1-1 correspondence between integers and rationals demonstrates. Even Cantor was often surprised at the implications of his work.
By a similar token there are “as many” real numbers between 0 and 1 as there are real numbers altogether, which is non-intuitive and non-obvious, yet a very real consequence of Cantor’s work.
But similar concepts were known for several hundred years by the time Cantor arrived. I’m not recalling names, but I believe it was noticed during the Renaissance era that two concentric circles with different radii contain the same number of points. It’s not much of a leap from there to identifying a circle minus a point with a line.
Apparently it is a pretty big leap, given how long it took anyone to make it. Everything is obvious in retrospect.
Ok your problem, quite simply, is that you have put the rationals in any old order.
You should in fact have put them in order. Once you do that you’ll see that the reals have to outnumber because if you think about it there will always be more reals “up to that point” (i.e. the number you’re constructing is something not in your list so your list is sizesofar+1)
In fact you can go even further by extending that argument- there’s an uncountable number of reals between any rational numbers!
This is about the only thing I learned at university.
Every rational number is a real number (in the same way, every natural number is a rational number).
You completely missed the point.
It indeed SEEMED obvious for thousands of years, and it still seems obvious today to the mathematically unsophisticated, that there are more rationals than integers, and more reals than rationals. One of Euclid’s common notions was “the whole is greater than the part.” The rationals are a proper superset of the integers, and the reals are a proper superset of the rationals, and that’s all you need to know.
But what seemed obvious turned out to be false in the case of integers vs rationals. And it turned out to be true in the case of reals vs. rationals. Cantor provided remarkably simple proofs for both, but IMO it was the integers vs rationals case that was the more surprising result.
OK, do so. You can start with 0. Then please give us the next several numbers in your sequence.
Which is to say, there’s different senses of the word “more” (and “same amount” and so on). The sense in which there are real numbers which are not rational has been known since the ancient Greeks; the sense in which there is no surjective map from rationals to reals was first demonstrated by Cantor (using a different argument than the famous diagonalization one (one more directly tailored to real numbers); the diagonalization argument came only later, and really isn’t directly about reals so much as digit-sequences. It’s actually a little messy to show that there are the same number of reals as digit-sequences, though of course Cantor did that as well).
The fact that these two senses of “more” diverge was actually noticed long before Cantor; Galileo had remarked upon the curious phenomenon that, in the one sense, there are many more natural numbers than square integers (since many naturals are not squares), but in the other sense, there are the same amount (since a one to one correspondence is obvious).
(It should be stressed that it’s not illegitimate to speak of non-Cantorian sense of “more”, “larger”, etc; the sense in which a mile is much larger than an inch is quite important, even if they have the same cardinality of points. Indeed, perhaps the Cantorian senses of the terms cause more confusion than they help, as a default)
Oh fuck, turns out I learned nothing at all.
(seriously, it’s no problem to do so conceptually. obviously you cannot sort an infinite set in real life but you can work with it. plus it’s trivial that you can arbitarily map members of the same set to other members of the same set on a 1 to 1 basis so it being in order doesn’t matter as such)
It sounds like what you’re really asking is, if A is a subset of B, how do we know that all the elements of B can’t in any way be paired up with elements of A so that there remain elements of A left over?
The quantity of rationals must be less than, greater than, or equal to, the quantity of the reals, since there aren’t any other relations available.
The quantity of rationals cannot be greater than the quantity of reals, because the rationals are a subset of the reals.
The quantity of rationals cannot be equal to the quantity of reals, by the diagonal argument.
Therefore, the quantity of rationals must be less than the quantity of the reals.
Well, that’s the problem with “obvious” statements about infinities. I can take your example and change it as follows: “There [are] integers that [are] not even integers. But all even integers are integers, so it seems obvious that there are more integers [than even integers].” This is, of course, false: the cardinality of the set of even integers and the set of all integers is the same.
ETA: upon re-reading your later post, I think I agree with your larger point: “obvious” statements about the sizes of infinite sets aren’t necessarily true.
(Bold added)
With due respect, I think I have to call BS on this argument. The bolded statement appears to be the trichotomy rule I learned in Algebra I which says: Given two numbers a and b, exactly one of these conditions is true: a < b ; a = b ; a > b
But as MikeS points out, everything you think you know about finite numbers goes out the window when you start dealing with infinities. Everything needs to be proved afresh or, more often, defined afresh (like relative sizes for sets when infinite sets are involved). You can’t just start an argument like this with any a priori statements that generalize facts about numbers to include infinities. For the purpose of fighting ignorance, that isn’t good enough.
You really have to give some kind of new argument or definition, like Cantor’s diagonal proof or something of the sort.