Refuting the Anti-Cantor Cranks












53












$begingroup$


I occasionally have the opportunity to argue with anti-Cantor cranks, people who for some reason or the other attack the validity of Cantor's diagonalization proof of the uncountability of the real numbers, arguably one of the most beautiful ideas in mathematics. They usually make the same sorts of arguments, so years ago I wrote up this FAQ to deal with them. Unfortunately, it's still hard to get anywhere with these people; the discussion frequently turns into something of this form:



ME: Suppose there is an ordered list containing all the real numbers. Then we can read off the diagonal entries and construct a real number that differs in the Nth decimal place from the Nth real number on the list. This real number obviously cannot be in the list. So the list doesn't contain all the real numbers.



THEM: Of course your proposed number is not on the list; it's not a well-defined real number.



ME: What do you mean? I gave you the exact procedure for constructing it. You take the Nth real number on the list, and you make it differ from that number in the Nth decimal place.



THEM: But if we really have a list of all the real numbers, then your proposed number has to be somewhere in the list, right?



ME: Yes, of course, so let's say it's in the 57th place. Then it would have to differ from itself in the 57th place, which is impossible!



THEM: Exactly, it's impossible! Your definition requires that it differs in some place from itself, which is impossible, so your definition is bad.



ME: But you're only saying that it's impossible on the basis of the assumption that there's a complete list of real numbers, and the whole point is to disprove that assumption.



THEM: But we're doing this proof under that assumption, so how can we make a definition that runs contrary to that assumption?



ME: But that definition is a good one regardless of whether there are countably or uncountably many reals. It is a complete, algorithmic, unambiguous specification of the real number. What else could you want?



THEM: I want the definition to be both unambiguous and non-contradictory, and your definition is contradictory!



ME: Forget about the purported complete lists of real numbers for a moment. Don't you agree that for any list of real numbers, complete or incomplete, it's possible to construct a real number that differs in the Nth place from the Nth number on the list?



THEM: No, it's only possible to construct such a real number if that real number isn't on the list, otherwise it's a contradictory definition.



ME: Don't you see that the contradiction is not the fault of my perfectly good definition, but rather the fault of your assumption that there are countably many real numbers?



THEM: No, I don't.



ME: But what if we took our putative complete list of real numbers, and fed it in line by line into a computer with an algorithm that spits out, digit by digit, a real number that differs in the Nth digit from the Nth number on the list? Would such a computer program work?



THEM: No it wouldn't, the computer program would hit the place on the list where the number being constructed would reside, and then it would get crash, because it can't choose a digit for the number that differs in the nth place from itself.



ME: Argh!



So how do I stop going in circles and convince them that they're wrong?



Any help would be greatly appreciated.



Thank You in Advance.






elementary-set-theory soft-question cardinals education infinity







share|cite|improve this question











$endgroup$








  • 72




    $begingroup$
    If they are true cranks, give up. Ain't gonna happen.
    $endgroup$
    – Ross Millikan
    Oct 15 '13 at 15:30






  • 10




    $begingroup$
    I only discussed with anti-Cantorians after I had uttered a discouraging word to a student. Serving my penance, you see.
    $endgroup$
    – Jyrki Lahtonen
    Oct 15 '13 at 15:36








  • 15




    $begingroup$
    Your biggest problem with this hypothetical anti-Cantor crank is that E seems to not understand proof by contradiction. I guess there should be some overlap between Cantor-truthers and people who don't understand contradiction, but my experience has been that the problem is usually more along the lines of not understanding the relationship between "sets", "lists", and "countable". Discomfort with contradiction is a separate issue that should be straightened out in a calmer setting, not in a case where the result is so unintuitive.
    $endgroup$
    – Eric Stucky
    Oct 15 '13 at 15:41








  • 23




    $begingroup$
    Point out to them that, by their argument "we assume a list of all real numbers, so it's impossible to construct a number not on the list", you could also prove that the only color is black, since assuming that black is the only color we cannot find another one. If that doesn't work then they don't understand logic and will never be convinced of anything.
    $endgroup$
    – Ryan Reich
    Oct 15 '13 at 15:42






  • 7




    $begingroup$
    I think that you may need to more clearly distinguish between the "Set of all Reals" and a "List of all Reals". The point of Cantor's proof is that there is such a set, but there cannot be such a list.
    $endgroup$
    – RBarryYoung
    Oct 15 '13 at 21:24
















53












$begingroup$


I occasionally have the opportunity to argue with anti-Cantor cranks, people who for some reason or the other attack the validity of Cantor's diagonalization proof of the uncountability of the real numbers, arguably one of the most beautiful ideas in mathematics. They usually make the same sorts of arguments, so years ago I wrote up this FAQ to deal with them. Unfortunately, it's still hard to get anywhere with these people; the discussion frequently turns into something of this form:



ME: Suppose there is an ordered list containing all the real numbers. Then we can read off the diagonal entries and construct a real number that differs in the Nth decimal place from the Nth real number on the list. This real number obviously cannot be in the list. So the list doesn't contain all the real numbers.



THEM: Of course your proposed number is not on the list; it's not a well-defined real number.



ME: What do you mean? I gave you the exact procedure for constructing it. You take the Nth real number on the list, and you make it differ from that number in the Nth decimal place.



THEM: But if we really have a list of all the real numbers, then your proposed number has to be somewhere in the list, right?



ME: Yes, of course, so let's say it's in the 57th place. Then it would have to differ from itself in the 57th place, which is impossible!



THEM: Exactly, it's impossible! Your definition requires that it differs in some place from itself, which is impossible, so your definition is bad.



ME: But you're only saying that it's impossible on the basis of the assumption that there's a complete list of real numbers, and the whole point is to disprove that assumption.



THEM: But we're doing this proof under that assumption, so how can we make a definition that runs contrary to that assumption?



ME: But that definition is a good one regardless of whether there are countably or uncountably many reals. It is a complete, algorithmic, unambiguous specification of the real number. What else could you want?



THEM: I want the definition to be both unambiguous and non-contradictory, and your definition is contradictory!



ME: Forget about the purported complete lists of real numbers for a moment. Don't you agree that for any list of real numbers, complete or incomplete, it's possible to construct a real number that differs in the Nth place from the Nth number on the list?



THEM: No, it's only possible to construct such a real number if that real number isn't on the list, otherwise it's a contradictory definition.



ME: Don't you see that the contradiction is not the fault of my perfectly good definition, but rather the fault of your assumption that there are countably many real numbers?



THEM: No, I don't.



ME: But what if we took our putative complete list of real numbers, and fed it in line by line into a computer with an algorithm that spits out, digit by digit, a real number that differs in the Nth digit from the Nth number on the list? Would such a computer program work?



THEM: No it wouldn't, the computer program would hit the place on the list where the number being constructed would reside, and then it would get crash, because it can't choose a digit for the number that differs in the nth place from itself.



ME: Argh!



So how do I stop going in circles and convince them that they're wrong?



Any help would be greatly appreciated.



Thank You in Advance.






elementary-set-theory soft-question cardinals education infinity







share|cite|improve this question











$endgroup$








  • 72




    $begingroup$
    If they are true cranks, give up. Ain't gonna happen.
    $endgroup$
    – Ross Millikan
    Oct 15 '13 at 15:30






  • 10




    $begingroup$
    I only discussed with anti-Cantorians after I had uttered a discouraging word to a student. Serving my penance, you see.
    $endgroup$
    – Jyrki Lahtonen
    Oct 15 '13 at 15:36








  • 15




    $begingroup$
    Your biggest problem with this hypothetical anti-Cantor crank is that E seems to not understand proof by contradiction. I guess there should be some overlap between Cantor-truthers and people who don't understand contradiction, but my experience has been that the problem is usually more along the lines of not understanding the relationship between "sets", "lists", and "countable". Discomfort with contradiction is a separate issue that should be straightened out in a calmer setting, not in a case where the result is so unintuitive.
    $endgroup$
    – Eric Stucky
    Oct 15 '13 at 15:41








  • 23




    $begingroup$
    Point out to them that, by their argument "we assume a list of all real numbers, so it's impossible to construct a number not on the list", you could also prove that the only color is black, since assuming that black is the only color we cannot find another one. If that doesn't work then they don't understand logic and will never be convinced of anything.
    $endgroup$
    – Ryan Reich
    Oct 15 '13 at 15:42






  • 7




    $begingroup$
    I think that you may need to more clearly distinguish between the "Set of all Reals" and a "List of all Reals". The point of Cantor's proof is that there is such a set, but there cannot be such a list.
    $endgroup$
    – RBarryYoung
    Oct 15 '13 at 21:24














53












53








53


26



$begingroup$


I occasionally have the opportunity to argue with anti-Cantor cranks, people who for some reason or the other attack the validity of Cantor's diagonalization proof of the uncountability of the real numbers, arguably one of the most beautiful ideas in mathematics. They usually make the same sorts of arguments, so years ago I wrote up this FAQ to deal with them. Unfortunately, it's still hard to get anywhere with these people; the discussion frequently turns into something of this form:



ME: Suppose there is an ordered list containing all the real numbers. Then we can read off the diagonal entries and construct a real number that differs in the Nth decimal place from the Nth real number on the list. This real number obviously cannot be in the list. So the list doesn't contain all the real numbers.



THEM: Of course your proposed number is not on the list; it's not a well-defined real number.



ME: What do you mean? I gave you the exact procedure for constructing it. You take the Nth real number on the list, and you make it differ from that number in the Nth decimal place.



THEM: But if we really have a list of all the real numbers, then your proposed number has to be somewhere in the list, right?



ME: Yes, of course, so let's say it's in the 57th place. Then it would have to differ from itself in the 57th place, which is impossible!



THEM: Exactly, it's impossible! Your definition requires that it differs in some place from itself, which is impossible, so your definition is bad.



ME: But you're only saying that it's impossible on the basis of the assumption that there's a complete list of real numbers, and the whole point is to disprove that assumption.



THEM: But we're doing this proof under that assumption, so how can we make a definition that runs contrary to that assumption?



ME: But that definition is a good one regardless of whether there are countably or uncountably many reals. It is a complete, algorithmic, unambiguous specification of the real number. What else could you want?



THEM: I want the definition to be both unambiguous and non-contradictory, and your definition is contradictory!



ME: Forget about the purported complete lists of real numbers for a moment. Don't you agree that for any list of real numbers, complete or incomplete, it's possible to construct a real number that differs in the Nth place from the Nth number on the list?



THEM: No, it's only possible to construct such a real number if that real number isn't on the list, otherwise it's a contradictory definition.



ME: Don't you see that the contradiction is not the fault of my perfectly good definition, but rather the fault of your assumption that there are countably many real numbers?



THEM: No, I don't.



ME: But what if we took our putative complete list of real numbers, and fed it in line by line into a computer with an algorithm that spits out, digit by digit, a real number that differs in the Nth digit from the Nth number on the list? Would such a computer program work?



THEM: No it wouldn't, the computer program would hit the place on the list where the number being constructed would reside, and then it would get crash, because it can't choose a digit for the number that differs in the nth place from itself.



ME: Argh!



So how do I stop going in circles and convince them that they're wrong?



Any help would be greatly appreciated.



Thank You in Advance.






elementary-set-theory soft-question cardinals education infinity







share|cite|improve this question











$endgroup$




I occasionally have the opportunity to argue with anti-Cantor cranks, people who for some reason or the other attack the validity of Cantor's diagonalization proof of the uncountability of the real numbers, arguably one of the most beautiful ideas in mathematics. They usually make the same sorts of arguments, so years ago I wrote up this FAQ to deal with them. Unfortunately, it's still hard to get anywhere with these people; the discussion frequently turns into something of this form:



ME: Suppose there is an ordered list containing all the real numbers. Then we can read off the diagonal entries and construct a real number that differs in the Nth decimal place from the Nth real number on the list. This real number obviously cannot be in the list. So the list doesn't contain all the real numbers.



THEM: Of course your proposed number is not on the list; it's not a well-defined real number.



ME: What do you mean? I gave you the exact procedure for constructing it. You take the Nth real number on the list, and you make it differ from that number in the Nth decimal place.



THEM: But if we really have a list of all the real numbers, then your proposed number has to be somewhere in the list, right?



ME: Yes, of course, so let's say it's in the 57th place. Then it would have to differ from itself in the 57th place, which is impossible!



THEM: Exactly, it's impossible! Your definition requires that it differs in some place from itself, which is impossible, so your definition is bad.



ME: But you're only saying that it's impossible on the basis of the assumption that there's a complete list of real numbers, and the whole point is to disprove that assumption.



THEM: But we're doing this proof under that assumption, so how can we make a definition that runs contrary to that assumption?



ME: But that definition is a good one regardless of whether there are countably or uncountably many reals. It is a complete, algorithmic, unambiguous specification of the real number. What else could you want?



THEM: I want the definition to be both unambiguous and non-contradictory, and your definition is contradictory!



ME: Forget about the purported complete lists of real numbers for a moment. Don't you agree that for any list of real numbers, complete or incomplete, it's possible to construct a real number that differs in the Nth place from the Nth number on the list?



THEM: No, it's only possible to construct such a real number if that real number isn't on the list, otherwise it's a contradictory definition.



ME: Don't you see that the contradiction is not the fault of my perfectly good definition, but rather the fault of your assumption that there are countably many real numbers?



THEM: No, I don't.



ME: But what if we took our putative complete list of real numbers, and fed it in line by line into a computer with an algorithm that spits out, digit by digit, a real number that differs in the Nth digit from the Nth number on the list? Would such a computer program work?



THEM: No it wouldn't, the computer program would hit the place on the list where the number being constructed would reside, and then it would get crash, because it can't choose a digit for the number that differs in the nth place from itself.



ME: Argh!



So how do I stop going in circles and convince them that they're wrong?



Any help would be greatly appreciated.



Thank You in Advance.






elementary-set-theory soft-question cardinals education infinity




elementary-set-theory soft-question cardinals education infinity






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Oct 15 '13 at 15:51







Keshav Srinivasan

















asked Oct 15 '13 at 15:25









Keshav SrinivasanKeshav Srinivasan

2,05311442




2,05311442








  • 72




    $begingroup$
    If they are true cranks, give up. Ain't gonna happen.
    $endgroup$
    – Ross Millikan
    Oct 15 '13 at 15:30






  • 10




    $begingroup$
    I only discussed with anti-Cantorians after I had uttered a discouraging word to a student. Serving my penance, you see.
    $endgroup$
    – Jyrki Lahtonen
    Oct 15 '13 at 15:36








  • 15




    $begingroup$
    Your biggest problem with this hypothetical anti-Cantor crank is that E seems to not understand proof by contradiction. I guess there should be some overlap between Cantor-truthers and people who don't understand contradiction, but my experience has been that the problem is usually more along the lines of not understanding the relationship between "sets", "lists", and "countable". Discomfort with contradiction is a separate issue that should be straightened out in a calmer setting, not in a case where the result is so unintuitive.
    $endgroup$
    – Eric Stucky
    Oct 15 '13 at 15:41








  • 23




    $begingroup$
    Point out to them that, by their argument "we assume a list of all real numbers, so it's impossible to construct a number not on the list", you could also prove that the only color is black, since assuming that black is the only color we cannot find another one. If that doesn't work then they don't understand logic and will never be convinced of anything.
    $endgroup$
    – Ryan Reich
    Oct 15 '13 at 15:42






  • 7




    $begingroup$
    I think that you may need to more clearly distinguish between the "Set of all Reals" and a "List of all Reals". The point of Cantor's proof is that there is such a set, but there cannot be such a list.
    $endgroup$
    – RBarryYoung
    Oct 15 '13 at 21:24














  • 72




    $begingroup$
    If they are true cranks, give up. Ain't gonna happen.
    $endgroup$
    – Ross Millikan
    Oct 15 '13 at 15:30






  • 10




    $begingroup$
    I only discussed with anti-Cantorians after I had uttered a discouraging word to a student. Serving my penance, you see.
    $endgroup$
    – Jyrki Lahtonen
    Oct 15 '13 at 15:36








  • 15




    $begingroup$
    Your biggest problem with this hypothetical anti-Cantor crank is that E seems to not understand proof by contradiction. I guess there should be some overlap between Cantor-truthers and people who don't understand contradiction, but my experience has been that the problem is usually more along the lines of not understanding the relationship between "sets", "lists", and "countable". Discomfort with contradiction is a separate issue that should be straightened out in a calmer setting, not in a case where the result is so unintuitive.
    $endgroup$
    – Eric Stucky
    Oct 15 '13 at 15:41








  • 23




    $begingroup$
    Point out to them that, by their argument "we assume a list of all real numbers, so it's impossible to construct a number not on the list", you could also prove that the only color is black, since assuming that black is the only color we cannot find another one. If that doesn't work then they don't understand logic and will never be convinced of anything.
    $endgroup$
    – Ryan Reich
    Oct 15 '13 at 15:42






  • 7




    $begingroup$
    I think that you may need to more clearly distinguish between the "Set of all Reals" and a "List of all Reals". The point of Cantor's proof is that there is such a set, but there cannot be such a list.
    $endgroup$
    – RBarryYoung
    Oct 15 '13 at 21:24








72




72




$begingroup$
If they are true cranks, give up. Ain't gonna happen.
$endgroup$
– Ross Millikan
Oct 15 '13 at 15:30




$begingroup$
If they are true cranks, give up. Ain't gonna happen.
$endgroup$
– Ross Millikan
Oct 15 '13 at 15:30




10




10




$begingroup$
I only discussed with anti-Cantorians after I had uttered a discouraging word to a student. Serving my penance, you see.
$endgroup$
– Jyrki Lahtonen
Oct 15 '13 at 15:36






$begingroup$
I only discussed with anti-Cantorians after I had uttered a discouraging word to a student. Serving my penance, you see.
$endgroup$
– Jyrki Lahtonen
Oct 15 '13 at 15:36






15




15




$begingroup$
Your biggest problem with this hypothetical anti-Cantor crank is that E seems to not understand proof by contradiction. I guess there should be some overlap between Cantor-truthers and people who don't understand contradiction, but my experience has been that the problem is usually more along the lines of not understanding the relationship between "sets", "lists", and "countable". Discomfort with contradiction is a separate issue that should be straightened out in a calmer setting, not in a case where the result is so unintuitive.
$endgroup$
– Eric Stucky
Oct 15 '13 at 15:41






$begingroup$
Your biggest problem with this hypothetical anti-Cantor crank is that E seems to not understand proof by contradiction. I guess there should be some overlap between Cantor-truthers and people who don't understand contradiction, but my experience has been that the problem is usually more along the lines of not understanding the relationship between "sets", "lists", and "countable". Discomfort with contradiction is a separate issue that should be straightened out in a calmer setting, not in a case where the result is so unintuitive.
$endgroup$
– Eric Stucky
Oct 15 '13 at 15:41






23




23




$begingroup$
Point out to them that, by their argument "we assume a list of all real numbers, so it's impossible to construct a number not on the list", you could also prove that the only color is black, since assuming that black is the only color we cannot find another one. If that doesn't work then they don't understand logic and will never be convinced of anything.
$endgroup$
– Ryan Reich
Oct 15 '13 at 15:42




$begingroup$
Point out to them that, by their argument "we assume a list of all real numbers, so it's impossible to construct a number not on the list", you could also prove that the only color is black, since assuming that black is the only color we cannot find another one. If that doesn't work then they don't understand logic and will never be convinced of anything.
$endgroup$
– Ryan Reich
Oct 15 '13 at 15:42




7




7




$begingroup$
I think that you may need to more clearly distinguish between the "Set of all Reals" and a "List of all Reals". The point of Cantor's proof is that there is such a set, but there cannot be such a list.
$endgroup$
– RBarryYoung
Oct 15 '13 at 21:24




$begingroup$
I think that you may need to more clearly distinguish between the "Set of all Reals" and a "List of all Reals". The point of Cantor's proof is that there is such a set, but there cannot be such a list.
$endgroup$
– RBarryYoung
Oct 15 '13 at 21:24










9 Answers
9






active

oldest

votes


















67












$begingroup$

The formulation "If $f:mathbf{N} to mathbf{R}$ is an arbitrary mapping, then $f$ is not surjective" clearly fixes the original list of real numbers and sets aside the potentially combatitive issue of whether or not the list is all of $mathbf{R}$.



Significantly, the argument is no longer by contradiction, but by direct implication: The diagonal procedure constructs a real number not in the image of $f$. Perhaps this may help circumvent the sense of double-talk presumably conveyed in first positing the existence of an enumeration of $mathbf{R}$, then arguing that some infinite decimal is not on said list.






share|cite|improve this answer









$endgroup$









  • 13




    $begingroup$
    @Keshav Srinivasan: I've never really understood why some people have such difficulty with proofs by contradiction, since so many arguments in everyday life have the same form. For example, a person accused of murder might argue that he couldn't have killed 'X' because he was at a dinner party with several witnesses when 'X' was killed, so the assumption of killing 'X' contradicts his being not being able to be in two places at the same time. The same if you're a child and your mother accuses you of taking some cookies, and you've been in school all day.
    $endgroup$
    – Dave L. Renfro
    Oct 15 '13 at 19:25






  • 11




    $begingroup$
    @DaveL.Renfro That last example is regrettably incorrect. Mothers do not reason by logic :-)
    $endgroup$
    – Thomas
    Oct 16 '13 at 0:46






  • 5




    $begingroup$
    @user8921 Bridges and planes can be made to work with 64 bit floating-point numbers. No "real" numbers are involved. The role of pi is played by an actor named 3.1415926535, or similar.
    $endgroup$
    – Kaz
    Oct 16 '13 at 0:49






  • 3




    $begingroup$
    @Thomas This is because mothers are by definition always correct :)
    $endgroup$
    – Neal
    Oct 16 '13 at 1:22






  • 4




    $begingroup$
    @Kaz, very true, but on a finite stage, the role of Cantor's diagonal argument would be played by another actor with an uncanny resemblance to the infinitary Cantor diagonal argument.
    $endgroup$
    – zyx
    Oct 16 '13 at 4:31



















13












$begingroup$

An error of tactics and substance, made in that FAQ and an uncountable number of online debates of these matters, is to equate




reasonable objections to parts of the framework (including objections identical to ideas published and developed by accomplished mathematicians)




with




mistakes in digesting the proof on its own terms.




The first category, of coherent self-consistent criticisms that in some views or formalizations are correct objections, include




  • there can be no actual or completed infinity

  • proof by contradiction and/or excluded middle logic, is bad

  • there should be an effective procedure/definition for every number

  • the number of effective procedures/definitions is countable


