QED, and the many shades of proof

“Good, he did not have enough imagination to become a mathematician.” ~ David Hilbert, upon hearing that one of his students had dropped out to study poetry

Often in high school mathematics, the common curriculum places emphasis on the theory of solving, rather than proving. Rightfully so, as I might add, since one must know what it is they are proving before going about the business itself. Truthfully, the motif of this article is purely derived from my desire to produce an interesting piece that remains as a subset of my personal interests, rather than due to any clarion call from my inner conscience to inform the general populace on the beauty of mathematical proof. Regardless, this article will be a primer for those not too familiar with the language of proofs or its applications. 

We begin with the definition of the common axiom. A mathematical proof is a deductive argument for a mathematical statement, showing that the stated assumptions logically guarantee the conclusion, constructed from original assumptions called axioms. You will find that any example of mathematical proof will be a modification of an axiom, although some changes may be less recognisable compared to others. We can start with one of the simpler axioms: The axiom of Equality.

x=x

You might have seen this before. For generalising the notion of axioms, you might get as such: 

∀x φ → φₜˣ

This is the Axiom scheme for universal instantiation. I will have difficulty expressing this in text due to the limits in both my own knowledge and my keyboard, but simply, Phi is a formula, x is a variable, and t is a term that is substitutable for x in Phi. The term on the right denotes formula Phi with the term t substituted for x. 

Proof by contradiction, also known as “reductio ad absurdum” in logic, is a greatly convenient  method of mathematical proof where one assumes the negation of the statement to be proven and shows that this assumption always leads to a contradiction. By establishing that the negation cannot be true, one therefore concludes that the original statement must be true. The beauty of this technique lies in its ability to use logical implications to derive an absurd or impossible result from a false assumption. A mathematical proof employing proof by contradiction usually proceeds as follows:

The proposition to be proved is P.

We assume P to be false, i.e., we assume ¬P.

It is then shown that ¬P implies falsehood. This is often accomplished by deriving two mutually contradictory assertions, Q and ¬Q, and appealing to the law of noncontradiction, which states that contradictory propositions cannot both be true in the same sense at the same time.

Since assuming P to be false leads to a contradiction, it is concluded that P is in fact true.

Below is an example of such approach:

Theorem: Suppose n is an integer and n^2 is even. Then, n is also even.

Assumption: Assume n is odd. That means n can be written as 2k + 1 for some integer k.

Logical Derivation:

When we square n, we get:

n^2 = (2k + 1)^2

This expands to:

n^2 = 4k^2 + 4k + 1

And can be written as:

n^2 = 2(2k^2 + 2k) + 1

This result is an odd number.

Find a Contradiction: We started with the assumption that n^2 is even, but from our derivation, we found that n^2 is odd. This is a contradiction.

Conclusion: Our original assumption that n is odd must be incorrect. Therefore, n is even.

Proof by mathematical induction is a particularly elegant technique (and my personal favourite) used to establish the truth of infinitely many statements in a systematic manner. The process begins with a base case, which is usually a specific instance of the statement that can be proven directly, either by any method described previously, or something else entirely. Next, the inductive step involves assuming the statement holds for some arbitrary case, often denoted by n, and then showing that this assumption implies the statement is also true for the next case, n+1. If both these steps are successfully carried out, it can be inferred that the statement is true for all integers greater than or equal to the base case. Here is a simple example:

Proof by Mathematical Induction: Sum of the First n Positive Integers

Statement: For any positive integer n, the sum of the first n positive integers equals n(n+1)/2.

Base Case (n = 1):

The sum of the first positive integer is 1. Using our formula, we get:

1(1+1)/2 = 2/2 = 1.

This matches our expected sum, so the base case is true.

Inductive Step:

Let’s assume that our statement is true for some arbitrary positive integer k. This means:

1 + 2 + … + k = k(k+1)/2. (This is our inductive hypothesis.)

Now, we want to prove it for k+1. If our formula is correct, then the sum for k+1 terms would be:

1 + 2 + … + k + (k+1) = (k+1)(k+2)/2.

Building from our inductive hypothesis, the sum becomes:

k(k+1)/2 + (k+1).

Combining like terms, we get:

(k+1)(k+2)/2.

This matches the sum we wanted to prove, so the inductive step is valid.

Conclusion:

Given that our base case is true, and our inductive step is valid, by the principle of mathematical induction, we conclude that our statement is true for all positive integers n.

Visual proof is also something that is used, but halfway through writing this, I remembered that I had a personal vendetta against visual proofs, and as such, I will not be writing about them at all.