I haven’t written a basics post in a while, because for the most part, that well has run dry, but once
\nin a while, one still pops up. I got an email recently asking about proofs by contradiction and
\ncounterexamples, and I thought that would be a great subject for a post. The email was really
\nsomeone trying to get me to do their homework for them, which I’m not going to do – but I can
\nexplain the ideas, and the relationships and differences between them.<\/p>\n
Proof by contradiction, also known as “reductio ad absurdum”, is one of the most beautiful proof
\ntechniques in math. In my experience, among proofs of difficult theorems, proofs by contradiction are the
\nmost easy to understand. The basic idea of them is very simple. Want to prove that something is true? Look
\nat what would happen if it were false. If you get a nonsensical, contradictory result from assuming its
\nfalse, then it must be true.<\/p>\n
<\/p>\n
Let’s be a bit more precise. The principle of proof by contradiction comes from the logical law of the
\nexcluded middle, which says “for any statement S, (S or not S) is true” – that is, S must be either true or false. From that, we can infer that if S in true, not S must be false; if not S is true, then S must be false. There is no third option. So if we can prove that (not S) is false, then we know that S must be true. The way that we can prove that (not S) is false is by assuming that it’s true, and showing that
\nthat leads to a contradictory result.<\/p>\n
The alterative form (which is really the same thing, but can look different when it’s presented by
\nmediocre teachers) is proving that something is false. Just switch S and not S in the above discussion. Proving that S is false is just another way of saying that we want to prove that (not S) is
\ntrue. In a proof by contradiction, we can do that by assuming that S is true, and showing that that
\nleads to a contradictory result.<\/p>\n
As always, things are best with an example. Since I’m a computer scientist, I’ll pull out
\nmy favorite proof by contradiction: the proof of the Halting theorem.<\/p>\n
Suppose you have a computer, which we’ll call φ. Every program for φ can be
\ndescribed by as a number. Similarly, every possibly input for a program can be represented
\nas a number. The result of running a particular program on φ can be described as a function
\nφ(p,i) where p is the program, and i is the input.<\/p>\n
One thing about programs is that they can contain infinite loops: there are some programs The answer is no. The way that we prove that is by a classic proof by contradiction. So we For another example, one of the classic logic errors is the misuse of implication. If you have a logical statement We can prove that that kind of inference is invalid. The way we’ll do it is by assuming its true, Presto, one proof by contradiction.<\/p>\n Often, as in the example above, when you do proof by contradiction, what you do is find a specific An important thing to be careful for in proofs by contradiction is that you are actually obtaining As an interesting concluding side-note, there are schools of mathematical thought that do not I haven’t written a basics post in a while, because for the most part, that well has run dry, but once in a while, one still pops up. I got an email recently asking about proofs by contradiction and counterexamples, and I thought that would be a great subject for a post. The email was […]<\/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":[74],"tags":[],"class_list":["post-546","post","type-post","status-publish","format-standard","hentry","category-basics"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-8O","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/546","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=546"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/546\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=546"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=546"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=546"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\nwhich for some inputs will run forever without producing any results. One thing that we would
\nreally like to know is for a program p with input i, will φ(p,i) ever return a result? If
\nit does, we say that program p halts<\/em> with input i. The big question is, can we
\nwrite a program h such that takes any pair of p and i as inputs, and tells us whether p halts with input i?<\/p>\n
\nstart by assuming that it’s true:<\/p>\n\n
\nhalts, and false otherwise.<\/p>\n
\nφ(h,(q,i)) returns true, then q enters an endless loop. Otherwise, q halts.<\/li>\n
\nsays that q doesn’t halt, then q halts. Therefore h isn’t a program which correctly says
\nwhether another program will halt. This contradicts the assumption in step one, so that
\nassumption must be false.<\/li>\n<\/ol>\n
\nthat for all possible values X, if A is true for X, then B must also true for that X, and you know that A is true for some specific thing Y, then you can infer that B must be true for Y. There’s a common error where you get that backwards: for all X, if A is true for X, then B must be true for X, and you know B is true for some specific Y, then inferring A is true for Y. That is not<\/em> valid inference – it’s false.<\/p>\n
\nand then reasoning from it.<\/p>\n\n
\n“B is true for Y”, then “A is true for Y”.<\/li>\n
\nand we’ll use it as an instantiation of the rule above: If we know that “If X is a man, then X is mortal, and we know that X is a mortal, then X is a man.”<\/li>\n
\nthat means that the statement cannot be true.<\/li>\n<\/ol>\n
\nexample which leads to a contradiction. If you can do that, that example is called a
\ncounter-example<\/em> for the disproven statement. Not all proofs by contradiction use specific
\ncounter-examples. A proof by contradiction can be done using a specific counterexample for which the
\nstatement is false. But it can also be done in a more general way by using general principles to show that
\nthere is a contradiction. Stylistically, it’s usually considered more elegant in a proof by
\ncontradiction to show a way o constructing a specific counterexample. In the two example proofs
\nI showed above, both proofs used counterexamples. The first proof used a constructed counter-example<\/em>: it didn’t show a specific counter-example, but it showed how to construct
\na counterexample. The second proof used a specific counter-example. Most<\/em> proofs
\nby contradiction rely on a constructed counter-example, but sometimes you can simply show by
\npure logic that the assumption leads to a contradiction.<\/p>\n
\ntrue contradictions<\/em>. Many creationist “proofs” about evolution, age of the universe, radiological
\ndating, and many other things are structured as proofs by contradiction; but the conclusion is merely
\nsomething that seems<\/em> unlikely, without actually being a logical contradiction. A very common
\nexample of this is the big-numbers argument, in which the creationist says “Suppose that life were the
\nproduct of natural processes. Then the following unlikely events would have had to occur. The probability
\nof that combination of events is incredibly small, therefore it couldn’t have happened.” That’s not
\na proof of any kind. There is no logical contradiction between “X has a probability of 1 in 101010<\/sup><\/sup> of occuring”, “X occured”. Improbable never equals impossible, no matter
\nhow small the probability – and so it can’t create a logical contradiction, which is required for
\na proof by contradiction.<\/p>\n
\nfully accept proof by contradiction. For example, intuitionism doesn’t accept the law
\nof the excluded middle, which limits proof by contradiction. Intuitionism also, by its
\nnature, requires that proofs of existence show how to construct an example. So a proof by
\ncontradiction that proves that something exists, by showing that assuming its non-existence
\nleads to a logical contradiction, are not considered valid existence proofs in intuitionistic
\nlogic. <\/p>\n","protected":false},"excerpt":{"rendered":"