18 1. Logic and foundations compare the actual world against. In a similar spirit, an adversarial cross- examination, designed to poke holes in an alibi, can be viewed as roughly analogous to a proof by contradiction. Despite the presence of these non-mathematical analogies, though, proofs by contradiction are still often viewed with suspicion and unease by many students of mathematics. Perhaps the quintessential example of this is the standard proof of Cantor’s theorem that the set R of real numbers is un- countable. This is about as short and as elegant a proof by contradiction as one can have without being utterly trivial, and despite this (or perhaps because of this) it seems to offend the reason of many people when they are first exposed to it, to an extent far greater than most other results in mathematics8. In [Ta2010b, §1.15], I collected a family of well-known results in mathe- matics that were proven by contradiction, and specifically by a type of argu- ment that I called the “no-self-defeating object” argument that any object that was so ridiculously overpowered that it could be used to “defeat” its own existence, could not actually exist. Many basic results in mathematics can be phrased in this manner: not only Cantor’s theorem, but Euclid’s theorem on the infinitude of primes, G¨ odel’s incompleteness theorem, or the conclusion (from Russell’s paradox) that the class of all sets cannot itself be a set. In [Ta2010b, §1.15] each of these arguments was presented in the usual “proof by contradiction” manner I made the counterfactual hypothesis that the impossibly overpowered object existed, and then used this to eventually derive a contradiction. Mathematically, there is nothing wrong with this reasoning, but because the argument spends almost its entire duration in- side the bizarre counterfactual universe caused by an impossible hypothesis, readers who are not experienced with counterfactual thinking may view these arguments with unease. It was pointed out to me, though (originally with regards to Euclid’s theorem, but the same point in fact applies to the other results I presented), that one can pull a large fraction of each argument out of this counterfactual world, so that one can see most of the argument directly, without the need for any intrinsically impossible hypotheses. This is done by converting the “no- self-defeating object” argument into a logically equivalent “any object can be defeated” argument, with the former then being viewed as an immediate corollary of the latter. This change is almost trivial to enact (it is often little more than just taking the contrapositive of the original statement), 8The only other two examples I know of that come close to doing this are the fact that the real number 0.999 . . . is equal to 1, and the solution to the blue-eyed islanders puzzle (see [Ta2009, §1.1]).

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2013 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.