Completeness and Incompleteness

This is an appreciation, provoked by a depreciation, of Gödel’s Incompleteness Theorem of 1931.

In the “Gödel for Dummies” version of the Theorem, there are mathematical sentences that are both true and unprovable. This requires two points of clarification.

  1. Gödel shows,
    • not only that true unprovable sentences exist,
    • but also how to write down an example.

    This will be the sentence

    x Q(x, p),

    “For all numbers x, Q is true of x and p,”

    for a certain binary predicate Q and a certain number p.

  2. A sentence known to be true must have a proof of some kind. The proof that ∀x Q(x, p) is true will be of a new kind, not under consideration when the sentence is constructed. From a system for proving theorems that meets a certain standard, the sentence ∀x Q(x, p) is obtained, and this is not a theorem of that system.

The sentence ∀x Q(x, p) is true, because its very meaning is that the sentence ∀x Q(x, p) has no proof in the given system. In the “Gödel for Dummies” version, the sentence means, “I have no proof.” If this were false, then the sentence would have a proof and would therefore be true; thus it is true.

The sentence ∀x Q(x, p) does not refer to itself as such. The reader may skip the details, but

  • p is the “Gödel number” of the formula ∀x Q(x, y), and
  • Q is so defined that, for all numbers a and b,
    • if the sentence Q(a, b) is not true,
    • then, and only then,
      • b is the Gödel number of some formula φ(y), and
      • a is the Gödel number of a proof of the sentence φ(b) within our specified system.

Thus the meaning of ∀x Q(x, p) is that no x is ever the Gödel number of a proof of the sentence φ(p), when φ(y) is the formula of which p is the Gödel number. In short, φ(p) is unprovable. We now observe that φ(p) is precisely the sentence ∀x Q(x, p).

That is a simplified version of Gödel’s Theorem, such as can be found for example in the two-page article “Gödel’s Theorem” by Peter J. Cameron in the Princeton Companion to Mathematics (2008). There is additional interest in the full version of the Theorem, which is reviewed by C. Smorynski in a 46-page article, “The incompleteness theorems,” in the Handbook of Mathematical Logic (1977). My main source will be Gödel’s original article, translated as “On Formally Undecidable Propositions of Principia Mathematica and Related Systems I” in From Frege to Gödel: A Source Book in Mathematical Logic, 1879–1931 (third edition, 1976).

Even in the simplified version, is Gödel’s result surprising? At least one person thinks not. In an interview by John Horgan called “Philosophy Has Made Plenty of Progress” (Scientific American, November 1, 2018), Tim Maudlin says,

Absolutely no one should have ever been surprised that mathematical truth cannot be equated with theoremhood in some finite axiomatic system. An infinitude of mathematical truths are uninteresting trivia, with no obvious route to being proved. Example: [to be considered later].

… All Gödel did was find a clever way to construct a provably unprovable mathematical fact, given any consistent and finite set of axioms to work with. The work is clever but in no way profound. It should have come as no surprise at all.

That “clever way” laid the foundations of computer science, proof theory, recursion theory, and even, in a different sense, my own field, model theory. Perhaps one thinks these pursuits were going to develop anyway.

I see two important technical errors in what Maudlin says.

  1. Having “no obvious route to being proved” is not the same as being unprovable.
  2. Gödel’s Theorem holds, not for “any consistent and finite set of axioms,” but for any one that meets a certain criterion.

Several more points should be clarified.

  • The set of axioms covered by the Theorem need not be finite; it may be infinite, as long as it is recursive: this means there is a method for telling whether a given expression is one of the axioms.
  • The Theorem involves not just axioms, but rules of inference for deriving theorems from the axioms. Axioms and rules of inference together compose the kind of system, a proof-system, alluded to earlier.
  • Consistency has two meanings a priori:
    • A set of axioms is consistent if it has a model;
    • a proof-system is consistent if it cannot prove a contradiction.

    Before the Incompleteness Theorem could be proved, somebody needed to bring the two notions of consistency together with a Completeness Theorem; Gödel did this too.

