11 ms·

I find Cantor's diagonal argument unconvincing. The claim is that there are more real numbers in the range from zero to one than there are natural numbers. To

by zelah 9y ago

I find Cantor's diagonal argument unconvincing. The claim is that there are more real numbers in the range from zero to one than there are natural numbers. To see that this is false simply realize that you don't actually have to write a decimal point to specify the real numbers in this range. Without the decimal point these real numbers just become natural numbers. Can a rational person believe that there are infinite sequences of digits in the form of real numbers but not infinite sequences of digits in the form of natural numbers? The natural numbers are just an infinite sequence of finite numbers. If you believe n is a natural number then you must also believe that n*10 is a natural number. One more digit! There is always one more digit (that is what infinity implies). If there really are an infinite number of natural numbers then some of them must be of a transfinite number of digits or else you would be including numbers in the list more than once. The problem with Cantor's argument comes down to the fact that the procedure he uses to find a number not in the set is essentially the same as the procedure he uses for creating the infinite set in the first place. The only difference is our understanding of randomness. His procedure for finding a number not in the set may not seem very random but it might be as random as any other. A truly random coin could theoretically come up heads every time. The important part of his argument is that the infinite list of real numbers has no repeats. The diagonalization procedure similarly ensures that there are no repeats. On the one hand he claims the infinite set of real numbers exists. On the other hand he argues that the diagonalization that yields a number not in the set has not already been done. He takes away infinity and then gives it back! There is only one infinity. It means "repeat". It is simply the interplay of finite state with process. You can think of it as an "infinite loop" in programming. To say that one infinity is smaller than another is to deny that the smaller is infinite. Infinite means without bound.

ColinWright 9y ago
So if I understand you correctly, you find it unconvincing, and therefore generations of mathematicians who study these things must all be wrong. Perhaps you simply don't understand the argument in detail, and are relying on your intuition. And perhaps your intuition is faulty. Which seems more likely? So let me try to provide a better insight for you. Consider the collection of natural numbers, including 0. Call it N. We all agree that N, also described as the set of non-negative integers, is infinite. Now imagine flipping a coin at time t_0, t_1, t_2, etc. If you're worried that this will take infinite amounts of time, we can suppose that each flip - because we are practised - takes half the time of the previous flip, so all the flips can be done in finite time. However, we're in the realm of Pure Mathematics now, chasing the puzzle for its own sake, and not worrying about practicalities. So what might the result be? Well, you might get all heads, you might get all tails, you might get alternating heads and tail, in practice, of course, you'll get something that looks random. Let's think about all the possible results of flipping the coin. All possible results. Let's let F be the set of all possible results obtained from flipping the coin are each of t_0, t_1, t_2, and so on. We can think of F as functions from N to {H,T}. So we have F and N. Let's wonder if it's possible to have a function from N to F that hits every element of F. Suppose we can. So we have m:N -> F, and for every f in F, there is an n in N such that m(n)=f. Do you think that's possible? Because hundreds of thousands of mathematicians say that it's not possible.
- zelah 9y ago
  It is possible. The inverse of m is called q. The function q takes an infinite sequence of coin flips and one by one changes every heads to 1 and every tails to 0. The infinite string of zeros and ones is then prepended with a 1 and interpreted as a transfinite natural number in binary notation. This will not take forever because each change will only take half as long as the previous one. A transfinite natural number can exist since there are an infinite number of natural numbers. If we stop at 1-bit numbers then the natural numbers are not an infinite set. Likewise, if we stop at 2-bit numbers then the natural numbers are not an infinite set. Our only option is to concede that transfinite natural numbers do actually exist and that they can be put into correspondence with all sequences of coin flips. Hundreds of thousands of mathematicians are wrong.
  - ColinWright 9y ago
    So I asked: is it possible to have m:N -> F such that for every f in F, there is an n in N such that m(n)=f? Your reply says yes, but then your construction does not do it. In particular you said: > The infinite string of zeros and ones is then prepended with a 1 and interpreted as a transfinite natural number in binary notation. But the set N does not have transfinite natural numbers, so q does not map F to N, it maps F to something else. So I ask again, is it possible to have m:N -> F, such that for every f in F, there is an n in N such that m(n)=f?
    - zelah 9y ago
      >But the set N does not have transfinite natural numbers, so q does not map F to N, it maps F to something else. How many natural numbers are there? How many bits does it take to represent the average natural number? If you believe the natural numbers do not include transfinite numbers then how do you pick a successor when counting? There are infinite picks to be made so some of the picks must be transfinite. What I am calling a transfinite natural number must exist in N because N is an infinite set. Assume that N has only finite numbers in it but is itself an infinite set. Would you care to tell me which number (or numbers) are listed twice? But then it is not really a set!
