What is a proof

Proofs are the cornerstones of all mathematics; with proofs, you can build an entire pyramid from just a few stones, and upside down at that.

The meaning of proofs

Proofs make sense in mathematics for several reasons. The main reason is that without the help of proofs we are unable to confirm any idea or hypothesis that comes to mind. For example, we might believe that there are a finite number of prime numbers, but unless we have a proof, this becomes just a mindless statement. On the other hand, even unproven statements have meaning in mathematics (and elsewhere). The short answer is that if the assumption that there are finitely many prime numbers holds, then... some other theory holds.

But then we mustn't be surprised that in time someone proves that there are infinitely many prime numbers, as we will show below, and our whole theory collapses like a house of cards. Thus, thanks to the evidence, we can build houses of cards that never collapse.

The reason why proofs are taught in schools is that those who understand the proof will understand the substance. Usually, you can hardly thoroughly understand a given substance without understanding the evidence. I emphasized the word "understood" quite deliberately, because if you memorize the proofs the day before the exam and just spit it out on paper the next day, that doesn't mean you're any closer to understanding the subject matter.

Thus, when learning a subject, proofs answer the question "why does it work that way?" If you understand why a given thing works, you will remember it more easily, and over time you will definitely understand the substance more than a person who learned it in a "pour-it-out" style. The question is whether this is your goal.

What is proof

What a proof is is formally defined in mathematical logic, for example by syntactic entailment, but we make do with a much simpler definition.

At the beginning of every proof, we must have a statement that we want to prove. We mark this statement with the magic symbol $\phi$. It's a Greek letter that reads "phi". Next, we will need some set of axioms and assumptions, denoted by Ax, with which to prove the statement $\phi$. A set of axioms is something we already know, something we assume to be true. They can be things like "every even number is simultaneously divisible by two". Further, this set may contain formulas for modifying expressions that are proven somewhere off to the side and we already assume to be true, for example:

$$(a+b)^2=a^2+2ab+b^2;\qquad a,b\in\mathbb{R}$$

Now we will successively modify the statements in the set Ax until we get the statement $\phi$. All modifications must be logically correct, they must conform to the basic propositional logic. For example, if we wanted to prove the previous formula, we would proceed in such a way that the expression

$$(a+b)^2$$

we will make equivalent modifications until we get the expression on the right hand side. Demonstration:

$$(a+b)^2=(a+b)\cdot(a+b)=a\cdot a+a\cdot b + b\cdot a + b\cdot b=$$

$$=a\cdot a+2ab+b\cdot b=a^2+2ab+b^2$$

In the first step, we broke the power into a product, in the second step we multiplied the parentheses, in the third step we added the equal expressions, and in the last step we wrote the product as a power. Each step represented some elementary adjustment that we could afford, and we assume that each of these elementary adjustments is contained in the set Ax.

Importantly, each adjustment must be valid, it must build on something we already know. A mathematical proof is something like evolution - by successive small modifications we get one expression to express another.

Trivial proofs

A trivial proof (or also obvious proof) is a terminus technicus for a proof that doesn't fit on the board, so it is skipped and the student learns it from the script for homework. :-) Seriously - trivial proofs are some proofs that typically follow from some definition in one trivial step.

Let's try to illustrate with an example: consider the set of natural numbers, i.e. the set of numbers ℕ = {1, 2, 3, …}. We can now say that every fraction of the form:

$$\frac{q}{p}; \qquad q,p\in\mathbb{N}$$