For example, the fifth proposition of the first book of Euclid’s Elements is that the base angles of every isosceles triangle are equal to one another. By what we can now recognize as a rule of inference called instantiation, we can conclude that, if in a particular triangle ABC the sides AB and AC are equal, then so are the angles ABC and ACB. If we can prove that ABC is indeed thus isosceles, then, by another rule of inference, called modus ponens, the base angles of ABC must be equal.

Euclid does not spell out his rules of inference. They are nothing surprising. However, Euclid’s “common notions”—rules such as “Equals to the same are equal to one another”—can be understood as the axioms of his proof-system.

We can apply a proof-system to additional axioms, so as to derive theorems from these. Thus we can understand the Elements as an application of a certain proof-system to Euclid’s postulates, such as the Parallel Postulate (“If a straight line cross two others and make the interior angles on the same side less than two right angles, then the two straight lines, extended, will meet on that side”).

For the Incompleteness Theorem, Gödel derives a proof-system from the Principia Mathematica (1910–3) of Whitehead and Russell, and he applies it to the Peano axioms for the counting numbers.

Actually Gödel works with the natural numbers, which start with zero. The counting numbers start with unity; this is what Peano himself did, and I shall do the same, though there are technical reasons why having zero can be nice.

Unity is a counting number, and every counting number has a successor. Beyond this:

  1. Unity is not the successor of any counting number.
  2. Counting numbers with the same successor are the same.
  3. A set contains all counting numbers, provided it contains
    • the successor of its every element, and
    • unity.

Those are the Peano axioms, which Peano published in 1889, using notation that Russell and Whitehead would adopt for the Principia Mathematica. Dedekind published equivalent axioms in 1888, but without notation that caught on. He understood the axioms better though, as I have discussed in “Induction and Recursion” (The De Morgan Journal 2 no. 1 [2012], 99–125).

The third of the Peano axioms above is the Induction Axiom. The three Peano axioms together entail the Recursion Theorem.

  • Induction is a method of proving assertions that are true about all counting numbers.
  • Recursion is a method of defining new functions of counting numbers.

For example:

  • Every counting number is either unity or the successor of a counting number, since
    • unity meets this condition, and
    • the successor of every natural number that meets the condition meets the condition.

    Perhaps that is the simplest non-trivial proof by induction.

  • Denoting unity by 1 and the successor of m by Sm, we define addition recursively by requiring, for all counting numbers n and k,

    n + 1 = Sn,

    n + Sk = S(n + k).

    There is a similar recursive definition of multiplication.

The Induction Axiom is second-order, because when written out formally as

X (1 ∈ X & ∀y (yXy + 1 ∈ X) ⇒ ∀y yX),

the axiom uses a variable, namely X, that stands for sets of numbers. The variable y here stands for individual numbers; a formula using only such variables is first-order. Peano introduced the symbol ∈, read as “is in”; it is based on the Greek epsilon, the initial letter of ἐστί, meaning “is.” For the arrow ⇒ of implication, Peano used a different symbol (a reversed letter C, thus Ɔ, later stylized as ⊃).

The Recursion Theorem is also second-order, since it uses variables for functions of numbers:

xηζ (ζ(1) = x & ∀y ζ(Sy) = η(ζ(y))).

Gödel proves the Incompleteness Theorem using second-order variables. Then he shows that, by introducing second-order constants, such as + and ×, for the recursively defined functions of addition and multiplication, along with appropriate axioms that govern their behavior, we can do everything in first-order logic.

The first-order sentences that are true in a particular structure constitute the complete theory of that structure. The structure is then a model of that theory. If we let N be the set of counting numbers, then the complete theory of the structure (N, +, ×) is not recursively axiomatizable; in other words, the indicated complete theory is undecidable. This is Gödel’s result. Equivalently, any recursively axiomatized theory for which the structure (N, +, ×) is a model must be incomplete.

By contrast, Presburger gave, in 1929, a complete axiomatization of the complete theory of (N, +); Skolem gave, in 1930, the same for (N, ×). Since then, many decidable complete theories have been found. They are the subject of Abraham Robinson’s 1956 book Complete Theories, and they are a subject of model theory, which again is that branch of mathematical logic that I happen to specialize in.

