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\)