A calculus of the absurd

Chapter 6 Proof

We must not believe those, who today, with philosophical bearing and deliberative tone, prophesy the fall of culture and accept the ignorabimus [that we cannot know whether something is true or false]. For us there is no ignorabimus, and in my opinion none whatever in natural science. In opposition to the foolish ignorabimus our slogan shall be “Wir müssen wissen - wir werden wissen” [we must know — we will know]

— David Hilbert, RADIO ADDRESS IN 1930

The human mind is incapable of formulating (or mechanizing) all its mathematical intuitions, i.e., if it has succeeded in formulating some of them, this very fact yields new intuitive knowledge, e.g., the consistency of this formalism. This fact may be called the “incompletability” of mathematics. On the other hand, on the basis of what has been proved so far, it remains possible that there may exist (and even be empirically discoverable) a theorem proving machine which in fact is equivalent to mathematical intuition, but cannot be proved to be so, nor even be proved to yield only correct theorems of finitary number theory

Kurt Gödel, REMARKS ON HIS INCOMPLETENESS THEOREMS

6.1 Direct proof

A direct proof is where we show that a statement in the form “if \(A\), then \(B\)” is true by assuming that \(A\) is true, and showing that \(B\) must therefore also be true.

Example 6.1.1 Show that if \(k\) is an odd positive integer, then \(k^2\) is also odd.

We start by assuming that \(k\) is an odd positive integer. To do this, we want to find an algebraic way to represent \(k\). As every odd number can be written in the form⁴³⁴³ This can be proved by induction (see Section 6.3) \(2p + 1\) for suitable \(p\) (e.g. \(3 = 2\cdot 1 + 1\), \(5 = 2\cdot 2 + 1\), etc.) we can write \(k\) as \(2p + 1\). From there we apply our assumption to show that the result is true

\begin{align} (2p + 1)^2 &= 4p^2 + 4p + 1 \\ &= 2(2p^2 + 2p) + 1 \end{align}

As \(2(2p^2 + 2p) + 1\) is in the form⁴⁴⁴⁴ It’s not the specific expression or variable names which we chose that are important here - it’s the overarching structure of the expression - i.e. that it’s in the form \(2 \cdot \text {something} + 1\) which is important. \(2x + 1\), we have shown that this is true.

\(\Box \)