How to Write a Math Proof and Their Structure

Proofs in mathematics are what mathematics is all about. They are subject to entire books, created entire theories like Fermat’s last theorem, are hard to understand like currently Mochizuki’s proof of the ABC conjecture, or need computer assistance like the 4-color-theorem. They are sometimes even missing, although everybody believes in the statement like the Riemann hypothesis or $NP=P$. However, those are exceptions and events at the frontlines of mathematics. The daily mathematical life is cobblestoned by more or less easy deductions and conclusions. Some need detours like rather tricky integrals, a certain substitution or formula to solve them, and some need only modest calculation, or arguments along the line: What if not? The latter is the vast majority since they are required line by line when reading a proof: $A\Longrightarrow B$. They are also subject to the exercises and problems collected under ‘homework’. This little article will deal with them, i.e. the question: How to tackle a problem? There are simple functionalities behind most of them and I will try to give instruction on how to succeed in finding the way from $A$ to $B$.

Let us illustrate it with an easy example. Our statement will be:

If $x$cubed equals itself and is not a zero divisor, then it is not prime. Determine possible values. 

The scheme of proofs is in most cases the following

A few points are noticeable:

• What is meant by preprocessing?
• Why does it occur twice?
• Direct and indirect paths are not symmetric.
• How does ‘Context’ rule in?

The answers to these four points are half the way to our proof and especially important. ‘Preprocessing’ simply means the translation of the problem statement to equations and formulas we can work with. In our example we have

Step 1: A = “$x$ cubed equals itself and is not a zero divisor.”

Preprocessing $A$ means, that we name variables and clarify the conditions. The result of this process is

Step 2: Let $x^3=x$, and $xy= 0$ implies $y=0$.

The same must be done for our claim $B$.

Step 4: B= “The requested number is not prime. Calculate it.”

In our case, this is the definition of primality.

Step 3: $p$ is prime, if $p$ isn’t zero, no unit and $p|ab$ implies $p|a$ or $p|b$. A unit is simply an invertible element.

These steps are important. They do not require a lot of work to do, but they build the frame in which we will work, and the more detailed we will do these pre-processings, the easier it will be to communicate our thoughts to the reader. Furthermore, they deliver us tools to work with.

The broken symmetry between direct and indirect proofs explains why indirect thoughts, i.e. the answer to the question: What if not? are so famous. It provides an additional condition (step 9) to work with, namely $\text{not }B$. This will be helpful in many cases in which a direct computation cannot be applied, e.g. for nonexistence statements. If we have to show the absence of an object, it is rather natural to assume its existence and search for a contradiction. Otherwise, it will be hard to prove absence. Proofs of lower bounds can also be an example where indirect proof could be helpful. As a rule of thumb, one might say, that indirect proofs are the standard in algebra, and direct proofs the standard in calculus. This of course isn’t without many exceptions, but it outlines the way of thinking: what if not versus how to calculate.

Step 5: I thought of the information in step 5 to be that $x$ is not a zero divisor. It is a matter of taste whether such information is considered part of step 2 or occurs here. ‘Further conditions’ are often simply seemingly uninteresting adjectives in a problem statement. E.g. the hint that a ring is an integral domain or principal ideal domain, that a matrix is regular or a square matrix, the differentiability level of a function, the boundness of an operator, the continuity level of a function, whether an interval is (half-)open or (half-)closed. Little things like these which tend to get overlooked at first glance. They require careful reading and often contain substantial information. E.g. it is far easier to work with a Lipschitz continuous function than only a continuous function. Thus step 5 could be summarized as:

Do not overlook the tiny words in the problem statement.

Step 6: This is one of the most crucial points in proof. Maybe you have already recognized that important information is missing. We haven’t said where the $x$ is from! It is often assumed by context, where the entire problem takes place and as such often missed in the problem statement. Rigorously speaking, this is a mistake. And a severe one, too, as we will soon see. We only know that $x$ can be multiplied by itself and that $0$ hence addition seems to play a role, too. A compiler would give us an error message for the undefined variable, but we do not have a compiler. So what is $x$? A Boolean variable, integer, real, a ring element, which ring?, an algebra, which algebra?, a field, which field?, which characteristic?, a function, an operator, or a matrix? It is the context that is required here if we do not want to dismiss the problem as underdetermined. At school it is relatively easy: $x$ will be a real number. But outside of school, things become more complex. We have seen that multiplication and addition are required, so we may assume a ring structure. The terms prime and zero divisor also point in this direction.

Another important part of step 6 is previous results. For e.g. primality is equivalent to irreducibility in principal ideal domains, which could possibly be used if we may assume such a ring. We have invertibility for elements different from zero in a field. And in a Boolean ring, we have $x^2=x$. This shows us that the context, as well as previous results in that domain are important additional information. The problem above is of course underdetermined because I wanted to explain this. However, often people just assume that their readers will automatically know in which area the problem is settled without explicitly mentioning it. Let us assume in our case:

Let $x$ be in either $\mathbb{Z}$ or $\mathbb{Z}_p\,$($p$ prime), in which cases primality and irreducibility are the same.

The definition of irreducibility has now to be added to the preprocessing step 2.