Tim Maudlin specializes in the philosophy of physics. His belittling of accomplishments in other fields is unbecoming. Mathematics is intimately connected with physics, and the two fields have been indistinguishable for much of their history; but they are different. Briefly, mathematical proof is deductive; physical, inductive. Maudlin may be satisfied with the latter; others of us are not.

One might attempt to characterize an inductive proof, in the present sense, as having the form, “Such-and-such has happened, in n cases; therefore it will always happen.” For example, when we draw k points on the circumference of a circle, and connect them all with straight lines, these divide the circle into 2k − 1 regions in at least 5 cases, namely when k is 1, 2, 3, 4, or 5. Therefore, “by induction,” the same will happen, no matter what number k is.

Thus the given characterization of inductive proof is inadequate. The example is an incorrect proof, and it would be incorrect, even if the result were correct. In fact the result is not correct, since with 6 points we get 31 regions, not 32.

An inductive proof of the form given needs to be backed up with some kind of reason. Different fields of inquiry will allow different kinds of reasons. I can say no more than this, except that, in mathematics, the reason will again be a two-part deduction:

  1. That the assertion to be proved about k is true when k = 1, and
  2. That, for every counting number m,
    • if the assertion is true when k = m,
    • then the assertion is true when k = m + 1.

Elsewhere in the interview by John Horgan, Maudlin says he believes—though he has no proof—that

the fundamental physical law—when presented in the right mathematical language—will be so compellingly simple that we would think that any other structure would be unnecessarily complicated.

There seems to be no question of whether there is a fundamental physical law. However, it seems to me that, if there were a single “fundamental physical law,” it would effectively be an axiom from which every scientific truth could be proved. In that case, with Maudlin’s own interpretation of Gödel in mind, might we not suggest that physicists are wasting their time and our money, trying to find a fundamental physical law, since “absolutely no one” should expect it to exist?

Physics is mentioned in the 1958 book of Ernest Nagel and James R. Newman called Gödel’s Proof:

… although certain parts of physics were given an axiomatic formulation in antiquity (e.g., by Archimedes), until modern times geometry was the only branch of mathematics that had what most students considered a sound axiomatic basis.

But within the last two centuries the axiomatic method has come to be exploited with increasing power and vigor. New as well as old branches of mathematics, including the familiar arithmetic of cardinal (or “whole”) numbers, were supplied with what appeared to be adequate sets of axioms. A climate of opinion was thus generated in which it was tacitly assumed that each sector of mathematical thought can be supplied with a set of axioms sufficient for developing systematically the endless totality of true propositions about the given area of inquiry.

Gödel’s paper showed that this assumption is untenable …

Should mathematicians really have known all along that “this assumption” was untenable? They would first have had to recognize the assumption as such.

From the mid-nineteenth-century discovery of non-Euclidean geometry, one may induce that Euclidean geometry without the Parallel Postulate is incomplete. One can deduce the same thing, by using Euclidean geometry to construct a model of Lobachevskian geometry. In one such model, you let an infinite straight line divide the Euclidean plane into two parts. You throw out one part, along with the points on the dividing line itself. In the remaining “half-plane,” semicircles with centers on the boundary line are to be considered as “straight” in Lobachevski’s sense. So are straight lines at right angles to the boundary line; but no other lines, whether straight or curved, are to be considered as “straight” in Lobachevski’s sense. Euclidean full circles in the half-plane are Lobachevskian circles, though the centers will be different; right angles stay the same. In this way, as Euclidean geometry is consistent, so is Lobachevskian geometry, though it denies the Parallel Postulate; thus this postulate is not implied by Euclid’s other postulates.

We say Euclidean geometry is consistent, because we think that it has a model. In the seventeenth century, Descartes used this model to establish the consistency of algebra. The discovery of non-Euclidean geometry casts doubt on whether Euclidean geometry is consistent. We can now turn Descartes around. David Hilbert does this in The Foundations of Geometry (1899). If (Ω, +, ×, <) is an Archimedean ordered field that contains the square root of each sum a2 + b2, then the set Ω2 of ordered pairs of elements of Ω serves as a plane in which Hilbert’s axioms for Euclidean geometry are satisfied.

