The Implications of Gödel's Theorem

Talk given to the Sigma Club

on February 26th, 1998

by

Mr J.R. Lucas

Gödel's First Theorem, that a certain well-formed formula, which is the code for:

wff. no.m . . . . (An)(n is not the gödel number of m)

is neither provable not disprovable in first-order Peano Arithmetic (granted that it is consistent) has the following consequences:
1.Some purely arithmetical questions are undecidable---some research programmes may be hopeless. [J.Paris and L.Harrington, ``A Mathematical Incompleteness in Peano Arithmetic'', in J.Barwise, ed., Handbook of Mathematical Logic, Amsterdam, 1977.] So may-be we always shall be ignorant of the answers to some mathematical questions; no doctrine of Assurance.
2. Gödel's Second Theorem: The Consistency of a reasonably rich system cannot be proved within that system---End of Hilbert's Programme.
3. Church's Theorem
4. Non-standard models of Peano Arithmetic (can be proved without recourse to G\" odel's Theorem)--inadequacy of formal specification; suggests some form of realism.
5. Quine wrong in thinking first-order logic is cat's whiskers. See under III for difference between Peano's fifth postulate in first- and in second-order logic: Either we have only first-order logic, in which case we need some platonic access to the natural numbers in order to distinguish them from non-standard models of Peano Arithmetic: or we have second-order logic, which involves quantifcation over qualities and relations, which must then, Quinely, be supposed to exist.
6. Verificationism and Intuitionism are wrong.
7. Knowledge claims fallible
8. Realism
9. Quine still wrong in thinking first-order logic is cat's whiskers. Completeness of first-order logic shows poverty of aspiration rather than fulness of achievement. Implausible to maintain that truths of second-order logic are all analytic. But they are a priori.
10. If synthetic a priori propositions are possible, Empiricism wrong. Rationalism respectable.
11. To be reasonable is not merely to follow a rule. Reason can be creative and original.
12. Not out of the question to rely on other people being reasonable.

I Truth outruns provability

Once the concept of proof has been made explicit, and the criteria for being provable clearly laid down, Gödel's theorem shows that there are truths which go beyond that concept of provable. ``there are some mathematical disciplines that can never be completely formalized'' (J.Myhill, ``Some Implications of Mathematical Logic'', The Review of Metaphysics, VI, no.2, 1952, [pp.165-199, esp. pp.181-192,] p.182]. To be reasonable is not just to be in accordance with a rule. Aristotle sometimes talks of kata ton orthosn logon, according to the right rule, sometimes of meta logou, with reason; Gödel's theorem suggests that there is a real difference, and that however carefully we specify rules or criteria, reason is not just rule-observance and can go beyond mere conformity to rules.
Rules will still be important, but not all important.
Originality and creativity
In history or literary criticism it may be right to recognise the authority of great historians or sensitive critics without being able to reduce their reasoning to explicit syllogistic form.
In politics, although we may well distrust the judgement of men, we cannot have our government altogether a ``Government of laws, not men.''

II Non-standard Models of Peano Arithmetic

It is difficult to see how there could be a model of Peano's postulates other than the standard one, which we pictured as the boy's railway track starting with some buffers and extending indefinitely far in one direction. This indeed is how the non-standard model starts too. The non-standardness only crops up over the horizon, so to speak, that is, among the transfinite numbers. The non-standard model of Peano Arithmetic starts off with a progression of order-type w, but then has indefinitely many additional chunks, each of order-type w* + w, the order-type of the integers, negative as well as positive. The order-type w* + w looks like this: .... -7, -6, -5, -4, -3, -2, -1, 1, 2, 3, 4, 5, 6, 7,.... it is what we use for dating, where 1 BC is followed immediately by 1 AD.

The chunks of order-type w* + w in the non-standard model themselves have the order-type eta, the dense order-type exemplified by the rational numbers. There is a concertina effect. Wherever we look, we find a stretch of track of order-type w* + w, but between any two such stretches, unless they are part of the same chunk, and separated by only a finite number of pieces of rail, there are further chunks, each of order-type w* + w. That is to say, although locally we are dealing with a discrete ordering, where each bit of track has a next bit of track and a previous bit of track, globally the separate chunks, each of order-type w* + w, are not discrete; there is no next chunk after any particular one.
|+++. . . .++++. . . .++++. . . .++++. . . .++++. .. w w*+w w*+w w*+w w*+w
For fuller details, see G.S.Boolos and R.C.Jeffrey, Computability and Logic, Cambridge, 1974, 1980, 1989, Section 17, pp.193-195.

III Second-Order Logic

Peano's fifth postulate in first-order logic:

F(0) & [F(m) ---> F(m')] ---> (An)F(n)

with the F as a free variable, not bound by any quantifier. If you name any particular F you please, then provided that it is hereditary and holds of 0, it holds of all the natural numbers; but that is a less stringent condition than the second-order one, where it holds of every F, whether you name it or not. Indeed, there can be only a denumerable infinity, aleph_o, of Fs you might possibly name, whereas there may well be a non-denumerable infinity aleph_1 of properties over which the quantifier (AF) ranges in Peano's fifth postulate in second-order logic:

(AF){F(0) & [F(m) ---> F(m')] ---> (An)F(n)}

First-order logic is complete and compact. For every well-formed formula, G, of first-order logic,

|- G if and only if |= G,

but only because many well-formed formulae of second-order logic are not accounted well-formed in first-order logic.

Second-order logic is ontologically lush, not recursively axiomatizable, not analytic, but arguably adequate: first-order logic is economical with entities, can be done by computers, arguably analytic, but inadequate---even for characterizing the natural numbers.

Note: Self-reference only possible because there are a Dedekind infinity of natural numbers. Otherwise Gödel's coding impossible.