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:
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:
\(x=5\) and \(x+2=2x-3\),
\(x=5\) or \(x+2=2x-3\),