gus_massa 9y ago
[I'll try a non technical argument to convince you. It's also not a complete argument, so you must think about this for a while.] > If you believe n is a natural number then you must also believe that n x 10 is a natural number. One more digit! If you interpret the natural number in this way, the important property is that they have only a finite amount of "interesting" digits. Almost all their digits are zero. You can define the set of number that have a finite amount of non zero digits. Let's call them the "Very Boring" numbers. The set of the "Very Boring" numbers is infinite, but it's the same infinite that the Natural numbers. You can extend this set to include the periodic numbers, for example 46.2222222222222... and 462.2222222222222... and 4622.2222222222222... ... Let's call them the "Boring" numbers. You still get the same infinity. You can also 71.3535353535... and 713.5353535353... and 7135.3535353535... and all the periodic numbers. Now you have the "rational" numbers. You still get the same infinity. The Cantor's diagonal argument fails with Very Boring, Boring and Rational numbers. Because the number you get after taking the diagonal digits and changing them may not be Very Boring, Boring or Rational. -- A somewhat unrelated technical detail that may be useful: Most of the times you don't prove that the cardinal of real numbers between 0 and 1 is a bigger infinity than the cardinal of the natural numbers. I's much easier to consider the infinite strings of digits like "0.765653625367523765..." or "0.5265362556..." or "0.000073468763478..." and also the one with repetitions like "0.0006767000000..." or "0.0072257822222222...". This is essentially a copy of the real number, but in this copy "0.2999999999999..." is different from "0.300000000000000..." This trick makes much easier to prove that the diagonal ´+1 in each one digit is not in the list. Then it's possible to fix the details and use the real numbers instead of the infinite strings of digits.
- zelah 9y ago
  >I's much easier to consider the infinite strings of digits like "0.765653625367523765..." or "0.5265362556..." or "0.000073468763478..." and also the one with repetitions like "0.0006767000000..." or "0.0072257822222222...". This is essentially a copy of the real number, but in this copy "0.2999999999999..." is different from "0.300000000000000..." This trick makes much easier to prove that the diagonal ´+1 in each one digit is not in the list. Then it's possible to fix the details and use the real numbers instead of the infinite strings of digits. What am I missing? "0.765653625367523765..." could be assigned the transfinite natural number beginning "1765653625367523765..." "0.000073468763478..." could be assigned the transfinite natural number beginning "1000073468763478..." Transfinite natural numbers must exist otherwise you do not have an infinite set.
lisper 9y ago
> Without the decimal point these real numbers just become natural numbers. No, they don't, because the vast majority of them have an infinite number of digits to the right of the decimal point. That's the key: there are more numbers with an infinite number of non-zero digits (the reals) than there are numbers with a finite number of non-zero digits (the naturals). > The problem with Cantor's argument comes down to the fact that the procedure he uses to find a number not in the set is essentially the same as the procedure he uses for creating the infinite set in the first place. Again, no. Cantor doesn't create the set, you do. The proof is like a game. It says: give me any procedure for (putatively) making a list of all of the real numbers, and I will give you back a number that is not in the list.
- logfromblammo 9y ago
  Start with zero. Add an infinitesimal epsilon an infinite number of times. Now go back to zero and subtract the same epsilon an infinite number of times. You have now traversed all the real numbers. The decimal representation of the epsilon has an infinite number of zeroes after the decimal point and before the last digit, which is '1'. So if you were to just chop off the leading zero and decimal point to make an equivalence with natural numbers, the epsilon is as much a representation of the natural number 1 as 0.1 or 0.01 or 0.001 or 0.0001 . Infinite real number equivalents to one natural number.
  - kmill 9y ago
    That infinitesimal is not a real number. To simplify a little, a real number is something which is the limit of a sequence of rational numbers. Or, given an error bound 1/n, you can write down a rational number within 1/n of the real number. Two real numbers are the same if the difference between their approximations converges to 0 as n gets arbitrarily large. A number with infinitely many zeros after the decimal point is within 1/n of zero no matter the n. Therefore the number is zero. This is like how 0.9999... is 1. The reason is that 1-0.999... is within 1/n of 0 no matter the n. Suppose you had an infinitesimal epsilon (outside the real numbers --- this is fine, and people do this). How many times are you planning on adding it to itself? To get any actual real number, you are going to have to add it to itself well more than countably many times, though I'm not sure this makes much sense.
empath75 9y ago
> To see that this is false simply realize that you don't actually have to write a decimal point to specify the real numbers in this range. Without the decimal point these real numbers just become natural numbers. There are no natural numbers with infinite digits, so this is not correct.
- mturmon 9y ago
  Your answer is buried, which is too bad, because it is the one-sentence rebuttal to the construction above.
- Zaak 9y ago
  > There are no natural numbers with infinite digits, so this is not correct. Exactly. If you allow an infinite number of digits you wind up with the p-adic numbers, which are uncountable just like the reals.
