Mathematical Structures, 9

The last two weeks of the course are about proofs: how to construct them, how to read them, how to spot false proofs, and so on. In keeping with the spirit of the course, we have seen many proofs along the way, including some of the classics, such as Euclid’s proof of the infinity of primes, and proofs of the irrationality of √2, e (in the supplementary material), and log102 (in an exercise). So this won’t come as a total surprise.

In the “numbers” part of the course, the message was not “Forget everything you thought you knew about numbers, I’m going to tell you how it really is”; rather, “You know already what numbers are, now we are going to dig a little deeper and make it a bit more precise.” I take the same attitude to logic and proof. I believe strongly in the point of view advocated by Julian Jaynes, in the remarkable book The Origin of Consciousness in the Breakdown of the Bicameral Mind:

Reasoning and logic are to each other as health is to medicine, or — better — as conduct is to morality. Reasoning refers to a gamut of natural thought processes in the everyday world. Logic is how we ought to think if objective truth is our goal — and the everyday world is very little concerned with objective truth. Logic is the science of the justification of conclusions we have reached by natural reasoning. My point here is that, for such natural reasoning to occur, consciousness is not necessary. The very reason we need logic at all is because most reasoning is not conscious at all.

Consider, for example, implication. The statement “P implies Q” is false if P is true and Q is false, and true in all other cases. This seems bizarre at first sight: shouldn’t there be something to say that Q can be deduced from P by some kind of argument, or at least that there is some connection, logical, material, or whatever, between P and Q? No, the definition I gave tells you the whole story. I used the example “If it is fine tomorrow I will take you to the Zoo” to try to persuade doubters in the class of this. The only situation in which my statement is untrue is when it is fine and I don’t take you to the zoo. Some people wanted it to be false if it rains, but I tried my best to talk them out of this. But I believe that, in practice, people use this rule correctly in ordinary argument; like riding a bicycle, it is only when you stop to think about what you are doing that trouble can arise.

So, for example, I overheard someone on the BBC World Service say,

You can’t square the circle unless everyone is singing from the same sheet.

True or false?

This example provoked some discussion of the word “unless”. The sentence “P unless Q” has the feel of an implication, and I would read it as “(not Q) implies P“.

We discussed various formal things such as the contrapositive, the converse, proof by contradiction, proof by exhaustion (otherwise known as “divide and conquer”), and more specialised things like induction and Cantor’s diagonal argument. On the way, we saw many proofs, such as the arithmetic-geometric mean inequality and Fermat’s little theorem (proved by divide-and-conquer, one case involving induction, the Binomial Theorem, and the divisibility of binomial coefficients by a prime).