Step 2 (revisited): An element $x$ is irreducible if it cannot be written as a proper multiplication $x=ab$, i.e. if $x\neq 0$ and $a,b$ are not invertible.

Until now we only have clarified the framework, whether explicitly stated or assumed via context. Those steps do not require much time, but they provide the toolbox we will need, or as I like to say: writing is faster than thinking. So take your time and prepare your problems. You will recover the time with interest during the actual proofs.

Steps 7 and 10: The school version of the problem is easy since it more or less neglects all reasons for single steps, automatically assumes real numbers or integers, and doesn’t care a lot about definitions. It reads like this:

\begin{align*} x^3&=x \\x^2&=1 \\x &=\pm 1 \end{align*}

This is nice and probably will satisfy your teacher, but it lacks a few details. In general, we want to know, why certain steps are legitimate. A more detailed version would perhaps include two cases: $x=0$ and $x\neq 0$. But even those are sloppy, as unequal zero does not automatically allow a cancellation, as there might be no inverse! Also, it is a good practice to avoid cases whenever possible or at least avoid them as long as possible. Thus a better approach reads:

\begin{align*} x^3&=x \\ x^3-x&=0 \\ x(x-1)(x+1)&=0 \\  (x-1)(x+1)&=0 \quad \text{ since }x \text{ is no zero divisor } \\  x=1 \, &\vee \, x=-1 \quad \text{ since } \mathbb{Z} \text{ as well as } \mathbb{Z}_p \text{ are integral domains } \\  & \pm 1 \quad \text{ are both units, i.e. invertible, so } x \text{ cannot be prime }\end{align*}

Here we have actually used, or better associated all given conditions to the calculation steps we performed and left the cases until the very last statement.

Steps 8,9 and 10: On this path we assume $\lnot B$, i.e. $x$ is prime. Since primality and irreducibility are the same, and we already have a decomposition of $x=x\cdot x\cdot x$, the decomposition has to be trivial, i.e. $x$ is either zero or a unit and thus not prime.

The indirect path is admittedly a bit artificial, however, it serves as a demonstration. The additional assumption does the job and the work is hidden in the theorem that both terms are equivalent. Let us finally drop a few words on the required

Solutions.

On all paths, we ended up with units. The conditions in statement $A$ rule out $x=0$. Now in $\mathbb{Z}$ the units are $\pm 1$, but in $\mathbb{Z}_p$ all numbers are units except zero. This shows the limits of indirect proofs. On this path, we still have no idea what $x$ actually is, except that it is not prime. This is sufficient for $\mathbb{Z}$ but not for $\mathbb{Z}_p\,.$ We fortunately also did the direct proof and ended up with $(x-1)(x+1)=0$. This equation bears the last detail:

\begin{align*} (x-1)(x+1)=0 \Longrightarrow \begin{cases} \pm 1 &\text{ in } \mathbb{Z}\\ 1\, , \,-1 &\text{ in } \mathbb{Z}_p\text{ if } p > 2 \\ 1 &\text{ in } \mathbb{Z}_p \text{ if } p=2 \end{cases} \end{align*}

Of course, we still need another formal step. A closer look at our proof shows, that we derived a necessary condition on $x$, that is $x\in \{\,-1\,,\,1\,\}$. However, we did not show that this condition is sufficient, too! It is quite obvious here, so a final sentence will do …

… and all possibilities for $x$ satisfy $x^3=x$.

… but to be correct and rigorous, this would have to be shown. In more complex examples, e.g. differential equations, integrals, or longer calculations, this step is actually necessary. The longer a proof or calculation is, the more likely it is that steps have been used which are not reversible. We usually start with some equations and deduce conditions for our solutions, we narrow it down until we have the answer. However, it might well happen in more complicated situations, that we narrow it down to a number or a function which isn’t a solution anymore. E.g. we could have deduced $x=0$ from $x^3=x$, but this solution does not satisfy all of our conditions.

So always make sure, that your solution is actually one!

Let me finally mention, that those simplifying conditions imposed on the domain where $x$ is chosen from are actually required for our proofs.

In $\mathbb{Z}_{15}$ we have $4^3 \equiv 64 \equiv 4 \operatorname{mod} 15$ which isn’t prime, but it is neither $0$ nor a unit nor $\pm 1$. So things are more complicated in $\mathbb{Z}_n$ with arbitrary $n$.

If $x = \begin{pmatrix}\cos \varphi &-\sin \varphi \\\sin \varphi & \cos \varphi\end{pmatrix}$ was a rotation matrix, then we still had $x^3=x \Longrightarrow x \in \{\,\pm I\,\}$, but the proof would be a slightly different one since we don’t have an integral domain anymore, and the reason to cancel $x$ is that it is invertible. The condition that $x$ isn’t a zero divisor would be obsolete.

In a Boolean algebra, all elements satisfy $x^3=x\cdot x^2 = x \cdot x = x^2 = x$.

This shows that context and hidden assumptions do make a difference, so better mention them.

How does the scheme above match our homework structure?

• Problem Statement: steps 1 and 4
• Relevant Equations: steps 5 and 6
• An Attempt at a Solution: steps 2 and 3 and an attempt of steps 7 to 10

Comments here