bmh_ca 9y ago
> There is only one infinity. Fractions are countable. Real numbers are not. In other words, fractions, integers, positive integers all belong to the set of countable infinities, meaning there is an isomorphic function that bidirectionally maps each positive integer (the count) to every item in the target, countable infinity. There is no isomorphism between real numbers and any countable set. If you create one before you are 40, you will get a Field Medal. The isomorphism and the distinction between sets that have them and sets that do not has proven useful. You could think of infinity as one concept, but it is usefully divided into countable and uncountable versions.
throwawayjava 9y ago
It's OK not to be convinced by an argument, even a mathematical proof, and especially an informal proof. But Cantor's argument is correct. If you don't find a mathematical proof convincing even though all the trained mathematicians seem to believe the proof is correct, here's my advice. You should FIRST convert the proof into a sequence of valid deductions in a fixed logic. (If you cannot do this, you don't understand the proof/theorem; perhaps (re-)take a few mathematics courses.) If you can find a mistake in the completely formal proof, then you can convert that mistake into an informal explanation. If your disagreement boils down to a disagreement with a axiom in the formal system even though most mathematicians accept it as an adequate foundations, realize you're getting close to philosophy. This advice is meant for people at the first phase in Terry Tao's hierarchy of mathematical maturity. So not great advice if you're a genius or a trained mathematician (read: people call you doctor). > There is only one infinity. It means "repeat". It is simply the interplay of finite state with process. You can think of it as an "infinite loop" in programming. To say that one infinity is smaller than another is to deny that the smaller is infinite. Infinite means without bound. But "modeling non-terminating loops in a computer program" is NOT the motivation for real numbers, so this foundational criticism of completing the rationals makes absolutely no sense.
- mmarx 9y ago
  > But "modeling non-terminating loops in a computer program" is NOT the motivation for real numbers Indeed Turing himself proved that there are non-computable real numbers.
cjslep 9y ago
There is one English definition of infinity, but when applied to ordinals ("degrees of freedoms"), you get different mathematical concepts of infinity. Vsauce's explanation is approachable: https://youtu.be/SrU9YDoXE88 https://youtu.be/SrU9YDoXE88
- zelah 9y ago
  Thanks - that was very fun!
jakef 9y ago
The natural numbers are each finite. In set theory, the standard way they are defined is that they can be constructed by assuming the existence of the empty set (or 0) and assuming that if you "insert a set into itself" the result will be a set. (So they can be thought of as {} = 0, {{}} = 1, {{}, {{}}} = 2, etc.). The natural numbers are simply the (smallest) set that contains the empty set and is closed under this "insert a set into itself" operation (successor). It only contains finite sets since the successor operation will never turn an finite set into an infinite set. The existence of this set of ALL natural numbers (an infinite object) relies on an axiom, the axiom of infinity. There is no transfinite natural number.
deadmetheny 9y ago
The hubris in this thread is spectacular. Multiple people are demonstrating that your grasp of the math here is wrong, yet you keep arguing that no, the mathematicians must be wrong because you haven't grasped the idea. You could argue that only one infinity exists/actually matters in devland, but in mathematics it's absolutely not the case.
traitormonkey 9y ago
Cantor draws a diagonal and says 'See this number is not in the list'. However he hasn't sorted the list properly.
v64 9y ago
That's not how infinity works, which is why many results involving infinity are counterintuitive. For instance, consider the natural numbers and just the even natural numbers. Intuition says these two sets must differ in size, because I took one set and removed half of its elements. But the mapping f(x) = 2x is a trivial bijection from the natural numbers to the even natural numbers, showing the two sets are of equal size. Do you agree with the statement that two infinite sets are of different cardinality if it can be shown that no bijection exists between them? Let's consider an uncountable set that's simpler to imagine than the real numbers: the power set of the natural numbers, that is, the set of all subsets of N. It can be shown that no bijection exists between any set and its power set (Cantor's theorem [1]). Do you agree with that theorem? It can also be shown that a bijection does exist between the power set of N and R [2], implying they are of the same cardinality, and are both of a larger cardinality than N. > There is only one infinity. It means "repeat". Then what does it mean to you that infinite sets can be constructed that can be shown to have no bijection between them? [1] https://en.wikipedia.org/wiki/Cantor%27s_theorem https://en.wikipedia.org/wiki/Cantor%27s_theorem [2] https://en.wikipedia.org/wiki/Schr%C3%B6der%E2%80%93Bernstein_theorem https://en.wikipedia.org/wiki/Schr%C3%B6der%E2%80%93Bernstei...
iamlucaswolf 9y ago
Phew, you have some courage, questioning the foundations of modern Mathematics in a place like this. But I can relate to your concerns about Cantor's argument. When I first heard it, it also felt artificial and unconvincing to me. What helped me (as with many proofs and concepts in Math) was an image, a visual metaphor if you like. Imagine a very, very large paper on which you place infinitely many dots in a grid. That's the infinity you were referring to, the infinity of a for-loop, discrete infinity. Here's the trick: you can always add more dots, say by making the distance between grid points half as small, which would quadruple the number of dots in your grid. But no matter how many dots you place on the paper, ho matter how fine your grid, there will always be holes (imagine "zooming in" on a square of four grid points). In fact, most of the paper will be empty! The other kind of infinity, continuous infinity, does not have any holes. Every spot is covered. You could not add any grid point, because the whole paper itself is painted. I'm not a "full-time Mathematician", so this view may be entirely wrong. But it helped me understand and appreciate Cantor. Perhaps it did the same for you. Cheers!
- yorwba 9y ago
  That's a very nice intuition, but for the wrong concept. What you have been describing is the difference between a dense set (almost no holes) and a nowhere-dense set (holes everywhere). It turns out that there is a nowhere-dense set that is still uncountably infinite: https://en.wikipedia.org/wiki/Cantor_set https://en.wikipedia.org/wiki/Cantor_set
  - waqf 9y ago
    No, iamlucaswolf is correct, describing a countable dense set (the dyadic rational points) and an uncountable dense set.
