A calculus of the absurd

Chapter 5 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 mü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 Gödel, remarks on his incompleteness theorems

5.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 10 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 form4343 This can be proved by induction (see Section 5.2) \(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 form4444 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 \)

5.1.1 Proving identities

When proving identities (i.e. expressions in the form \(A = B\)) there are two ways to do it.

  • • Pick a side (any side, but as a rule of thumb the one which looks more complex/messy) and show that there exist a sequence of steps (applications of statements that one knows to be true, e.g. that \(-1 \leqq \sin (x) \leqq 1\) or if \(a \ne 0\) and \(ab = ac\), then \(b = c\)) which rewrite one side as the other. Important: these steps must be invertible (i.e. they can be applied both ways, as otherwise the equality does not run in both directions - for example, squaring can be dangerous when working from one side to the other, as when taking the square root there are two solutions) as this is the essence of the “trick” which allows us to save half the work.

  • • Show that we can rewrite \(A\) and \(B\) and \(B\) as \(A\). The only advantage of this method over the previous one is that we may use irreversible steps.

There is also another way to prove that \(A = B\) which relies on the fact that the \(\leqq \) operator is “antisymmetric”, which is maths jargon for \(A = B\) if and only if \(A \leqq B\) and \(B \leqq A\). This technique can be really powerful in many situations.

TODO: example of using antisymmetric property of \(\leqq \) to prove things