Mathematics and Logic, 2

This is a continuation of a previous post, which you may want to read first. In this post I want to make some further remarks on Gödel’s Incompleteness Theorem, and on the contributions of logic to mathematics.

Recall that the desirable properties of a logical system, soundness and completeness, mean that a formula f is provable if and only if it is true in all interpretations. More generally, a formula f is provable from a set S of formulae if it is true in all interpretations satisfying all the formulae in S.

This last property has an important consequence: a set S of formulae is consistent (no contradiction can be proved from it) if and only if it is satisfiable (true in some interpretation). For a contradiction is true in no interpretation, so is deducible from S if and only if S is true in no interpretation.

Consistency was a matter of great signficance to Hilbert and his followers. Part of Gödel’s Incompleteness Theorem (sometimes called the Second Incompleteness Theorem) states that a logical system which is at least strong enough to include the theory of the natural numbers (with order, addition, and multiplication) cannot prove its own consistency. For example, Peano’s axioms, the commonest such system for the natural numbers, cannot prove their own consistency. Should we worry?

The vast majority of mathematicians accept the existence of the natural numbers. It is easy to see that they do indeed satisfy Peano’s axioms. So, as stated above, this shows that the axioms are consistent.

Another take on this is to consider the Zermelo–Fraenkel axioms for set theory. Now set theory is generally accepted as the standard foundation for mathematics: everything that mathematicians study, from natural numbers to Banach algebras, can be built in set theory. Now the Zermelo–Fraenkel axioms are strong enough to prove the consistency of the Peano axioms. (This is because, as hinted, the natural numbers can be constructed in set theory, see below.)

Of course this only pushes the difficulty elsewhere, since the ZF axioms cannot prove their own consistency. But ZF with a “large cardinal axiom” proves the consistency of ZF. The higher we go, the smaller proportion of mathematicians accept the axioms, of course! While few doubt the existence of the natural numbers, “inaccessible cardinals” are more problematic.

I mention in passing a popular fad, which is to regard category theory rather than set theory as the natural foundation for mathematics. But this is a cop-out: the foundational difficulties with category theory (the large cardinal axioms that have to be assumed) are much stronger than for set theory!

Briefly, the construction of numbers in set theory. Numbers are for counting; like the standard metre, the standard number 2 should be a 2-element set against which other sets can be compared to see if they have 2 elements. The standard set 0 must be the empty set (it follows from the Axiom of Extensionality that there is only one empty set, so we have no choice). Then the standard 1-element set should be the only one we have at this point, namely the set {0}; the standard 2-element set {0,1} (in other words, {0,{0}}); and so on. Each number is the set of its predecessors.

To return to the “First Incompleteness Theorem”, the existence of true but unprovable statements in a theory at least as strong as Peano’s. We have to look at what appear to be ways to circumvent this. If f is true but unprovable, why not just add f as a new axiom? No contradiction will be introduced by this procedure. But Gödel’s argument still applies, and gives a true but unprovable statement in the new theory; and so on ad infinitum.

Why not be bolder then, and add all true statements as axioms? Ah, that won’t work. One of our requirements for a logical system is that there should be a mechanical procedure for recognising the axioms; and there is no mechanical procedure for recognising true statements about the natural numbers. (This was Alan Turing’s great contribution; but in a sense, it must be so, else Gödel’s theorem would be false. Turing gave a precise definition of a “mechanical procedure” by inventing the Turing machine, the theoretical computer which is the prototype for our real computers.)

What do these true but unprovable statements look like? They have the property that Gödel required of them; but, if written out as logical statements in terms of order, addition and multiplication on the natural numbers, they are entirely unnatural (and dependent on the particular axiom system chosen).

There was considerable excitement in the 1970s when Jeff Paris and Leo Harrington found the first example of a “natural” true but unprovable statement. Their statement was a variant of Ramsey’s theorem; I’ll discuss it below.

But it remains true that mathematicians are not very worried by incompleteness, and Hilbert’s warcry, “We must know, we shall know” is still largely true. Very recently, my colleague Angus Macintyre gave a talk at which he announced that Andrew Wiles’ proof of Fermat’s Last Theorem can be formulated as a proof from Peano’s axioms. (This is a considerable achievement. Wiles deduced Fermat’s Last Theorem from his work on the Shimura–Taniyama Conjecture, on the equivalence of modular forms and elliptic functions. It is not clear a priori that these concepts can even be expressed in the language of arithmetic!)

So, despite Fernández-Armesto’s claim, mathematicians seem relatively impervious to post-modernist notions of the relativity of truth. We are fairly sure that we can spot an incorrect argument, and most of us feel that we could prove the recalcitrant theorem we are working on, if only we were clever and industrious enough.

It is very nearly true that no statement which mathematicians had previously invested time and effort in trying to prove has ever turned out to be undecidable. (The exception to this is the Continuum Hypothesis, the statement that there is no set intermediate in size between the natural numbers and the real numbers. This was one of Hilbert’s famous problems posed in 1900; in 1960, Paul Cohen showed that it is independent of the Zermelo–Fraenkel axioms. This means that, rather like geometry where we can study either Euclidean or non-Euclidean geometry (or both), we can do mathematics in which the Continuum Hypothesis is true, or in which it is false.)