is a valid fraction, i.e., we can find no pair of numbers q, p, for which the given fraction is meaningless. How would we prove this? First, we need to figure out when a fraction does not make sense. A fraction is meaningless when there is zero in the denominator (we can't divide by zero). So we need to prove that p≠0 for all possible p. But we know that p is taken from the natural numbers, which we have defined as ℕ = {1, 2, 3, …}. The set of natural numbers does not contain zero, so the number p will always be different from zero.

$$\forall p\in\mathbb{N}: p\ne 0$$

And we have done the proof. We know that if both the numerator and denominator of a fraction are from natural numbers, the fraction will be valid.

Trivial proofs tend to be really trivial, but only if you know the surrounding context. For example, if you don't understand the concept of a set or don't know what it means that p is an element of the set ℕ, then this proof wasn't trivial for you either. Thus, trivial proofs are not so much characterized by being simple as by being short and arising simply from some (arbitrarily difficult) context.

Counterexample

A counterexample is perhaps the simplest form of proving that a given expression is not true. The important thing is the word is not. A counterexample may in fact point out a case where the given statement is not true, but in general even a lot of examples are not enough when there are infinitely many elements in play to test from.

Example: "every natural number is greater than ten". How do we prove that this is not true? A counterexample to our statement is the number five, for example. The number five is a natural number and is not greater than ten. We cannot prove the statement by listing several natural numbers that are greater than ten. You cannot say "the natural numbers 11, 12, 13, 123, and 5345 are greater than 10, so the statement is true". You can't. We've only picked a few examples for which our statement is true, but that says nothing about the other numbers we haven't mentioned at all.

Second example: every man over six feet tall has brown or blue eyes. I suppose few people are able to find a counterexample. What does that tell us about the statement in question? Well, nothing at all. If we can't find a counterexample, it doesn't necessarily mean that the statement is true. A counterexample may exist somewhere, we just aren't able to find it right now. Not being able to find a counterexample does not prove that the statement is true.

Direct evidence

The basic type of proof is direct evidence. We dryly follow the definition and modify the initial statement until we get the statement we want to get. Typically, we want to prove a statement that takes the form of an implication $A\Rightarrow B$, where A is some starting point, an assumption, and B is the statement we want to derive, to prove. If the statement A holds, then the statement B holds. Often we are given only the statement B, i.e., what we want to prove, and we have to choose the statement A appropriately.

The following procedure uses implication to derive further statements, and the last statement is the statement B. Schematically, this could be written as follows:

$$A\Rightarrow A_1\Rightarrow A_2\Rightarrow A_3\Rightarrow\ldots \Rightarrow A_n \Rightarrow B$$

As an example, we prove that the statement

$$a>1\Rightarrow a^2>1$$

Now in steps:

1. Since a>1, surely a>0 also holds and so does a≠0 (actually we just weaken the condition).

• Since a is not equal to zero and is positive, we can safely multiply the variable a by the whole inequality. If a were zero, we couldn't multiply at all; if it were negative, we would have to reverse the inequality. After multiplying by the variable a we get the expression a²>a.
• At this point, we know that a>1 and we also know that a²>a. If we put these two expressions together, we get: a²>a>1.
• From here, we just remove the middle expression and we have the expression a²>1. We could afford to do this because a is greater than one and a² is greater than a. If a² is greater than a and a is also greater than one, then surely a² is greater than one.

Symbolically, we could write it like this:

$$a>1\Rightarrow a>0 \Rightarrow a^2>a \Rightarrow a^2>a>1 \Rightarrow a^2>1.$$

Indirect evidence

Indirect proof already makes more use of the properties of implication. If we have to prove a statement of the form $A\Rightarrow B$, we can use the reversed implication and prove

$$\neg B \Rightarrow \neg A.$$

This approach can sometimes be more convenient than, say, direct proof. Proof by contradiction uses a similar procedure, to which any indirect proof can be mapped. Let's try to indirectly prove the statement

$$a-b=0\Rightarrow a=b.$$

We now make a reversal of the implication:

$$\begin{eqnarray} \neg(a=b)&\Rightarrow&\neg(a-b=0)\\ a\ne b&\Rightarrow&a-b\ne0 \end{eqnarray}$$

If a≠ b, we can decompose b into the sum b = a + x, where x represents the distance of b from a. The expression changes as follows:

$$a\ne (a+x)\Rightarrow a-(a+x)\ne0;\quad x\ne0$$

Subtract those variables a, which we can:

$$0\ne x\Rightarrow x\ne 0; \quad x\ne0$$

We can see that everywhere we have that x is different from zero, the statement is proved, thus the original statement holds

$$a-b=0\Rightarrow a=b.$$

Other proving techniques are, for example, the proof by dispute or proof by induction already mentioned.

Other sources

• Mathematical proof on Wikipedia