The Proof Course: Lecture 1

In this blog-based lecture course we will learn how to build mathematical proofs.

Let us begin with something simple. You are most likely familiar with "solving an equation". You are given an "equation", say \[x+2=2x-3\] with an "unknown" number \(x\) and you need to find all possible values of \(x\), so that the equation holds true. You then follow a certain process of creating new equations from the given one until you reach the solution: \[2+3=2x-x\] \[5=x\] This computation is in fact an example of a proof. To be more precise, there are two proofs here: one for proving that

if \(x+2=2x-3\) then \(x=5\) (Proposition A),

and the other proving that

if \(x=5\) then \(x+2=2x-3\) (Proposition B).

The first proof is the same as the series of equations above. The second proof is still the same series, but in reverse direction. The two Propositions A and B together guarantee that not only \(x=5\) fulfills the original equation (Proposition B), but that there is no other value of \(x\) that would fulfill the same equation (Proposition A). It is because of the presence of these two proofs in our computation that we can be sure that \(x=5\) is indeed the solution of the equation \(x+2=2x-3\).

In general, a proof is a series of mathematical formulas, like the equations above. However, in addition to a "vertical" structure of a proof, where each line displays a formula that has been derived from one or more previous lines, there is also a "horizontal" structure, where each line of a proof has a certain horizontal offset. This is, at least, according to a certain proof calculus formulated by someone by the name of Fitch. There are other ways of defining/describing proofs; in fact, there is an entire subject of proof theory, which studies these other ways. We will care little about those other ways and stick to the one we started describing, as it is closest to how mathematicians actually compose proofs in their everyday job.

So where were we? We were talking about "vertical" and "horizontal" structure of a proof. Not to complicate things too much at once, let us first get a handle on the vertical structure of proofs, illustrating it on various example proofs that have most primitive possible horizontal structure. We will then, slowly, complexify the horizontal structure as well.

For Proposition A, the proof goes like this:

1. \(x+2=2x-3\)
2. \(2+3=2x-x\)
3. \(5=x\)

The numbers at the start of each line are just for our reference purposes, they do not form part of the proof. Line 2 is a logical conclusion of Line 1: if \(x+2=2x-3\) then it must be so that \(2+3=2x-x\), since we could add \(3\) to both sides of the equality and subtract \(x\) as well – a process under which the equality will remain true if it were true at the start.

Line 3 is (again) a logical conclusion of Line 2: since \(5=2+3\) and \(2x-x=x\), so if the equality in Line 2 were true then the equality in Line 3 must be true as well.

A series of lines of mathematical formulas where every next line is a logical conclusion of the previous one or more lines, is a mathematical proof with simplest possible horizontal structure. We will call such proofs "basic".

Proposition B also has a basic proof:

1. \(5=x\)
2. \(2+3=2x-x\)
3. \(x+2=2x-3\)

Just as before, every next line is a logical conclusion of the previous one.

What about the first line (in each proof)? If the first line were to also satisfy the requirement that it is a logical conclusion of the previous lines, then, since there are no lines before the first line, it would appear that the first line is true on its own, without a need for justification. If course, in both proofs this is false: in the first proof, we cannot claim that Line 1 is true. Truth of Line 1 in the first proof depends on the value of \(x\). Without knowing anything about the value of \(x\), we cannot claim that \(x+2=2x-3\), since if, say, \(x=0\), then \(x+2=2x-3\) is clearly false. The same for the second proof - we cannot claim that Line 1 is true. Instead, the role of the first line in each of the proofs is to "assume" they are true, and then see what conclusions can be drawn from such assumption. Recall that Proposition B, for instance, states that if \(x=5\) then \(x+2=2x-3\). It does not state that 

\(x=5\) and \(x+2=2x-3\), 

or that 

\(x=5\) or \(x+2=2x-3\), 

and so on. So in a basic proof the first line will always be an assumption, unlike the rest of the lines, which are conclusions from the previous one or several lines.