{"id":848,"date":"2010-03-09T20:26:38","date_gmt":"2010-03-09T20:26:38","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2010\/03\/09\/grandiose-crankery-cantor-godel-church-turing-morons\/"},"modified":"2010-03-09T20:26:38","modified_gmt":"2010-03-09T20:26:38","slug":"grandiose-crankery-cantor-godel-church-turing-morons","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2010\/03\/09\/grandiose-crankery-cantor-godel-church-turing-morons\/","title":{"rendered":"Grandiose Crankery: Cantor, Godel, Church, Turing, &#8230; Morons!"},"content":{"rendered":"<p> A bunch of people have been asking me to take a look at <a href=\"http:\/\/arxiv.org\/abs\/1002.4433\">yet another piece of Cantor crankery<\/a> recently posted to Arxiv. In general, I&#8217;m sick and tired of Cantor crankery &#8211; it&#8217;s been occupying much too much space on this blog lately. But this one is a real prize. It&#8217;s an approach that I&#8217;ve never seen before: instead of the usual weaseling around, this one goes straight for Cantor&#8217;s proof.<\/p>\n<p> But it does much, much more than that. In terms of ambition, this thing really takes the cake. According to the author, one J. A. Perez, he doesn&#8217;t just refute Cantor. No, that would be trivial! Every run-of-the-mill crackpot claims to refute cantor! Perez  claims to refute Cantor, G&ouml;del, Church, and Turing. Among others. He claims to reform the axiom of infinity in set theory to remove the problems that it supposedly causes. He claims to be able to use his reformed axiom of infinity together with his refutation of Cantor to get rid of the continuum hypothesis, and to eliminate any strange results proved by the axiom of choice.<\/p>\n<p> Yes, Mr. (Dr? Professor? J. Random Schmuck?) Perez is nothing if not a true mastermind, a mathematical genius of utterly epic proportions! The man who single-handedly refutes pretty much all of 20th century mathematics! The man who has determined that now we must throw away Cantor and G&ouml;del, and reinstate Hilbert&#8217;s program. The perfect mathematics is at hand, if we will only listen to his utter brilliance!<\/p>\n<p><!--more--><\/p>\n<p> To give you a bit of background: towards the beginning of the 20th century, mathematics was in a confused state. They&#8217;d just started to encounter problems with paradoxical statements in foundational things like set theory. David Hilbert, one of the great mathematicians of the time, set out a grand goal: to create the perfect mathematical foundation. The goal was to carefully start from first principles, and:<\/p>\n<ul>\n<li> create a precise formal system in which everything followed a set of strict, well-defined rules;\n<li> define the rules to prevent inconsistency by strictly preventing anything from reasoning about itself. This was done by by separating everything strictly into orders. A first order statement could talk about mathematical objects, but not about predicates. A second order statement could talk about objects and first-order predicates, but not about second-order predicates. A third order statement could talk about primitive objects, first order predicates, and second order predicates &#8211; but not about third. But within the system, you could never even formulate a statement in which a second-order predicate talked about a second-order predicate.<\/li>\n<li> the system was supposed to be complete: in it, all true statements could be <em>proved<\/em> to be true; all false statements could be <em>proved<\/em> to be false; and all statements were either true or false.<\/li>\n<li> the system was supposed to be consistent: no contradictions could ever be derived from valid applications of the system. Every statement was either true or false &#8211; there would be no statements that could be proved to be both true and false; and there would be no statements that could not be proved to be either true or false.<\/li>\n<li> the system was supposed to be <em>decidable<\/em>: there would be a mechanical process which, given any statement, would be able to tell you after a finite period of time whether the statement was true or false.<\/li>\n<\/ul>\n<p> Hilbert&#8217;s program was a huge deal. It consumed a huge amount of time and resources from the best mathematicians of the time. It&#8217;s well known for producing a major work by Russell and Whitehead called the Principia, which took hundreds of pages to work its way up to <a href=\"http:\/\/scienceblogs.com\/goodmath\/2006\/06\/extreme_math_1_1_2.php\">being able to prove that 1 + 1 = 2.<\/a> It was a truly epic project; but if it were successful, it would have put all of mathematics on a sound basis. It would, in some deep and important sense, have <em>completed<\/em> mathematics.<\/p>\n<p> Alas, G&ouml;del&#8217;s work blew Hilbert&#8217;s program right out of the water. You can&#8217;t built a complete, consistent system of mathematics. You can&#8217;t define a complete system of math with a decision procedure. But our intrepid genius claims that all of this is wrong: Cantor&#8217;s set theory is bogus, the set of reals is the same size as the set of natural numbers, G&ouml;del&#8217;s incompleteness theorems are wrong, Turing was wrong about computability, and we can re-instate Hilbert&#8217;s program, finish the Principia, and happily have the perfect mathematical system, with J. A. Perez as the most brilliant mathematician of all time.<\/p>\n<p> Except for the minor problem that he&#8217;s completely wrong.<\/p>\n<p> What he does is interesting, in a brain-dead sort of way. He basically tries to find a problem with the basic proof technique used by both Cantor and G&ouml;del. Of course, proof by contradiction is an old, well-respected proof system. You can&#8217;t just say that all proofs by contradiction are wrong. There are lots of really good proofs that are done by contradiction. But Cantor and G&ouml;del are obviously wrong, and yet both proofs look bulletproof &#8211; so there&#8217;s got to be something wrong with how they used proofs by contradiction.<\/p>\n<p> What he homed in on is what he calls internal contradiction versus external contradiction.<\/p>\n<p> He claim that the classical uses of proof by contradiction are what he calls external contradiction. In proof by external contradiction, you start with a statement P, which you want to prove is true. So you assume that it&#8217;s false, and then you use that to derive a contradiction. So you assume not-P, and then use that to derive a proof of some <em>other<\/em> statement, R, which is known to be false. So by the process of proof from not-P, you&#8217;ve derived the contradiction R&and;&not;R. By simple logic, that means that not-P allowed you to prove a false statement, which in turn means that not-P is false, and that means that P is true. Presto, you&#8217;ve got your proof.<\/p>\n<p> In contrast, Cantor and G&ouml;del are what he calls proof by <em>internal<\/em> contradiction. He claims that in these proofs, you start with the statement you want to prove &#8211; P. Then you negate P; and by using not-P, you can derive a proof that P is true. So not-P is used to derive P.Instead of &not;P deriving R&and;&not;R, &not;P is used to derive &not;P&and;P.<\/p>\n<p> It&#8217;s an interesting distinction in its way &#8211; it&#8217;s fundamentally a difference between a proof built on self-reference, and one that isn&#8217;t. Self-reference is the source of many problems &#8211; the fundamental paradoxical statements that have plagued modern math are all built on self reference: Cantor&#8217;s naive set theory was shown inconsistent by the use of a self-referential object: the set of all sets that do not contain themselves; G&ouml;del&#8217;s proof is build around the self referential statement &#8220;There is no proof that this statement is true&#8221;.<\/p>\n<p> But there&#8217;s no logical flaw with a proof that has a self-referential aspect. Or is there? Perez claims that there is.<\/p>\n<p> Let&#8217;s start with his version of a proof by external contradiction. He says that every proof is, essentially, a sequence of statements, Q<sub>1<\/sub>, Q<sub>2<\/sub>, &#8230;, Q<sub>n<\/sub>, where each statement Q<sub>i+1<\/sub> is an implication of Q<sub>n<\/sub>. So you can state a proof as Q<sub>1<\/sub> &rArr; Q<sub>2<\/sub> &rArr; &#8230; &rArr; Q<sub>n<\/sub>, where Q<sub>n<\/sub> is the conclusion. In this formulation, Q<sub>1<\/sub> is the statement &not;P &#8211; that is, the <em>negation<\/em> of the statement you want to prove; and Q<sub>n<\/sub> is the statement R&and;&not;R, where R is some statement that is neither P nor &not;P. (That last line is, according to Perez, very important. He repeats it several times in different ways.) So the entire proof can be reduced to &not;P&rArr;(R&and;&not;R).<\/p>\n<p> In a proof by <em>internal<\/em> contradiction, you&#8217;ve got the same basic setup, except that you start with &not;P, and you end up with &not;P&rArr;(&not;P&and;P). That is, the final contradiction that breaks the proof contains the initial false assumption.<\/p>\n<p> According to Perez, that&#8217;s potentially a problem. It isn&#8217;t <em>necessarily<\/em> a problem, but it might be. See, if you can reason backwards from the contradiction to cast doubt on any of the earlier statements, then according to him, the proof will fail.<\/p>\n<p> This is where things start to get a bit goofy. Suppose that in your basic proof schema, all of the implications were not just implications, but logical equivalences. That is, your proof schema for the proof by internal contradiction was: (&not;P)&hArr;Q<sub>2<\/sub>&hArr;&#8230;&hArr;Q<sub>n-1<\/sub>&hArr;(&not;P&and;P). Then you&#8217;ve got a known-falsehood at the end &#8211; and you can also use that backwards. So (&not;P&and;P) &hArr; Q<sub>n-1<\/sub>. And, in fact, (&not;P&and;P) imply each any every one of the Q<sub>i<\/sub>. So the invalid conclusion <em>implies<\/em> each of the statements in the proof &#8211; which means, according to Perez, that the truth of every statement is thrown into question; in fact, the proof by internal contradiction contains an implicit disproof of every true statement used in the proof. Since the entire proof technique is doing something that we know to be incorrect, that demonstrates that the proof by internal contradiction, when the logical connectives are equivalences, is invalid.<\/p>\n<p> If that proof technique is invalid, then every proof that was built using it is also invalid. So Cantor&#8217;s diagonalization goes out the window. And so does G&ouml;del. And so does most of Chaitin. And, well, lots of other stuff.<\/p>\n<p> The problem for Perez is that this argument is bogus in <em>so many ways<\/em>.<\/p>\n<p> Let&#8217;s take one nice one, which he&#8217;s absolutely explicit about. His proof schema is based on a proof as a sequence of <em>atomic<\/em> statements, each of which implies the following statement. That&#8217;s <em>not<\/em> the structure of a proof. A proof does have a series of implications leading to a conclusion, but it&#8217;s not linear. Proofs are <em>graphs<\/em> of implications, not lines.<\/p>\n<p> A perfect demonstration of how bogus this is comes from Perez&#8217;s discussion of Cantor&#8217;s diagonalization. According to Perez, you start with the statement P that you want to prove. In Cantor&#8217;s diagonalization, P is the statement: &#8220;The unit interval I = [0, 1)&#8221; is an uncountable set.&#8221;. The proof is sketched as:<\/p>\n<ol>\n<li> Take &not;P to use as the foundational step of the proof by contradiction: &not;P=&#8221;The unit interval I := [0, 1) is a countable set&#8221;.<\/li>\n<li> Q<sub>1<\/sub> = &#8220;The set I can be written out as an array of decimal expansions, &#8230;&#8221;<\/li>\n<li> Q<sub>2<\/sub> = &#8220;It is possible to define a real number &#8230; such that it belongs to the interval, but &#8230;&#8221;<\/li>\n<li> Q<sub>3<\/sub> = &#8220;The array is not a complete listing of the elements of I.&#8221;<\/li>\n<\/ol>\n<p> According to Perez, &not;P&hArr;Q<sub>1<\/sub>. That is <em>not<\/em> true: assuming that the interval is a countable set does <em>not<\/em> give you the fact that the set can be written out as an array of decimal expansions. The decimal expansions comes from an entirely different starting point. So the proof actually has two branches from the beginning. The proof isn&#8217;t a straight line of implication; it&#8217;s a branched structure. So the proof schema isn&#8217;t &#8220;&not;P&hArr;Q<sub>1<\/sub>&hArr;Q<sub>2<\/sub>&hArr;Q<sub>3<\/sub>.&#8221; It&#8217;s actually &#8220;&not;P. Q<sub>1<\/sub>. &not;P&and;Q<sub>1<\/sub>&and;&#8230;&harr;Q<sub>3<\/sub>.&#8221; (I left the dots, because there are still missing steps; &not;P&and;Q<sub>1<\/sub> isn&#8217;t enough to get to Q<sub>2<\/sub>.)<\/p>\n<p> The branching is a fundamental problem for Perez. Because what he wants to say is that every statement <em>used<\/em> in the proof is invalidated by the contradiction. But with logical connectives like &#8220;&and;&#8221;, that&#8217;s not true. Perez wants to say that since Q<sub>3<\/sub> provides a contradiction, that it invalidates Q<sub>2<\/sub>; which invalidates Q<sub>1<\/sub>. And, in fact, according to Perez&#8217;s reasoning, it does worse than that: it invalidates every axiom used in the proof &#8211; because the axioms are used as steps.<\/p>\n<p> But axioms aren&#8217;t used as discrete atomic steps of the proof implied by prior steps. They&#8217;re used as parts of complex statements. Axioms are used in the form &#8220;Q<sub>i<\/sub> &and; Axiom &hArr; Q<sub>i+1<\/sub>.&#8221; The negation of that doesn&#8217;t imply the negation of the axiom; it implies (&not;Q<sub>i<\/sub>) &or; &not;Axiom).<\/p>\n<p> And boom, there goes Perez&#8217;s proof; the structure of a proof by internal contradiction <em>doesn&#8217;t<\/em> imply the falsehood of every statement used in the proof. It doesn&#8217;t imply the falsehood of any axioms.<\/p>\n<p> But there&#8217;s more stupidity. One of the most basic rules of logic is that you can&#8217;t reason from contradiction. That is, given a statement like (A &and; &not;A), the statement is <em>always<\/em> false. Given any false statement, you can <em>arbitrarily<\/em> construct implications: for any possible statement S, no matter whether S is true or false, (A&and;&not;A)&hArr;S. The fact that a contradiction <em>implies<\/em> something is utterly worthless. You can never reason from that implication, because the statement (A&and;&not;A) is always false, so you can&#8217;t infer <em>anything<\/em> about the conclusion. The entire process that Perez uses, trying to trace backwards from a contradiction is fundamentally <em>meaningless<\/em>.<\/p>\n<p> From this point, things go downhill. Perez then verges into classic anti-Cantor-crackpot material, providing his version of several different constructions that allegedly demonstrate a correspondence between the natural numbers and the reals. And then he <em>really<\/em> goes off the deep end. <\/p>\n<p> Seriously, this is one of the most ridiculously grandiose works of crankery that I&#8217;ve ever seen.  This guy seriously believes that he&#8217;s pretty much the most brilliant mathematician in the history of mathematics, and that this paper is <em>the<\/em> ultimate mathematical tour-de-force. He&#8217;s probably sitting in his office waiting for his Fields medal.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>A bunch of people have been asking me to take a look at yet another piece of Cantor crankery recently posted to Arxiv. In general, I&#8217;m sick and tired of Cantor crankery &#8211; it&#8217;s been occupying much too much space on this blog lately. But this one is a real prize. It&#8217;s an approach that [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[11],"tags":[],"class_list":["post-848","post","type-post","status-publish","format-standard","hentry","category-cantor-crankery"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-dG","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/848","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=848"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/848\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=848"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=848"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=848"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}