### 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$$