2.5 What is not a proof?

The previous part of the text dealt with the question of what a proof is and contained several concrete examples of proofs. In this section, we will point out the most frequent errors related to proofs. Thus, we will deal with what it is not a proof.

2.5.1 „Proof“ by examples vs. counterexample

The truth of a general statement cannot be based on several specific examples that support its truthfulness. In contrast, the truth of the statement can be refuted by just one counterexample 9.

Let us see, as a demonstrative case, a claim that Fermat wrote in 1650:10

For any $n\in\mathbb{N}_0$ the number $2^{2^n} + 1$ is a prime number.

By exploring the value of the expression $2^{2^n} + 1$ for some small $n$ we obtain the numbers $3$, $5$, $17$, $257$, $65\,537$, which are prime. We have validated the claim for the first five cases. However, this does not proove the truth of the claim for all $n$! Indeed, the next value for $n = 6$ is not a prime number:

\begin{equation}\label{eq-rozklad}\tag{2.3} 2^{2^6} + 1 = 18446744073709551617 = 274177 \cdot 67280421310721. \end{equation}

Of course, in Fermat's time this breakdown of the formula was unknown. The formula (2.3) gives therefore a counterexample to Fermat's statement and refutes it. In other words it prooves that the statement is not true.For sure, examples supporting a claim can be sometimes useful. They could guide a person to guess a general claim. However, the truth of such claim cannot be derived from the examples. E.g., as mentioned above, the binomial theorem 2.2 cannot be proven by verifying his statement only for $n = 1,2,3$, because this does not say anything on the cases $n=4,5,\ldots$

2.5.2 From the assumption to the claim.

Another common phenomenon is the misunderstanding of the way a proof is conducted. Let us repeat again that the goal is to go from the assumption to the claim of a theorem/lemma/corollary through logical steps. If you are studying a proof, you should pay attention on where and how the assumptions were used (there is nothing more humorous than a proof in which the assumptions of the theorem do not show up at all).Let us try to illustrate this phenomenon on another rather common error. For simplicity, consider a very simple statement: the sum of even numbers is an even number. For the sake of completeness, let us recall that an integer $k$ is called even, when it can be expressed in the form $k = 2 \ell$, where $\ell$ is some other integer (this is the definition of evenness for integer numbers). As a proof, some students would write: „When I add two even numbers, I must get an even number again.“ Is this a proof? Of course not, it repeats what it is to be proven, it only says that the claim must be true. Even if that must is written in large font and blood, it will not be a reason (proof) for the statement to be true.A correct (direct) proof would look like this: let us take two even numbers, let us say $a,b \in \mathbb{Z}$. They are even (here it is the assumption) and therefore, by definition, there exist some integers $k$ and $\ell$ such that $a = 2k$ a $b = 2\ell$. Thus, considering their sum, according to the distributive law, it applies that

\begin{equation*} a + b = 2k + 2\ell = 2(k + \ell), \end{equation*}

Thus, we see that $a + b$ is actually the double of the integer number $k + \ell$, and so it is by definition even!I hope the reader will appreciate the difference between „obviousness“ and the real proof shown above, now. In the previous paragraph, based on assumptions, definition and properties of integers (distributive law, closeness with respect to sum), it has been shown that the statement is true.

2.5.3 Obvious proof

To conclude, let us point out the meaning of the word „obvious“. A claim is obvious, just when his proof immediately comes to your mind. Not because you believe it is true, but you do not really know why.