Hilbert observes the possibility of an Axiom of Completeness, which would ensure that Ω must be the field of real numbers. However, the completeness here is not of a theory, but of the ordering of the field. An ordered set is complete if every nonempty subset that has an upper bound has a least upper bound. This is a second-order condition. (It implies the corresponding result for lower bounds.)

As Tarski showed in the 1940s, the first-order theory of the real ordered field (R, +, ×, <) is decidable; equivalently, the field has a recursive axiomatization. The axioms are those of a real closed field. But there are other real closed fields besides R.

By contrast, the ordered field of real numbers is completely determined by the axioms of a complete ordered field; in a word, these axioms are categorical. So are the Peano axioms. However, in each of these two cases, one of the axioms is second-order. The Archimedean Axiom, which Ω above satisfies, is also second-order; however, the unique complete ordered field R is automatically Archimedean.

There is a third kind of completeness, enjoyed by a consistent proof-system when, for every sentence σ that is true in every model of a set Γ of axioms, there is a proof of σ from Γ. By the Completeness Theorem, proved by Gödel in his doctoral dissertation of 1930, a complete first-order proof-system can be extracted from the Principia Mathematica. Consequently, if this proof-system cannot derive a contradiction from a given set of axioms, then this set must be consistent in the sense of having a model.

At the beginning of the 1930 paper based on his dissertation, Gödel explains the Completeness Theorem as follows, for the case when Γ above is empty:

Whitehead and Russell, as is well known, constructed logic and mathematics by initially taking certain evident propositions as axioms and deriving the theorems of logic and mathematics from these by means of some precisely formulated principles of inference in a purely formal way (that is, without making further use of the meaning of the symbols). Of course, when such a procedure is followed the question at once arises whether the initially postulated system of axioms and principles of inference is complete, that is, whether it actually suffices for the derivation of every logico-mathematical proposition, or whether, perhaps, it is conceivable that there are true propositions (which may even be provable by means of other principles) that cannot be derived in the system under consideration.

It seems that in fact the question of completeness did not arise at once, at least not for Russell and Whitehead, though it did for Hilbert and Ackermann in 1928. Nonetheless, Gödel continues:

For the formulas of the propositional calculus the question has been settled affirmatively; that is, it has been shown that every correct formula of the propositional calculus does indeed follow from the axioms given in Principia Mathematica. The same will be done here for a wider realm of formulas, namely those of the “restricted functional calculus” …

The restricted functional calculus is a calculus of what we now call first-order formulas. In the same paper, Gödel proves also the countable case of what we now call the Compactness Theorem: that if every finite subset of a set Γ of sentences has a model, then Γ itself has a model. Malcev will later establish the general case, where Γ may be uncountable. The general form of the Completeness Theorem follows from the special form (where Γ is empty) and Compactness. Conversely, since proofs are finite, Completeness implies Compactness.

There can be no compactness theorem for second-order logic, and hence no completeness theorem. For example, to the axioms for a complete ordered field, we can add infinitely many axioms, whereby the ordered field has an element a that is greater than 1, 2, 3, and so on, and is thus infinite. A model of these axioms would be non-Archimedean, and then its ordering would not be complete (since there could be no least upper bound on the set of finite elements). So the enlarged set of axioms has no model, although every finite subset has one, namely R itself with a great enough.

In Hilbert’s Foundations of Geometry, the distinction between first- and second-order logic has yet to be recognized. In the Principia Mathematica, Russell and Whitehead work with variables of arbitrarily high order. For the Incompleteness Theorem, as we said, Gödel works first with the whole system of the Principia Mathematica, before showing that first-order logic is enough.

Pace Mr Maudlin, a lot of distinctions have to be discovered, before the question can even be raised of whether there are undecidable first-order theories.

The physicist Richard Feynman had a way of teasing mathematicians about their proofs. Possibly Maudlin imitates Feynman, who told his mathematician friends,