Finally, let me turn to the contributions of logic to “straight” mathematics. As I tried to stress in the previous posting, mathematicians in their daily work never reduce all their arguments to the pedantic small steps required by logic. So the syntactic aspect of logic is not much of a concern. But results such as Gödel’s Completeness Theorem for first-order logic have important consequences for ordinary mathematics. Here are two of them, which I would regard as the portals of model theory. (A model for a set S of formulae is a structure in which the formulae of S are true. This is entirely a semantic notion.) Let S be a set of sentences (formulae with no free variables) in a first-order language which has at most countably many symbols in its alphabet.

• The Compactness Theorem: If every finite subset of S has a model, then S has a model.
• The Downward Löwenheim–Skolem Theorem: If S has a model, then it has a model which is at most countably infinite.

A word about the proofs. According to soundness and completeness, the statement “S has a model” is equivalent to “S is consistent”. Now if S is inconsistent, then a contradiction can be proved from it; since proofs are finite, the contradiction must follow from a finite subset of S. This proves Compactness. The Downward Löwenheim–Skolem Theorem relies on the fact that, in the proof of Completeness, it is necessary to construct a model for a consistent set of sentences; observing the proof we see that the model constructed is at most countably infinite.

There is an “upward Löwenheim–Skolem Theorem” which states that, if S is consistent and has an infinite model, then it has arbitrarily large infinite models. But this follows easily from the Compactness Theorem.

Ramsey’s Theorem has a rather complicated statement. The easiest finite form of it is the party theorem: given any number k, there is a number n=R(k) such that, among any given n people, there are either k mutual friends or k mutual strangers. (We assume that any two people are either friends or strangers. The proof that R(3)=6 is well-known, a good exercise if you haven’t seen it.) This can be formulated (and proved) in Peano arithmetic. But there is an infinite form: given an infinite number of people, there are either infinitely many mutual friends or infinitely many mutual strangers. This is a theorem of set theory which can be proved from the Zermelo–Fraenkel axioms. Now the Compactness Theorem shows that the finite party theorem is a consequence of the infinite one.

The Paris–Harrington Theorem, alluded to before, is a generalised version of Ramsey’s Theorem. The “party” version says that, given k, there is a number n=PH(k) such that, given n people p₀,…,p_n-1, there is a set of at least k people, mutual friends or mutual strangers, so that if the least-numbered person in the set is p_m, then there are more than m people in the set.

The theorem is true; it can be deduced from the infinite Ramsey theorem by exactly the same compactness argument that gives the finite Ramsey theorem. But, although it can be formulated in the language of Peano arithmetic, it cannot be proved from Peano’s axioms. The reason is interesting; the appropriate “Paris–Harrington function” grows so rapidly that it cannot be expressed in terms of the functions of arithmetic!

I will end with another connection, very relevant to my own interests.

By the Upward Löwenheim–Skolem Theorem, a theory which has infinite models will have arbitrarily large infinite models; so no set of first-order axioms can uniquely specify an infinite structure. The next best thing is to specify a structure once the size is given. The most interesting case to me is the following.

A set S of first-order sentences is countably categorical if it has a countable model, but only one (that is, any two countable models are isomorphic). A countable structure with countably categorical theory is thus one which can be completely specified by a set of first-order axioms together with the extra assertion that it is countable. The prototype is a theorem of Cantor: A countable dense totally ordered set without endpoints is isomorphic to the rational numbers. (The conditions of being totally ordered and without endpoints are first-order statements.)

Now the following remarkable theorem was proved independently in 1959 by three people, Engeler, Ryll-Nardzewski and Svenonius:

A countable structure M has countably categorical theory if and only if its automorphism group has only finitely many orbits on the set of n-tuples of elements of M for all natural numbers n.

In other words, axiomatisability (by countability and first-order axioms) is equivalent to symmetry (for the condition of the theorem asserts that such a structure has a huge and rich group of automorphisms). I still regard this equivalence of axiomatisability and symmetry one of the most remarkable facts in mathematics.

As I described in the previous post, in the 1970s, I had started to look at permutation groups which have only finitely many orbits on n-tuples for all n. I coined the term oligomorphic for such groups (or, to be accurate, asked my neighbour Roger Green to coin it), on the grounds that different orbits represent different “shapes” of n-tuples, and the condition requires only a few (i.e. finitely many) such shapes. So I fell in love with logic when I realised that oligomorphic groups are essentially just the automorphism groups of structures with countably categorical theories!

So to conclude with two immediate consequences of the “portals of model theory” to oligomorphic permutation groups. Let G be an oligomorphic permutation group, and let a_n(G) be the number of orbits of G on n-tuples. Call a sequence of natural numbers realisable if it arises in this way.

Which sequences are realisable? We are very far from a complete answer to this question; but here are two general remarks.

• By the downward Löwenheim–Skolem Theorem, if a sequence is realisable, then it is realisable by a countable group acting on a countable set. So this theory is not plagued with difficulties about “large cardinals”.
• By the Compactness Theorem, a sequence is realisable if and only if every (finite) initial subsequence of it is an initial subsequence of some realisable sequence. So realisability is a “finitely determined” property.