## How to prove stuff

A while ago, I wrote up a post that explained what a mathematical proof is. In short, a mathematical proof is a bunch of sentences that follow from other sentences. And when mathematicians have been trying to prove stuff for hundreds of years, well, we’re bound to get fairly good at it. And to develop techniques.

So, then. Given any theory (that is, a set of logical sentences) $\mathcal T$, when a sentence S is a theorem (that is, it can be proven from the theory), we write $\mathcal T\vdash S$. And if we want to prove a thing, it may not be the case that we actually know that the thing is true. Sometimes we just have an intuition that it may be true. Or maybe we know it’s true because some other mathematician has told us it’s true, but we don’t see how. So we need to find a way to do it.

Direct proof

The simplest case of proof is one where we just show that a sentence follows directly from our axioms. We start with our theory $\mathcal T$ and a finite bunch of sentences $\{A, B, C, ...\}$ and we show that $\mathcal T\rightarrow A\rightarrow B\rightarrow C\rightarrow ...\rightarrow S$. These sentences are the steps of the proof, and S is our desired theorem.

As an example, suppose $\mathcal T$ is the theory of arithmetic, plus the sentence $n\text{ is an odd number}"$. We want to prove the sentence $S:n^2\text{ is an odd number}"$. That is, we want to prove that the square of any odd number is also an odd number. If $n$ is an odd number, then there exists some integer $k$ such that $n = 2k+1$. That’s our sentence $A$. That sentence implies $B:n^2 = (2k+1)^2$ which implies $C: n^2 = 4k^2+4k+1$ which in turn implies $D: n^2 = 2(2k^2+2k)+1$. Then, if we choose the integer $j = 2k^2+2$, we have that $D$ implies $S:n^2 = 2j+1$ and thus we proved that the square of an odd number is also an odd number: $\mathcal T\rightarrow A\rightarrow B\rightarrow C\rightarrow D\rightarrow S$.

Exhaustive proof

This is in fact a type of a direct proof, but it’s simpler. It’s used to prove finite conjectures, ones that are only valid for finitely many objects. We basically just check, one by one, that every element affected by the conjecture is true.

Let’s once again take $\mathcal T$ as the theory of arithmetic. We want to prove $S: \text{For every natural number }n\leq 3\text{ it is the case that }n^2\leq 9"$. This statement can be just seen as the statement $(0^2\leq 9)\land(1^2\leq 9)\land(2^2\leq 9)\land(3^2 \leq 9)$. Since each of the four cases is true, the entire conjecture is true, and thus we have proven it.

Proof by cases

This is similar to the exhaustive proof, except that instead of checking each object that’s affected by the sentence, we divide the objects into different possible groups, and then show that the objects of each group all satisfy the sentence.

For example, suppose I want to prove the sentence $S:x^2\geq 0\text{ for every real number }x"$: the square of any real number is nonnegative. We can divide the real numbers in three cases: $x < 0$, $x = 0$, and $x > 0$.

• On the third case, we’re multiplying two positive numbers together, and that gives us a nonnegative number.
• On the second, we’re multiplying $0$ by itself, which gives us $0$, which is a nonnegative number.
• On the first case, there exists some positive number $y$ such that $x = -1*y$, which means that $x^2 = (-1)*(-1)*y*y$. Since we know that $(-1)*(-1) = 1$ and that $y^2\geq 0$, then $x^2\geq 0$.

Since every real number must fall into one of these cases, we have that every real number obeys the theorem, and we’ve proven it.

Proof by contraposition

$\mathcal T$ is a conjunction of sentences we assume to be true (our axioms and theorems). If it’s the case that $\mathcal T\vdash S$, then $\mathcal T\rightarrow S$. Now, modus ponens to modus tollens, this means that if I find that S is false, we must necessarily also find that something in $\mathcal T$ is false: $\bar S\rightarrow \bar{\mathcal T}$.

As an example, I want to prove the conjecture $\text{If }n\text{ is an integer such that }3n+2\text{ is odd, then so is }n"$. In this case, then, our theory $\mathcal T$ is the theory of arithmetic plus the sentences $n\text{ is an integer}"$ and $3n+2\text{ is odd}"$, and we want to prove $S:n\text{ is odd}"$. Let’s try to do it by contraposition: assume $n$ is even. Then there is some integer $k$ such that $3n+2=3(2k)+2 = 6k+2 = 2(3k+1)$ which is an even number. Therefore, assuming $\bar S$ (that is, $n\text{ is even}"$) we concluded $\bar{\mathcal T}$ (in this specific case, $3n+2\text{ is even}"$), which contraposes our assumption, so our theorem is proven.

And I will use this in the next section: in the direct proof section, we proved that if $n$ is odd, then so is $n^2$; therefore, if $n^2$ is even, so is $n$.

This is a special case of the proof by contraposition. Here, instead of the negation of S contraposing some theory $latex\mathcal T&s=0$, it contradicts logic itself. That is, if we prove that the negation of S implies a contradiction (such as $\bar S\rightarrow (P\land\bar P)$ for some P, or just more generally $\bar S\rightarrow \bot$), it must be the case that S is true. I will use a very famous example: the proof that $\sqrt 2$ is not a rational number.

A number $m$ is said to be rational if and only if there exist integers $p$ and $q$ such that $m = \frac p q$. Furthermore, we can pick two integers such that they’re relatively prime (that is, share no divisors). So, let’s assume $\sqrt 2$ is a rational number and see where that leads us. If $\sqrt 2 = \frac p q$ then we can square both sides and the equality will hold, $(\sqrt 2)^2 = 2 = \frac{p^2}{q^2} = \left(\frac p q\right)^2$. From that it follows that $p^2=2q^2$ which means that $p^2$, and therefore $p$, is an even number. So there exists some integer $k$ such that $p=2k$, and so $p^2=(2k)^2=4k^2=2q^2$. Taking that last equality and dividing both sides by $2$, we find that $q^2=2k^2$, and that means $q$ is an even number. However, $p$ and $q$ cannot both be even, because they’re supposed to be relatively prime and so cannot have 2 as a common divisor. From this, then, it follows that $\sqrt 2$ cannot be a rational number.

Independence

Sometimes, it turns out that the sentence S we’re trying to prove from our theory $\mathcal T$ is not actually a theorem of the theorem. One might then intuitively expect that in that case the negation of S is a theorem. However, that’s not always the case! Sometimes, both $\mathcal T\nvdash S$ and $\mathcal T\nvdash\bar S$ are true! When that happens, we say that S is independent of our theory $\mathcal T$, in that it’s neither true nor false according to that theory. This means that both the theory $\mathcal T\cup S$ and the theory $\mathcal T\cup \bar S$ can be consistent, useful theories (unless $\mathcal T$ itself wasn’t consistent to begin with).

I explained this when I talked about axioms. If you remove, say, axiom A1 from the Peano Axioms, you can’t prove it from the other ones. Symmetry is an independent proposition of the remaining axioms, and therefore needs to be stated. I also mentioned the historical case of Euclid, who thought but couldn’t prove that the parallel postulate followed from his other axioms of geometry. It turned out that it didn’t, and neither did its negation, and so when you use it you have the so-called Euclidean Geometries, and when you use its negation you have the non-Euclidean Geometries.

There are many interesting propositions that are independent of our theories, and we can have lots of fun playing with them. But the techniques used to prove independence are advanced Model Theory techniques, and do not belong in this simple intuitive explanation.

Still, there we go, a bunch of neat heuristics to prove things in mathematics!