I bet there isn’t a single theorem that you can tell me—what the assumptions are and what the theorem is in terms I can understand—where I can’t tell you right away whether it’s true or false.

Could Feynman could cut up an orange and rearrange the pieces into another solid sphere, as large as the sun? He thought not. The mathematicians said he could. However, this result, the Banach–Tarski Paradox, requires infinite divisibility of matter (also the Axiom of Choice). Feynman was correct, if his friends were talking about real oranges, made up of atoms. “So I always won,” he said:

If I guessed it right, great. If I guessed it wrong, there was always something I could find in their simplification that they left out.

This is from “Surely You’re Joking, Mr. Feynman!” (1985; page 85).

By way of showing that the Incompleteness Theorem should have been obvious, Maudlin proposes the question of whether, in the decimal expansions of two real numbers, there is a difference in the first digit, and the next two digits, and the next three digits, and so on. Approximately eight times out of nine, all of these differences will occur. In this case, in Maudlin’s terminology, the original numbers fail to “match.” Can we then prove the failure? Maudlin says,

No amount of just grinding out the digits and checking will ever prove it: there are always more digits to check. And I see zero prospect of any other way to prove that they don’t match. So if they don’t match, that is an unprovable mathematical fact.

Maudlin sees no way to come up with a proof; therefore, for him, there is no proof. This is an induction. Mathematics asks for deductions.

I recall a fellow mathematician to have said that a conjecture ought to be more certain than a theorem. You can prove a theorem without having any intuition for the result; but your proof can always contain mistakes that you did not notice. If you make a conjecture, your confidence in it ought to be greater than your confidence in all of the steps of a proof that convinces you of some other assertion. That is one opinion. I believe the person who expressed it had confidence in the Conjecture of Birch and Swinnerton-Dyer. This did not mean he was going to derive consequences from the conjecture and assert them as new theorems.

As for Gödel’s Completeness Theorem, one might try to argue that there are uncountably many real numbers, but only countably many proofs; therefore there are examples pairs of real numbers that do not “match,” although we cannot prove this failure. As an alternative to Gödel’s proof, such an argument itself fails, because only countably many real numbers can be defined. For example, if you are going to express a real number by its decimal expansion, you need a rule for generating the digits; and there can be only countably many such rules.

There can be only countably many recursively axiomatized complete theories. However, there are uncountably many countable complete theories, since the structure (N, 1, S, P) has a different theory for each choice of P as a subset of N. We can conclude that one of these theories, even uncountably many of them, must be undecidable; but we do not yet know which. Gödel, again, gives us an example, namely (N, +, ×), of a structure with an undecidable theory.

Gödel’s Proof

Let us look in detail at Gödel’s argument.

If you are reading these words on a computer screen, you know that, behind the scenes, each letter has a certain code, which is a number. We express mathematics using formulas; we can understand these as strings of symbols or characters from a certain list; we can give each of those characters a number. One example of a formula is a sentence expressing Fermat’s Last Theorem, proved by Wiles:

xyzw (xw + yw = zw & w ≠ 1 ⇒ w = 2).

Let us call this an arithmetical formula, because the variables range over the counting numbers—arithmoi for the Greeks. Unity was not an arithmos, because it was just one; but we let this slide. Again, Gödel allows zero as well, but I prefer to leave this out.

We should understand the typographical raising of an exponent as having its own symbol, such as a circumflex (ˆ). Then the symbols that we used above are on the list

∀, x, y, z, w, (, ˆ, +, =, &, ≠, 1, ⇒, 2, ).

We can understand our formula itself as the list

∀, x, ∀, y, ∀, z, ∀, w, (, x, ˆ, w, +, y, ˆ, w, =, z, ˆ, w, &, w, ≠, 1, ⇒, w, =, 2, ).

We number the list of all symbols that we may want to use. For writing down numbers themselves in arithmetical formulas, the ten usual digits suffice; moreover, since any number can be written as a sum

1 + 1 + … + 1,