weichi 9y ago
You need to write down the 1-1 correspondence you are proposing. Don't describe it in words, actually start writing the natural numbers in one column and the corresponding reals in the other. When you do this, you will find either that the 1-1 correspondence that you are envisioning doesn't actually work (i.e., it isn't 1-1), or that it does work ... but in that case, Cantor's diagonalization argument can be applied to it.
moyix 9y ago
Based on your other replies, I suspect it's not worth engaging, but for anyone else reading, here's a great article by a math journal editor writing about all of the different attempts to disprove Cantor's diagonal argument he received and tracing out some common mistakes he saw: http://www.logic.univie.ac.at/~ykhomski/ST2013/Hodges.pdf http://www.logic.univie.ac.at/~ykhomski/ST2013/Hodges.pdf
- zelah 9y ago
  Thank you - I have read this and do realize I am out of my depth.
peteretep 9y ago
What a shame you're getting downvoted, simply because you're wrong. > Without the decimal point these real > numbers just become natural numbers. If your argument is true, presumably you could write a simple program that would generate all the real numbers with a single, infinite loop? I wonder how you'd manage to generate 0.1 and 1.0 with your scheme.
- jerf 9y ago
  "What a shame you're getting downvoted, simply because you're wrong." It's not simply because of being wrong. Being wrong is a hazard to your karma, yes, even sometimes just asking questions can be a hazard (which I dislike and do what little I can to fight, but it's still obviously true). But there's a much bigger hazard being invoked here.
- bllguo 9y ago
  That is extremely disingenuous of you. He's being downvoted for his massive arrogance.
- andrewla 9y ago
  I agree that the downvoting is unfortunate. I guess the assumption is that the post is simply a troll, which seems to be backed up by some of the down-thread replies. Even so, the original post just seems like a list of common misunderstandings about Cantor's notion of infinity and how it corresponds to the way that we use the word in colloquial use. In defense of the GP, I think they were simply thinking of numbers in [0,1). If you write them backwards, it almost seems like it would work: 1 -> .1 2 -> .2 ... 9 -> .9 10 -> .01 11 -> .11 12 -> .21 ... 3124 -> .4213 ... Done! Unfortunately, you are either stuck with the fact that some numbers (even simple rational ones) do not have a finite decimal expansion. In most formal proofs of the diagonal theorem, we use the infinite representation without trailing 0s (using trailing 9's instead) to force uniqueness, which makes it even trickier. Or you're stuck trying to assume that there are natural numbers with an infinite representation, so the decimal representation of the rational number 1/3 would correspond to an actual natural number.
littlestymaar 9y ago
The error in your reasoning lies here : > Without the decimal point these real numbers just become natural numbers This is wrong because irrational numbers have an infinite number of digit, if you remove the «dot» you end up with a number infinitely long, which is not a natural number. □ Edit: the set of natural numbers is infinite, which means it can contain arbitrarily big numbers, yet it doesn't contain «numbers» with an infinite amount of digits.
kmill 9y ago
I think I figured it out: you must be one of the aliens predicted by the downward Löwenheim–Skolem theorem! If we could have a model of set theory (a set1 of all set2s, where a set1 is a set in our set theory and a set2 a modeled set, like an interpreter), which is necessarily infinitely large, then the downward Löwenheim–Skolem theorem implies there is a model that is only countably infinite. There is a model of the real numbers in there, so from our point of view, the real numbers are countable! Though from the model's point of view, Cantor's diagonal argument still works, and they are not countable! My theory is that you are looking at our real numbers and thinking they are countable because you have a much more powerful set of natural numbers than the rest of us. Unfortunately for you, your bijection between our reals and your naturals does not carry over to our set theory. You should find, however, that you do not have a bijection between your reals and your naturals. One problem with this is that Gödel's incompleteness theorem implies that if we ever had a model and could prove it was a model, then set theory would be inconsistent. More seriously, Cantor's argument as usually given is not Cantor's original argument. He originally did something involving nested closed intervals, but it was simplified to listing out the digit expansions of a list of real numbers. I am partial to the following argument: suppose there were an invertible function f between N and infinite sequences of 0's and 1's. The type of f is written N -> (N -> Bool) since an infinite sequence of 0's and 1's is a function from N to {0,1}. Let g(n)=not f(n)(n). This is a function N -> Bool. Since f is invertible, let finv be the inverse f : (N -> Bool) -> N. Then finv(g) is a natural number. Plug this into g: g(finv(g)) = not f(finv(g))(finv(g)) = not g(finv(g)) Uh oh, the value of g at finv(g) is not whatever its value is. Something must be wrong: it could be there is no set of natural numbers or booleans (unlikely), that g is not definable (but it is a simple expression of f, and not even recursive; unlikely), or that there is no such function f (this is the only assumption remaining, so there must not have been an f that is a bijection). Notice there was nothing special about N in this argument. It could have been a finite set, an infinite set, or even the real numbers, and we still would have concluded there is some value at which g is not its own value! It is possible to prove that there are at least as many real numbers as there are sequences N -> Bool using infinite series. It is also possible to prove there are no more real numbers than there are such sequences.
- myren 9y ago
0xBABAD00C 9y ago
I find that people who question Cantor's (obviously correct) theorems and concepts seem to share commonalities with people questioning Einstein's (obviously correct) theories and concepts. Let's just say if Cantor's last name was Rasmussen and the infinities weren't indexed Alephs, I wouldn't expect people to get their panties in a bunch over abstract math, and care so much about proving him wrong, a fraud, a lunatic, etc (without even a basic understanding of the subject). It hits the subconscious strings of jealousy and mistrust of the majority towards the more successful almost-the-same-but-not-quite minority so very perfectly, especially when the subject matter put forward by the minority is cryptic or unintuitive at the first glance... Just a theory :)
SubiculumCode 9y ago
Congratulations. You hijacked a thread.
haddy6235 9y ago
Why do mathematicians normally not distinguish between numbers for counting and numbers for measuring (length, volume, etc)? They are fundamentally different, and conflation makes many arguments hard to grasp.
myren 9y ago
"If there really are an infinite number of natural numbers then some of them must be of a transfinite number of digits or else you would be including numbers in the list more than once." Theorem: There are no infinite natural numbers. Proof: By Induction: Induction Start: 0 is finite. Induction Step: If n is finite then n+1 is finite. The principle of induction then tells us: All natural numbers are finite. If all natural numbers are finite, then there are no infinite natural numbers. End of proof.

