The Proof Course: Lecture 2

Many real-life situations lead us to considering a mathematical problem dealing with finding all possible numbers \(x\) satisfying a certain formula. In most primitive cases, this formula is an equation involving basic arithmetic operations (like the one we considered in Lecture 1). As an example of a formula that does not fall in this category, consider the following one:

\(x<y^2\) for every value of \(y\) (Formula A)

In other words, the formula expresses the property that no matter what value of \(y\) we pick, we will always have \(x<y^2\). Let us write this purely symbolically as follows (so that it looks more like a formula!):

\(y\Rightarrow x<y^2\) (symbolic form of Formula A)

In general, the symbol "\(\Rightarrow\)" describes logical implication of statements. Here the implication is: if \(y\) has a specific value then \(x<y^2\). In the symbolic form above, the assumption that \(y\) has a specific value is expressed by just writing \(y\) on the LHS (left-hand-side) of the implication symbol "\(\Rightarrow\)". Since we are not giving any further detail as to which specific value does \(y\) have, the implication must not be dependent on such detail, and hence the RHS (right-hand-side), \(x<y^2\), must hold for all values of \(y\). Note however that this type of symbolic forms, where variables are allowed to be written on their own like in the LHS of the implication symbol above, is not a standard practice. We will nevertheless stick to it, as it makes understanding proofs easier. 

So, what is the solution of Formula A? If \(x<y^2\) needs to hold for every value of \(y\), then in particular, it must hold for \(y=0\), giving us \(x<0^2=0\). This can be written out purely symbolically, as a proof:

1. \(y\Rightarrow x<y^2\)
2. \(x<0^2\)
3. \(x<0\)

However, as we know from Lecture 1 already, this proof only proves that if Formula A is true then \(x<0\). In order for \(x<0\) to be the solution of Formula A, we also need to prove that if \(x<0\) then Formula A is true. Well, since \(0\leqslant y^2\) is true for every \(y\), combining \(x<0\) with \(0\leqslant y^2\) we will get \(x<y^2\), as required in Formula A. So the proof is:

1. \(x<0\)
2. \(y\Rightarrow 0\leqslant y^2\)
3. \(y\Rightarrow x<y^2\)

Note that it seems as if this proof violates our requirement that in a basic proof, every line except the first one must be a logical conclusion of the previous one or several lines. Line 2 does not necessarily seem to be a conclusion of Line 1. Instead, it is simply a general true fact that does not seem to logically depend on Line 1 at all: it says that the square of every number is greater or equal to \(0\). We can account for such situations by agreeing that "several" in "one or several lines" includes the case of "\(0\) many". So in a basic proof we can also include lines that recall facts we know. If we had not done that in the above proof, we would have to skip from Line 1 directly to Line 3, and it may not have been so clear how does one logically conclude Line 3 from Line 1. So we allow inclusion of known facts as lines in a basic proof for the sake of clarity. Knowing this, we might want to make the first proof clearer by inserting one such line:

1. \(y\Rightarrow x<y^2\)
2. \(x<0^2\)
3. \(0^2=0\)
4. \(x<0\)

Read More

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.

Read More