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
Oh dear.
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.
Peter Cameron's Blog 
Not to mention Skolem Arithmetic, where the operation of multiplication is kept but addition is thrown away, which is also complete.
Pingback: Mathematics and Logic, 2 « Peter Cameron’s Blog
With regards to the ‘every mathematician must be confident that they could write their proofs out in formal logic’ point:
I am well aware that such a phrase is routinely used to motivate students (I’ve used it myself) and that in some sense it is true. However, I think very few mathematicians ever consider how much work it might be to actually do such a thing. In practice, we appeal to intuition and avoid logically correct deduction. We simply do so in a way that other mathematicians are willing to accept. It is an interesting exercise to take some favourite theorem in your area and attempt to state and prove it formally – but I believe many mathematicians will decide the lesson has been learned long before completing the exercise.
I do not think we should try, at least amongst ourselves, to pretend that we produce logically perfect work (even assuming the axioms). We simply require that the average mathematician (in the form of a referee) accepts the authors’ hand-waving.
It’s also certainly true that there are accepted statements which are stated as coming from some paper, yet that paper contains no more than a statement that a proof exists. A good example is that of the Blow-up Lemma in graph theory: it is typically used with ‘restrictions’, and cited from a paper which does not prove any such statement – it merely states that such a proof is possible (the version without ‘restrictions’ is proven, but it is not clear how one can modify the proof).
Absolutely so. I once asked a logic class to write out a formal proof that a group in which the square of every element is the identity must be abelian. One conscientious student actually did the exercise; the proof was 700 lines long. Most of the class, as you say, learned the lesson much earlier.
Still, I mentioned Angus Macintyre’s recent claim that the proof of Fermat’s Last Theorem can be done in Peano arithmetic. These things do matter, I think.
@Peter: I really would like to SEE the 700-lines-long proof of your student. Could you make it available (to me)? (I am sure it is an impressive example of how long the walks are that one usually takes “in one step”.)
Another question: What is the status of Angus Macintyre’s claim that the proof of FLT can be done in PA? Is there a paper?
There is no paper, this was just a homework problem which only one student engaged with. (I hadn’t realised myself just how bad it would be!) I may have had an electronic copy once, but it is long gone.
I don’t know whether Angus intends to publish a proof of his claim. I haven’t seen him for some time. I guess you will have to ask him.
Pingback: Formal Logic « Peter Cameron's Blog
Hi there, I enjoy reading through your post. I wanted
to write a little comment to support you.
Is it going to be in the betAAAAAA
From a logic and math novice: could you explain “The proof, of course, is by induction on the length of (that is, the number of steps in) the assumed proof of q.”
I’m not sure how far back to go. Do you understand proof by induction? If I am trying to establish a statement about a natural number n, what I have to do is to prove that it holds for n=1, and that if it holds for all numbers less than n then it holds for n. For then the proposition holds for all numbers less than 2 (i.e. for 1) and so holds for 2; then it holds for all numbers less than 3 (i.e. for 1 and 2) and so it holds for 3; and so on.
Now for the Deduction Theorem. We are trying to show that if you can prove p→q from a set S of assumptions, then you can prove q from the assumptions augmented by p. This depends on the formal definition of proof and the allowable rules. We are assuming that we have a formal proof of p→q, with, say, n steps, and we are assuming that if an implication can be proved in fewer than n steps then the desired conclusion holds. Now the last step in the proof in front of us is either quoting an axiom or an assumption or (most likely) is an inference from previous steps in the proof. In the last case, the hypotheses in the inference have shorter proofs, so we know that the conclusion of the Deduction Theorem holds for them; using the rules of the formal system we can deduce the required conclusion.
I can’t really be more explicit without going into precise details about the proof system involved here, which is not pretty.
Where is part 2?
No offense intended, just calling a spade a spade, but you have not defined what is proof in mathematics; the way I am impressed by your words, is that you are a quibbler.
Anyway, let me see part 2.
Specially, in part 2, please talk about the role of evidence if any in mathematics, and please: no quibbling; for Armesto “[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.”
Marius de Jess
Part 2 is at https://cameroncounts.wordpress.com/2010/01/07/mathematics-and-logic-2/
Thanks a lot for your reaction.
I cannot commend you enough for this gesture, it speaks loads to your credit, bravo!
Now, if I may, have you done any thinking on the role of evidence in mathematics?
By evidence I mean experience of man, your and my and every human’s experience.
Eating is an experience, so is thinking.
Thinking is an experience that can be carried on without any connection with experience of the kind like eating and getting kicked in the ass by someone saucy and stronger than you.
My question is this: Are mathematicians exclusively I mean the people into what is called abstract mathematics into thinking with no connection to experience of the kind like eating and being kicked in the ass by a saucy person stronger than you.
Now, if socalled abstract mathematics can get along pretty well with just abstract thinking but never coming down to evidence meaning experience of the kind like eating and being kicked in the butt, how does it come about that as I seem to understand that some very abstract mathematics is found or discovered to be useful in the solution of engineering problems.
But and correct me if I am wrong, even without however such abstract mathematics, is it possible to construct a space vehicle to get to the moon and return to earth?
I hope to learn from you in matters of mathematics.
Marius de Jess
You ask hard questions! I will put a considered reply here later.
My favorite polymathematician, Charles Sanders Peirce, also gave a fourfold classification of what he called “methods of fixing belief”, or “settling opinion”, most notably and seminally in his paper, “The Fixation of Belief” (1877). Adjusting his nomenclature very slightly, if only for the sake of preserving a mnemonic rhyme scheme, we may refer to his four types as Tenacity, Authority, Plausibility (à priori pleasingness), and full-fledged Scientific Inquiry.
Pingback: Tenacity, Authority, Plausibility, Inquiry | Inquiry Into Inquiry
Pingback: On Defending God’s Reputation From Brain-Washed Idiots | Fight For Sense
Pingback: Lógica: rama de las matemáticas y de la filosofía | Militarizando al Cyrus
How did fix the answer to question asked by your students on using induction to prove statements about mathematics. I think it is a valid question.
It is a good question. It led us to a good discussion. My reply was, roughly (I don’t remember exactly — this was forty years ago!) that in my view mathematical logic is part of mathematics, and the same students would not complain if I used induction in a course on group theory or functional analysis. But I don’t think I said this in an aggressive way to choke off discussion. (At least I hope I didn’t!) You have to remember that I was learning logic myself at the time, so I felt their difficulties quite strongly.
We do not raise the same questions in group theory since we assume axioms of set theory and logical framework(whatever that means) and we believe that all of mathematics can be derived from set theory. But it is reasonable to ask such questions in a course on logic. Also, now that you are older(and more experienced) what would be your take on the same question now, since the way logic was taught then has not changed the way it is taught now. .
There are two quite different things here, in my view. One is the use of logic as the formally correct way to reason. The other is the body of results in the subject “mathematical logic”, including the compactness theorem for first-order logic, the incompleteness theorem in Peano arithmetic, various results in proof theory, etc. The second is clearly a branch of mathematics like any other. The first is somewhat special but I don’t need the second in order to check that a proof in group theory is correct, for example.
What I believe now is stated cleary by Julian Jaynes: you can find this on my page of quotes. We use formal logic in reasoning only as a last resort. Most of the time we do mathematics without having the logical rules uppermost in our minds: we use them unconsciously as a kind of mental hygiene. But we could go back and prove everything formally if challenged (or at least, so we believe).
After my first experiences teaching logic, I used to enjoy provoking the maths and philosophy students by telling them that a proof was anything you could get past a referee. (An important part of a philosopher’s training is to learn to destroy other people’s arguments; you have to have your wits about you to destroy this one.)