You cannot overcome these criticisms as such. Instead, the explanation is to present Cantor's proof in a way that is compatible with the criticism either by showing that the disputed concept does not appear in the proof, or formulating the diagonalization argument as it would be stated in a finitist, constructive, predicative, computable, or definable mathematics.






share|cite|improve this answer











$endgroup$









  • 2




    $begingroup$
    The FAQ item 1 is incorrect as it implies that definable reals (or sequences) are countable. This is only true in a non-definable mathematics. If you take the FAQ's suggestion to use definable objects only, then Cantor's theorem is still correct, but one has to formulate it for a definable world. It also is not true that not accepting Platonism or infinite sets invalidates diagonalization.
    $endgroup$
    – zyx
    Oct 16 '13 at 1:27








  • 1




    $begingroup$
    The thing is, the people the FAQ is intended for are not spending their energy arguing against some narrow version of Cantor's proof about effective enumerations of computable real numbers, for instance. They're arguing against the standard proof for the Platonistic result, and they're not realizing that they reject the presuppositions which even the statement of the theorem are based on. They're willing to accept that the statement of the theorem is meaningful, they just think it happens to be false, so I'm trying to say that that's not a coherent viewpoint.
    $endgroup$
    – Keshav Srinivasan
    Oct 16 '13 at 1:36






  • 4




    $begingroup$
    It is not likely you can formulate an unassailable argument that will succeed in every case. However, where an objection consists of coherent and incoherent parts, removing the dispute about the coherent part reduces the number of things in contention, and might help clarify to the skeptic that the incoherent part is not correct. Besides that, it is misleading both to the objector and to any observers should it be done in an online forum, to not handle the coherent part as being valid.
    $endgroup$
    – zyx
    Oct 16 '13 at 1:42








  • 3




    $begingroup$
    Thank you for standing up for reason. I am baffled by the number of people in mathematics who will loudly defend straw-man tactics when they are aesthetically favorable. It would make as much sense to ban anyone without a Ph.D. from discussing the diagonalization proof, on the grounds that they do not truly understand the foundations. As beautiful as Cantor's work is, I think that what has been done with topoi is even more so. It is thus a good thing, as you point out, that we do not really have to choose—at least so long as we don't get carried away by unfair and oppositional attitudes.
    $endgroup$
    – Slade
    Oct 16 '13 at 2:26






  • 1




    $begingroup$
    @RobertFrost That is nonsense. If the system is inconsistent then everything is true in that system and hence proof by contradiction is certainly valid.
    $endgroup$
    – Tobias Kildetoft
    Jun 27 '16 at 6:53



















11












$begingroup$

You could try limiting the discussion to the finite case of Cantor's theorem as a first step. Show them that for every function $f$ on the finite set ${1,ldots,n}$ there is a subset of the domain ${1,ldots,n}$ that is not an element of $text{ran}(f)$. Show them how the construction works for some examples, say $n = 2$ and $n=3$.



If they don't accept this argument in the finite case, then challenge them to write down a counterexample $f$. If they do accept it, ask them to point out what goes wrong when $text{dom}(f)$ is $mathbb{N}$ (or an arbitrary set, although this may be too abstract for them.) At least you might be able to separate their confusion about diagonalization from their confusion about infinity.



EDIT: I am talking about the version of Cantor's theorem for sets of natural numbers rather than the version for real numbers. If they do not understand the correspondence between real numbers and sets of natural numbers, their notion of "real number" is probably not precise enough to have a reasonable discussion about Cantor's theorem.






share|cite|improve this answer











$endgroup$









  • 1




    $begingroup$
    These people usually don't know much if any set theory, so you can't really go through the proof of Cantor's theorem that the power set has a bigger cardinality with them. And in any case they're usually constructivists of some stripe, so they probably wouldn't accept the existence of the power set of N.
    $endgroup$
    – Keshav Srinivasan
    Oct 15 '13 at 16:22






  • 1




    $begingroup$
    @KeshavSrinivasan I appreciate your point, but I was hoping that they would be able to deal with the set theory in the finite case. Also, I purposefully phrased my answer so as not to mention the power set of $mathbb{N}$, and not to rely on the power set axiom at all. If they don't accept the collection of all subsets of $mathbb{N}$ as a class, then I don't see what they could possibly construe the real numbers to be.
    $endgroup$
    – Trevor Wilson
    Oct 15 '13 at 16:27






  • 6




    $begingroup$
    @KeshavSrinivasan Then maybe they are right, and there really are only countably many points on the number line ;-) You have to commit to some formal definition of the real numbers for Cantor's theorem to be a theorem, and if they understand this formal definition, then they should be able to understand how real numbers correspond to sets of natural numbers. If they don't, then you have a more fundamental problem to deal with first.
    $endgroup$
    – Trevor Wilson
    Oct 15 '13 at 16:34






  • 2




    $begingroup$
    @KeshavSrinivasan But what if they are requiring the real numbers to be computable, but are not requiring the function $f : mathbb{N} to mathbb{R}$ to be computable? My point is just that if you expect to convince them that you are right and they are wrong, then first you should fix precisely a context where this is true, and make sure they know what it is. If they have a precise understanding of "infinite decimal", they must also have a precise understanding of "set of natural numbers".
    $endgroup$
    – Trevor Wilson
    Oct 15 '13 at 17:11






  • 2




    $begingroup$
    ...I'm not saying they need to accept arbitrary sets; we can restrict our attention to the case where the domain of $f$ is either a natural number or $mathbb{N}$ itself.
    $endgroup$
    – Trevor Wilson
    Oct 15 '13 at 17:11



















6












$begingroup$

The conversation seems almost equivalent to this hypothetical one about the irrationality of $sqrt 2$:



ME: Suppose there are positive integers $m$, $n$ such that $m^2=2n^2$. Then we can generate a list of all prime factors and read off the exponent of $2$. This exponent should be even (because it is in the unique factorization of $m^2$) but also odd (because it is in the unique factorization of $2n^2$) so the equalilty cannot hold for any $m,n$.



THEM: Of course your proposed exponent cannot exist; it's not a well-defined integer.



ME: What do you mean? I gave you the exact procedure for constructing it: factorize that number. Check the factorization theorem.



THEM: But if we really have a list of prime factors then factor 2 has to have some exponent, right?



ME: Yes, of course, so let's say it's 57. Then it is odd and it would be also the double of an integer, that is impossible.



THEM: Exactly, it's impossible! Your definition of the exponent requires that it is both odd and even, which is impossible, so your definition is bad.



ME: But you're only saying that it's impossible on the basis of the assumption that the equality $m^2=2n^2$ holds for some positive integers $m$ and $n$, and the whole point is to disprove that assumption.



THEM: But we're doing this proof under that assumption, so how can we make a definition that runs contrary to that assumption?



ME: But that definition is a good one regardless of whether the assumption is true or false. It is a complete, algorithmic, unambiguous specification of an integer (the exponent of 2 in the unique prime factorization). What else could you want?



THEM: I want the definition to be both unambiguous and non-contradictory, and your definition is contradictory!



ME: Forget about the equality to be disproved for a moment. Don't you agree that for any number it's possible to construct a prime factorization and define the exponent of $2$?



THEM: No, it's only possible to define such an exponent if the number $a$ to be factorized is not such that $a=m^2=2n^2$, otherwise it's a contradictory definition.



ME: Don't you see that the contradiction is not the fault of my perfectly good definition, but rather the fault of your assumption that $m^2=2n^2$?



THEM: No, I don't.



ME: But what if we took our putative number $a=m^2=2n^2$, and fed it into a computer with an algorithm that spits the exponent of $2$ in the prime factorization? Would such a computer program work?



THEM: No it wouldn't, the computer program would hit the place on the list where the exponent of $2$ would be computed and then it would get crash, because it can't produce a number that is both odd and even.






share|cite|improve this answer











$endgroup$













  • $begingroup$
    Interesting, can you spell out the proof that the square root of 2 is irrational using the exponent of 2? I've never seen that proof. I've only seen the conventional proof where you assume it's in simplest form and get a simpler form, or equivalently you construct an infinite descending sequence of natural numbers by continually dividing by 2.
    $endgroup$
    – Keshav Srinivasan
    Apr 30 '16 at 20:08












  • $begingroup$
    But yeah, you seem to have constructed an analogous situation to the one I keep encountering with anti-Cantor cranks. So how would you explain to them the error in their reasoning in your case, and in my case?
    $endgroup$
    – Keshav Srinivasan
    Apr 30 '16 at 20:09












  • $begingroup$
    It's very simple: $m^2$ must have an even exponent of $2$ in the prime factorization, $2n^2$ must have an odd exponent of $2$
    $endgroup$
    – Marco Disce
    Apr 30 '16 at 20:14










  • $begingroup$
    OK yeah, that makes sense, thanks. So how would you respond to the "them" in the dialogue?
    $endgroup$
    – Keshav Srinivasan
    Apr 30 '16 at 20:18






  • 3




    $begingroup$
    Here also you can argue contrapositively, without making the initial controversial hypothesis: Let $m$ and $n$ be arbitrary positive integers. Each of $m^{2}$ and $2n^{2}$ factors uniquely into primes. However, the exponent of $2$ in $m^{2}$ is even, while the exponent of $2$ in $2n^{2}$ is odd. Since no integer is both even and odd, the factorizations of $m^{2}$ and $2n^{2}$ are distinct, and consequently $m^{2} neq 2n^{2}$. Needless to say, I prefer this to "descent-type" arguments. :)
    $endgroup$
    – Andrew D. Hwang
    May 1 '16 at 13:39



















5












$begingroup$

It's not a proof, but in this situation it is reasonable to be like cranky student. When I say that his algorithm is wrong he can't agree until I show him any counterexample. So you can just ask your opponents to give you method of constructing such list. And you would always be able to show that list is incomplete:)



Anyway there are several different ways to prove that set of real numbers is uncountable. Are all of them rejected by your cranks?






share|cite|improve this answer









$endgroup$









  • 2




    $begingroup$
    Ok, then you are just lucky they don't claim that set of integers is finite:)
    $endgroup$
    – Smylic
    Oct 16 '13 at 1:03






  • 1




    $begingroup$
    Well, sometimes the cranks have a claim that they have constructed a complete list of real numbers, but a lot of the time they just reject Cantor's claim that such a list cannot exist, as opposed to making an affirmative claim on their part. Or they cite a reason that the real numbers are countable, but that reason does not actually give you a procedure for making a complete list of real numbers. And yes, there are other proofs of uncountability, but for instance you need a fair amount of math background for the proof that a perfect set is uncountable, whereas Cantor requires little.
    $endgroup$
    – Keshav Srinivasan
    Oct 16 '13 at 1:03






  • 5




    $begingroup$
    I was 13 when I got to know about 5 different proofs and had understood all of them. I think the following is not too hard. Consider a numbered list of all real numbers of $[0, 1]$. Let cover $i$th of them by open interval of length $3^{-i}$. Since each point is inside its own inteval (which has positive length) then is should be covered by at least one inteval. But cumulative length of all invervals is $frac12$, so union of them all can't cover all points of $[0, 1]$.
    $endgroup$
    – Smylic
    Oct 16 '13 at 1:13










  • $begingroup$
    Why wouldn't that proof show equally well that there are uncountably many rational numbers between $0$ and $1$?
    $endgroup$
    – Keshav Srinivasan
    Oct 16 '13 at 5:12






  • 2




    $begingroup$
    Not every point of $[0, 1]$ is rational, so covering every rational point doesn't mean covering every point and the whole segment.
    $endgroup$
    – Smylic
    Oct 16 '13 at 15:32



















4












$begingroup$

Instead of entering a discussion about the proof for real numbers, I would propose discussing instead the abstract version, which gives far less opportunity for polemic. Let the "crank" decide what he thinks about the abstract version and its proof, and then see where to go from there. If he refuses the abstract version, he should either be able to find fault with the proof, or accept being inconsistent (if finding no fault in the proof but still rejecting the conclusion). When accepting the abstract version one can still refuse application for the real numbers (for instance by denying the existence of infinite sets, or maybe accepting existence of the natural numbers but not of their power set), but it forces one to draw a line somewhere; once this is done there is really nothing left to discuss. For reference, here it is:



Proposition. For every set $X$ and every map $defP{mathcal P}f:XtoP(X)$ there exists $Y_finP(X)$ such that for all $xin X$ one has $Y_fneq f(x)$.



Proof. Take $Y_f={, zin Xmid znotin f(z),}$. For $xin Y_f$ one has $xnotin f(x)$ so $Y_fneq f(x)$. For $xin X$ with $xnotin Y_f$ one has $xin f(x)$, so $Y_fneq f(x)$. This establishes $Y_fneq f(x)$ for all $xin X$.






share|cite|improve this answer











$endgroup$









  • 1




    $begingroup$
    The problem is, these people usually don't know much if any set theory, so you can't really go through the proof of Cantor's theorem that the power set has a bigger cardinality with them. Cantor's diagonal proof of the uncountability of the reals is usually the only proof they can comprehend.
    $endgroup$
    – Keshav Srinivasan
    Feb 19 '14 at 15:13










  • $begingroup$
    @KeshavSrinivasan: Apperently you are complaining it is just another proof they cannot comprehend. Note that the only "set theory" really used is that one can define a subset by telling which elements to keep and which ones not to keep. You can view sets as lists of their elements if you like, and get close to the traditional diagonal, without having to bother about reals. I think if they cannot comprehend maps from a set to its power set, there is really no point in discussing countability of real numbers with them in the first place.
    $endgroup$
    – Marc van Leeuwen
    Feb 19 '14 at 15:30












  • $begingroup$
    If they learned enough set theory, they'd probably abandon their objections to Cantor's diagonal proof anyway. But in any case, I suppose the objection I described in my question could be carried over to the Cantor's theorem case: they would say that the definition of $Y_f$ doesn't make sense in the case when $f$ is surjective, and that the contradiction you get in the case when $f$ is surjective indicates that $Y_f$ does not exist, not that $f$ is not surjective. The fundamental problem with these people is that they're misattributing the source of the contradiction.
    $endgroup$
    – Keshav Srinivasan
    Feb 19 '14 at 15:39






  • 1




    $begingroup$
    @byserpas I don't understand at all what you want to say. It is not that restricted comprehension forbids you to have a universal set; rather it would require another axiom, namely unrestricted comprehension, to have a universal set. But then you get the Russell paradox and an inconsistent theory. Also any diagonal argument is essentially about a power set or something very similar like digit strings (mapping natural numbers to ${0,1,ldots,9}$ is very similar to mapping them to ${mathrm{false},mathrm{true}}$).
    $endgroup$
    – Marc van Leeuwen
    May 8 '15 at 6:03








  • 1




    $begingroup$
    @byserpas If there is only one set, then you've got no set theory (in the sense that you can only formulate statements that are trivially true or false). You need no other axioms than something "there is no $x$ but $A$, and $xin A$ if and only $x=A$". You won't have any constructions like powerset (though you can give any name you like to the construction that always produces $A$), no natural numbers, no reals, no diagonal argument, nothing. It is an utterly boring enterprise. Go try to sell it to somebody as set theory, but don't waste our time with it.
    $endgroup$
    – Marc van Leeuwen
    May 8 '15 at 8:47





















3












$begingroup$

Cantor's proof is not about numbers at all (there is a problem with trying to use it on numbers), it is about infinite strings of two characters. See http://www.logicmuseum.com/cantor/diagarg.htm.



Call them Cantor Strings. Cantor used "M" and "W" which, while they are visually interesting, are hard to distinguish. You can use "0" and "1" and claim they represent fractions in binary representation, but there is a problem. For example, 5/16 has two such binary representations: 0.01010000... and 0.01001111... . So you can't claim a number is missing, if all you prove is that a string is missing.



Ignoring this fault, as most treatments do, your very first statement is not what Cantor does "ME: Suppose there is an ordered list containing all the (Cantor Strings)." The first step of Cantor's Proof is "Consider ANY list that links every natural number to a unique Cantor String." Nowhere is it assumed that this means all Cantor Strings.



In fact, diagonalization proves the opposite. It proves: "If you have a set of Cantor Stings that can be listed this way, then it does not include all Cantor Strings."



It is a simple trick of logic to invert the statement "If A, then B" to get the 100% equivalent statement "If NOT B, then NOT A." So diagonalization also proves "If you have a set of all Cantor Strings, then it can't be listed this way."



Elegant, no?



The reason so many Anti-Cantor cranks exists, is because we don;t seem to teach Cantor's proof correctly.






share|cite|improve this answer











$endgroup$









  • 1




    $begingroup$
    I actually make the point that you're making later on in the dialogue; look at where it says "Forget about the purported complete lists of real numbers for a moment..." The problem is, when I phrase the proof that way, the cranks' retort is that they do not think that the diagonalization procedure will always work in constructing a well-defined real number (or infinite string if you prefer). They think that the diagonalization procedure is not well-defined if you start with a list that happens to be complete. The problem is that they're misdiagnosing the source of the contradiction.
    $endgroup$
    – Keshav Srinivasan
    Apr 16 '16 at 20:27












  • $begingroup$
    I'd agree, if you you'd said "They think that the diagonalization procedure is not well-defined if you start with a list that happens to be INFINITE." The two are not the same, and I do feel it is the "infinite" part that confuses them. Not the "complete" part.
    $endgroup$
    – JeffJo
    Apr 17 '16 at 19:09












  • $begingroup$
    No, they're fine with infinite lists. Like if you start with an infinite list of the form .0111111... then .1011111... then .1101111... etc., they think diagonalization is a well-defined procedure. But they think that if the list happens to be complete, then the diagonalization process is not well-defined. That's because if the list was complete and the diagonalization procedure was well-defined, then the number being constructed would be somewhere in the list, say the Nth spot. And then Nth digit of that number would be ill-defined, because it's required to differ from itself.
    $endgroup$
    – Keshav Srinivasan
    Apr 17 '16 at 19:51










  • $begingroup$
    So they think that the diagonalization process is only well-defined for those lists which do not contain the number which would be constructed through diagonalization. Like I said, the problem is that they're misdiagnosing the source of the contradiction. They don't understand that the diagonalization process is well-defined for all lists.
    $endgroup$
    – Keshav Srinivasan
    Apr 17 '16 at 19:54










  • $begingroup$
    And I think that their difficulty comes when they try to correlate the infinite length of the strings, to the infinite length of the assumed "complete" list. The question they have - the one behind the imagined contradiction you describe - is "If the list is infinite, how can it not contain all possible strings?" The answer is that you can correlate two infinities in more than one way, and some ways miss elements of one..
    $endgroup$
    – JeffJo
    Apr 18 '16 at 13:56



















2












$begingroup$

I think the only way would be to find a different proof that holds against the main concern of the typical objections:

Does the constructed number actually exist?



I'll try to illustrate a proof that can address this concern.

Let's consider lists of real numbers written in base 10 and build a number from the list using this rule:




If the n^th digit of the n^th number of the list is 1, we change it to 2, otherwise we change it to 1.




We're assuming the list is made of infinite rows; if not, we could always repeat the same numbers from the beginning in the same order and get our new number.

Let's give a name to numbers that can be obtained from lists with this particular rule: if I wanted to be specific, I would call them something like "(1->2)(else->1) diagonals", but for the sake of brevity i'll call them diagonals.

Any real with some digit different than 1 or 2 is not diagonal.

If a real only has ones and twos, it could be diagonal.



Note that if reals are countable, both diagonals and not diagonals are countable (as you could just list them in the order you found for the reals)



Now, what if we listed all the not diagonals?
From where we are, we couldn't immediately conclude that the not diagonals are uncountable, since the diagonal number of the list of course wouldn't be in the list of not diagonal numbers.

But it exists: it's something made of just ones and twos. probably more ones.

So, there are diagonal numbers: you can easily imagine them in this setting.



But, what if we listed all diagonal numbers?



It's a list, so it has a diagonal number, not in the list by construction.

But it's a list of diagonals: it should have its diagonal number.
So, usual argument, usual contradiction, just in a slightly different setting: in here, you can conclude that diagonal numbers aren't countable, but you can't say the same about not diagonal numbers. (at least, not immediately)
But it doesn't matter, because the real numbers are made of diagonals and not diagonals, and if diagonals are not countable, neither are real numbers!



So, my hope is that this argument could break the chain a bit, since it does provide a list of real numbers that doesn't contain its diagonal (the not diagonals), which you don't need to prove are uncountable, but also a list of real numbers that, if it existed, it couldn't contain its diagonal nor not contain it.

Basically, good cop and bad cop i guess? Except with lists.






share|cite|improve this answer









$endgroup$













  • $begingroup$
    I think they would still make the same objection I discuss in my question: they would say that it's possible to construct a diagonal for the list of all non-diagonals, but it's impossible to construct a diagonal for the list of all diagonals. And their reasoning would be that if the diagonal for the list of diagonals did exist, then it would have to differ from itself, which is impossible. Therefore, the list of diagonals can't have a diagonal. The fundamental problem is that they don't realize that taking the diagonal is a valid operation for all lists.
    $endgroup$
    – Keshav Srinivasan
    May 7 '15 at 20:23










  • $begingroup$
    Well, the arguments in the essence are the same, so yes, it's likely things wouldn't change at all. But, sometimes a minimal superficial change can trigger a different reaction, even if the math behind it is the same... I mean, the reasoning to get is that one, there's no way around it. One can only arrange the same arguments in a different fashion, so that the counterarguments can fall in a different way until they hopefully unclick by themselves.
    $endgroup$
    – byserpas
    May 7 '15 at 20:43



















-2












$begingroup$

First off, there are formally verified proofs of the theorem. In fact, every major theorem proof system or proof explorer has proved it, and it is number 22 in the classic "100 theorems" benchmark: http://www.cs.ru.nl/~freek/100/



The problem is one may not accept the axioms and rules of inference.



However, that is not the only problem. One may not even accept the statement as it is stated. I will show an alternative statement, which may be what the cranks have in mind.



Consider a Gödel numbering or any similar scheme from the naturals to the formulas of set theory. Clearly, this numbering lists all the possible formulas of set theory.



Since real numbers are merely formulas of set theory, the encoding will define every real number. This last statement is bound to be controversial, but nonetheless it's a valid definition of what it means to be a real number and your cranky friends could be utilizing it. (In fact, if I am understanding Asaf correctly, interestingly enough, this is the usual definition: Undefinable Real Numbers )



No idea why this got a down-vote and a delete request. The point was not brought forward in the previous answers and is based on Hamkin's answer: https://mathoverflow.net/questions/44102/is-the-analysis-as-taught-in-universities-in-fact-the-analysis-of-definable-numb#answer-44129