by zelah 9y ago

ColinWright 9y ago

So if I understand you correctly, you find it unconvincing, and therefore generations of mathematicians who study these things must all be wrong. Perhaps you simply don't understand the argument in detail, and are relying on your intuition. And perhaps your intuition is faulty. Which seems more likely? So let me try to provide a better insight for you. Consider the collection of natural numbers, including 0. Call it N. We all agree that N, also described as the set of non-negative integers, is infinite. Now imagine flipping a coin at time t_0, t_1, t_2, etc. If you're worried that this will take infinite amounts of time, we can suppose that each flip - because we are practised - takes half the time of the previous flip, so all the flips can be done in finite time. However, we're in the realm of Pure Mathematics now, chasing the puzzle for its own sake, and not worrying about practicalities. So what might the result be? Well, you might get all heads, you might get all tails, you might get alternating heads and tail, in practice, of course, you'll get something that looks random. Let's think about all the possible results of flipping the coin. All possible results. Let's let F be the set of all possible results obtained from flipping the coin are each of t_0, t_1, t_2, and so on. We can think of F as functions from N to {H,T}. So we have F and N. Let's wonder if it's possible to have a function from N to F that hits every element of F. Suppose we can. So we have m:N -> F, and for every f in F, there is an n in N such that m(n)=f. Do you think that's possible? Because hundreds of thousands of mathematicians say that it's not possible.

zelah 9y ago
It is possible. The inverse of m is called q. The function q takes an infinite sequence of coin flips and one by one changes every heads to 1 and every tails to 0. The infinite string of zeros and ones is then prepended with a 1 and interpreted as a transfinite natural number in binary notation. This will not take forever because each change will only take half as long as the previous one. A transfinite natural number can exist since there are an infinite number of natural numbers. If we stop at 1-bit numbers then the natural numbers are not an infinite set. Likewise, if we stop at 2-bit numbers then the natural numbers are not an infinite set. Our only option is to concede that transfinite natural numbers do actually exist and that they can be put into correspondence with all sequences of coin flips. Hundreds of thousands of mathematicians are wrong.
- ColinWright 9y ago
  So I asked: is it possible to have m:N -> F such that for every f in F, there is an n in N such that m(n)=f? Your reply says yes, but then your construction does not do it. In particular you said: > The infinite string of zeros and ones is then prepended with a 1 and interpreted as a transfinite natural number in binary notation. But the set N does not have transfinite natural numbers, so q does not map F to N, it maps F to something else. So I ask again, is it possible to have m:N -> F, such that for every f in F, there is an n in N such that m(n)=f?
  - zelah 9y ago
    >But the set N does not have transfinite natural numbers, so q does not map F to N, it maps F to something else. How many natural numbers are there? How many bits does it take to represent the average natural number? If you believe the natural numbers do not include transfinite numbers then how do you pick a successor when counting? There are infinite picks to be made so some of the picks must be transfinite. What I am calling a transfinite natural number must exist in N because N is an infinite set. Assume that N has only finite numbers in it but is itself an infinite set. Would you care to tell me which number (or numbers) are listed twice? But then it is not really a set!

gus_massa 9y ago

[I'll try a non technical argument to convince you. It's also not a complete argument, so you must think about this for a while.] > If you believe n is a natural number then you must also believe that n x 10 is a natural number. One more digit! If you interpret the natural number in this way, the important property is that they have only a finite amount of "interesting" digits. Almost all their digits are zero. You can define the set of number that have a finite amount of non zero digits. Let's call them the "Very Boring" numbers. The set of the "Very Boring" numbers is infinite, but it's the same infinite that the Natural numbers. You can extend this set to include the periodic numbers, for example 46.2222222222222... and 462.2222222222222... and 4622.2222222222222... ... Let's call them the "Boring" numbers. You still get the same infinity. You can also 71.3535353535... and 713.5353535353... and 7135.3535353535... and all the periodic numbers. Now you have the "rational" numbers. You still get the same infinity. The Cantor's diagonal argument fails with Very Boring, Boring and Rational numbers. Because the number you get after taking the diagonal digits and changing them may not be Very Boring, Boring or Rational. -- A somewhat unrelated technical detail that may be useful: Most of the times you don't prove that the cardinal of real numbers between 0 and 1 is a bigger infinity than the cardinal of the natural numbers. I's much easier to consider the infinite strings of digits like "0.765653625367523765..." or "0.5265362556..." or "0.000073468763478..." and also the one with repetitions like "0.0006767000000..." or "0.0072257822222222...". This is essentially a copy of the real number, but in this copy "0.2999999999999..." is different from "0.300000000000000..." This trick makes much easier to prove that the diagonal ´+1 in each one digit is not in the list. Then it's possible to fix the details and use the real numbers instead of the infinite strings of digits.