the symbols + and 1 suffice. Still our list of symbols may be infinite, since there is no bound on the number of variables that we may want to use. We could however let every variable be x followed by some number of “primes,” as in x′, x′′, x′′′, and so on. In any case, every symbol on our list can be given its own number, even if the list is infinite. Using these numbers, we can convert any formula into a list of numbers. This will always be a finite list.

We can convert such a list into a single number, in a reversible way. Gödel’s method relies on the Fundamental Theorem of Arithmetic, that each number has a unique prime factorization. If we list the prime numbers as p1, p2, p3, and so on, then any finite list

n1, n2, …, nk

of numbers corresponds reversibly to the product

p1n1 × p2n2 × … × pknk.

In this way, given an arithmetical formula φ, we convert it into a list of numbers, and then into a single number. Let us denote this last number by

φ›.

We now call this the Gödel number of φ.

Given some true arithmetical sentences, we can derive other true sentences in a formal way, by such rules of inference as were mentioned earlier. For example,

  • if ∀xφ(x) is true, then so is φ(3), that is, φ(1 + 1 + 1); and
  • if φ and φψ are true, then so is ψ.

If we choose a specific list Σ of true arithmetical sentences, called axioms, then a proof from Σ is a finite list of sentences, each one being either an axiom or a sentence derived from previous sentences by a rule of inference. The last sentence on the list is what the proof proves. If a proof Σ is the list

σ1, …, σk,

so that Σ proves σk, then we define

‹Σ› = p1‹σ1 × p2‹σ2 × … × pk‹σk.

Our list of axioms may be infinite. Still we shall require the list to be recursive; again, this means there will be some clear rule for determining whether a given sentence is on the list. Equivalently, the set of Gödel numbers ‹σ› of sentences σ on the list should be recursive.

The notions of recursive set, formula, and proof are bound up together so that, for any counting number m, a recursive set of m-tuples of counting numbers is precisely a subset R of Nm such that, for some formula φ(x1, …, xm), for all m-tuples (a1, …, am) in Nm, the following two conditions hold.

  1. (a1, …, am) belongs to R if and only if the sentence φ(a1, …, am) is true.
  2. Whichever of the sentences φ(a1, …, am) and ¬φ(a1, …, am) is true, it has a proof.

The first condition is that φ defines R. We need the second condition, because the set that a formula defines is not always recursive: this will be a consequence of Gödel’s Theorem.

In forty-five steps, Gödel shows that there is a formula B(x, y) defining a recursive set, and for all counting numbers a and c, the sentence B(a, c) is true if and only if, for some proof Γ of a sentence σ, we have

a = ‹Γ›,

c = ‹σ›.

There is then another formula, Q(x, y), also defining a recursive set, and for all counting numbers a and b, the sentence Q(a, b) is true if and only if

  • b = ‹φ(y)› for some formula φ(y), and
  • the negation ¬B(a, ‹φ(b)›) is true, so that a is not ‹Γ› for any proof Γ—if it even exists—of φ(b).

Now let p be the number ‹∀x Q(x, y)›. Suppose, if possible, that there is a proof Γ of ∀x Q(x, p). Then

  • B(‹Γ›, ‹∀x Q(x, p)›) is true, by definition of B; therefore
  • ¬Q(‹Γ›, p) is true, by definition of Q and p.

Since Q, and therefore ¬Q, defines a recursive set, the true sentence ¬Q(‹Γ›, p) has a proof. We can extend this to a proof of ¬∀x Q(x, p).

In short, if ∀x Q(x, p) is provable, then so is its negation. Assuming our proof-system is consistent, we can conclude that ∀x Q(x, p) has no proof. In particular, for each counting number n, ¬B(n, ‹∀x Q(x, p)›) is true. This sentence is equivalent to Q(n, p), which therefore has a proof.

According to Gödel,

We can readily see that the proof just given is constructive; that is, the following has been proved in an intuitionistically unobjectionable manner.

The “following”—what we have proved—is that, if either of ∀x Q(x, p) and ¬∀x Q(x, p) has a proof, then from it we can obtain proofs of

  • the sentence ¬∀x Q(x, p) and,
  • for each counting number n, the sentence Q(n, p).

