1
$\begingroup$

Here, Terence Tao presents a collection of similar mathematical arguments that he calls "no self-defeating object" (examples are Euclids proof of the infinitude of the primes and Cantor's theorem). In the second post, he remarks that one can reformulate these "no-self defeating object" arguments to get a "every object can be defeated"-version.

The simplest example "no self-defeating object" goes as follows:

Proposition 1 (No largest natural number). There does not exist a natural number N that is larger than all the other natural numbers.

Proof: Suppose for contradiction that there was such a largest natural number N. Then N+1 is also a natural number which is strictly larger than N, contradicting the hypothesis that N is the largest natural number.

The corresponding "every object can be defeated"-version is:

Proposition 1′. Given any natural number N, one can find another natural number N' which is larger than N.

Proof. Take N' := N+1.

Terence Tao also remarks:

"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), but it does offer a slightly different “non-counterfactual” (or more precisely, “not necessarily counterfactual”) perspective on these arguments which may assist in understanding how they work."

My question: What has the contrapositive to do with the change from "no self-defeating object" to "every object can be defeated"?

As I understand it, the "no self-defeating object"-version is of the form "$\neg\exists x: P(x)$" and the "every object can be defeated"-version is "$\forall x:\neg P(x)$". That these are equivalent is de Morgan for quantifiers, what does it have to do with contrapositives?

$\endgroup$
  • 1
    $\begingroup$ Somewhat relevant. $\endgroup$ – Henning Makholm Oct 9 '16 at 12:14
  • $\begingroup$ @HenningMakholm: Ah, thanks. So do you think that Terence Tao just compared the change from $\neg\exists x : P(x)$ to $\forall x : \neg P(x)$ to taking the contrapositive, but is not saying that this is the same as taking contrapositives? $\endgroup$ – user376483 Oct 9 '16 at 12:45
  • 1
    $\begingroup$ I'm not privy to Tao's thoughts, so the most I'm saying is that I too see a similarity between this kind of rewriting and contraposition, and once mused that it might be useful to call it contraposition. (Not many here agreed with that, though -- but it nice to see perhaps Tao might). $\endgroup$ – Henning Makholm Oct 9 '16 at 12:48
  • 1
    $\begingroup$ One way to make it look more like a contrapositive is to view it as a change from "if $m$ is larger than all natural numbers then $m$ is not a natural number" to "if $m$ is a natural number then $m$ is not larger than all natural numbers". Of course, Tao only says that the process he describes is "often" "little more" than just taking the contrapositive, he does not claim that what he is doing is literally a contrapositive. I do find that mathematicians and logicians often use "contrapositive" informally in a broader sense than its formal meaning. $\endgroup$ – Carl Mummert Oct 9 '16 at 16:42
1
$\begingroup$

If, as is standard in presentations of intuitionistic logic, you treat $\lnot \phi$ as $\phi \Rightarrow \mathsf{false}$ then the role of the contrapositive here becomes clear: the contrapositive of:

$$(\exists N \in \Bbb{N}\cdot\forall m\in \Bbb{N}\cdot N > m) \Rightarrow \mathsf{false}$$

is:

$$\lnot \mathsf{false} \Rightarrow \lnot(\exists N \in \Bbb{N}\cdot\forall m\in \Bbb{N}\cdot N > m)$$

which, using De Morgan's laws and a tiny bit of arithmetic reasoning (to make things agree with Tao's presentation) is equivalent to: $$\forall N \in \Bbb{N}\cdot\exists m\in \Bbb{N}\cdot m > N.$$

This transformation giving Tao's Proposition $1'$ makes clear the innate constructive nature of the reasoning that is presented in disguise in the proof by contradiction in Tao's Proposition $1$.

$\endgroup$
  • $\begingroup$ After all, this also relies on De Morgan's rule, and I don't see why you first interpret $\phi$ as $\phi\implies\bot$ and form the contrapositive of $(\exists N \in \Bbb{N}\cdot\forall m\in \Bbb{N}\cdot N > m) \Rightarrow \mathsf{false}$. One could just form the contrapositive of $\exists N \in \Bbb{N}\cdot\forall m\in \Bbb{N}\cdot N \geq m$ which is $\exists N \in \Bbb{N}\cdot\forall m\in \Bbb{N}\cdot N > m$. $\endgroup$ – user377104 Oct 25 '16 at 17:24
  • $\begingroup$ Of course it relies on De Morgan's laws: the point is that the end result is a constructive truth that captures exactly what the proof actually proves. The reason for interpreting $\lnot \phi$ as $\phi \Rightarrow \mathsf{false}$ is because the notion of contrapositive is usually associated with implications: which is the point of the question: "what does this have to do with contrapositives?" The two existentially quantified statements that you claim are contrapositives are not contrapositives in any sense of the term that I am aware of. $\endgroup$ – Rob Arthan Oct 25 '16 at 19:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.