zelah 9y ago
>I's much easier to consider the infinite strings of digits like "0.765653625367523765..." or "0.5265362556..." or "0.000073468763478..." and also the one with repetitions like "0.0006767000000..." or "0.0072257822222222...". This is essentially a copy of the real number, but in this copy "0.2999999999999..." is different from "0.300000000000000..." This trick makes much easier to prove that the diagonal ´+1 in each one digit is not in the list. Then it's possible to fix the details and use the real numbers instead of the infinite strings of digits. What am I missing? "0.765653625367523765..." could be assigned the transfinite natural number beginning "1765653625367523765..." "0.000073468763478..." could be assigned the transfinite natural number beginning "1000073468763478..." Transfinite natural numbers must exist otherwise you do not have an infinite set.

lisper 9y ago

> Without the decimal point these real numbers just become natural numbers. No, they don't, because the vast majority of them have an infinite number of digits to the right of the decimal point. That's the key: there are more numbers with an infinite number of non-zero digits (the reals) than there are numbers with a finite number of non-zero digits (the naturals). > The problem with Cantor's argument comes down to the fact that the procedure he uses to find a number not in the set is essentially the same as the procedure he uses for creating the infinite set in the first place. Again, no. Cantor doesn't create the set, you do. The proof is like a game. It says: give me any procedure for (putatively) making a list of all of the real numbers, and I will give you back a number that is not in the list.

logfromblammo 9y ago
Start with zero. Add an infinitesimal epsilon an infinite number of times. Now go back to zero and subtract the same epsilon an infinite number of times. You have now traversed all the real numbers. The decimal representation of the epsilon has an infinite number of zeroes after the decimal point and before the last digit, which is '1'. So if you were to just chop off the leading zero and decimal point to make an equivalence with natural numbers, the epsilon is as much a representation of the natural number 1 as 0.1 or 0.01 or 0.001 or 0.0001 . Infinite real number equivalents to one natural number.
- kmill 9y ago
  That infinitesimal is not a real number. To simplify a little, a real number is something which is the limit of a sequence of rational numbers. Or, given an error bound 1/n, you can write down a rational number within 1/n of the real number. Two real numbers are the same if the difference between their approximations converges to 0 as n gets arbitrarily large. A number with infinitely many zeros after the decimal point is within 1/n of zero no matter the n. Therefore the number is zero. This is like how 0.9999... is 1. The reason is that 1-0.999... is within 1/n of 0 no matter the n. Suppose you had an infinitesimal epsilon (outside the real numbers --- this is fine, and people do this). How many times are you planning on adding it to itself? To get any actual real number, you are going to have to add it to itself well more than countably many times, though I'm not sure this makes much sense.

empath75 9y ago

> To see that this is false simply realize that you don't actually have to write a decimal point to specify the real numbers in this range. Without the decimal point these real numbers just become natural numbers. There are no natural numbers with infinite digits, so this is not correct.

mturmon 9y ago
Your answer is buried, which is too bad, because it is the one-sentence rebuttal to the construction above.
Zaak 9y ago
> There are no natural numbers with infinite digits, so this is not correct. Exactly. If you allow an infinite number of digits you wind up with the p-adic numbers, which are uncountable just like the reals.

bmh_ca 9y ago

> There is only one infinity. Fractions are countable. Real numbers are not. In other words, fractions, integers, positive integers all belong to the set of countable infinities, meaning there is an isomorphic function that bidirectionally maps each positive integer (the count) to every item in the target, countable infinity. There is no isomorphism between real numbers and any countable set. If you create one before you are 40, you will get a Field Medal. The isomorphism and the distinction between sets that have them and sets that do not has proven useful. You could think of infinity as one concept, but it is usefully divided into countable and uncountable versions.

throwawayjava 9y ago