Not all of these sentences can be true in N. If the theorems of our proof-system must be true in N, then neither ∀x Q(x, p) nor its negation is provable in the system.

If we are not worried about being “intuitionistically unobjectionable,” we may just observe that, if the sentence ∀x Q(x, p) is false, this means that the same sentence actually has a proof; thus, if our proof-system is consistent, the given sentence must be true, while it has no proof.

We saw earlier the Recursion Theorem, whereby, if a is a counting number, and f is a function of counting numbers, then there is another such function, g, given uniquely by the requirements

g(1) = a,

x g(Sx) = f(g(x)),

where S is the function converting x to x + 1. Functions built up in this way, from constant functions and S, by repeated application of recursion in the sense above are by definition recursive (now they are called primitive recursive). If f is recursive, so is the solution set of the equation f(x) = 1. There are clear procedures for

  • evaluating a recursive function at a particular number;
  • determining whether a particular number belongs to a recursive set.

We have seen that addition is recursive. We can understand the formula

x + y = z

to be an abbreviation of the formula

η (η(1) = Sx & ∀w η(Sw) = S(η(w)) & η(y) = z).

This is how formulas defining recursive sets are obtained. However, the example here is second-order. We can simplify it to the formula

η (η(1) = Sx & ∀w (w < yη(Sw) = S(η(w))) & η(y) = z).

That x + y = z means there are numbers u1, …, uy such that

u1 = Sx,

w (w < yuw + 1 = S(uw)),

uy = z.

By the Chinese Remainder Theorem, there are numbers b and d such that each uk is the remainder of b after division by 1 + kd. This allows us to express x + y = z in a first-order way. In return though, we need both addition and multiplication, in order to be able to do this. However, if we allow ourselves symbols for these operations, then we can define all other recursive functions and relations using first-order formulas.

They will not be arbitrary first-order formulas either, but their quantified variables will be bounded, as in

x (x < z & R(x, y)).

Conversely, the sets defined by such formulas are recursive.

Recursive functions and sets are now called primitive recursive, because as Gödel observed in lectures at the Institute for Advanced Study in Princeton in 1934, there are general recursive functions that are not recursive in the original sense (as Ackermann had shown in 1928).

There is a Second Incompleteness Theorem. The set of all Gödel numbers of sentences being recursive, there is a formula F defining it. Let τ be the sentence

y (F(y) & ∀x ¬B(x, y)).

This sentence expresses the consistency of our proof-system. Thus we have shown

τ ⇒ ∀x Q(x, p).

Our proof of this can be formalized within our proof-system (though as Gödel admits, this point needs fleshing out). The proof of ∀x Q(x, p) cannot be formalized. Therefore a proof of τ cannot be formalized, if it is true. If consistent, our system cannot prove this.

Coda

The theory of (N, +, ×) has no recursive axiomatization; but again, the theories of some interesting structures do have. This is what makes interesting the mathematics that I do.

John Horgan’s interview of Tim Maudlin is called, again, “Philosophy Has Made Plenty of Progress.” According to Maudlin,

Overwhelmingly most philosophers are atheists or agnostics, which I take to be convergence to the truth.

According to Christopher Hitchens in God Is Not Great (2007),

Not all can be agreed on matters of aesthetics, but we secular humanists and atheists and agnostics do not wish to deprive humanity of its wonders or consolations. Not in the least. If you will devote a little time to studying the staggering photographs taken by the Hubble telescope, you will be scrutinizing things that are far more awesome and mysterious and beautiful—and more chaotic and overwhelming and forbidding—than any creation or “end of days” story …

Twenty years ago, in 1998, when I was a post-doc at the Mathematical Sciences Research Institute in Berkeley, a friend sent me prints of a couple of those Hubble photographs. I have them still. They are awesome and mysterious and so on, as Hitchens says; but I leave off the comparative “more.” More awesome to me is the power of the mind, in its ability to create myths, to take and interpret photographs, and especially to discover, prove, and make use of such results as Gödel’s Incompleteness Theorem.

%d bloggers like this: