Apologies: this will be a long post, and there will be more to come. But it may be useful to you if you are getting to grips with logic: I have tried to keep the overall picture in view.
Over Christmas I read Truth: A History and a Guide for the Perplexed by Felipe Fernández-Armesto. A brave book, in which a mere historian ventures into anthropology, philosophy, mathematics and science to ask about how we decide what is true (and what has gone wrong with this mechanism in recent times).
He distinguishes four “sources” of truth, which roughly in order of appearance in the historical record are: “truth-feelings”, authority (scripture, mystical experience, etc.), reasoning (especially mathematics), and evidence of our senses (leading to science). In the end, he claims that all of these are in crisis.
Sad to say, whenever I read a book with such a broad sweep as this one, I almost always find that it falls over on things I know about (leading me to wonder if it is just as shaky all the way through). What do non-mathematicians most often come to grief over? That’s right, Gödel’s Theorem. Fernández-Armesto says:
it has proved impossible to circumvent arguments proposed by Gödel in 1932 which suggest that contradictions are inherent in any system which purports to be both complete and consistent
So here goes, with an attempt to clarify the relationship between mathematics and logic, and what Gödel actually said.
First, some personal history.
I didn’t learn logic as a student. When I was interviewed for a teaching job in Oxford in 1975, the University was very short of people prepared to teach logic, and I was asked in the interview whether I would be prepared to teach it. I replied something along the lines of “Not under any circumstances!” But they appointed me anyway. My mathematical interests were shifting at that time from finite to infinite permutation groups, and I soon realised that I would need to learn some logic; I was becoming aware that the logicians had techniques and a point of view that would be useful to me. (I will describe the context of this in the next post.) So I volunteered to give the lectures, and learned the subject by keeping one step ahead of the students. I learned it well enough that when the Princeton Companion to Mathematics was being produced, the editors asked me to write the article on Gödel’s Theorem.
Logic plays a double role in mathematics. What most people think of as its role, but is really rather unimportant for most mathematicians, is that it provides the foundations on which the subject is built. No mathematician ever writes out a long complicated argument by going back to the notation and formalism of logic; but every mathematician must have the confidence that she could do so if it were demanded. As Julian Jaynes put it in his iconic 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.
Thus it might be said that mathematics naturally proceeds by Fernández-Armesto’s “truth-feelings” (though these feelings are the result of a learned notion of rigour becoming unconscious after long use, as with any learned skill, and not any kind of deep instinct), but with logic always there as a last resort.
The second and much more important role of logic is as a branch of mathematics, on a par with number theory or algebraic geometry; it develops by using the common culture of mathematics, and makes its own rather important contributions to this culture. There will be examples in the next post.
The two roles were borne home to me during that first lecture course I gave. The Deduction Theorem asserts that, if a proposition q can be deduced from a set S of propositions together with an extra proposition p, then the proposition p→q (“p implies q“) can be deduced from S alone. The proof, of course, is by induction on the length of (that is, the number of steps in) the assumed proof of q. The audience included philosophy students as well as mathematicians. One of these raised his hand and said, “Logic is supposed to be the foundation of mathematics. How come you are using mathematics to prove a result in logic?” Of course, if the subject had been number theory, and I was proving the case n=3 of Fermat’s Last Theorem by induction, the objection would not have been raised.
Anyway, now to Fernández-Armesto’s assertion that “contradictions are inherent in any system which purports to be complete and consistent”. We should look at what these words mean. Firstly, “purports” is extremely derogatory to a mathematician, so I propose to give Fernández-Armesto the benefit of the doubt and simply omit it. Let us suppose that he said “contradictions are inherent in any system which is complete and consistent”. This statement is now itself a contradiction, since “consistent” means “free from contradiction”. Well, perhaps he meant to exploit this contradiction and say “no system is complete and consistent”? If so, he is simply wrong.
A logical system of any kind has the following parts. First, there is an alphabet of symbols from which formulae will be built. These could include symbols for variables, logical symbols such as connectives and quantifiers, and mathematical symbols standing for relations, functions and constants.
A formula is a finite string of symbols. But not every finite string of symbols is a formula. There should be a rule, mechanical in nature, for deciding whether a string of symbols is a valid (or well-formed) formula. Such a rule is often given by specifying “atomic” formulae and giving rules for building more complicated formulae from simpler ones, together with a proof that any valid formula can be built up in a unique and recognisable way by the rules.
Note in passing the connection with computation: the rule for recognising a formula should be capable of execution by a computer without any “intelligence”.
Now the logical system specifies certain formulae as “axioms”, and also gives “rules of inference” by means of which we can deduce a new formula from a given collection of formulae. Any formula which can be deduced from the “axioms” is called a “theorem”; a formula which can be deduced from the axioms together with a set S of formulae is a “consequence” of S. Once again, we require that there is a mechanical way to decide whether a formula is an axiom, and whether a purported deduction actually follows the rules of inference.
So far, all is entirely syntactical; meaning has not entered into the system at all. We do this by means of an interpretation, which may begin by attaching real mathematical objects to the constants, functions and relations, but ends by assigning a truth value T (true) or F (false) to each formula. There are rules for working out these truth values. In practice they give the expected result. It is easy to write the statement “for all x and y, we have xy=yx” in a suitable formal system; an interpretation of the system in a group will be true if and only if the group is abelian.
Now a formula p is logically valid if it is true in every interpretation, and is a logical consequence of a set S if it is true in all interpretations which make every formula in S true.
Finally we can say what soundness and completeness are. A system is sound if all its theorems are logically valid, and is complete if all its logically valid formulae are theorems. A sound system is free of contradiction, since a contradiction cannot be logically valid. Clearly soundness is an essential requirement, and completeness a desirable requirement, for any logical system which is to serve as a basis of mathematics. Now Fernández-Armesto seems to be saying that Gödel showed that no sound and complete system for mathematics can exist. Did he?
Actually, rather the reverse. Two very important and familiar systems are sound and complete. The first of these is propositional (or Boolean) logic, where atomic propositions have no internal structure, but are simply statements which are either true or false and are combined with connectives such as “and”, “or”, “not”, “implies”. We can decide whether a compound proposition is logically valid by constructing a truth table for it; there are standard deduction systems for propositional logic which prove precisely the logically valid formulae.
Next up is first-order logic, which is the formalism in which most of mathematics is naturally cast. I have hinted at its structure above: we have constants, functions, and variables which are combined into “atomic” propositions by means of relations (including the relation of equality); these are then joined by connectives as in the Boolean case, or bound by quantifiers over variables such as “for all x, …” or “there exists x such that …” Gödel proved that first-order logic is complete.
What is this incompleteness, then? Gödel’s major theorem asserts something more specific. Any logical system provided with axioms which attempts to describe the natural numbers with the operations of addition and multiplication and the relation of order, if it is consistent, must be “incomplete”, in the sense that there are true statements about the natural numbers which are not provable. Of course, by the completeness theorem, any statement which is true in all models of the axioms is provable. So this is actually a constructive theorem: it says that any axiom system which attempts to describe the natural numbers, if consistent, will always have “non-standard models”, structures which satisfy the axioms but fail to have some property which is true of the natural numbers.
This is quite subtle. It is known that the theory of the natural numbers, with the order relation and the operation of addition (but not multiplication) is complete: this is Pressberger arithmetic. Somehow throwing in multiplication as well makes the difference, despite the truism that “multiplication can be defined in terms of addition”.
That’s all for now; more later.