It's OK not to be convinced by an argument, even a mathematical proof, and especially an informal proof. But Cantor's argument is correct. If you don't find a mathematical proof convincing even though all the trained mathematicians seem to believe the proof is correct, here's my advice. You should FIRST convert the proof into a sequence of valid deductions in a fixed logic. (If you cannot do this, you don't understand the proof/theorem; perhaps (re-)take a few mathematics courses.) If you can find a mistake in the completely formal proof, then you can convert that mistake into an informal explanation. If your disagreement boils down to a disagreement with a axiom in the formal system even though most mathematicians accept it as an adequate foundations, realize you're getting close to philosophy. This advice is meant for people at the first phase in Terry Tao's hierarchy of mathematical maturity. So not great advice if you're a genius or a trained mathematician (read: people call you doctor). > There is only one infinity. It means "repeat". It is simply the interplay of finite state with process. You can think of it as an "infinite loop" in programming. To say that one infinity is smaller than another is to deny that the smaller is infinite. Infinite means without bound. But "modeling non-terminating loops in a computer program" is NOT the motivation for real numbers, so this foundational criticism of completing the rationals makes absolutely no sense.

mmarx 9y ago
> But "modeling non-terminating loops in a computer program" is NOT the motivation for real numbers Indeed Turing himself proved that there are non-computable real numbers.

cjslep 9y ago

There is one English definition of infinity, but when applied to ordinals ("degrees of freedoms"), you get different mathematical concepts of infinity. Vsauce's explanation is approachable: https://youtu.be/SrU9YDoXE88 https://youtu.be/SrU9YDoXE88

zelah 9y ago
Thanks - that was very fun!

jakef 9y ago

The natural numbers are each finite. In set theory, the standard way they are defined is that they can be constructed by assuming the existence of the empty set (or 0) and assuming that if you "insert a set into itself" the result will be a set. (So they can be thought of as {} = 0, {{}} = 1, {{}, {{}}} = 2, etc.). The natural numbers are simply the (smallest) set that contains the empty set and is closed under this "insert a set into itself" operation (successor). It only contains finite sets since the successor operation will never turn an finite set into an infinite set. The existence of this set of ALL natural numbers (an infinite object) relies on an axiom, the axiom of infinity. There is no transfinite natural number.

deadmetheny 9y ago

The hubris in this thread is spectacular. Multiple people are demonstrating that your grasp of the math here is wrong, yet you keep arguing that no, the mathematicians must be wrong because you haven't grasped the idea. You could argue that only one infinity exists/actually matters in devland, but in mathematics it's absolutely not the case.

traitormonkey 9y ago

Cantor draws a diagonal and says 'See this number is not in the list'. However he hasn't sorted the list properly.

v64 9y ago

That's not how infinity works, which is why many results involving infinity are counterintuitive. For instance, consider the natural numbers and just the even natural numbers. Intuition says these two sets must differ in size, because I took one set and removed half of its elements. But the mapping f(x) = 2x is a trivial bijection from the natural numbers to the even natural numbers, showing the two sets are of equal size. Do you agree with the statement that two infinite sets are of different cardinality if it can be shown that no bijection exists between them? Let's consider an uncountable set that's simpler to imagine than the real numbers: the power set of the natural numbers, that is, the set of all subsets of N. It can be shown that no bijection exists between any set and its power set (Cantor's theorem [1]). Do you agree with that theorem? It can also be shown that a bijection does exist between the power set of N and R [2], implying they are of the same cardinality, and are both of a larger cardinality than N. > There is only one infinity. It means "repeat". Then what does it mean to you that infinite sets can be constructed that can be shown to have no bijection between them? [1] https://en.wikipedia.org/wiki/Cantor%27s_theorem https://en.wikipedia.org/wiki/Cantor%27s_theorem [2] https://en.wikipedia.org/wiki/Schr%C3%B6der%E2%80%93Bernstein_theorem https://en.wikipedia.org/wiki/Schr%C3%B6der%E2%80%93Bernstei...

iamlucaswolf 9y ago

Phew, you have some courage, questioning the foundations of modern Mathematics in a place like this. But I can relate to your concerns about Cantor's argument. When I first heard it, it also felt artificial and unconvincing to me. What helped me (as with many proofs and concepts in Math) was an image, a visual metaphor if you like. Imagine a very, very large paper on which you place infinitely many dots in a grid. That's the infinity you were referring to, the infinity of a for-loop, discrete infinity. Here's the trick: you can always add more dots, say by making the distance between grid points half as small, which would quadruple the number of dots in your grid. But no matter how many dots you place on the paper, ho matter how fine your grid, there will always be holes (imagine "zooming in" on a square of four grid points). In fact, most of the paper will be empty! The other kind of infinity, continuous infinity, does not have any holes. Every spot is covered. You could not add any grid point, because the whole paper itself is painted. I'm not a "full-time Mathematician", so this view may be entirely wrong. But it helped me understand and appreciate Cantor. Perhaps it did the same for you. Cheers!

yorwba 9y ago
That's a very nice intuition, but for the wrong concept. What you have been describing is the difference between a dense set (almost no holes) and a nowhere-dense set (holes everywhere). It turns out that there is a nowhere-dense set that is still uncountably infinite: https://en.wikipedia.org/wiki/Cantor_set https://en.wikipedia.org/wiki/Cantor_set
- waqf 9y ago
  No, iamlucaswolf is correct, describing a countable dense set (the dyadic rational points) and an uncountable dense set.

weichi 9y ago