Simply substitute definable real number in place of real number and the diagonalization proof no longer works. Note that each real number may be definable.






share|cite|improve this answer











$endgroup$












    protected by user642796 Feb 19 '14 at 8:28



    Thank you for your interest in this question.
    Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).



    Would you like to answer one of these unanswered questions instead?














    9 Answers
    9






    active

    oldest

    votes








    9 Answers
    9






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    67












    $begingroup$

    The formulation "If $f:mathbf{N} to mathbf{R}$ is an arbitrary mapping, then $f$ is not surjective" clearly fixes the original list of real numbers and sets aside the potentially combatitive issue of whether or not the list is all of $mathbf{R}$.



    Significantly, the argument is no longer by contradiction, but by direct implication: The diagonal procedure constructs a real number not in the image of $f$. Perhaps this may help circumvent the sense of double-talk presumably conveyed in first positing the existence of an enumeration of $mathbf{R}$, then arguing that some infinite decimal is not on said list.






    share|cite|improve this answer









    $endgroup$









    • 13




      $begingroup$
      @Keshav Srinivasan: I've never really understood why some people have such difficulty with proofs by contradiction, since so many arguments in everyday life have the same form. For example, a person accused of murder might argue that he couldn't have killed 'X' because he was at a dinner party with several witnesses when 'X' was killed, so the assumption of killing 'X' contradicts his being not being able to be in two places at the same time. The same if you're a child and your mother accuses you of taking some cookies, and you've been in school all day.
      $endgroup$
      – Dave L. Renfro
      Oct 15 '13 at 19:25






    • 11




      $begingroup$
      @DaveL.Renfro That last example is regrettably incorrect. Mothers do not reason by logic :-)
      $endgroup$
      – Thomas
      Oct 16 '13 at 0:46






    • 5




      $begingroup$
      @user8921 Bridges and planes can be made to work with 64 bit floating-point numbers. No "real" numbers are involved. The role of pi is played by an actor named 3.1415926535, or similar.
      $endgroup$
      – Kaz
      Oct 16 '13 at 0:49






    • 3




      $begingroup$
      @Thomas This is because mothers are by definition always correct :)
      $endgroup$
      – Neal
      Oct 16 '13 at 1:22






    • 4




      $begingroup$
      @Kaz, very true, but on a finite stage, the role of Cantor's diagonal argument would be played by another actor with an uncanny resemblance to the infinitary Cantor diagonal argument.
      $endgroup$
      – zyx
      Oct 16 '13 at 4:31
















    67












    $begingroup$

    The formulation "If $f:mathbf{N} to mathbf{R}$ is an arbitrary mapping, then $f$ is not surjective" clearly fixes the original list of real numbers and sets aside the potentially combatitive issue of whether or not the list is all of $mathbf{R}$.



    Significantly, the argument is no longer by contradiction, but by direct implication: The diagonal procedure constructs a real number not in the image of $f$. Perhaps this may help circumvent the sense of double-talk presumably conveyed in first positing the existence of an enumeration of $mathbf{R}$, then arguing that some infinite decimal is not on said list.






    share|cite|improve this answer









    $endgroup$









    • 13




      $begingroup$
      @Keshav Srinivasan: I've never really understood why some people have such difficulty with proofs by contradiction, since so many arguments in everyday life have the same form. For example, a person accused of murder might argue that he couldn't have killed 'X' because he was at a dinner party with several witnesses when 'X' was killed, so the assumption of killing 'X' contradicts his being not being able to be in two places at the same time. The same if you're a child and your mother accuses you of taking some cookies, and you've been in school all day.
      $endgroup$
      – Dave L. Renfro
      Oct 15 '13 at 19:25






    • 11




      $begingroup$
      @DaveL.Renfro That last example is regrettably incorrect. Mothers do not reason by logic :-)
      $endgroup$
      – Thomas
      Oct 16 '13 at 0:46






    • 5




      $begingroup$
      @user8921 Bridges and planes can be made to work with 64 bit floating-point numbers. No "real" numbers are involved. The role of pi is played by an actor named 3.1415926535, or similar.
      $endgroup$
      – Kaz
      Oct 16 '13 at 0:49






    • 3




      $begingroup$
      @Thomas This is because mothers are by definition always correct :)
      $endgroup$
      – Neal
      Oct 16 '13 at 1:22






    • 4




      $begingroup$
      @Kaz, very true, but on a finite stage, the role of Cantor's diagonal argument would be played by another actor with an uncanny resemblance to the infinitary Cantor diagonal argument.
      $endgroup$
      – zyx
      Oct 16 '13 at 4:31














    67












    67








    67





    $begingroup$

    The formulation "If $f:mathbf{N} to mathbf{R}$ is an arbitrary mapping, then $f$ is not surjective" clearly fixes the original list of real numbers and sets aside the potentially combatitive issue of whether or not the list is all of $mathbf{R}$.



    Significantly, the argument is no longer by contradiction, but by direct implication: The diagonal procedure constructs a real number not in the image of $f$. Perhaps this may help circumvent the sense of double-talk presumably conveyed in first positing the existence of an enumeration of $mathbf{R}$, then arguing that some infinite decimal is not on said list.






    share|cite|improve this answer









    $endgroup$



    The formulation "If $f:mathbf{N} to mathbf{R}$ is an arbitrary mapping, then $f$ is not surjective" clearly fixes the original list of real numbers and sets aside the potentially combatitive issue of whether or not the list is all of $mathbf{R}$.



    Significantly, the argument is no longer by contradiction, but by direct implication: The diagonal procedure constructs a real number not in the image of $f$. Perhaps this may help circumvent the sense of double-talk presumably conveyed in first positing the existence of an enumeration of $mathbf{R}$, then arguing that some infinite decimal is not on said list.







    share|cite|improve this answer












    share|cite|improve this answer



    share|cite|improve this answer










    answered Oct 15 '13 at 16:01









    Andrew D. HwangAndrew D. Hwang

    52.7k447112




    52.7k447112








    • 13




      $begingroup$
      @Keshav Srinivasan: I've never really understood why some people have such difficulty with proofs by contradiction, since so many arguments in everyday life have the same form. For example, a person accused of murder might argue that he couldn't have killed 'X' because he was at a dinner party with several witnesses when 'X' was killed, so the assumption of killing 'X' contradicts his being not being able to be in two places at the same time. The same if you're a child and your mother accuses you of taking some cookies, and you've been in school all day.
      $endgroup$
      – Dave L. Renfro
      Oct 15 '13 at 19:25






    • 11




      $begingroup$
      @DaveL.Renfro That last example is regrettably incorrect. Mothers do not reason by logic :-)
      $endgroup$
      – Thomas
      Oct 16 '13 at 0:46






    • 5




      $begingroup$
      @user8921 Bridges and planes can be made to work with 64 bit floating-point numbers. No "real" numbers are involved. The role of pi is played by an actor named 3.1415926535, or similar.
      $endgroup$
      – Kaz
      Oct 16 '13 at 0:49






    • 3




      $begingroup$
      @Thomas This is because mothers are by definition always correct :)
      $endgroup$
      – Neal
      Oct 16 '13 at 1:22






    • 4




      $begingroup$
      @Kaz, very true, but on a finite stage, the role of Cantor's diagonal argument would be played by another actor with an uncanny resemblance to the infinitary Cantor diagonal argument.
      $endgroup$
      – zyx
      Oct 16 '13 at 4:31














    • 13




      $begingroup$
      @Keshav Srinivasan: I've never really understood why some people have such difficulty with proofs by contradiction, since so many arguments in everyday life have the same form. For example, a person accused of murder might argue that he couldn't have killed 'X' because he was at a dinner party with several witnesses when 'X' was killed, so the assumption of killing 'X' contradicts his being not being able to be in two places at the same time. The same if you're a child and your mother accuses you of taking some cookies, and you've been in school all day.
      $endgroup$
      – Dave L. Renfro
      Oct 15 '13 at 19:25






    • 11




      $begingroup$
      @DaveL.Renfro That last example is regrettably incorrect. Mothers do not reason by logic :-)
      $endgroup$
      – Thomas
      Oct 16 '13 at 0:46






    • 5




      $begingroup$
      @user8921 Bridges and planes can be made to work with 64 bit floating-point numbers. No "real" numbers are involved. The role of pi is played by an actor named 3.1415926535, or similar.
      $endgroup$
      – Kaz
      Oct 16 '13 at 0:49






    • 3




      $begingroup$
      @Thomas This is because mothers are by definition always correct :)
      $endgroup$
      – Neal
      Oct 16 '13 at 1:22






    • 4




      $begingroup$
      @Kaz, very true, but on a finite stage, the role of Cantor's diagonal argument would be played by another actor with an uncanny resemblance to the infinitary Cantor diagonal argument.
      $endgroup$
      – zyx
      Oct 16 '13 at 4:31








    13




    13




    $begingroup$
    @Keshav Srinivasan: I've never really understood why some people have such difficulty with proofs by contradiction, since so many arguments in everyday life have the same form. For example, a person accused of murder might argue that he couldn't have killed 'X' because he was at a dinner party with several witnesses when 'X' was killed, so the assumption of killing 'X' contradicts his being not being able to be in two places at the same time. The same if you're a child and your mother accuses you of taking some cookies, and you've been in school all day.
    $endgroup$
    – Dave L. Renfro
    Oct 15 '13 at 19:25




    $begingroup$
    @Keshav Srinivasan: I've never really understood why some people have such difficulty with proofs by contradiction, since so many arguments in everyday life have the same form. For example, a person accused of murder might argue that he couldn't have killed 'X' because he was at a dinner party with several witnesses when 'X' was killed, so the assumption of killing 'X' contradicts his being not being able to be in two places at the same time. The same if you're a child and your mother accuses you of taking some cookies, and you've been in school all day.
    $endgroup$
    – Dave L. Renfro
    Oct 15 '13 at 19:25




    11




    11




    $begingroup$
    @DaveL.Renfro That last example is regrettably incorrect. Mothers do not reason by logic :-)
    $endgroup$
    – Thomas
    Oct 16 '13 at 0:46




    $begingroup$
    @DaveL.Renfro That last example is regrettably incorrect. Mothers do not reason by logic :-)
    $endgroup$
    – Thomas
    Oct 16 '13 at 0:46




    5




    5




    $begingroup$
    @user8921 Bridges and planes can be made to work with 64 bit floating-point numbers. No "real" numbers are involved. The role of pi is played by an actor named 3.1415926535, or similar.
    $endgroup$
    – Kaz
    Oct 16 '13 at 0:49




    $begingroup$
    @user8921 Bridges and planes can be made to work with 64 bit floating-point numbers. No "real" numbers are involved. The role of pi is played by an actor named 3.1415926535, or similar.
    $endgroup$
    – Kaz
    Oct 16 '13 at 0:49




    3




    3




    $begingroup$
    @Thomas This is because mothers are by definition always correct :)
    $endgroup$
    – Neal
    Oct 16 '13 at 1:22




    $begingroup$
    @Thomas This is because mothers are by definition always correct :)
    $endgroup$
    – Neal
    Oct 16 '13 at 1:22




    4




    4




    $begingroup$
    @Kaz, very true, but on a finite stage, the role of Cantor's diagonal argument would be played by another actor with an uncanny resemblance to the infinitary Cantor diagonal argument.
    $endgroup$
    – zyx
    Oct 16 '13 at 4:31




    $begingroup$
    @Kaz, very true, but on a finite stage, the role of Cantor's diagonal argument would be played by another actor with an uncanny resemblance to the infinitary Cantor diagonal argument.
    $endgroup$
    – zyx
    Oct 16 '13 at 4:31











    13












    $begingroup$

    An error of tactics and substance, made in that FAQ and an uncountable number of online debates of these matters, is to equate




    reasonable objections to parts of the framework (including objections identical to ideas published and developed by accomplished mathematicians)




    with




    mistakes in digesting the proof on its own terms.




    The first category, of coherent self-consistent criticisms that in some views or formalizations are correct objections, include




    • there can be no actual or completed infinity

    • proof by contradiction and/or excluded middle logic, is bad

    • there should be an effective procedure/definition for every number

    • the number of effective procedures/definitions is countable


    You cannot overcome these criticisms as such. Instead, the explanation is to present Cantor's proof in a way that is compatible with the criticism either by showing that the disputed concept does not appear in the proof, or formulating the diagonalization argument as it would be stated in a finitist, constructive, predicative, computable, or definable mathematics.






    share|cite|improve this answer











    $endgroup$









    • 2




      $begingroup$
      The FAQ item 1 is incorrect as it implies that definable reals (or sequences) are countable. This is only true in a non-definable mathematics. If you take the FAQ's suggestion to use definable objects only, then Cantor's theorem is still correct, but one has to formulate it for a definable world. It also is not true that not accepting Platonism or infinite sets invalidates diagonalization.
      $endgroup$
      – zyx
      Oct 16 '13 at 1:27








    • 1




      $begingroup$
      The thing is, the people the FAQ is intended for are not spending their energy arguing against some narrow version of Cantor's proof about effective enumerations of computable real numbers, for instance. They're arguing against the standard proof for the Platonistic result, and they're not realizing that they reject the presuppositions which even the statement of the theorem are based on. They're willing to accept that the statement of the theorem is meaningful, they just think it happens to be false, so I'm trying to say that that's not a coherent viewpoint.
      $endgroup$
      – Keshav Srinivasan
      Oct 16 '13 at 1:36






    • 4




      $begingroup$
      It is not likely you can formulate an unassailable argument that will succeed in every case. However, where an objection consists of coherent and incoherent parts, removing the dispute about the coherent part reduces the number of things in contention, and might help clarify to the skeptic that the incoherent part is not correct. Besides that, it is misleading both to the objector and to any observers should it be done in an online forum, to not handle the coherent part as being valid.
      $endgroup$
      – zyx
      Oct 16 '13 at 1:42








    • 3




      $begingroup$
      Thank you for standing up for reason. I am baffled by the number of people in mathematics who will loudly defend straw-man tactics when they are aesthetically favorable. It would make as much sense to ban anyone without a Ph.D. from discussing the diagonalization proof, on the grounds that they do not truly understand the foundations. As beautiful as Cantor's work is, I think that what has been done with topoi is even more so. It is thus a good thing, as you point out, that we do not really have to choose—at least so long as we don't get carried away by unfair and oppositional attitudes.
      $endgroup$
      – Slade
      Oct 16 '13 at 2:26






    • 1




      $begingroup$
      @RobertFrost That is nonsense. If the system is inconsistent then everything is true in that system and hence proof by contradiction is certainly valid.
      $endgroup$
      – Tobias Kildetoft
      Jun 27 '16 at 6:53
















    13












    $begingroup$

    An error of tactics and substance, made in that FAQ and an uncountable number of online debates of these matters, is to equate




    reasonable objections to parts of the framework (including objections identical to ideas published and developed by accomplished mathematicians)




    with




    mistakes in digesting the proof on its own terms.




    The first category, of coherent self-consistent criticisms that in some views or formalizations are correct objections, include




    • there can be no actual or completed infinity

    • proof by contradiction and/or excluded middle logic, is bad

    • there should be an effective procedure/definition for every number

    • the number of effective procedures/definitions is countable


    You cannot overcome these criticisms as such. Instead, the explanation is to present Cantor's proof in a way that is compatible with the criticism either by showing that the disputed concept does not appear in the proof, or formulating the diagonalization argument as it would be stated in a finitist, constructive, predicative, computable, or definable mathematics.






    share|cite|improve this answer











    $endgroup$









    • 2




      $begingroup$
      The FAQ item 1 is incorrect as it implies that definable reals (or sequences) are countable. This is only true in a non-definable mathematics. If you take the FAQ's suggestion to use definable objects only, then Cantor's theorem is still correct, but one has to formulate it for a definable world. It also is not true that not accepting Platonism or infinite sets invalidates diagonalization.
      $endgroup$
      – zyx
      Oct 16 '13 at 1:27








    • 1




      $begingroup$
      The thing is, the people the FAQ is intended for are not spending their energy arguing against some narrow version of Cantor's proof about effective enumerations of computable real numbers, for instance. They're arguing against the standard proof for the Platonistic result, and they're not realizing that they reject the presuppositions which even the statement of the theorem are based on. They're willing to accept that the statement of the theorem is meaningful, they just think it happens to be false, so I'm trying to say that that's not a coherent viewpoint.
      $endgroup$
      – Keshav Srinivasan
      Oct 16 '13 at 1:36






    • 4




      $begingroup$
      It is not likely you can formulate an unassailable argument that will succeed in every case. However, where an objection consists of coherent and incoherent parts, removing the dispute about the coherent part reduces the number of things in contention, and might help clarify to the skeptic that the incoherent part is not correct. Besides that, it is misleading both to the objector and to any observers should it be done in an online forum, to not handle the coherent part as being valid.
      $endgroup$
      – zyx
      Oct 16 '13 at 1:42








    • 3




      $begingroup$
      Thank you for standing up for reason. I am baffled by the number of people in mathematics who will loudly defend straw-man tactics when they are aesthetically favorable. It would make as much sense to ban anyone without a Ph.D. from discussing the diagonalization proof, on the grounds that they do not truly understand the foundations. As beautiful as Cantor's work is, I think that what has been done with topoi is even more so. It is thus a good thing, as you point out, that we do not really have to choose—at least so long as we don't get carried away by unfair and oppositional attitudes.
      $endgroup$
      – Slade
      Oct 16 '13 at 2:26






    • 1




      $begingroup$
      @RobertFrost That is nonsense. If the system is inconsistent then everything is true in that system and hence proof by contradiction is certainly valid.
      $endgroup$
      – Tobias Kildetoft
      Jun 27 '16 at 6:53














    13












    13








    13





    $begingroup$

    An error of tactics and substance, made in that FAQ and an uncountable number of online debates of these matters, is to equate




    reasonable objections to parts of the framework (including objections identical to ideas published and developed by accomplished mathematicians)




    with




    mistakes in digesting the proof on its own terms.




    The first category, of coherent self-consistent criticisms that in some views or formalizations are correct objections, include




    • there can be no actual or completed infinity

    • proof by contradiction and/or excluded middle logic, is bad

    • there should be an effective procedure/definition for every number

    • the number of effective procedures/definitions is countable


    You cannot overcome these criticisms as such. Instead, the explanation is to present Cantor's proof in a way that is compatible with the criticism either by showing that the disputed concept does not appear in the proof, or formulating the diagonalization argument as it would be stated in a finitist, constructive, predicative, computable, or definable mathematics.






    share|cite|improve this answer











    $endgroup$



    An error of tactics and substance, made in that FAQ and an uncountable number of online debates of these matters, is to equate




    reasonable objections to parts of the framework (including objections identical to ideas published and developed by accomplished mathematicians)




    with




    mistakes in digesting the proof on its own terms.




    The first category, of coherent self-consistent criticisms that in some views or formalizations are correct objections, include




    • there can be no actual or completed infinity

    • proof by contradiction and/or excluded middle logic, is bad

    • there should be an effective procedure/definition for every number

    • the number of effective procedures/definitions is countable


    You cannot overcome these criticisms as such. Instead, the explanation is to present Cantor's proof in a way that is compatible with the criticism either by showing that the disputed concept does not appear in the proof, or formulating the diagonalization argument as it would be stated in a finitist, constructive, predicative, computable, or definable mathematics.







    share|cite|improve this answer














    share|cite|improve this answer



    share|cite|improve this answer








    edited Oct 15 '13 at 23:54

























    answered Oct 15 '13 at 23:49









    zyxzyx

    31.4k33698




    31.4k33698








    • 2




      $begingroup$
      The FAQ item 1 is incorrect as it implies that definable reals (or sequences) are countable. This is only true in a non-definable mathematics. If you take the FAQ's suggestion to use definable objects only, then Cantor's theorem is still correct, but one has to formulate it for a definable world. It also is not true that not accepting Platonism or infinite sets invalidates diagonalization.
      $endgroup$
      – zyx
      Oct 16 '13 at 1:27








    • 1




      $begingroup$
      The thing is, the people the FAQ is intended for are not spending their energy arguing against some narrow version of Cantor's proof about effective enumerations of computable real numbers, for instance. They're arguing against the standard proof for the Platonistic result, and they're not realizing that they reject the presuppositions which even the statement of the theorem are based on. They're willing to accept that the statement of the theorem is meaningful, they just think it happens to be false, so I'm trying to say that that's not a coherent viewpoint.
      $endgroup$
      – Keshav Srinivasan
      Oct 16 '13 at 1:36






    • 4




      $begingroup$
      It is not likely you can formulate an unassailable argument that will succeed in every case. However, where an objection consists of coherent and incoherent parts, removing the dispute about the coherent part reduces the number of things in contention, and might help clarify to the skeptic that the incoherent part is not correct. Besides that, it is misleading both to the objector and to any observers should it be done in an online forum, to not handle the coherent part as being valid.
      $endgroup$
      – zyx
      Oct 16 '13 at 1:42








    • 3




      $begingroup$
      Thank you for standing up for reason. I am baffled by the number of people in mathematics who will loudly defend straw-man tactics when they are aesthetically favorable. It would make as much sense to ban anyone without a Ph.D. from discussing the diagonalization proof, on the grounds that they do not truly understand the foundations. As beautiful as Cantor's work is, I think that what has been done with topoi is even more so. It is thus a good thing, as you point out, that we do not really have to choose—at least so long as we don't get carried away by unfair and oppositional attitudes.
      $endgroup$
      – Slade
      Oct 16 '13 at 2:26






    • 1




      $begingroup$
      @RobertFrost That is nonsense. If the system is inconsistent then everything is true in that system and hence proof by contradiction is certainly valid.
      $endgroup$
      – Tobias Kildetoft
      Jun 27 '16 at 6:53














    • 2




      $begingroup$
      The FAQ item 1 is incorrect as it implies that definable reals (or sequences) are countable. This is only true in a non-definable mathematics. If you take the FAQ's suggestion to use definable objects only, then Cantor's theorem is still correct, but one has to formulate it for a definable world. It also is not true that not accepting Platonism or infinite sets invalidates diagonalization.
      $endgroup$
      – zyx
      Oct 16 '13 at 1:27








    • 1




      $begingroup$
      The thing is, the people the FAQ is intended for are not spending their energy arguing against some narrow version of Cantor's proof about effective enumerations of computable real numbers, for instance. They're arguing against the standard proof for the Platonistic result, and they're not realizing that they reject the presuppositions which even the statement of the theorem are based on. They're willing to accept that the statement of the theorem is meaningful, they just think it happens to be false, so I'm trying to say that that's not a coherent viewpoint.
      $endgroup$
      – Keshav Srinivasan
      Oct 16 '13 at 1:36






    • 4




      $begingroup$
      It is not likely you can formulate an unassailable argument that will succeed in every case. However, where an objection consists of coherent and incoherent parts, removing the dispute about the coherent part reduces the number of things in contention, and might help clarify to the skeptic that the incoherent part is not correct. Besides that, it is misleading both to the objector and to any observers should it be done in an online forum, to not handle the coherent part as being valid.
      $endgroup$
      – zyx
      Oct 16 '13 at 1:42








    • 3




      $begingroup$
      Thank you for standing up for reason. I am baffled by the number of people in mathematics who will loudly defend straw-man tactics when they are aesthetically favorable. It would make as much sense to ban anyone without a Ph.D. from discussing the diagonalization proof, on the grounds that they do not truly understand the foundations. As beautiful as Cantor's work is, I think that what has been done with topoi is even more so. It is thus a good thing, as you point out, that we do not really have to choose—at least so long as we don't get carried away by unfair and oppositional attitudes.
      $endgroup$
      – Slade
      Oct 16 '13 at 2:26






    • 1




      $begingroup$
      @RobertFrost That is nonsense. If the system is inconsistent then everything is true in that system and hence proof by contradiction is certainly valid.
      $endgroup$
      – Tobias Kildetoft
      Jun 27 '16 at 6:53








    2




    2




    $begingroup$
    The FAQ item 1 is incorrect as it implies that definable reals (or sequences) are countable. This is only true in a non-definable mathematics. If you take the FAQ's suggestion to use definable objects only, then Cantor's theorem is still correct, but one has to formulate it for a definable world. It also is not true that not accepting Platonism or infinite sets invalidates diagonalization.
    $endgroup$
    – zyx
    Oct 16 '13 at 1:27






    $begingroup$
    The FAQ item 1 is incorrect as it implies that definable reals (or sequences) are countable. This is only true in a non-definable mathematics. If you take the FAQ's suggestion to use definable objects only, then Cantor's theorem is still correct, but one has to formulate it for a definable world. It also is not true that not accepting Platonism or infinite sets invalidates diagonalization.
    $endgroup$
    – zyx
    Oct 16 '13 at 1:27






    1




    1




    $begingroup$
    The thing is, the people the FAQ is intended for are not spending their energy arguing against some narrow version of Cantor's proof about effective enumerations of computable real numbers, for instance. They're arguing against the standard proof for the Platonistic result, and they're not realizing that they reject the presuppositions which even the statement of the theorem are based on. They're willing to accept that the statement of the theorem is meaningful, they just think it happens to be false, so I'm trying to say that that's not a coherent viewpoint.
    $endgroup$
    – Keshav Srinivasan
    Oct 16 '13 at 1:36




    $begingroup$
    The thing is, the people the FAQ is intended for are not spending their energy arguing against some narrow version of Cantor's proof about effective enumerations of computable real numbers, for instance. They're arguing against the standard proof for the Platonistic result, and they're not realizing that they reject the presuppositions which even the statement of the theorem are based on. They're willing to accept that the statement of the theorem is meaningful, they just think it happens to be false, so I'm trying to say that that's not a coherent viewpoint.
    $endgroup$
    – Keshav Srinivasan
    Oct 16 '13 at 1:36




    4




    4




    $begingroup$
    It is not likely you can formulate an unassailable argument that will succeed in every case. However, where an objection consists of coherent and incoherent parts, removing the dispute about the coherent part reduces the number of things in contention, and might help clarify to the skeptic that the incoherent part is not correct. Besides that, it is misleading both to the objector and to any observers should it be done in an online forum, to not handle the coherent part as being valid.
    $endgroup$
    – zyx
    Oct 16 '13 at 1:42






    $begingroup$
    It is not likely you can formulate an unassailable argument that will succeed in every case. However, where an objection consists of coherent and incoherent parts, removing the dispute about the coherent part reduces the number of things in contention, and might help clarify to the skeptic that the incoherent part is not correct. Besides that, it is misleading both to the objector and to any observers should it be done in an online forum, to not handle the coherent part as being valid.
    $endgroup$
    – zyx
    Oct 16 '13 at 1:42






    3




    3




    $begingroup$
    Thank you for standing up for reason. I am baffled by the number of people in mathematics who will loudly defend straw-man tactics when they are aesthetically favorable. It would make as much sense to ban anyone without a Ph.D. from discussing the diagonalization proof, on the grounds that they do not truly understand the foundations. As beautiful as Cantor's work is, I think that what has been done with topoi is even more so. It is thus a good thing, as you point out, that we do not really have to choose—at least so long as we don't get carried away by unfair and oppositional attitudes.
    $endgroup$
    – Slade
    Oct 16 '13 at 2:26




    $begingroup$
    Thank you for standing up for reason. I am baffled by the number of people in mathematics who will loudly defend straw-man tactics when they are aesthetically favorable. It would make as much sense to ban anyone without a Ph.D. from discussing the diagonalization proof, on the grounds that they do not truly understand the foundations. As beautiful as Cantor's work is, I think that what has been done with topoi is even more so. It is thus a good thing, as you point out, that we do not really have to choose—at least so long as we don't get carried away by unfair and oppositional attitudes.
    $endgroup$
    – Slade
    Oct 16 '13 at 2:26




    1




    1




    $begingroup$
    @RobertFrost That is nonsense. If the system is inconsistent then everything is true in that system and hence proof by contradiction is certainly valid.
    $endgroup$
    – Tobias Kildetoft
    Jun 27 '16 at 6:53




    $begingroup$
    @RobertFrost That is nonsense. If the system is inconsistent then everything is true in that system and hence proof by contradiction is certainly valid.
    $endgroup$
    – Tobias Kildetoft
    Jun 27 '16 at 6:53











    11












    $begingroup$

    You could try limiting the discussion to the finite case of Cantor's theorem as a first step. Show them that for every function $f$ on the finite set ${1,ldots,n}$ there is a subset of the domain ${1,ldots,n}$ that is not an element of $text{ran}(f)$. Show them how the construction works for some examples, say $n = 2$ and $n=3$.



    If they don't accept this argument in the finite case, then challenge them to write down a counterexample $f$. If they do accept it, ask them to point out what goes wrong when $text{dom}(f)$ is $mathbb{N}$ (or an arbitrary set, although this may be too abstract for them.) At least you might be able to separate their confusion about diagonalization from their confusion about infinity.



    EDIT: I am talking about the version of Cantor's theorem for sets of natural numbers rather than the version for real numbers. If they do not understand the correspondence between real numbers and sets of natural numbers, their notion of "real number" is probably not precise enough to have a reasonable discussion about Cantor's theorem.






    share|cite|improve this answer











    $endgroup$









    • 1




      $begingroup$
      These people usually don't know much if any set theory, so you can't really go through the proof of Cantor's theorem that the power set has a bigger cardinality with them. And in any case they're usually constructivists of some stripe, so they probably wouldn't accept the existence of the power set of N.
      $endgroup$
      – Keshav Srinivasan
      Oct 15 '13 at 16:22






    • 1




      $begingroup$
      @KeshavSrinivasan I appreciate your point, but I was hoping that they would be able to deal with the set theory in the finite case. Also, I purposefully phrased my answer so as not to mention the power set of $mathbb{N}$, and not to rely on the power set axiom at all. If they don't accept the collection of all subsets of $mathbb{N}$ as a class, then I don't see what they could possibly construe the real numbers to be.
      $endgroup$
      – Trevor Wilson
      Oct 15 '13 at 16:27






    • 6




      $begingroup$
      @KeshavSrinivasan Then maybe they are right, and there really are only countably many points on the number line ;-) You have to commit to some formal definition of the real numbers for Cantor's theorem to be a theorem, and if they understand this formal definition, then they should be able to understand how real numbers correspond to sets of natural numbers. If they don't, then you have a more fundamental problem to deal with first.
      $endgroup$
      – Trevor Wilson
      Oct 15 '13 at 16:34






    • 2




      $begingroup$
      @KeshavSrinivasan But what if they are requiring the real numbers to be computable, but are not requiring the function $f : mathbb{N} to mathbb{R}$ to be computable? My point is just that if you expect to convince them that you are right and they are wrong, then first you should fix precisely a context where this is true, and make sure they know what it is. If they have a precise understanding of "infinite decimal", they must also have a precise understanding of "set of natural numbers".
      $endgroup$
      – Trevor Wilson
      Oct 15 '13 at 17:11






    • 2




      $begingroup$
      ...I'm not saying they need to accept arbitrary sets; we can restrict our attention to the case where the domain of $f$ is either a natural number or $mathbb{N}$ itself.
      $endgroup$
      – Trevor Wilson
      Oct 15 '13 at 17:11
















    11












    $begingroup$

    You could try limiting the discussion to the finite case of Cantor's theorem as a first step. Show them that for every function $f$ on the finite set ${1,ldots,n}$ there is a subset of the domain ${1,ldots,n}$ that is not an element of $text{ran}(f)$. Show them how the construction works for some examples, say $n = 2$ and $n=3$.



    If they don't accept this argument in the finite case, then challenge them to write down a counterexample $f$. If they do accept it, ask them to point out what goes wrong when $text{dom}(f)$ is $mathbb{N}$ (or an arbitrary set, although this may be too abstract for them.) At least you might be able to separate their confusion about diagonalization from their confusion about infinity.



    EDIT: I am talking about the version of Cantor's theorem for sets of natural numbers rather than the version for real numbers. If they do not understand the correspondence between real numbers and sets of natural numbers, their notion of "real number" is probably not precise enough to have a reasonable discussion about Cantor's theorem.






    share|cite|improve this answer











    $endgroup$









    • 1




      $begingroup$
      These people usually don't know much if any set theory, so you can't really go through the proof of Cantor's theorem that the power set has a bigger cardinality with them. And in any case they're usually constructivists of some stripe, so they probably wouldn't accept the existence of the power set of N.
      $endgroup$
      – Keshav Srinivasan
      Oct 15 '13 at 16:22






    • 1




      $begingroup$
      @KeshavSrinivasan I appreciate your point, but I was hoping that they would be able to deal with the set theory in the finite case. Also, I purposefully phrased my answer so as not to mention the power set of $mathbb{N}$, and not to rely on the power set axiom at all. If they don't accept the collection of all subsets of $mathbb{N}$ as a class, then I don't see what they could possibly construe the real numbers to be.
      $endgroup$
      – Trevor Wilson
      Oct 15 '13 at 16:27






    • 6




      $begingroup$
      @KeshavSrinivasan Then maybe they are right, and there really are only countably many points on the number line ;-) You have to commit to some formal definition of the real numbers for Cantor's theorem to be a theorem, and if they understand this formal definition, then they should be able to understand how real numbers correspond to sets of natural numbers. If they don't, then you have a more fundamental problem to deal with first.
      $endgroup$
      – Trevor Wilson
      Oct 15 '13 at 16:34






    • 2




      $begingroup$
      @KeshavSrinivasan But what if they are requiring the real numbers to be computable, but are not requiring the function $f : mathbb{N} to mathbb{R}$ to be computable? My point is just that if you expect to convince them that you are right and they are wrong, then first you should fix precisely a context where this is true, and make sure they know what it is. If they have a precise understanding of "infinite decimal", they must also have a precise understanding of "set of natural numbers".
      $endgroup$
      – Trevor Wilson
      Oct 15 '13 at 17:11






    • 2




      $begingroup$
      ...I'm not saying they need to accept arbitrary sets; we can restrict our attention to the case where the domain of $f$ is either a natural number or $mathbb{N}$ itself.
      $endgroup$
      – Trevor Wilson
      Oct 15 '13 at 17:11














    11












    11








    11





    $begingroup$

    You could try limiting the discussion to the finite case of Cantor's theorem as a first step. Show them that for every function $f$ on the finite set ${1,ldots,n}$ there is a subset of the domain ${1,ldots,n}$ that is not an element of $text{ran}(f)$. Show them how the construction works for some examples, say $n = 2$ and $n=3$.



    If they don't accept this argument in the finite case, then challenge them to write down a counterexample $f$. If they do accept it, ask them to point out what goes wrong when $text{dom}(f)$ is $mathbb{N}$ (or an arbitrary set, although this may be too abstract for them.) At least you might be able to separate their confusion about diagonalization from their confusion about infinity.



    EDIT: I am talking about the version of Cantor's theorem for sets of natural numbers rather than the version for real numbers. If they do not understand the correspondence between real numbers and sets of natural numbers, their notion of "real number" is probably not precise enough to have a reasonable discussion about Cantor's theorem.






    share|cite|improve this answer











    $endgroup$



    You could try limiting the discussion to the finite case of Cantor's theorem as a first step. Show them that for every function $f$ on the finite set ${1,ldots,n}$ there is a subset of the domain ${1,ldots,n}$ that is not an element of $text{ran}(f)$. Show them how the construction works for some examples, say $n = 2$ and $n=3$.



    If they don't accept this argument in the finite case, then challenge them to write down a counterexample $f$. If they do accept it, ask them to point out what goes wrong when $text{dom}(f)$ is $mathbb{N}$ (or an arbitrary set, although this may be too abstract for them.) At least you might be able to separate their confusion about diagonalization from their confusion about infinity.



    EDIT: I am talking about the version of Cantor's theorem for sets of natural numbers rather than the version for real numbers. If they do not understand the correspondence between real numbers and sets of natural numbers, their notion of "real number" is probably not precise enough to have a reasonable discussion about Cantor's theorem.







    share|cite|improve this answer














    share|cite|improve this answer



    share|cite|improve this answer








    edited Oct 15 '13 at 19:07

























    answered Oct 15 '13 at 16:11









    Trevor WilsonTrevor Wilson

    14.7k2456




    14.7k2456








    • 1




      $begingroup$
      These people usually don't know much if any set theory, so you can't really go through the proof of Cantor's theorem that the power set has a bigger cardinality with them. And in any case they're usually constructivists of some stripe, so they probably wouldn't accept the existence of the power set of N.
      $endgroup$
      – Keshav Srinivasan
      Oct 15 '13 at 16:22






    • 1




      $begingroup$
      @KeshavSrinivasan I appreciate your point, but I was hoping that they would be able to deal with the set theory in the finite case. Also, I purposefully phrased my answer so as not to mention the power set of $mathbb{N}$, and not to rely on the power set axiom at all. If they don't accept the collection of all subsets of $mathbb{N}$ as a class, then I don't see what they could possibly construe the real numbers to be.
      $endgroup$
      – Trevor Wilson
      Oct 15 '13 at 16:27






    • 6




      $begingroup$
      @KeshavSrinivasan Then maybe they are right, and there really are only countably many points on the number line ;-) You have to commit to some formal definition of the real numbers for Cantor's theorem to be a theorem, and if they understand this formal definition, then they should be able to understand how real numbers correspond to sets of natural numbers. If they don't, then you have a more fundamental problem to deal with first.
      $endgroup$
      – Trevor Wilson
      Oct 15 '13 at 16:34






    • 2




      $begingroup$
      @KeshavSrinivasan But what if they are requiring the real numbers to be computable, but are not requiring the function $f : mathbb{N} to mathbb{R}$ to be computable? My point is just that if you expect to convince them that you are right and they are wrong, then first you should fix precisely a context where this is true, and make sure they know what it is. If they have a precise understanding of "infinite decimal", they must also have a precise understanding of "set of natural numbers".
      $endgroup$
      – Trevor Wilson
      Oct 15 '13 at 17:11






    • 2




      $begingroup$
      ...I'm not saying they need to accept arbitrary sets; we can restrict our attention to the case where the domain of $f$ is either a natural number or $mathbb{N}$ itself.
      $endgroup$
      – Trevor Wilson
      Oct 15 '13 at 17:11














    • 1




      $begingroup$
      These people usually don't know much if any set theory, so you can't really go through the proof of Cantor's theorem that the power set has a bigger cardinality with them. And in any case they're usually constructivists of some stripe, so they probably wouldn't accept the existence of the power set of N.
      $endgroup$
      – Keshav Srinivasan
      Oct 15 '13 at 16:22






    • 1




      $begingroup$
      @KeshavSrinivasan I appreciate your point, but I was hoping that they would be able to deal with the set theory in the finite case. Also, I purposefully phrased my answer so as not to mention the power set of $mathbb{N}$, and not to rely on the power set axiom at all. If they don't accept the collection of all subsets of $mathbb{N}$ as a class, then I don't see what they could possibly construe the real numbers to be.
      $endgroup$
      – Trevor Wilson
      Oct 15 '13 at 16:27






    • 6




      $begingroup$
      @KeshavSrinivasan Then maybe they are right, and there really are only countably many points on the number line ;-) You have to commit to some formal definition of the real numbers for Cantor's theorem to be a theorem, and if they understand this formal definition, then they should be able to understand how real numbers correspond to sets of natural numbers. If they don't, then you have a more fundamental problem to deal with first.
      $endgroup$
      – Trevor Wilson
      Oct 15 '13 at 16:34






    • 2




      $begingroup$
      @KeshavSrinivasan But what if they are requiring the real numbers to be computable, but are not requiring the function $f : mathbb{N} to mathbb{R}$ to be computable? My point is just that if you expect to convince them that you are right and they are wrong, then first you should fix precisely a context where this is true, and make sure they know what it is. If they have a precise understanding of "infinite decimal", they must also have a precise understanding of "set of natural numbers".
      $endgroup$
      – Trevor Wilson
      Oct 15 '13 at 17:11






    • 2




      $begingroup$
      ...I'm not saying they need to accept arbitrary sets; we can restrict our attention to the case where the domain of $f$ is either a natural number or $mathbb{N}$ itself.
      $endgroup$
      – Trevor Wilson
      Oct 15 '13 at 17:11








    1




    1




    $begingroup$
    These people usually don't know much if any set theory, so you can't really go through the proof of Cantor's theorem that the power set has a bigger cardinality with them. And in any case they're usually constructivists of some stripe, so they probably wouldn't accept the existence of the power set of N.
    $endgroup$
    – Keshav Srinivasan
    Oct 15 '13 at 16:22




    $begingroup$
    These people usually don't know much if any set theory, so you can't really go through the proof of Cantor's theorem that the power set has a bigger cardinality with them. And in any case they're usually constructivists of some stripe, so they probably wouldn't accept the existence of the power set of N.
    $endgroup$
    – Keshav Srinivasan
    Oct 15 '13 at 16:22




    1




    1




    $begingroup$
    @KeshavSrinivasan I appreciate your point, but I was hoping that they would be able to deal with the set theory in the finite case. Also, I purposefully phrased my answer so as not to mention the power set of $mathbb{N}$, and not to rely on the power set axiom at all. If they don't accept the collection of all subsets of $mathbb{N}$ as a class, then I don't see what they could possibly construe the real numbers to be.
    $endgroup$
    – Trevor Wilson
    Oct 15 '13 at 16:27




    $begingroup$
    @KeshavSrinivasan I appreciate your point, but I was hoping that they would be able to deal with the set theory in the finite case. Also, I purposefully phrased my answer so as not to mention the power set of $mathbb{N}$, and not to rely on the power set axiom at all. If they don't accept the collection of all subsets of $mathbb{N}$ as a class, then I don't see what they could possibly construe the real numbers to be.
    $endgroup$
    – Trevor Wilson
    Oct 15 '13 at 16:27




    6




    6




    $begingroup$
    @KeshavSrinivasan Then maybe they are right, and there really are only countably many points on the number line ;-) You have to commit to some formal definition of the real numbers for Cantor's theorem to be a theorem, and if they understand this formal definition, then they should be able to understand how real numbers correspond to sets of natural numbers. If they don't, then you have a more fundamental problem to deal with first.
    $endgroup$
    – Trevor Wilson
    Oct 15 '13 at 16:34




    $begingroup$
    @KeshavSrinivasan Then maybe they are right, and there really are only countably many points on the number line ;-) You have to commit to some formal definition of the real numbers for Cantor's theorem to be a theorem, and if they understand this formal definition, then they should be able to understand how real numbers correspond to sets of natural numbers. If they don't, then you have a more fundamental problem to deal with first.
    $endgroup$
    – Trevor Wilson
    Oct 15 '13 at 16:34




    2




    2




    $begingroup$
    @KeshavSrinivasan But what if they are requiring the real numbers to be computable, but are not requiring the function $f : mathbb{N} to mathbb{R}$ to be computable? My point is just that if you expect to convince them that you are right and they are wrong, then first you should fix precisely a context where this is true, and make sure they know what it is. If they have a precise understanding of "infinite decimal", they must also have a precise understanding of "set of natural numbers".
    $endgroup$
    – Trevor Wilson
    Oct 15 '13 at 17:11




    $begingroup$
    @KeshavSrinivasan But what if they are requiring the real numbers to be computable, but are not requiring the function $f : mathbb{N} to mathbb{R}$ to be computable? My point is just that if you expect to convince them that you are right and they are wrong, then first you should fix precisely a context where this is true, and make sure they know what it is. If they have a precise understanding of "infinite decimal", they must also have a precise understanding of "set of natural numbers".
    $endgroup$
    – Trevor Wilson
    Oct 15 '13 at 17:11




    2




    2




    $begingroup$
    ...I'm not saying they need to accept arbitrary sets; we can restrict our attention to the case where the domain of $f$ is either a natural number or $mathbb{N}$ itself.
    $endgroup$
    – Trevor Wilson
    Oct 15 '13 at 17:11




    $begingroup$
    ...I'm not saying they need to accept arbitrary sets; we can restrict our attention to the case where the domain of $f$ is either a natural number or $mathbb{N}$ itself.
    $endgroup$
    – Trevor Wilson
    Oct 15 '13 at 17:11











    6












    $begingroup$

    The conversation seems almost equivalent to this hypothetical one about the irrationality of $sqrt 2$:



    ME: Suppose there are positive integers $m$, $n$ such that $m^2=2n^2$. Then we can generate a list of all prime factors and read off the exponent of $2$. This exponent should be even (because it is in the unique factorization of $m^2$) but also odd (because it is in the unique factorization of $2n^2$) so the equalilty cannot hold for any $m,n$.



    THEM: Of course your proposed exponent cannot exist; it's not a well-defined integer.



    ME: What do you mean? I gave you the exact procedure for constructing it: factorize that number. Check the factorization theorem.



    THEM: But if we really have a list of prime factors then factor 2 has to have some exponent, right?



    ME: Yes, of course, so let's say it's 57. Then it is odd and it would be also the double of an integer, that is impossible.



    THEM: Exactly, it's impossible! Your definition of the exponent requires that it is both odd and even, which is impossible, so your definition is bad.



    ME: But you're only saying that it's impossible on the basis of the assumption that the equality $m^2=2n^2$ holds for some positive integers $m$ and $n$, and the whole point is to disprove that assumption.



    THEM: But we're doing this proof under that assumption, so how can we make a definition that runs contrary to that assumption?



    ME: But that definition is a good one regardless of whether the assumption is true or false. It is a complete, algorithmic, unambiguous specification of an integer (the exponent of 2 in the unique prime factorization). What else could you want?



    THEM: I want the definition to be both unambiguous and non-contradictory, and your definition is contradictory!



    ME: Forget about the equality to be disproved for a moment. Don't you agree that for any number it's possible to construct a prime factorization and define the exponent of $2$?



    THEM: No, it's only possible to define such an exponent if the number $a$ to be factorized is not such that $a=m^2=2n^2$, otherwise it's a contradictory definition.



    ME: Don't you see that the contradiction is not the fault of my perfectly good definition, but rather the fault of your assumption that $m^2=2n^2$?



    THEM: No, I don't.



    ME: But what if we took our putative number $a=m^2=2n^2$, and fed it into a computer with an algorithm that spits the exponent of $2$ in the prime factorization? Would such a computer program work?



    THEM: No it wouldn't, the computer program would hit the place on the list where the exponent of $2$ would be computed and then it would get crash, because it can't produce a number that is both odd and even.






    share|cite|improve this answer











    $endgroup$













    • $begingroup$
      Interesting, can you spell out the proof that the square root of 2 is irrational using the exponent of 2? I've never seen that proof. I've only seen the conventional proof where you assume it's in simplest form and get a simpler form, or equivalently you construct an infinite descending sequence of natural numbers by continually dividing by 2.
      $endgroup$
      – Keshav Srinivasan
      Apr 30 '16 at 20:08












    • $begingroup$
      But yeah, you seem to have constructed an analogous situation to the one I keep encountering with anti-Cantor cranks. So how would you explain to them the error in their reasoning in your case, and in my case?
      $endgroup$
      – Keshav Srinivasan
      Apr 30 '16 at 20:09












    • $begingroup$
      It's very simple: $m^2$ must have an even exponent of $2$ in the prime factorization, $2n^2$ must have an odd exponent of $2$
      $endgroup$
      – Marco Disce
      Apr 30 '16 at 20:14










    • $begingroup$
      OK yeah, that makes sense, thanks. So how would you respond to the "them" in the dialogue?
      $endgroup$
      – Keshav Srinivasan
      Apr 30 '16 at 20:18






    • 3




      $begingroup$
      Here also you can argue contrapositively, without making the initial controversial hypothesis: Let $m$ and $n$ be arbitrary positive integers. Each of $m^{2}$ and $2n^{2}$ factors uniquely into primes. However, the exponent of $2$ in $m^{2}$ is even, while the exponent of $2$ in $2n^{2}$ is odd. Since no integer is both even and odd, the factorizations of $m^{2}$ and $2n^{2}$ are distinct, and consequently $m^{2} neq 2n^{2}$. Needless to say, I prefer this to "descent-type" arguments. :)
      $endgroup$
      – Andrew D. Hwang
      May 1 '16 at 13:39
















    6












    $begingroup$

    The conversation seems almost equivalent to this hypothetical one about the irrationality of $sqrt 2$:



    ME: Suppose there are positive integers $m$, $n$ such that $m^2=2n^2$. Then we can generate a list of all prime factors and read off the exponent of $2$. This exponent should be even (because it is in the unique factorization of $m^2$) but also odd (because it is in the unique factorization of $2n^2$) so the equalilty cannot hold for any $m,n$.



    THEM: Of course your proposed exponent cannot exist; it's not a well-defined integer.



    ME: What do you mean? I gave you the exact procedure for constructing it: factorize that number. Check the factorization theorem.



    THEM: But if we really have a list of prime factors then factor 2 has to have some exponent, right?



    ME: Yes, of course, so let's say it's 57. Then it is odd and it would be also the double of an integer, that is impossible.



    THEM: Exactly, it's impossible! Your definition of the exponent requires that it is both odd and even, which is impossible, so your definition is bad.



    ME: But you're only saying that it's impossible on the basis of the assumption that the equality $m^2=2n^2$ holds for some positive integers $m$ and $n$, and the whole point is to disprove that assumption.



    THEM: But we're doing this proof under that assumption, so how can we make a definition that runs contrary to that assumption?



    ME: But that definition is a good one regardless of whether the assumption is true or false. It is a complete, algorithmic, unambiguous specification of an integer (the exponent of 2 in the unique prime factorization). What else could you want?



    THEM: I want the definition to be both unambiguous and non-contradictory, and your definition is contradictory!



    ME: Forget about the equality to be disproved for a moment. Don't you agree that for any number it's possible to construct a prime factorization and define the exponent of $2$?



    THEM: No, it's only possible to define such an exponent if the number $a$ to be factorized is not such that $a=m^2=2n^2$, otherwise it's a contradictory definition.



    ME: Don't you see that the contradiction is not the fault of my perfectly good definition, but rather the fault of your assumption that $m^2=2n^2$?



    THEM: No, I don't.



    ME: But what if we took our putative number $a=m^2=2n^2$, and fed it into a computer with an algorithm that spits the exponent of $2$ in the prime factorization? Would such a computer program work?



    THEM: No it wouldn't, the computer program would hit the place on the list where the exponent of $2$ would be computed and then it would get crash, because it can't produce a number that is both odd and even.






    share|cite|improve this answer











    $endgroup$













    • $begingroup$
      Interesting, can you spell out the proof that the square root of 2 is irrational using the exponent of 2? I've never seen that proof. I've only seen the conventional proof where you assume it's in simplest form and get a simpler form, or equivalently you construct an infinite descending sequence of natural numbers by continually dividing by 2.
      $endgroup$
      – Keshav Srinivasan
      Apr 30 '16 at 20:08












    • $begingroup$
      But yeah, you seem to have constructed an analogous situation to the one I keep encountering with anti-Cantor cranks. So how would you explain to them the error in their reasoning in your case, and in my case?
      $endgroup$
      – Keshav Srinivasan
      Apr 30 '16 at 20:09












    • $begingroup$
      It's very simple: $m^2$ must have an even exponent of $2$ in the prime factorization, $2n^2$ must have an odd exponent of $2$
      $endgroup$
      – Marco Disce
      Apr 30 '16 at 20:14










    • $begingroup$
      OK yeah, that makes sense, thanks. So how would you respond to the "them" in the dialogue?
      $endgroup$
      – Keshav Srinivasan
      Apr 30 '16 at 20:18






    • 3




      $begingroup$
      Here also you can argue contrapositively, without making the initial controversial hypothesis: Let $m$ and $n$ be arbitrary positive integers. Each of $m^{2}$ and $2n^{2}$ factors uniquely into primes. However, the exponent of $2$ in $m^{2}$ is even, while the exponent of $2$ in $2n^{2}$ is odd. Since no integer is both even and odd, the factorizations of $m^{2}$ and $2n^{2}$ are distinct, and consequently $m^{2} neq 2n^{2}$. Needless to say, I prefer this to "descent-type" arguments. :)
      $endgroup$
      – Andrew D. Hwang
      May 1 '16 at 13:39














    6












    6








    6





    $begingroup$

    The conversation seems almost equivalent to this hypothetical one about the irrationality of $sqrt 2$:



    ME: Suppose there are positive integers $m$, $n$ such that $m^2=2n^2$. Then we can generate a list of all prime factors and read off the exponent of $2$. This exponent should be even (because it is in the unique factorization of $m^2$) but also odd (because it is in the unique factorization of $2n^2$) so the equalilty cannot hold for any $m,n$.



    THEM: Of course your proposed exponent cannot exist; it's not a well-defined integer.



    ME: What do you mean? I gave you the exact procedure for constructing it: factorize that number. Check the factorization theorem.



    THEM: But if we really have a list of prime factors then factor 2 has to have some exponent, right?



    ME: Yes, of course, so let's say it's 57. Then it is odd and it would be also the double of an integer, that is impossible.



    THEM: Exactly, it's impossible! Your definition of the exponent requires that it is both odd and even, which is impossible, so your definition is bad.



    ME: But you're only saying that it's impossible on the basis of the assumption that the equality $m^2=2n^2$ holds for some positive integers $m$ and $n$, and the whole point is to disprove that assumption.



    THEM: But we're doing this proof under that assumption, so how can we make a definition that runs contrary to that assumption?



    ME: But that definition is a good one regardless of whether the assumption is true or false. It is a complete, algorithmic, unambiguous specification of an integer (the exponent of 2 in the unique prime factorization). What else could you want?



    THEM: I want the definition to be both unambiguous and non-contradictory, and your definition is contradictory!



    ME: Forget about the equality to be disproved for a moment. Don't you agree that for any number it's possible to construct a prime factorization and define the exponent of $2$?



    THEM: No, it's only possible to define such an exponent if the number $a$ to be factorized is not such that $a=m^2=2n^2$, otherwise it's a contradictory definition.



    ME: Don't you see that the contradiction is not the fault of my perfectly good definition, but rather the fault of your assumption that $m^2=2n^2$?



    THEM: No, I don't.



    ME: But what if we took our putative number $a=m^2=2n^2$, and fed it into a computer with an algorithm that spits the exponent of $2$ in the prime factorization? Would such a computer program work?



    THEM: No it wouldn't, the computer program would hit the place on the list where the exponent of $2$ would be computed and then it would get crash, because it can't produce a number that is both odd and even.






    share|cite|improve this answer











    $endgroup$



    The conversation seems almost equivalent to this hypothetical one about the irrationality of $sqrt 2$:



    ME: Suppose there are positive integers $m$, $n$ such that $m^2=2n^2$. Then we can generate a list of all prime factors and read off the exponent of $2$. This exponent should be even (because it is in the unique factorization of $m^2$) but also odd (because it is in the unique factorization of $2n^2$) so the equalilty cannot hold for any $m,n$.



    THEM: Of course your proposed exponent cannot exist; it's not a well-defined integer.



    ME: What do you mean? I gave you the exact procedure for constructing it: factorize that number. Check the factorization theorem.



    THEM: But if we really have a list of prime factors then factor 2 has to have some exponent, right?



    ME: Yes, of course, so let's say it's 57. Then it is odd and it would be also the double of an integer, that is impossible.



    THEM: Exactly, it's impossible! Your definition of the exponent requires that it is both odd and even, which is impossible, so your definition is bad.



    ME: But you're only saying that it's impossible on the basis of the assumption that the equality $m^2=2n^2$ holds for some positive integers $m$ and $n$, and the whole point is to disprove that assumption.



    THEM: But we're doing this proof under that assumption, so how can we make a definition that runs contrary to that assumption?



    ME: But that definition is a good one regardless of whether the assumption is true or false. It is a complete, algorithmic, unambiguous specification of an integer (the exponent of 2 in the unique prime factorization). What else could you want?



    THEM: I want the definition to be both unambiguous and non-contradictory, and your definition is contradictory!



    ME: Forget about the equality to be disproved for a moment. Don't you agree that for any number it's possible to construct a prime factorization and define the exponent of $2$?



    THEM: No, it's only possible to define such an exponent if the number $a$ to be factorized is not such that $a=m^2=2n^2$, otherwise it's a contradictory definition.



    ME: Don't you see that the contradiction is not the fault of my perfectly good definition, but rather the fault of your assumption that $m^2=2n^2$?



    THEM: No, I don't.



    ME: But what if we took our putative number $a=m^2=2n^2$, and fed it into a computer with an algorithm that spits the exponent of $2$ in the prime factorization? Would such a computer program work?



    THEM: No it wouldn't, the computer program would hit the place on the list where the exponent of $2$ would be computed and then it would get crash, because it can't produce a number that is both odd and even.







    share|cite|improve this answer














    share|cite|improve this answer



    share|cite|improve this answer








    edited Feb 11 '17 at 7:55

























    answered Apr 30 '16 at 19:52









    Marco DisceMarco Disce

    1,3861216




    1,3861216












    • $begingroup$
      Interesting, can you spell out the proof that the square root of 2 is irrational using the exponent of 2? I've never seen that proof. I've only seen the conventional proof where you assume it's in simplest form and get a simpler form, or equivalently you construct an infinite descending sequence of natural numbers by continually dividing by 2.
      $endgroup$
      – Keshav Srinivasan
      Apr 30 '16 at 20:08












    • $begingroup$
      But yeah, you seem to have constructed an analogous situation to the one I keep encountering with anti-Cantor cranks. So how would you explain to them the error in their reasoning in your case, and in my case?
      $endgroup$
      – Keshav Srinivasan
      Apr 30 '16 at 20:09












    • $begingroup$
      It's very simple: $m^2$ must have an even exponent of $2$ in the prime factorization, $2n^2$ must have an odd exponent of $2$
      $endgroup$
      – Marco Disce
      Apr 30 '16 at 20:14










    • $begingroup$
      OK yeah, that makes sense, thanks. So how would you respond to the "them" in the dialogue?
      $endgroup$
      – Keshav Srinivasan
      Apr 30 '16 at 20:18






    • 3




      $begingroup$
      Here also you can argue contrapositively, without making the initial controversial hypothesis: Let $m$ and $n$ be arbitrary positive integers. Each of $m^{2}$ and $2n^{2}$ factors uniquely into primes. However, the exponent of $2$ in $m^{2}$ is even, while the exponent of $2$ in $2n^{2}$ is odd. Since no integer is both even and odd, the factorizations of $m^{2}$ and $2n^{2}$ are distinct, and consequently $m^{2} neq 2n^{2}$. Needless to say, I prefer this to "descent-type" arguments. :)
      $endgroup$
      – Andrew D. Hwang
      May 1 '16 at 13:39


















    • $begingroup$
      Interesting, can you spell out the proof that the square root of 2 is irrational using the exponent of 2? I've never seen that proof. I've only seen the conventional proof where you assume it's in simplest form and get a simpler form, or equivalently you construct an infinite descending sequence of natural numbers by continually dividing by 2.
      $endgroup$
      – Keshav Srinivasan
      Apr 30 '16 at 20:08












    • $begingroup$
      But yeah, you seem to have constructed an analogous situation to the one I keep encountering with anti-Cantor cranks. So how would you explain to them the error in their reasoning in your case, and in my case?
      $endgroup$
      – Keshav Srinivasan
      Apr 30 '16 at 20:09












    • $begingroup$
      It's very simple: $m^2$ must have an even exponent of $2$ in the prime factorization, $2n^2$ must have an odd exponent of $2$
      $endgroup$
      – Marco Disce
      Apr 30 '16 at 20:14










    • $begingroup$
      OK yeah, that makes sense, thanks. So how would you respond to the "them" in the dialogue?
      $endgroup$
      – Keshav Srinivasan
      Apr 30 '16 at 20:18






    • 3




      $begingroup$
      Here also you can argue contrapositively, without making the initial controversial hypothesis: Let $m$ and $n$ be arbitrary positive integers. Each of $m^{2}$ and $2n^{2}$ factors uniquely into primes. However, the exponent of $2$ in $m^{2}$ is even, while the exponent of $2$ in $2n^{2}$ is odd. Since no integer is both even and odd, the factorizations of $m^{2}$ and $2n^{2}$ are distinct, and consequently $m^{2} neq 2n^{2}$. Needless to say, I prefer this to "descent-type" arguments. :)
      $endgroup$
      – Andrew D. Hwang
      May 1 '16 at 13:39
















    $begingroup$
    Interesting, can you spell out the proof that the square root of 2 is irrational using the exponent of 2? I've never seen that proof. I've only seen the conventional proof where you assume it's in simplest form and get a simpler form, or equivalently you construct an infinite descending sequence of natural numbers by continually dividing by 2.
    $endgroup$
    – Keshav Srinivasan
    Apr 30 '16 at 20:08






    $begingroup$
    Interesting, can you spell out the proof that the square root of 2 is irrational using the exponent of 2? I've never seen that proof. I've only seen the conventional proof where you assume it's in simplest form and get a simpler form, or equivalently you construct an infinite descending sequence of natural numbers by continually dividing by 2.
    $endgroup$
    – Keshav Srinivasan
    Apr 30 '16 at 20:08














    $begingroup$
    But yeah, you seem to have constructed an analogous situation to the one I keep encountering with anti-Cantor cranks. So how would you explain to them the error in their reasoning in your case, and in my case?
    $endgroup$
    – Keshav Srinivasan
    Apr 30 '16 at 20:09






    $begingroup$
    But yeah, you seem to have constructed an analogous situation to the one I keep encountering with anti-Cantor cranks. So how would you explain to them the error in their reasoning in your case, and in my case?
    $endgroup$
    – Keshav Srinivasan
    Apr 30 '16 at 20:09














    $begingroup$
    It's very simple: $m^2$ must have an even exponent of $2$ in the prime factorization, $2n^2$ must have an odd exponent of $2$
    $endgroup$
    – Marco Disce
    Apr 30 '16 at 20:14




    $begingroup$
    It's very simple: $m^2$ must have an even exponent of $2$ in the prime factorization, $2n^2$ must have an odd exponent of $2$
    $endgroup$
    – Marco Disce
    Apr 30 '16 at 20:14












    $begingroup$
    OK yeah, that makes sense, thanks. So how would you respond to the "them" in the dialogue?
    $endgroup$
    – Keshav Srinivasan
    Apr 30 '16 at 20:18




    $begingroup$
    OK yeah, that makes sense, thanks. So how would you respond to the "them" in the dialogue?
    $endgroup$
    – Keshav Srinivasan
    Apr 30 '16 at 20:18




    3




    3




    $begingroup$
    Here also you can argue contrapositively, without making the initial controversial hypothesis: Let $m$ and $n$ be arbitrary positive integers. Each of $m^{2}$ and $2n^{2}$ factors uniquely into primes. However, the exponent of $2$ in $m^{2}$ is even, while the exponent of $2$ in $2n^{2}$ is odd. Since no integer is both even and odd, the factorizations of $m^{2}$ and $2n^{2}$ are distinct, and consequently $m^{2} neq 2n^{2}$. Needless to say, I prefer this to "descent-type" arguments. :)
    $endgroup$
    – Andrew D. Hwang
    May 1 '16 at 13:39




    $begingroup$
    Here also you can argue contrapositively, without making the initial controversial hypothesis: Let $m$ and $n$ be arbitrary positive integers. Each of $m^{2}$ and $2n^{2}$ factors uniquely into primes. However, the exponent of $2$ in $m^{2}$ is even, while the exponent of $2$ in $2n^{2}$ is odd. Since no integer is both even and odd, the factorizations of $m^{2}$ and $2n^{2}$ are distinct, and consequently $m^{2} neq 2n^{2}$. Needless to say, I prefer this to "descent-type" arguments. :)
    $endgroup$
    – Andrew D. Hwang
    May 1 '16 at 13:39











    5












    $begingroup$

    It's not a proof, but in this situation it is reasonable to be like cranky student. When I say that his algorithm is wrong he can't agree until I show him any counterexample. So you can just ask your opponents to give you method of constructing such list. And you would always be able to show that list is incomplete:)



    Anyway there are several different ways to prove that set of real numbers is uncountable. Are all of them rejected by your cranks?






    share|cite|improve this answer









    $endgroup$









    • 2




      $begingroup$
      Ok, then you are just lucky they don't claim that set of integers is finite:)
      $endgroup$
      – Smylic
      Oct 16 '13 at 1:03






    • 1




      $begingroup$
      Well, sometimes the cranks have a claim that they have constructed a complete list of real numbers, but a lot of the time they just reject Cantor's claim that such a list cannot exist, as opposed to making an affirmative claim on their part. Or they cite a reason that the real numbers are countable, but that reason does not actually give you a procedure for making a complete list of real numbers. And yes, there are other proofs of uncountability, but for instance you need a fair amount of math background for the proof that a perfect set is uncountable, whereas Cantor requires little.
      $endgroup$
      – Keshav Srinivasan
      Oct 16 '13 at 1:03






    • 5




      $begingroup$
      I was 13 when I got to know about 5 different proofs and had understood all of them. I think the following is not too hard. Consider a numbered list of all real numbers of $[0, 1]$. Let cover $i$th of them by open interval of length $3^{-i}$. Since each point is inside its own inteval (which has positive length) then is should be covered by at least one inteval. But cumulative length of all invervals is $frac12$, so union of them all can't cover all points of $[0, 1]$.
      $endgroup$
      – Smylic
      Oct 16 '13 at 1:13










    • $begingroup$
      Why wouldn't that proof show equally well that there are uncountably many rational numbers between $0$ and $1$?
      $endgroup$
      – Keshav Srinivasan
      Oct 16 '13 at 5:12






    • 2




      $begingroup$
      Not every point of $[0, 1]$ is rational, so covering every rational point doesn't mean covering every point and the whole segment.
      $endgroup$
      – Smylic
      Oct 16 '13 at 15:32
















    5












    $begingroup$

    It's not a proof, but in this situation it is reasonable to be like cranky student. When I say that his algorithm is wrong he can't agree until I show him any counterexample. So you can just ask your opponents to give you method of constructing such list. And you would always be able to show that list is incomplete:)



    Anyway there are several different ways to prove that set of real numbers is uncountable. Are all of them rejected by your cranks?






    share|cite|improve this answer









    $endgroup$









    • 2




      $begingroup$
      Ok, then you are just lucky they don't claim that set of integers is finite:)
      $endgroup$
      – Smylic
      Oct 16 '13 at 1:03






    • 1




      $begingroup$
      Well, sometimes the cranks have a claim that they have constructed a complete list of real numbers, but a lot of the time they just reject Cantor's claim that such a list cannot exist, as opposed to making an affirmative claim on their part. Or they cite a reason that the real numbers are countable, but that reason does not actually give you a procedure for making a complete list of real numbers. And yes, there are other proofs of uncountability, but for instance you need a fair amount of math background for the proof that a perfect set is uncountable, whereas Cantor requires little.
      $endgroup$
      – Keshav Srinivasan
      Oct 16 '13 at 1:03






    • 5




      $begingroup$
      I was 13 when I got to know about 5 different proofs and had understood all of them. I think the following is not too hard. Consider a numbered list of all real numbers of $[0, 1]$. Let cover $i$th of them by open interval of length $3^{-i}$. Since each point is inside its own inteval (which has positive length) then is should be covered by at least one inteval. But cumulative length of all invervals is $frac12$, so union of them all can't cover all points of $[0, 1]$.
      $endgroup$
      – Smylic
      Oct 16 '13 at 1:13










    • $begingroup$
      Why wouldn't that proof show equally well that there are uncountably many rational numbers between $0$ and $1$?
      $endgroup$
      – Keshav Srinivasan
      Oct 16 '13 at 5:12






    • 2




      $begingroup$
      Not every point of $[0, 1]$ is rational, so covering every rational point doesn't mean covering every point and the whole segment.
      $endgroup$
      – Smylic
      Oct 16 '13 at 15:32














    5












    5








    5





    $begingroup$

    It's not a proof, but in this situation it is reasonable to be like cranky student. When I say that his algorithm is wrong he can't agree until I show him any counterexample. So you can just ask your opponents to give you method of constructing such list. And you would always be able to show that list is incomplete:)



    Anyway there are several different ways to prove that set of real numbers is uncountable. Are all of them rejected by your cranks?






    share|cite|improve this answer









    $endgroup$



    It's not a proof, but in this situation it is reasonable to be like cranky student. When I say that his algorithm is wrong he can't agree until I show him any counterexample. So you can just ask your opponents to give you method of constructing such list. And you would always be able to show that list is incomplete:)



    Anyway there are several different ways to prove that set of real numbers is uncountable. Are all of them rejected by your cranks?







    share|cite|improve this answer












    share|cite|improve this answer



    share|cite|improve this answer










    answered Oct 15 '13 at 22:09









    SmylicSmylic

    4,53921225




    4,53921225








    • 2




      $begingroup$
      Ok, then you are just lucky they don't claim that set of integers is finite:)
      $endgroup$
      – Smylic
      Oct 16 '13 at 1:03






    • 1




      $begingroup$
      Well, sometimes the cranks have a claim that they have constructed a complete list of real numbers, but a lot of the time they just reject Cantor's claim that such a list cannot exist, as opposed to making an affirmative claim on their part. Or they cite a reason that the real numbers are countable, but that reason does not actually give you a procedure for making a complete list of real numbers. And yes, there are other proofs of uncountability, but for instance you need a fair amount of math background for the proof that a perfect set is uncountable, whereas Cantor requires little.
      $endgroup$
      – Keshav Srinivasan
      Oct 16 '13 at 1:03






    • 5




      $begingroup$
      I was 13 when I got to know about 5 different proofs and had understood all of them. I think the following is not too hard. Consider a numbered list of all real numbers of $[0, 1]$. Let cover $i$th of them by open interval of length $3^{-i}$. Since each point is inside its own inteval (which has positive length) then is should be covered by at least one inteval. But cumulative length of all invervals is $frac12$, so union of them all can't cover all points of $[0, 1]$.
      $endgroup$
      – Smylic
      Oct 16 '13 at 1:13










    • $begingroup$
      Why wouldn't that proof show equally well that there are uncountably many rational numbers between $0$ and $1$?
      $endgroup$
      – Keshav Srinivasan
      Oct 16 '13 at 5:12






    • 2




      $begingroup$
      Not every point of $[0, 1]$ is rational, so covering every rational point doesn't mean covering every point and the whole segment.
      $endgroup$
      – Smylic
      Oct 16 '13 at 15:32














    • 2




      $begingroup$
      Ok, then you are just lucky they don't claim that set of integers is finite:)
      $endgroup$
      – Smylic
      Oct 16 '13 at 1:03






    • 1




      $begingroup$
      Well, sometimes the cranks have a claim that they have constructed a complete list of real numbers, but a lot of the time they just reject Cantor's claim that such a list cannot exist, as opposed to making an affirmative claim on their part. Or they cite a reason that the real numbers are countable, but that reason does not actually give you a procedure for making a complete list of real numbers. And yes, there are other proofs of uncountability, but for instance you need a fair amount of math background for the proof that a perfect set is uncountable, whereas Cantor requires little.
      $endgroup$
      – Keshav Srinivasan
      Oct 16 '13 at 1:03






    • 5




      $begingroup$
      I was 13 when I got to know about 5 different proofs and had understood all of them. I think the following is not too hard. Consider a numbered list of all real numbers of $[0, 1]$. Let cover $i$th of them by open interval of length $3^{-i}$. Since each point is inside its own inteval (which has positive length) then is should be covered by at least one inteval. But cumulative length of all invervals is $frac12$, so union of them all can't cover all points of $[0, 1]$.
      $endgroup$
      – Smylic
      Oct 16 '13 at 1:13










    • $begingroup$
      Why wouldn't that proof show equally well that there are uncountably many rational numbers between $0$ and $1$?
      $endgroup$
      – Keshav Srinivasan
      Oct 16 '13 at 5:12






    • 2




      $begingroup$
      Not every point of $[0, 1]$ is rational, so covering every rational point doesn't mean covering every point and the whole segment.
      $endgroup$
      – Smylic
      Oct 16 '13 at 15:32








    2




    2




    $begingroup$
    Ok, then you are just lucky they don't claim that set of integers is finite:)
    $endgroup$
    – Smylic
    Oct 16 '13 at 1:03




    $begingroup$
    Ok, then you are just lucky they don't claim that set of integers is finite:)
    $endgroup$
    – Smylic
    Oct 16 '13 at 1:03




    1




    1




    $begingroup$
    Well, sometimes the cranks have a claim that they have constructed a complete list of real numbers, but a lot of the time they just reject Cantor's claim that such a list cannot exist, as opposed to making an affirmative claim on their part. Or they cite a reason that the real numbers are countable, but that reason does not actually give you a procedure for making a complete list of real numbers. And yes, there are other proofs of uncountability, but for instance you need a fair amount of math background for the proof that a perfect set is uncountable, whereas Cantor requires little.
    $endgroup$
    – Keshav Srinivasan
    Oct 16 '13 at 1:03




    $begingroup$
    Well, sometimes the cranks have a claim that they have constructed a complete list of real numbers, but a lot of the time they just reject Cantor's claim that such a list cannot exist, as opposed to making an affirmative claim on their part. Or they cite a reason that the real numbers are countable, but that reason does not actually give you a procedure for making a complete list of real numbers. And yes, there are other proofs of uncountability, but for instance you need a fair amount of math background for the proof that a perfect set is uncountable, whereas Cantor requires little.
    $endgroup$
    – Keshav Srinivasan
    Oct 16 '13 at 1:03




    5




    5




    $begingroup$
    I was 13 when I got to know about 5 different proofs and had understood all of them. I think the following is not too hard. Consider a numbered list of all real numbers of $[0, 1]$. Let cover $i$th of them by open interval of length $3^{-i}$. Since each point is inside its own inteval (which has positive length) then is should be covered by at least one inteval. But cumulative length of all invervals is $frac12$, so union of them all can't cover all points of $[0, 1]$.
    $endgroup$
    – Smylic
    Oct 16 '13 at 1:13




    $begingroup$
    I was 13 when I got to know about 5 different proofs and had understood all of them. I think the following is not too hard. Consider a numbered list of all real numbers of $[0, 1]$. Let cover $i$th of them by open interval of length $3^{-i}$. Since each point is inside its own inteval (which has positive length) then is should be covered by at least one inteval. But cumulative length of all invervals is $frac12$, so union of them all can't cover all points of $[0, 1]$.
    $endgroup$
    – Smylic
    Oct 16 '13 at 1:13












    $begingroup$
    Why wouldn't that proof show equally well that there are uncountably many rational numbers between $0$ and $1$?
    $endgroup$
    – Keshav Srinivasan
    Oct 16 '13 at 5:12




    $begingroup$
    Why wouldn't that proof show equally well that there are uncountably many rational numbers between $0$ and $1$?
    $endgroup$
    – Keshav Srinivasan
    Oct 16 '13 at 5:12




    2




    2




    $begingroup$
    Not every point of $[0, 1]$ is rational, so covering every rational point doesn't mean covering every point and the whole segment.
    $endgroup$
    – Smylic
    Oct 16 '13 at 15:32




    $begingroup$
    Not every point of $[0, 1]$ is rational, so covering every rational point doesn't mean covering every point and the whole segment.
    $endgroup$
    – Smylic
    Oct 16 '13 at 15:32











    4












    $begingroup$

    Instead of entering a discussion about the proof for real numbers, I would propose discussing instead the abstract version, which gives far less opportunity for polemic. Let the "crank" decide what he thinks about the abstract version and its proof, and then see where to go from there. If he refuses the abstract version, he should either be able to find fault with the proof, or accept being inconsistent (if finding no fault in the proof but still rejecting the conclusion). When accepting the abstract version one can still refuse application for the real numbers (for instance by denying the existence of infinite sets, or maybe accepting existence of the natural numbers but not of their power set), but it forces one to draw a line somewhere; once this is done there is really nothing left to discuss. For reference, here it is:



    Proposition. For every set $X$ and every map $defP{mathcal P}f:XtoP(X)$ there exists $Y_finP(X)$ such that for all $xin X$ one has $Y_fneq f(x)$.



    Proof. Take $Y_f={, zin Xmid znotin f(z),}$. For $xin Y_f$ one has $xnotin f(x)$ so $Y_fneq f(x)$. For $xin X$ with $xnotin Y_f$ one has $xin f(x)$, so $Y_fneq f(x)$. This establishes $Y_fneq f(x)$ for all $xin X$.






    share|cite|improve this answer











    $endgroup$









    • 1




      $begingroup$
      The problem is, these people usually don't know much if any set theory, so you can't really go through the proof of Cantor's theorem that the power set has a bigger cardinality with them. Cantor's diagonal proof of the uncountability of the reals is usually the only proof they can comprehend.
      $endgroup$
      – Keshav Srinivasan
      Feb 19 '14 at 15:13










    • $begingroup$
      @KeshavSrinivasan: Apperently you are complaining it is just another proof they cannot comprehend. Note that the only "set theory" really used is that one can define a subset by telling which elements to keep and which ones not to keep. You can view sets as lists of their elements if you like, and get close to the traditional diagonal, without having to bother about reals. I think if they cannot comprehend maps from a set to its power set, there is really no point in discussing countability of real numbers with them in the first place.
      $endgroup$
      – Marc van Leeuwen
      Feb 19 '14 at 15:30












    • $begingroup$
      If they learned enough set theory, they'd probably abandon their objections to Cantor's diagonal proof anyway. But in any case, I suppose the objection I described in my question could be carried over to the Cantor's theorem case: they would say that the definition of $Y_f$ doesn't make sense in the case when $f$ is surjective, and that the contradiction you get in the case when $f$ is surjective indicates that $Y_f$ does not exist, not that $f$ is not surjective. The fundamental problem with these people is that they're misattributing the source of the contradiction.
      $endgroup$
      – Keshav Srinivasan
      Feb 19 '14 at 15:39






    • 1




      $begingroup$
      @byserpas I don't understand at all what you want to say. It is not that restricted comprehension forbids you to have a universal set; rather it would require another axiom, namely unrestricted comprehension, to have a universal set. But then you get the Russell paradox and an inconsistent theory. Also any diagonal argument is essentially about a power set or something very similar like digit strings (mapping natural numbers to ${0,1,ldots,9}$ is very similar to mapping them to ${mathrm{false},mathrm{true}}$).
      $endgroup$
      – Marc van Leeuwen
      May 8 '15 at 6:03








    • 1




      $begingroup$
      @byserpas If there is only one set, then you've got no set theory (in the sense that you can only formulate statements that are trivially true or false). You need no other axioms than something "there is no $x$ but $A$, and $xin A$ if and only $x=A$". You won't have any constructions like powerset (though you can give any name you like to the construction that always produces $A$), no natural numbers, no reals, no diagonal argument, nothing. It is an utterly boring enterprise. Go try to sell it to somebody as set theory, but don't waste our time with it.
      $endgroup$
      – Marc van Leeuwen
      May 8 '15 at 8:47


















    4












    $begingroup$

    Instead of entering a discussion about the proof for real numbers, I would propose discussing instead the abstract version, which gives far less opportunity for polemic. Let the "crank" decide what he thinks about the abstract version and its proof, and then see where to go from there. If he refuses the abstract version, he should either be able to find fault with the proof, or accept being inconsistent (if finding no fault in the proof but still rejecting the conclusion). When accepting the abstract version one can still refuse application for the real numbers (for instance by denying the existence of infinite sets, or maybe accepting existence of the natural numbers but not of their power set), but it forces one to draw a line somewhere; once this is done there is really nothing left to discuss. For reference, here it is:



    Proposition. For every set $X$ and every map $defP{mathcal P}f:XtoP(X)$ there exists $Y_finP(X)$ such that for all $xin X$ one has $Y_fneq f(x)$.



    Proof. Take $Y_f={, zin Xmid znotin f(z),}$. For $xin Y_f$ one has $xnotin f(x)$ so $Y_fneq f(x)$. For $xin X$ with $xnotin Y_f$ one has $xin f(x)$, so $Y_fneq f(x)$. This establishes $Y_fneq f(x)$ for all $xin X$.






    share|cite|improve this answer











    $endgroup$









    • 1




      $begingroup$
      The problem is, these people usually don't know much if any set theory, so you can't really go through the proof of Cantor's theorem that the power set has a bigger cardinality with them. Cantor's diagonal proof of the uncountability of the reals is usually the only proof they can comprehend.
      $endgroup$
      – Keshav Srinivasan
      Feb 19 '14 at 15:13










    • $begingroup$
      @KeshavSrinivasan: Apperently you are complaining it is just another proof they cannot comprehend. Note that the only "set theory" really used is that one can define a subset by telling which elements to keep and which ones not to keep. You can view sets as lists of their elements if you like, and get close to the traditional diagonal, without having to bother about reals. I think if they cannot comprehend maps from a set to its power set, there is really no point in discussing countability of real numbers with them in the first place.
      $endgroup$
      – Marc van Leeuwen
      Feb 19 '14 at 15:30












    • $begingroup$
      If they learned enough set theory, they'd probably abandon their objections to Cantor's diagonal proof anyway. But in any case, I suppose the objection I described in my question could be carried over to the Cantor's theorem case: they would say that the definition of $Y_f$ doesn't make sense in the case when $f$ is surjective, and that the contradiction you get in the case when $f$ is surjective indicates that $Y_f$ does not exist, not that $f$ is not surjective. The fundamental problem with these people is that they're misattributing the source of the contradiction.
      $endgroup$
      – Keshav Srinivasan
      Feb 19 '14 at 15:39






    • 1




      $begingroup$
      @byserpas I don't understand at all what you want to say. It is not that restricted comprehension forbids you to have a universal set; rather it would require another axiom, namely unrestricted comprehension, to have a universal set. But then you get the Russell paradox and an inconsistent theory. Also any diagonal argument is essentially about a power set or something very similar like digit strings (mapping natural numbers to ${0,1,ldots,9}$ is very similar to mapping them to ${mathrm{false},mathrm{true}}$).
      $endgroup$
      – Marc van Leeuwen
      May 8 '15 at 6:03








    • 1




      $begingroup$
      @byserpas If there is only one set, then you've got no set theory (in the sense that you can only formulate statements that are trivially true or false). You need no other axioms than something "there is no $x$ but $A$, and $xin A$ if and only $x=A$". You won't have any constructions like powerset (though you can give any name you like to the construction that always produces $A$), no natural numbers, no reals, no diagonal argument, nothing. It is an utterly boring enterprise. Go try to sell it to somebody as set theory, but don't waste our time with it.
      $endgroup$
      – Marc van Leeuwen
      May 8 '15 at 8:47
















    4












    4








    4





    $begingroup$

    Instead of entering a discussion about the proof for real numbers, I would propose discussing instead the abstract version, which gives far less opportunity for polemic. Let the "crank" decide what he thinks about the abstract version and its proof, and then see where to go from there. If he refuses the abstract version, he should either be able to find fault with the proof, or accept being inconsistent (if finding no fault in the proof but still rejecting the conclusion). When accepting the abstract version one can still refuse application for the real numbers (for instance by denying the existence of infinite sets, or maybe accepting existence of the natural numbers but not of their power set), but it forces one to draw a line somewhere; once this is done there is really nothing left to discuss. For reference, here it is:



    Proposition. For every set $X$ and every map $defP{mathcal P}f:XtoP(X)$ there exists $Y_finP(X)$ such that for all $xin X$ one has $Y_fneq f(x)$.



    Proof. Take $Y_f={, zin Xmid znotin f(z),}$. For $xin Y_f$ one has $xnotin f(x)$ so $Y_fneq f(x)$. For $xin X$ with $xnotin Y_f$ one has $xin f(x)$, so $Y_fneq f(x)$. This establishes $Y_fneq f(x)$ for all $xin X$.






    share|cite|improve this answer











    $endgroup$



    Instead of entering a discussion about the proof for real numbers, I would propose discussing instead the abstract version, which gives far less opportunity for polemic. Let the "crank" decide what he thinks about the abstract version and its proof, and then see where to go from there. If he refuses the abstract version, he should either be able to find fault with the proof, or accept being inconsistent (if finding no fault in the proof but still rejecting the conclusion). When accepting the abstract version one can still refuse application for the real numbers (for instance by denying the existence of infinite sets, or maybe accepting existence of the natural numbers but not of their power set), but it forces one to draw a line somewhere; once this is done there is really nothing left to discuss. For reference, here it is:



    Proposition. For every set $X$ and every map $defP{mathcal P}f:XtoP(X)$ there exists $Y_finP(X)$ such that for all $xin X$ one has $Y_fneq f(x)$.



    Proof. Take $Y_f={, zin Xmid znotin f(z),}$. For $xin Y_f$ one has $xnotin f(x)$ so $Y_fneq f(x)$. For $xin X$ with $xnotin Y_f$ one has $xin f(x)$, so $Y_fneq f(x)$. This establishes $Y_fneq f(x)$ for all $xin X$.







    share|cite|improve this answer














    share|cite|improve this answer



    share|cite|improve this answer








    edited Feb 19 '14 at 8:53

























    answered Feb 19 '14 at 8:43









    Marc van LeeuwenMarc van Leeuwen

    86.6k5107221




    86.6k5107221








    • 1




      $begingroup$
      The problem is, these people usually don't know much if any set theory, so you can't really go through the proof of Cantor's theorem that the power set has a bigger cardinality with them. Cantor's diagonal proof of the uncountability of the reals is usually the only proof they can comprehend.
      $endgroup$
      – Keshav Srinivasan
      Feb 19 '14 at 15:13










    • $begingroup$
      @KeshavSrinivasan: Apperently you are complaining it is just another proof they cannot comprehend. Note that the only "set theory" really used is that one can define a subset by telling which elements to keep and which ones not to keep. You can view sets as lists of their elements if you like, and get close to the traditional diagonal, without having to bother about reals. I think if they cannot comprehend maps from a set to its power set, there is really no point in discussing countability of real numbers with them in the first place.
      $endgroup$
      – Marc van Leeuwen
      Feb 19 '14 at 15:30












    • $begingroup$
      If they learned enough set theory, they'd probably abandon their objections to Cantor's diagonal proof anyway. But in any case, I suppose the objection I described in my question could be carried over to the Cantor's theorem case: they would say that the definition of $Y_f$ doesn't make sense in the case when $f$ is surjective, and that the contradiction you get in the case when $f$ is surjective indicates that $Y_f$ does not exist, not that $f$ is not surjective. The fundamental problem with these people is that they're misattributing the source of the contradiction.
      $endgroup$
      – Keshav Srinivasan
      Feb 19 '14 at 15:39






    • 1




      $begingroup$
      @byserpas I don't understand at all what you want to say. It is not that restricted comprehension forbids you to have a universal set; rather it would require another axiom, namely unrestricted comprehension, to have a universal set. But then you get the Russell paradox and an inconsistent theory. Also any diagonal argument is essentially about a power set or something very similar like digit strings (mapping natural numbers to ${0,1,ldots,9}$ is very similar to mapping them to ${mathrm{false},mathrm{true}}$).
      $endgroup$
      – Marc van Leeuwen
      May 8 '15 at 6:03








    • 1




      $begingroup$
      @byserpas If there is only one set, then you've got no set theory (in the sense that you can only formulate statements that are trivially true or false). You need no other axioms than something "there is no $x$ but $A$, and $xin A$ if and only $x=A$". You won't have any constructions like powerset (though you can give any name you like to the construction that always produces $A$), no natural numbers, no reals, no diagonal argument, nothing. It is an utterly boring enterprise. Go try to sell it to somebody as set theory, but don't waste our time with it.
      $endgroup$
      – Marc van Leeuwen
      May 8 '15 at 8:47
















    • 1




      $begingroup$
      The problem is, these people usually don't know much if any set theory, so you can't really go through the proof of Cantor's theorem that the power set has a bigger cardinality with them. Cantor's diagonal proof of the uncountability of the reals is usually the only proof they can comprehend.
      $endgroup$
      – Keshav Srinivasan
      Feb 19 '14 at 15:13










    • $begingroup$
      @KeshavSrinivasan: Apperently you are complaining it is just another proof they cannot comprehend. Note that the only "set theory" really used is that one can define a subset by telling which elements to keep and which ones not to keep. You can view sets as lists of their elements if you like, and get close to the traditional diagonal, without having to bother about reals. I think if they cannot comprehend maps from a set to its power set, there is really no point in discussing countability of real numbers with them in the first place.
      $endgroup$
      – Marc van Leeuwen
      Feb 19 '14 at 15:30












    • $begingroup$
      If they learned enough set theory, they'd probably abandon their objections to Cantor's diagonal proof anyway. But in any case, I suppose the objection I described in my question could be carried over to the Cantor's theorem case: they would say that the definition of $Y_f$ doesn't make sense in the case when $f$ is surjective, and that the contradiction you get in the case when $f$ is surjective indicates that $Y_f$ does not exist, not that $f$ is not surjective. The fundamental problem with these people is that they're misattributing the source of the contradiction.
      $endgroup$
      – Keshav Srinivasan
      Feb 19 '14 at 15:39






    • 1




      $begingroup$
      @byserpas I don't understand at all what you want to say. It is not that restricted comprehension forbids you to have a universal set; rather it would require another axiom, namely unrestricted comprehension, to have a universal set. But then you get the Russell paradox and an inconsistent theory. Also any diagonal argument is essentially about a power set or something very similar like digit strings (mapping natural numbers to ${0,1,ldots,9}$ is very similar to mapping them to ${mathrm{false},mathrm{true}}$).
      $endgroup$
      – Marc van Leeuwen
      May 8 '15 at 6:03








    • 1




      $begingroup$
      @byserpas If there is only one set, then you've got no set theory (in the sense that you can only formulate statements that are trivially true or false). You need no other axioms than something "there is no $x$ but $A$, and $xin A$ if and only $x=A$". You won't have any constructions like powerset (though you can give any name you like to the construction that always produces $A$), no natural numbers, no reals, no diagonal argument, nothing. It is an utterly boring enterprise. Go try to sell it to somebody as set theory, but don't waste our time with it.
      $endgroup$
      – Marc van Leeuwen
      May 8 '15 at 8:47










    1




    1




    $begingroup$
    The problem is, these people usually don't know much if any set theory, so you can't really go through the proof of Cantor's theorem that the power set has a bigger cardinality with them. Cantor's diagonal proof of the uncountability of the reals is usually the only proof they can comprehend.
    $endgroup$
    – Keshav Srinivasan
    Feb 19 '14 at 15:13




    $begingroup$
    The problem is, these people usually don't know much if any set theory, so you can't really go through the proof of Cantor's theorem that the power set has a bigger cardinality with them. Cantor's diagonal proof of the uncountability of the reals is usually the only proof they can comprehend.
    $endgroup$
    – Keshav Srinivasan
    Feb 19 '14 at 15:13












    $begingroup$
    @KeshavSrinivasan: Apperently you are complaining it is just another proof they cannot comprehend. Note that the only "set theory" really used is that one can define a subset by telling which elements to keep and which ones not to keep. You can view sets as lists of their elements if you like, and get close to the traditional diagonal, without having to bother about reals. I think if they cannot comprehend maps from a set to its power set, there is really no point in discussing countability of real numbers with them in the first place.
    $endgroup$
    – Marc van Leeuwen
    Feb 19 '14 at 15:30






    $begingroup$
    @KeshavSrinivasan: Apperently you are complaining it is just another proof they cannot comprehend. Note that the only "set theory" really used is that one can define a subset by telling which elements to keep and which ones not to keep. You can view sets as lists of their elements if you like, and get close to the traditional diagonal, without having to bother about reals. I think if they cannot comprehend maps from a set to its power set, there is really no point in discussing countability of real numbers with them in the first place.
    $endgroup$
    – Marc van Leeuwen
    Feb 19 '14 at 15:30














    $begingroup$
    If they learned enough set theory, they'd probably abandon their objections to Cantor's diagonal proof anyway. But in any case, I suppose the objection I described in my question could be carried over to the Cantor's theorem case: they would say that the definition of $Y_f$ doesn't make sense in the case when $f$ is surjective, and that the contradiction you get in the case when $f$ is surjective indicates that $Y_f$ does not exist, not that $f$ is not surjective. The fundamental problem with these people is that they're misattributing the source of the contradiction.
    $endgroup$
    – Keshav Srinivasan
    Feb 19 '14 at 15:39




    $begingroup$
    If they learned enough set theory, they'd probably abandon their objections to Cantor's diagonal proof anyway. But in any case, I suppose the objection I described in my question could be carried over to the Cantor's theorem case: they would say that the definition of $Y_f$ doesn't make sense in the case when $f$ is surjective, and that the contradiction you get in the case when $f$ is surjective indicates that $Y_f$ does not exist, not that $f$ is not surjective. The fundamental problem with these people is that they're misattributing the source of the contradiction.
    $endgroup$
    – Keshav Srinivasan
    Feb 19 '14 at 15:39




    1




    1




    $begingroup$
    @byserpas I don't understand at all what you want to say. It is not that restricted comprehension forbids you to have a universal set; rather it would require another axiom, namely unrestricted comprehension, to have a universal set. But then you get the Russell paradox and an inconsistent theory. Also any diagonal argument is essentially about a power set or something very similar like digit strings (mapping natural numbers to ${0,1,ldots,9}$ is very similar to mapping them to ${mathrm{false},mathrm{true}}$).
    $endgroup$
    – Marc van Leeuwen
    May 8 '15 at 6:03






    $begingroup$
    @byserpas I don't understand at all what you want to say. It is not that restricted comprehension forbids you to have a universal set; rather it would require another axiom, namely unrestricted comprehension, to have a universal set. But then you get the Russell paradox and an inconsistent theory. Also any diagonal argument is essentially about a power set or something very similar like digit strings (mapping natural numbers to ${0,1,ldots,9}$ is very similar to mapping them to ${mathrm{false},mathrm{true}}$).
    $endgroup$
    – Marc van Leeuwen
    May 8 '15 at 6:03






    1




    1




    $begingroup$
    @byserpas If there is only one set, then you've got no set theory (in the sense that you can only formulate statements that are trivially true or false). You need no other axioms than something "there is no $x$ but $A$, and $xin A$ if and only $x=A$". You won't have any constructions like powerset (though you can give any name you like to the construction that always produces $A$), no natural numbers, no reals, no diagonal argument, nothing. It is an utterly boring enterprise. Go try to sell it to somebody as set theory, but don't waste our time with it.
    $endgroup$
    – Marc van Leeuwen
    May 8 '15 at 8:47






    $begingroup$
    @byserpas If there is only one set, then you've got no set theory (in the sense that you can only formulate statements that are trivially true or false). You need no other axioms than something "there is no $x$ but $A$, and $xin A$ if and only $x=A$". You won't have any constructions like powerset (though you can give any name you like to the construction that always produces $A$), no natural numbers, no reals, no diagonal argument, nothing. It is an utterly boring enterprise. Go try to sell it to somebody as set theory, but don't waste our time with it.
    $endgroup$
    – Marc van Leeuwen
    May 8 '15 at 8:47













    3












    $begingroup$

    Cantor's proof is not about numbers at all (there is a problem with trying to use it on numbers), it is about infinite strings of two characters. See http://www.logicmuseum.com/cantor/diagarg.htm.



    Call them Cantor Strings. Cantor used "M" and "W" which, while they are visually interesting, are hard to distinguish. You can use "0" and "1" and claim they represent fractions in binary representation, but there is a problem. For example, 5/16 has two such binary representations: 0.01010000... and 0.01001111... . So you can't claim a number is missing, if all you prove is that a string is missing.



    Ignoring this fault, as most treatments do, your very first statement is not what Cantor does "ME: Suppose there is an ordered list containing all the (Cantor Strings)." The first step of Cantor's Proof is "Consider ANY list that links every natural number to a unique Cantor String." Nowhere is it assumed that this means all Cantor Strings.



    In fact, diagonalization proves the opposite. It proves: "If you have a set of Cantor Stings that can be listed this way, then it does not include all Cantor Strings."



    It is a simple trick of logic to invert the statement "If A, then B" to get the 100% equivalent statement "If NOT B, then NOT A." So diagonalization also proves "If you have a set of all Cantor Strings, then it can't be listed this way."



    Elegant, no?



    The reason so many Anti-Cantor cranks exists, is because we don;t seem to teach Cantor's proof correctly.






    share|cite|improve this answer











    $endgroup$









    • 1




      $begingroup$
      I actually make the point that you're making later on in the dialogue; look at where it says "Forget about the purported complete lists of real numbers for a moment..." The problem is, when I phrase the proof that way, the cranks' retort is that they do not think that the diagonalization procedure will always work in constructing a well-defined real number (or infinite string if you prefer). They think that the diagonalization procedure is not well-defined if you start with a list that happens to be complete. The problem is that they're misdiagnosing the source of the contradiction.
      $endgroup$
      – Keshav Srinivasan
      Apr 16 '16 at 20:27












    • $begingroup$
      I'd agree, if you you'd said "They think that the diagonalization procedure is not well-defined if you start with a list that happens to be INFINITE." The two are not the same, and I do feel it is the "infinite" part that confuses them. Not the "complete" part.
      $endgroup$
      – JeffJo
      Apr 17 '16 at 19:09












    • $begingroup$
      No, they're fine with infinite lists. Like if you start with an infinite list of the form .0111111... then .1011111... then .1101111... etc., they think diagonalization is a well-defined procedure. But they think that if the list happens to be complete, then the diagonalization process is not well-defined. That's because if the list was complete and the diagonalization procedure was well-defined, then the number being constructed would be somewhere in the list, say the Nth spot. And then Nth digit of that number would be ill-defined, because it's required to differ from itself.
      $endgroup$
      – Keshav Srinivasan
      Apr 17 '16 at 19:51










    • $begingroup$
      So they think that the diagonalization process is only well-defined for those lists which do not contain the number which would be constructed through diagonalization. Like I said, the problem is that they're misdiagnosing the source of the contradiction. They don't understand that the diagonalization process is well-defined for all lists.
      $endgroup$
      – Keshav Srinivasan
      Apr 17 '16 at 19:54










    • $begingroup$
      And I think that their difficulty comes when they try to correlate the infinite length of the strings, to the infinite length of the assumed "complete" list. The question they have - the one behind the imagined contradiction you describe - is "If the list is infinite, how can it not contain all possible strings?" The answer is that you can correlate two infinities in more than one way, and some ways miss elements of one..
      $endgroup$
      – JeffJo
      Apr 18 '16 at 13:56
















    3












    $begingroup$

    Cantor's proof is not about numbers at all (there is a problem with trying to use it on numbers), it is about infinite strings of two characters. See http://www.logicmuseum.com/cantor/diagarg.htm.



    Call them Cantor Strings. Cantor used "M" and "W" which, while they are visually interesting, are hard to distinguish. You can use "0" and "1" and claim they represent fractions in binary representation, but there is a problem. For example, 5/16 has two such binary representations: 0.01010000... and 0.01001111... . So you can't claim a number is missing, if all you prove is that a string is missing.



    Ignoring this fault, as most treatments do, your very first statement is not what Cantor does "ME: Suppose there is an ordered list containing all the (Cantor Strings)." The first step of Cantor's Proof is "Consider ANY list that links every natural number to a unique Cantor String." Nowhere is it assumed that this means all Cantor Strings.



    In fact, diagonalization proves the opposite. It proves: "If you have a set of Cantor Stings that can be listed this way, then it does not include all Cantor Strings."



    It is a simple trick of logic to invert the statement "If A, then B" to get the 100% equivalent statement "If NOT B, then NOT A." So diagonalization also proves "If you have a set of all Cantor Strings, then it can't be listed this way."



    Elegant, no?



    The reason so many Anti-Cantor cranks exists, is because we don;t seem to teach Cantor's proof correctly.






    share|cite|improve this answer











    $endgroup$









    • 1




      $begingroup$
      I actually make the point that you're making later on in the dialogue; look at where it says "Forget about the purported complete lists of real numbers for a moment..." The problem is, when I phrase the proof that way, the cranks' retort is that they do not think that the diagonalization procedure will always work in constructing a well-defined real number (or infinite string if you prefer). They think that the diagonalization procedure is not well-defined if you start with a list that happens to be complete. The problem is that they're misdiagnosing the source of the contradiction.
      $endgroup$
      – Keshav Srinivasan
      Apr 16 '16 at 20:27












    • $begingroup$
      I'd agree, if you you'd said "They think that the diagonalization procedure is not well-defined if you start with a list that happens to be INFINITE." The two are not the same, and I do feel it is the "infinite" part that confuses them. Not the "complete" part.
      $endgroup$
      – JeffJo
      Apr 17 '16 at 19:09












    • $begingroup$
      No, they're fine with infinite lists. Like if you start with an infinite list of the form .0111111... then .1011111... then .1101111... etc., they think diagonalization is a well-defined procedure. But they think that if the list happens to be complete, then the diagonalization process is not well-defined. That's because if the list was complete and the diagonalization procedure was well-defined, then the number being constructed would be somewhere in the list, say the Nth spot. And then Nth digit of that number would be ill-defined, because it's required to differ from itself.
      $endgroup$
      – Keshav Srinivasan
      Apr 17 '16 at 19:51










    • $begingroup$
      So they think that the diagonalization process is only well-defined for those lists which do not contain the number which would be constructed through diagonalization. Like I said, the problem is that they're misdiagnosing the source of the contradiction. They don't understand that the diagonalization process is well-defined for all lists.
      $endgroup$
      – Keshav Srinivasan
      Apr 17 '16 at 19:54










    • $begingroup$
      And I think that their difficulty comes when they try to correlate the infinite length of the strings, to the infinite length of the assumed "complete" list. The question they have - the one behind the imagined contradiction you describe - is "If the list is infinite, how can it not contain all possible strings?" The answer is that you can correlate two infinities in more than one way, and some ways miss elements of one..
      $endgroup$
      – JeffJo
      Apr 18 '16 at 13:56














    3












    3








    3





    $begingroup$

    Cantor's proof is not about numbers at all (there is a problem with trying to use it on numbers), it is about infinite strings of two characters. See http://www.logicmuseum.com/cantor/diagarg.htm.



    Call them Cantor Strings. Cantor used "M" and "W" which, while they are visually interesting, are hard to distinguish. You can use "0" and "1" and claim they represent fractions in binary representation, but there is a problem. For example, 5/16 has two such binary representations: 0.01010000... and 0.01001111... . So you can't claim a number is missing, if all you prove is that a string is missing.



    Ignoring this fault, as most treatments do, your very first statement is not what Cantor does "ME: Suppose there is an ordered list containing all the (Cantor Strings)." The first step of Cantor's Proof is "Consider ANY list that links every natural number to a unique Cantor String." Nowhere is it assumed that this means all Cantor Strings.



    In fact, diagonalization proves the opposite. It proves: "If you have a set of Cantor Stings that can be listed this way, then it does not include all Cantor Strings."



    It is a simple trick of logic to invert the statement "If A, then B" to get the 100% equivalent statement "If NOT B, then NOT A." So diagonalization also proves "If you have a set of all Cantor Strings, then it can't be listed this way."



    Elegant, no?



    The reason so many Anti-Cantor cranks exists, is because we don;t seem to teach Cantor's proof correctly.






    share|cite|improve this answer











    $endgroup$



    Cantor's proof is not about numbers at all (there is a problem with trying to use it on numbers), it is about infinite strings of two characters. See http://www.logicmuseum.com/cantor/diagarg.htm.



    Call them Cantor Strings. Cantor used "M" and "W" which, while they are visually interesting, are hard to distinguish. You can use "0" and "1" and claim they represent fractions in binary representation, but there is a problem. For example, 5/16 has two such binary representations: 0.01010000... and 0.01001111... . So you can't claim a number is missing, if all you prove is that a string is missing.



    Ignoring this fault, as most treatments do, your very first statement is not what Cantor does "ME: Suppose there is an ordered list containing all the (Cantor Strings)." The first step of Cantor's Proof is "Consider ANY list that links every natural number to a unique Cantor String." Nowhere is it assumed that this means all Cantor Strings.



    In fact, diagonalization proves the opposite. It proves: "If you have a set of Cantor Stings that can be listed this way, then it does not include all Cantor Strings."



    It is a simple trick of logic to invert the statement "If A, then B" to get the 100% equivalent statement "If NOT B, then NOT A." So diagonalization also proves "If you have a set of all Cantor Strings, then it can't be listed this way."



    Elegant, no?



    The reason so many Anti-Cantor cranks exists, is because we don;t seem to teach Cantor's proof correctly.







    share|cite|improve this answer














    share|cite|improve this answer



    share|cite|improve this answer








    edited May 19 '16 at 23:49

























    answered Apr 16 '16 at 20:04









    JeffJoJeffJo

    1554




    1554








    • 1




      $begingroup$
      I actually make the point that you're making later on in the dialogue; look at where it says "Forget about the purported complete lists of real numbers for a moment..." The problem is, when I phrase the proof that way, the cranks' retort is that they do not think that the diagonalization procedure will always work in constructing a well-defined real number (or infinite string if you prefer). They think that the diagonalization procedure is not well-defined if you start with a list that happens to be complete. The problem is that they're misdiagnosing the source of the contradiction.
      $endgroup$
      – Keshav Srinivasan
      Apr 16 '16 at 20:27












    • $begingroup$
      I'd agree, if you you'd said "They think that the diagonalization procedure is not well-defined if you start with a list that happens to be INFINITE." The two are not the same, and I do feel it is the "infinite" part that confuses them. Not the "complete" part.
      $endgroup$
      – JeffJo
      Apr 17 '16 at 19:09












    • $begingroup$
      No, they're fine with infinite lists. Like if you start with an infinite list of the form .0111111... then .1011111... then .1101111... etc., they think diagonalization is a well-defined procedure. But they think that if the list happens to be complete, then the diagonalization process is not well-defined. That's because if the list was complete and the diagonalization procedure was well-defined, then the number being constructed would be somewhere in the list, say the Nth spot. And then Nth digit of that number would be ill-defined, because it's required to differ from itself.
      $endgroup$
      – Keshav Srinivasan
      Apr 17 '16 at 19:51










    • $begingroup$
      So they think that the diagonalization process is only well-defined for those lists which do not contain the number which would be constructed through diagonalization. Like I said, the problem is that they're misdiagnosing the source of the contradiction. They don't understand that the diagonalization process is well-defined for all lists.
      $endgroup$
      – Keshav Srinivasan
      Apr 17 '16 at 19:54










    • $begingroup$
      And I think that their difficulty comes when they try to correlate the infinite length of the strings, to the infinite length of the assumed "complete" list. The question they have - the one behind the imagined contradiction you describe - is "If the list is infinite, how can it not contain all possible strings?" The answer is that you can correlate two infinities in more than one way, and some ways miss elements of one..
      $endgroup$
      – JeffJo
      Apr 18 '16 at 13:56














    • 1




      $begingroup$
      I actually make the point that you're making later on in the dialogue; look at where it says "Forget about the purported complete lists of real numbers for a moment..." The problem is, when I phrase the proof that way, the cranks' retort is that they do not think that the diagonalization procedure will always work in constructing a well-defined real number (or infinite string if you prefer). They think that the diagonalization procedure is not well-defined if you start with a list that happens to be complete. The problem is that they're misdiagnosing the source of the contradiction.
      $endgroup$
      – Keshav Srinivasan
      Apr 16 '16 at 20:27












    • $begingroup$
      I'd agree, if you you'd said "They think that the diagonalization procedure is not well-defined if you start with a list that happens to be INFINITE." The two are not the same, and I do feel it is the "infinite" part that confuses them. Not the "complete" part.
      $endgroup$
      – JeffJo
      Apr 17 '16 at 19:09












    • $begingroup$
      No, they're fine with infinite lists. Like if you start with an infinite list of the form .0111111... then .1011111... then .1101111... etc., they think diagonalization is a well-defined procedure. But they think that if the list happens to be complete, then the diagonalization process is not well-defined. That's because if the list was complete and the diagonalization procedure was well-defined, then the number being constructed would be somewhere in the list, say the Nth spot. And then Nth digit of that number would be ill-defined, because it's required to differ from itself.
      $endgroup$
      – Keshav Srinivasan
      Apr 17 '16 at 19:51










    • $begingroup$
      So they think that the diagonalization process is only well-defined for those lists which do not contain the number which would be constructed through diagonalization. Like I said, the problem is that they're misdiagnosing the source of the contradiction. They don't understand that the diagonalization process is well-defined for all lists.
      $endgroup$
      – Keshav Srinivasan
      Apr 17 '16 at 19:54










    • $begingroup$
      And I think that their difficulty comes when they try to correlate the infinite length of the strings, to the infinite length of the assumed "complete" list. The question they have - the one behind the imagined contradiction you describe - is "If the list is infinite, how can it not contain all possible strings?" The answer is that you can correlate two infinities in more than one way, and some ways miss elements of one..
      $endgroup$
      – JeffJo
      Apr 18 '16 at 13:56








    1




    1




    $begingroup$
    I actually make the point that you're making later on in the dialogue; look at where it says "Forget about the purported complete lists of real numbers for a moment..." The problem is, when I phrase the proof that way, the cranks' retort is that they do not think that the diagonalization procedure will always work in constructing a well-defined real number (or infinite string if you prefer). They think that the diagonalization procedure is not well-defined if you start with a list that happens to be complete. The problem is that they're misdiagnosing the source of the contradiction.
    $endgroup$
    – Keshav Srinivasan
    Apr 16 '16 at 20:27






    $begingroup$
    I actually make the point that you're making later on in the dialogue; look at where it says "Forget about the purported complete lists of real numbers for a moment..." The problem is, when I phrase the proof that way, the cranks' retort is that they do not think that the diagonalization procedure will always work in constructing a well-defined real number (or infinite string if you prefer). They think that the diagonalization procedure is not well-defined if you start with a list that happens to be complete. The problem is that they're misdiagnosing the source of the contradiction.
    $endgroup$
    – Keshav Srinivasan
    Apr 16 '16 at 20:27














    $begingroup$
    I'd agree, if you you'd said "They think that the diagonalization procedure is not well-defined if you start with a list that happens to be INFINITE." The two are not the same, and I do feel it is the "infinite" part that confuses them. Not the "complete" part.
    $endgroup$
    – JeffJo
    Apr 17 '16 at 19:09






    $begingroup$
    I'd agree, if you you'd said "They think that the diagonalization procedure is not well-defined if you start with a list that happens to be INFINITE." The two are not the same, and I do feel it is the "infinite" part that confuses them. Not the "complete" part.
    $endgroup$
    – JeffJo
    Apr 17 '16 at 19:09














    $begingroup$
    No, they're fine with infinite lists. Like if you start with an infinite list of the form .0111111... then .1011111... then .1101111... etc., they think diagonalization is a well-defined procedure. But they think that if the list happens to be complete, then the diagonalization process is not well-defined. That's because if the list was complete and the diagonalization procedure was well-defined, then the number being constructed would be somewhere in the list, say the Nth spot. And then Nth digit of that number would be ill-defined, because it's required to differ from itself.
    $endgroup$
    – Keshav Srinivasan
    Apr 17 '16 at 19:51




    $begingroup$
    No, they're fine with infinite lists. Like if you start with an infinite list of the form .0111111... then .1011111... then .1101111... etc., they think diagonalization is a well-defined procedure. But they think that if the list happens to be complete, then the diagonalization process is not well-defined. That's because if the list was complete and the diagonalization procedure was well-defined, then the number being constructed would be somewhere in the list, say the Nth spot. And then Nth digit of that number would be ill-defined, because it's required to differ from itself.
    $endgroup$
    – Keshav Srinivasan
    Apr 17 '16 at 19:51












    $begingroup$
    So they think that the diagonalization process is only well-defined for those lists which do not contain the number which would be constructed through diagonalization. Like I said, the problem is that they're misdiagnosing the source of the contradiction. They don't understand that the diagonalization process is well-defined for all lists.
    $endgroup$
    – Keshav Srinivasan
    Apr 17 '16 at 19:54




    $begingroup$
    So they think that the diagonalization process is only well-defined for those lists which do not contain the number which would be constructed through diagonalization. Like I said, the problem is that they're misdiagnosing the source of the contradiction. They don't understand that the diagonalization process is well-defined for all lists.
    $endgroup$
    – Keshav Srinivasan
    Apr 17 '16 at 19:54












    $begingroup$
    And I think that their difficulty comes when they try to correlate the infinite length of the strings, to the infinite length of the assumed "complete" list. The question they have - the one behind the imagined contradiction you describe - is "If the list is infinite, how can it not contain all possible strings?" The answer is that you can correlate two infinities in more than one way, and some ways miss elements of one..
    $endgroup$
    – JeffJo
    Apr 18 '16 at 13:56




    $begingroup$
    And I think that their difficulty comes when they try to correlate the infinite length of the strings, to the infinite length of the assumed "complete" list. The question they have - the one behind the imagined contradiction you describe - is "If the list is infinite, how can it not contain all possible strings?" The answer is that you can correlate two infinities in more than one way, and some ways miss elements of one..
    $endgroup$
    – JeffJo
    Apr 18 '16 at 13:56











    2












    $begingroup$

    I think the only way would be to find a different proof that holds against the main concern of the typical objections:

    Does the constructed number actually exist?



    I'll try to illustrate a proof that can address this concern.

    Let's consider lists of real numbers written in base 10 and build a number from the list using this rule:




    If the n^th digit of the n^th number of the list is 1, we change it to 2, otherwise we change it to 1.




    We're assuming the list is made of infinite rows; if not, we could always repeat the same numbers from the beginning in the same order and get our new number.

    Let's give a name to numbers that can be obtained from lists with this particular rule: if I wanted to be specific, I would call them something like "(1->2)(else->1) diagonals", but for the sake of brevity i'll call them diagonals.

    Any real with some digit different than 1 or 2 is not diagonal.

    If a real only has ones and twos, it could be diagonal.



    Note that if reals are countable, both diagonals and not diagonals are countable (as you could just list them in the order you found for the reals)



    Now, what if we listed all the not diagonals?
    From where we are, we couldn't immediately conclude that the not diagonals are uncountable, since the diagonal number of the list of course wouldn't be in the list of not diagonal numbers.

    But it exists: it's something made of just ones and twos. probably more ones.

    So, there are diagonal numbers: you can easily imagine them in this setting.



    But, what if we listed all diagonal numbers?



    It's a list, so it has a diagonal number, not in the list by construction.

    But it's a list of diagonals: it should have its diagonal number.
    So, usual argument, usual contradiction, just in a slightly different setting: in here, you can conclude that diagonal numbers aren't countable, but you can't say the same about not diagonal numbers. (at least, not immediately)
    But it doesn't matter, because the real numbers are made of diagonals and not diagonals, and if diagonals are not countable, neither are real numbers!



    So, my hope is that this argument could break the chain a bit, since it does provide a list of real numbers that doesn't contain its diagonal (the not diagonals), which you don't need to prove are uncountable, but also a list of real numbers that, if it existed, it couldn't contain its diagonal nor not contain it.

    Basically, good cop and bad cop i guess? Except with lists.






    share|cite|improve this answer









    $endgroup$













    • $begingroup$
      I think they would still make the same objection I discuss in my question: they would say that it's possible to construct a diagonal for the list of all non-diagonals, but it's impossible to construct a diagonal for the list of all diagonals. And their reasoning would be that if the diagonal for the list of diagonals did exist, then it would have to differ from itself, which is impossible. Therefore, the list of diagonals can't have a diagonal. The fundamental problem is that they don't realize that taking the diagonal is a valid operation for all lists.
      $endgroup$
      – Keshav Srinivasan
      May 7 '15 at 20:23










    • $begingroup$
      Well, the arguments in the essence are the same, so yes, it's likely things wouldn't change at all. But, sometimes a minimal superficial change can trigger a different reaction, even if the math behind it is the same... I mean, the reasoning to get is that one, there's no way around it. One can only arrange the same arguments in a different fashion, so that the counterarguments can fall in a different way until they hopefully unclick by themselves.
      $endgroup$
      – byserpas
      May 7 '15 at 20:43
















    2












    $begingroup$

    I think the only way would be to find a different proof that holds against the main concern of the typical objections:

    Does the constructed number actually exist?



    I'll try to illustrate a proof that can address this concern.

    Let's consider lists of real numbers written in base 10 and build a number from the list using this rule:




    If the n^th digit of the n^th number of the list is 1, we change it to 2, otherwise we change it to 1.




    We're assuming the list is made of infinite rows; if not, we could always repeat the same numbers from the beginning in the same order and get our new number.

    Let's give a name to numbers that can be obtained from lists with this particular rule: if I wanted to be specific, I would call them something like "(1->2)(else->1) diagonals", but for the sake of brevity i'll call them diagonals.

    Any real with some digit different than 1 or 2 is not diagonal.

    If a real only has ones and twos, it could be diagonal.



    Note that if reals are countable, both diagonals and not diagonals are countable (as you could just list them in the order you found for the reals)



    Now, what if we listed all the not diagonals?
    From where we are, we couldn't immediately conclude that the not diagonals are uncountable, since the diagonal number of the list of course wouldn't be in the list of not diagonal numbers.

    But it exists: it's something made of just ones and twos. probably more ones.

    So, there are diagonal numbers: you can easily imagine them in this setting.



    But, what if we listed all diagonal numbers?



    It's a list, so it has a diagonal number, not in the list by construction.

    But it's a list of diagonals: it should have its diagonal number.
    So, usual argument, usual contradiction, just in a slightly different setting: in here, you can conclude that diagonal numbers aren't countable, but you can't say the same about not diagonal numbers. (at least, not immediately)
    But it doesn't matter, because the real numbers are made of diagonals and not diagonals, and if diagonals are not countable, neither are real numbers!



    So, my hope is that this argument could break the chain a bit, since it does provide a list of real numbers that doesn't contain its diagonal (the not diagonals), which you don't need to prove are uncountable, but also a list of real numbers that, if it existed, it couldn't contain its diagonal nor not contain it.

    Basically, good cop and bad cop i guess? Except with lists.






    share|cite|improve this answer









    $endgroup$













    • $begingroup$
      I think they would still make the same objection I discuss in my question: they would say that it's possible to construct a diagonal for the list of all non-diagonals, but it's impossible to construct a diagonal for the list of all diagonals. And their reasoning would be that if the diagonal for the list of diagonals did exist, then it would have to differ from itself, which is impossible. Therefore, the list of diagonals can't have a diagonal. The fundamental problem is that they don't realize that taking the diagonal is a valid operation for all lists.
      $endgroup$
      – Keshav Srinivasan
      May 7 '15 at 20:23










    • $begingroup$
      Well, the arguments in the essence are the same, so yes, it's likely things wouldn't change at all. But, sometimes a minimal superficial change can trigger a different reaction, even if the math behind it is the same... I mean, the reasoning to get is that one, there's no way around it. One can only arrange the same arguments in a different fashion, so that the counterarguments can fall in a different way until they hopefully unclick by themselves.
      $endgroup$
      – byserpas
      May 7 '15 at 20:43














    2












    2








    2





    $begingroup$

    I think the only way would be to find a different proof that holds against the main concern of the typical objections:

    Does the constructed number actually exist?



    I'll try to illustrate a proof that can address this concern.

    Let's consider lists of real numbers written in base 10 and build a number from the list using this rule:




    If the n^th digit of the n^th number of the list is 1, we change it to 2, otherwise we change it to 1.




    We're assuming the list is made of infinite rows; if not, we could always repeat the same numbers from the beginning in the same order and get our new number.

    Let's give a name to numbers that can be obtained from lists with this particular rule: if I wanted to be specific, I would call them something like "(1->2)(else->1) diagonals", but for the sake of brevity i'll call them diagonals.

    Any real with some digit different than 1 or 2 is not diagonal.

    If a real only has ones and twos, it could be diagonal.



    Note that if reals are countable, both diagonals and not diagonals are countable (as you could just list them in the order you found for the reals)



    Now, what if we listed all the not diagonals?
    From where we are, we couldn't immediately conclude that the not diagonals are uncountable, since the diagonal number of the list of course wouldn't be in the list of not diagonal numbers.

    But it exists: it's something made of just ones and twos. probably more ones.

    So, there are diagonal numbers: you can easily imagine them in this setting.



    But, what if we listed all diagonal numbers?



    It's a list, so it has a diagonal number, not in the list by construction.

    But it's a list of diagonals: it should have its diagonal number.
    So, usual argument, usual contradiction, just in a slightly different setting: in here, you can conclude that diagonal numbers aren't countable, but you can't say the same about not diagonal numbers. (at least, not immediately)
    But it doesn't matter, because the real numbers are made of diagonals and not diagonals, and if diagonals are not countable, neither are real numbers!



    So, my hope is that this argument could break the chain a bit, since it does provide a list of real numbers that doesn't contain its diagonal (the not diagonals), which you don't need to prove are uncountable, but also a list of real numbers that, if it existed, it couldn't contain its diagonal nor not contain it.

    Basically, good cop and bad cop i guess? Except with lists.






    share|cite|improve this answer









    $endgroup$



    I think the only way would be to find a different proof that holds against the main concern of the typical objections:

    Does the constructed number actually exist?



    I'll try to illustrate a proof that can address this concern.

    Let's consider lists of real numbers written in base 10 and build a number from the list using this rule:




    If the n^th digit of the n^th number of the list is 1, we change it to 2, otherwise we change it to 1.




    We're assuming the list is made of infinite rows; if not, we could always repeat the same numbers from the beginning in the same order and get our new number.

    Let's give a name to numbers that can be obtained from lists with this particular rule: if I wanted to be specific, I would call them something like "(1->2)(else->1) diagonals", but for the sake of brevity i'll call them diagonals.

    Any real with some digit different than 1 or 2 is not diagonal.

    If a real only has ones and twos, it could be diagonal.



    Note that if reals are countable, both diagonals and not diagonals are countable (as you could just list them in the order you found for the reals)



    Now, what if we listed all the not diagonals?
    From where we are, we couldn't immediately conclude that the not diagonals are uncountable, since the diagonal number of the list of course wouldn't be in the list of not diagonal numbers.

    But it exists: it's something made of just ones and twos. probably more ones.

    So, there are diagonal numbers: you can easily imagine them in this setting.



    But, what if we listed all diagonal numbers?



    It's a list, so it has a diagonal number, not in the list by construction.

    But it's a list of diagonals: it should have its diagonal number.
    So, usual argument, usual contradiction, just in a slightly different setting: in here, you can conclude that diagonal numbers aren't countable, but you can't say the same about not diagonal numbers. (at least, not immediately)
    But it doesn't matter, because the real numbers are made of diagonals and not diagonals, and if diagonals are not countable, neither are real numbers!



    So, my hope is that this argument could break the chain a bit, since it does provide a list of real numbers that doesn't contain its diagonal (the not diagonals), which you don't need to prove are uncountable, but also a list of real numbers that, if it existed, it couldn't contain its diagonal nor not contain it.

    Basically, good cop and bad cop i guess? Except with lists.







    share|cite|improve this answer












    share|cite|improve this answer



    share|cite|improve this answer










    answered May 7 '15 at 20:16









    byserpasbyserpas

    427310




    427310












    • $begingroup$
      I think they would still make the same objection I discuss in my question: they would say that it's possible to construct a diagonal for the list of all non-diagonals, but it's impossible to construct a diagonal for the list of all diagonals. And their reasoning would be that if the diagonal for the list of diagonals did exist, then it would have to differ from itself, which is impossible. Therefore, the list of diagonals can't have a diagonal. The fundamental problem is that they don't realize that taking the diagonal is a valid operation for all lists.
      $endgroup$
      – Keshav Srinivasan
      May 7 '15 at 20:23










    • $begingroup$
      Well, the arguments in the essence are the same, so yes, it's likely things wouldn't change at all. But, sometimes a minimal superficial change can trigger a different reaction, even if the math behind it is the same... I mean, the reasoning to get is that one, there's no way around it. One can only arrange the same arguments in a different fashion, so that the counterarguments can fall in a different way until they hopefully unclick by themselves.
      $endgroup$
      – byserpas
      May 7 '15 at 20:43


















    • $begingroup$
      I think they would still make the same objection I discuss in my question: they would say that it's possible to construct a diagonal for the list of all non-diagonals, but it's impossible to construct a diagonal for the list of all diagonals. And their reasoning would be that if the diagonal for the list of diagonals did exist, then it would have to differ from itself, which is impossible. Therefore, the list of diagonals can't have a diagonal. The fundamental problem is that they don't realize that taking the diagonal is a valid operation for all lists.
      $endgroup$
      – Keshav Srinivasan
      May 7 '15 at 20:23










    • $begingroup$
      Well, the arguments in the essence are the same, so yes, it's likely things wouldn't change at all. But, sometimes a minimal superficial change can trigger a different reaction, even if the math behind it is the same... I mean, the reasoning to get is that one, there's no way around it. One can only arrange the same arguments in a different fashion, so that the counterarguments can fall in a different way until they hopefully unclick by themselves.
      $endgroup$
      – byserpas
      May 7 '15 at 20:43
















    $begingroup$
    I think they would still make the same objection I discuss in my question: they would say that it's possible to construct a diagonal for the list of all non-diagonals, but it's impossible to construct a diagonal for the list of all diagonals. And their reasoning would be that if the diagonal for the list of diagonals did exist, then it would have to differ from itself, which is impossible. Therefore, the list of diagonals can't have a diagonal. The fundamental problem is that they don't realize that taking the diagonal is a valid operation for all lists.
    $endgroup$
    – Keshav Srinivasan
    May 7 '15 at 20:23




    $begingroup$
    I think they would still make the same objection I discuss in my question: they would say that it's possible to construct a diagonal for the list of all non-diagonals, but it's impossible to construct a diagonal for the list of all diagonals. And their reasoning would be that if the diagonal for the list of diagonals did exist, then it would have to differ from itself, which is impossible. Therefore, the list of diagonals can't have a diagonal. The fundamental problem is that they don't realize that taking the diagonal is a valid operation for all lists.
    $endgroup$
    – Keshav Srinivasan
    May 7 '15 at 20:23












    $begingroup$
    Well, the arguments in the essence are the same, so yes, it's likely things wouldn't change at all. But, sometimes a minimal superficial change can trigger a different reaction, even if the math behind it is the same... I mean, the reasoning to get is that one, there's no way around it. One can only arrange the same arguments in a different fashion, so that the counterarguments can fall in a different way until they hopefully unclick by themselves.
    $endgroup$
    – byserpas
    May 7 '15 at 20:43




    $begingroup$
    Well, the arguments in the essence are the same, so yes, it's likely things wouldn't change at all. But, sometimes a minimal superficial change can trigger a different reaction, even if the math behind it is the same... I mean, the reasoning to get is that one, there's no way around it. One can only arrange the same arguments in a different fashion, so that the counterarguments can fall in a different way until they hopefully unclick by themselves.
    $endgroup$
    – byserpas
    May 7 '15 at 20:43











    -2












    $begingroup$

    First off, there are formally verified proofs of the theorem. In fact, every major theorem proof system or proof explorer has proved it, and it is number 22 in the classic "100 theorems" benchmark: http://www.cs.ru.nl/~freek/100/



    The problem is one may not accept the axioms and rules of inference.



    However, that is not the only problem. One may not even accept the statement as it is stated. I will show an alternative statement, which may be what the cranks have in mind.



    Consider a Gödel numbering or any similar scheme from the naturals to the formulas of set theory. Clearly, this numbering lists all the possible formulas of set theory.



    Since real numbers are merely formulas of set theory, the encoding will define every real number. This last statement is bound to be controversial, but nonetheless it's a valid definition of what it means to be a real number and your cranky friends could be utilizing it. (In fact, if I am understanding Asaf correctly, interestingly enough, this is the usual definition: Undefinable Real Numbers )



    No idea why this got a down-vote and a delete request. The point was not brought forward in the previous answers and is based on Hamkin's answer: https://mathoverflow.net/questions/44102/is-the-analysis-as-taught-in-universities-in-fact-the-analysis-of-definable-numb#answer-44129



    Simply substitute definable real number in place of real number and the diagonalization proof no longer works. Note that each real number may be definable.






    share|cite|improve this answer











    $endgroup$


















      -2












      $begingroup$

      First off, there are formally verified proofs of the theorem. In fact, every major theorem proof system or proof explorer has proved it, and it is number 22 in the classic "100 theorems" benchmark: http://www.cs.ru.nl/~freek/100/



      The problem is one may not accept the axioms and rules of inference.



      However, that is not the only problem. One may not even accept the statement as it is stated. I will show an alternative statement, which may be what the cranks have in mind.



      Consider a Gödel numbering or any similar scheme from the naturals to the formulas of set theory. Clearly, this numbering lists all the possible formulas of set theory.



      Since real numbers are merely formulas of set theory, the encoding will define every real number. This last statement is bound to be controversial, but nonetheless it's a valid definition of what it means to be a real number and your cranky friends could be utilizing it. (In fact, if I am understanding Asaf correctly, interestingly enough, this is the usual definition: Undefinable Real Numbers )



      No idea why this got a down-vote and a delete request. The point was not brought forward in the previous answers and is based on Hamkin's answer: https://mathoverflow.net/questions/44102/is-the-analysis-as-taught-in-universities-in-fact-the-analysis-of-definable-numb#answer-44129



      Simply substitute definable real number in place of real number and the diagonalization proof no longer works. Note that each real number may be definable.






      share|cite|improve this answer











      $endgroup$
















        -2












        -2








        -2





        $begingroup$

        First off, there are formally verified proofs of the theorem. In fact, every major theorem proof system or proof explorer has proved it, and it is number 22 in the classic "100 theorems" benchmark: http://www.cs.ru.nl/~freek/100/



        The problem is one may not accept the axioms and rules of inference.



        However, that is not the only problem. One may not even accept the statement as it is stated. I will show an alternative statement, which may be what the cranks have in mind.



        Consider a Gödel numbering or any similar scheme from the naturals to the formulas of set theory. Clearly, this numbering lists all the possible formulas of set theory.



        Since real numbers are merely formulas of set theory, the encoding will define every real number. This last statement is bound to be controversial, but nonetheless it's a valid definition of what it means to be a real number and your cranky friends could be utilizing it. (In fact, if I am understanding Asaf correctly, interestingly enough, this is the usual definition: Undefinable Real Numbers )



        No idea why this got a down-vote and a delete request. The point was not brought forward in the previous answers and is based on Hamkin's answer: https://mathoverflow.net/questions/44102/is-the-analysis-as-taught-in-universities-in-fact-the-analysis-of-definable-numb#answer-44129



        Simply substitute definable real number in place of real number and the diagonalization proof no longer works. Note that each real number may be definable.






        share|cite|improve this answer











        $endgroup$



        First off, there are formally verified proofs of the theorem. In fact, every major theorem proof system or proof explorer has proved it, and it is number 22 in the classic "100 theorems" benchmark: http://www.cs.ru.nl/~freek/100/



        The problem is one may not accept the axioms and rules of inference.



        However, that is not the only problem. One may not even accept the statement as it is stated. I will show an alternative statement, which may be what the cranks have in mind.



        Consider a Gödel numbering or any similar scheme from the naturals to the formulas of set theory. Clearly, this numbering lists all the possible formulas of set theory.



        Since real numbers are merely formulas of set theory, the encoding will define every real number. This last statement is bound to be controversial, but nonetheless it's a valid definition of what it means to be a real number and your cranky friends could be utilizing it. (In fact, if I am understanding Asaf correctly, interestingly enough, this is the usual definition: Undefinable Real Numbers )



        No idea why this got a down-vote and a delete request. The point was not brought forward in the previous answers and is based on Hamkin's answer: https://mathoverflow.net/questions/44102/is-the-analysis-as-taught-in-universities-in-fact-the-analysis-of-definable-numb#answer-44129



        Simply substitute definable real number in place of real number and the diagonalization proof no longer works. Note that each real number may be definable.







        share|cite|improve this answer














        share|cite|improve this answer



        share|cite|improve this answer








        edited Jan 8 at 16:57

























        answered Jul 28 '18 at 1:34









        DoleDole

        899514




        899514

















            protected by user642796 Feb 19 '14 at 8:28



            Thank you for your interest in this question.
            Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).



            Would you like to answer one of these unanswered questions instead?



            -

            Popular posts from this blog

            Mario Kart Wii

            Image
            Please consider supporting The Cutting Room Floor on Patreon. Thanks for all your support! Mario Kart Wii From The Cutting Room Floor Jump to: navigation, search Mario Kart Wii Developer : Nintendo Publisher : Nintendo Platform : Wii Released in JP : April 10, 2008 Released in US : April 27, 2008 Released in EU : April 11, 2008 Released in AU : April 24, 2008 Released in KR : April 30, 2009 This game has unused animations. This game has unused areas. This game has unused code. This game has unused objects. This game has unused modes / minigames. This game has unused graphics. This game has unused models. This game has unused items. This game has unused music. This game has regional differences. This game has a notes page This game has a prerelease article Mario Kart Wii is the sixth game in the series (not counting Arcade editions), which intro...
            Read more

            The Binding of Isaac: Rebirth/Afterbirth

            Image
            Please consider supporting The Cutting Room Floor on Patreon. Thanks for all your support! The Binding of Isaac: Rebirth/Afterbirth From The Cutting Room Floor < The Binding of Isaac: Rebirth Jump to: navigation, search This is a sub-page of The Binding of Isaac: Rebirth . Afterbirth is the first expansion pack for Rebirth and features a variety of improvements. Contents 1 Unused Graphics 1.1 Old Man Keeper 1.2 Skinless Hush 1.3 Miscellaneous Unused Hush Sprites 1.4 Generosity achievement 1.5 Afterbirth+ Room Editor 1.6 Bearded Ultra Greed 1.7 Early Ultra Greed 1.8 Unused Brownie Expression 1.9 Frail's Spinning Head 1.10 Mom's Dead Hand Alt 2 Unused Audio 2.1 Unused Dead Womb Layer 2.2 Unused Hush Battle Outro 2.3 The Stain Grunt Unused Graphics Old Man Keeper Image file: gfxuimain me...
            Read more

            What does “Dominus providebit” mean?

            Image
            5 Does "Dominus providebit" mean "The Lord will provide" or "The Lord provides"? I once had a bit of an argument with a guy who studied Latin over that. It's an inscription that appears on the rim of some old Swiss coins that I have. meaning latin-to-english-translation grammar-identification share | improve this question edited Jan 18 at 15:27 V2Blast 105 4 asked Jan 17 at 22:49 Donald K. Donald K. 26 1 ...
            Read more