PLP: An introduction to mathematical proof

So \(P(x): \) 8 is prime, and \(Q(x): x^3=17\text{.}\) A quick check shows that the hypothesis is false, so the result is vacuous. Of course we need to explain this to the reader in our proof otherwise its not a proof. It is safe to assume (in the context of writing a proof) that the reader knows their truth-tables. We don’t have to explain everything in every proof.

Now providing the reader knows what a prime number is, and that they recall the truth-table of the implication, then we have clearly demonstrated that the hypothesis is false and so the implication must be true. Thus the reader is now convinced, and all is good.

This is an example of a vacuous proof — it is true because the hypothesis is always false. Notice that we cannot use modus ponens with such an implication because the hypothesis will never be true; the implication is true but in a rather useless way.

Despite this being a vacuous proof, we can learn something useful from how it is formatted. It is customary to tell the reader “the proof starts here” and “the proof finishes there”, so that they know that all the necessary logic and mathematics is contained within that chunk of text. Typically we’ll start a proof by writing “Proof:” (maybe underlined) and then finish it with a little square “\(\square\)”. The little square denotes “End of proof” or “QED” = “quod erat demonstrandum” = “which was to be demonstrated”. It is perhaps a little pompous to write “QED” for such a little proof, so it is far more typical to see the little square. Some texts will use a little diamond “\(\blacklozenge\)” or “\(\lozenge\)”, or a little filled in square “\(\blacksquare\)”. Some online-texts will simply enclose the whole proof in a box. In the HTML version of this text we’ll enclose the proof in a box and also end it with a little square, while the PDF version of the text will simply have a little square.

Let’s look at another example.

Before writing anything down we should really read the hypothesis and conclusion very carefully. Notice that the hypothesis is saying something false. We know that the square of a number cannot be negative (we stated this as Fact 3.0.2), so the hypothesis is false.

The authors made an assumption about our reader in that proof — we’ve assumed that the reader knows Fact 3.0.2 well and so doesn’t need to be reminded of it in the proof. We could choose to make this more explicit depending on our audience and the context. If you are in doubt as to what your readers know, you should put in more details.

There are related (and similarly quite useless) results which come from the conclusion being true independent of the hypothesis. For example:

This is an example of a trivial proof. We could put in more details to prove that 17 really is prime but we are going to assume that our reader knows their times-tables and the first few primes. Notice that since the conclusion is always true, we cannot use modus tollens with this result. Again, the result is true but in a useless way.

Here is another one.

So now this looks a little harder but we can again look at this statement and see what is going on. The square of any number is always bigger or equal to zero (again Fact 3.0.2 is lurking here), so if we add 1 to it then it is definitely bigger than 0. We just need to translate this into mathematical language: Take any real number. Its square is bigger or equal to zero, so when we add 1, it is strictly bigger than 0.

Enough with the vacuous trivialities, it is high time we looked at some real results.