You need to write down the 1-1 correspondence you are proposing. Don't describe it in words, actually start writing the natural numbers in one column and the corresponding reals in the other. When you do this, you will find either that the 1-1 correspondence that you are envisioning doesn't actually work (i.e., it isn't 1-1), or that it does work ... but in that case, Cantor's diagonalization argument can be applied to it.

moyix 9y ago

Based on your other replies, I suspect it's not worth engaging, but for anyone else reading, here's a great article by a math journal editor writing about all of the different attempts to disprove Cantor's diagonal argument he received and tracing out some common mistakes he saw: http://www.logic.univie.ac.at/~ykhomski/ST2013/Hodges.pdf http://www.logic.univie.ac.at/~ykhomski/ST2013/Hodges.pdf

zelah 9y ago
Thank you - I have read this and do realize I am out of my depth.

peteretep 9y ago

What a shame you're getting downvoted, simply because you're wrong. > Without the decimal point these real > numbers just become natural numbers. If your argument is true, presumably you could write a simple program that would generate all the real numbers with a single, infinite loop? I wonder how you'd manage to generate 0.1 and 1.0 with your scheme.

jerf 9y ago
"What a shame you're getting downvoted, simply because you're wrong." It's not simply because of being wrong. Being wrong is a hazard to your karma, yes, even sometimes just asking questions can be a hazard (which I dislike and do what little I can to fight, but it's still obviously true). But there's a much bigger hazard being invoked here.
bllguo 9y ago
That is extremely disingenuous of you. He's being downvoted for his massive arrogance.
andrewla 9y ago
I agree that the downvoting is unfortunate. I guess the assumption is that the post is simply a troll, which seems to be backed up by some of the down-thread replies. Even so, the original post just seems like a list of common misunderstandings about Cantor's notion of infinity and how it corresponds to the way that we use the word in colloquial use. In defense of the GP, I think they were simply thinking of numbers in [0,1). If you write them backwards, it almost seems like it would work: 1 -> .1 2 -> .2 ... 9 -> .9 10 -> .01 11 -> .11 12 -> .21 ... 3124 -> .4213 ... Done! Unfortunately, you are either stuck with the fact that some numbers (even simple rational ones) do not have a finite decimal expansion. In most formal proofs of the diagonal theorem, we use the infinite representation without trailing 0s (using trailing 9's instead) to force uniqueness, which makes it even trickier. Or you're stuck trying to assume that there are natural numbers with an infinite representation, so the decimal representation of the rational number 1/3 would correspond to an actual natural number.

littlestymaar 9y ago

The error in your reasoning lies here : > Without the decimal point these real numbers just become natural numbers This is wrong because irrational numbers have an infinite number of digit, if you remove the «dot» you end up with a number infinitely long, which is not a natural number. □ Edit: the set of natural numbers is infinite, which means it can contain arbitrarily big numbers, yet it doesn't contain «numbers» with an infinite amount of digits.

kmill 9y ago

I think I figured it out: you must be one of the aliens predicted by the downward Löwenheim–Skolem theorem! If we could have a model of set theory (a set1 of all set2s, where a set1 is a set in our set theory and a set2 a modeled set, like an interpreter), which is necessarily infinitely large, then the downward Löwenheim–Skolem theorem implies there is a model that is only countably infinite. There is a model of the real numbers in there, so from our point of view, the real numbers are countable! Though from the model's point of view, Cantor's diagonal argument still works, and they are not countable! My theory is that you are looking at our real numbers and thinking they are countable because you have a much more powerful set of natural numbers than the rest of us. Unfortunately for you, your bijection between our reals and your naturals does not carry over to our set theory. You should find, however, that you do not have a bijection between your reals and your naturals. One problem with this is that Gödel's incompleteness theorem implies that if we ever had a model and could prove it was a model, then set theory would be inconsistent. More seriously, Cantor's argument as usually given is not Cantor's original argument. He originally did something involving nested closed intervals, but it was simplified to listing out the digit expansions of a list of real numbers. I am partial to the following argument: suppose there were an invertible function f between N and infinite sequences of 0's and 1's. The type of f is written N -> (N -> Bool) since an infinite sequence of 0's and 1's is a function from N to {0,1}. Let g(n)=not f(n)(n). This is a function N -> Bool. Since f is invertible, let finv be the inverse f : (N -> Bool) -> N. Then finv(g) is a natural number. Plug this into g: g(finv(g)) = not f(finv(g))(finv(g)) = not g(finv(g)) Uh oh, the value of g at finv(g) is not whatever its value is. Something must be wrong: it could be there is no set of natural numbers or booleans (unlikely), that g is not definable (but it is a simple expression of f, and not even recursive; unlikely), or that there is no such function f (this is the only assumption remaining, so there must not have been an f that is a bijection). Notice there was nothing special about N in this argument. It could have been a finite set, an infinite set, or even the real numbers, and we still would have concluded there is some value at which g is not its own value! It is possible to prove that there are at least as many real numbers as there are sequences N -> Bool using infinite series. It is also possible to prove there are no more real numbers than there are such sequences.

myren 9y ago

0xBABAD00C 9y ago

I find that people who question Cantor's (obviously correct) theorems and concepts seem to share commonalities with people questioning Einstein's (obviously correct) theories and concepts. Let's just say if Cantor's last name was Rasmussen and the infinities weren't indexed Alephs, I wouldn't expect people to get their panties in a bunch over abstract math, and care so much about proving him wrong, a fraud, a lunatic, etc (without even a basic understanding of the subject). It hits the subconscious strings of jealousy and mistrust of the majority towards the more successful almost-the-same-but-not-quite minority so very perfectly, especially when the subject matter put forward by the minority is cryptic or unintuitive at the first glance... Just a theory :)

SubiculumCode 9y ago

Congratulations. You hijacked a thread.

haddy6235 9y ago

Why do mathematicians normally not distinguish between numbers for counting and numbers for measuring (length, volume, etc)? They are fundamentally different, and conflation makes many arguments hard to grasp.

myren 9y ago

"If there really are an infinite number of natural numbers then some of them must be of a transfinite number of digits or else you would be including numbers in the list more than once." Theorem: There are no infinite natural numbers. Proof: By Induction: Induction Start: 0 is finite. Induction Step: If n is finite then n+1 is finite. The principle of induction then tells us: All natural numbers are finite. If all natural numbers are finite, then there are no infinite natural numbers. End of proof.