The Director’s Cut

The creation of numbers was the creation of things.
– Thierry of Chartres¹

It is a useful phrase—the director’s cut. It is useful because it sets the scene: the masterful director; his view; his vision. Mathematics has always been rich in its directors of note. In the third century BCE, Euclid subordinated two-dimensional space to five axioms. Twenty-three hundred years later, Giuseppe Peano brought the natural numbers under axiomatic control. The natural numbers are the oldest objects in our intellectual experience. Without them, we would be lost. Peano arithmetic comprises Peano’s axioms together with their logical consequences. It is a theory as rich as any in the sciences.² The hoarse, excitable Peano is behind the lens. Peano arithmetic, P_A, is what he sees; the natural numbers, ℕ, are what they are.

There it is: <P_A, ℕ>, the director’s cut.

Formal Arithmetic

Kurt Gödel published his remarkable incompleteness theorems in 1931.³ With the exception of John von Neumann, mathematicians found Gödel’s work very difficult.⁴ It remains difficult, uncanny in its power.⁵ “The formulae of a formal system,” Gödel wrote, “are, looked at from outside [äusserlich betrachtet], finite series of basic signs.”⁶ The basic signs are what they seem, but who is looking at them from the outside? It can hardly be Peano. The symbols in Peano arithmetic are transparent: Peano is looking through them. It is what we all do. A contrived withdrawal is required before symbols can be seen as signs.

Peano arithmetic is expressed in the language of mathematics and in ordinary English.⁷ For all natural numbers, m = n if and only if S(m) = S(n). Two numbers are equal if and only if their successors are equal. The exuberant mathematician is handling things with an easy familiarity. And why not? He commands the scene: Peano’s axioms, Peano arithmetic, and, beyond them, the natural numbers. The logician stands apart. His is an orthopedic practice. He is concerned to see the articulated skeleton beneath Peano arithmetic, its formal system F_PA.⁸ It is the logician who is looking at things from the outside.

Like certain objects in the physical world, F_PA is atomic in nature. Its atoms are its basic signs; its molecules, their combination. Logical constants are first: ‘~’ (not), ‘∨’ (or), ‘∀’ (all), ‘0’ (zero), ‘S’ (the successor of), and, in ‘)’ and ‘(’, right and left parentheses. Although sparse, these signs cover the contingencies, ordinary numerals vanishing in favor of a stuttering ‘S’, so that ‘S S S S (0)’ in F_PA does duty for ‘4’ in English. Individual variables are next: ‘x,’ ‘y,’ ‘z,’…, and the like. With arithmetical functions, predicates, and relations, it is more of the same.⁹ Whatever the signs, they must be combined, and this is a procedure superintended by specific rules. Elementary formulas are given explicitly. The well-formed formulas are then defined as the smallest set containing all of the elementary formulas and their negations, disjunctions, and universal quantifications.

If Peano arithmetic is an arithmetic theory, it is also an axiomatic theory. Theorems follow from the axioms in a gross cascade. It is the logician who must specify the rules of inference of a formal system, the flow of its deductions. An appeal to meaning is not allowed. A formal system is a system of signs. It might as well be a system of shapes. Some inexorable sense of rightness nevertheless prevails. Given

Mierīgie ūdēņi ir tie dziļākie ⊃ Mierīgie ūdēņi ir tie dziļākie

and

Mierīgie ūdēņi ir tie dziļākie,

it follows that

Mierīgie ūdēņi ir tie dziļākie.

If the underlying language is inscrutable,¹⁰ this inference is crystal clear, contingent only on the antecedent identification of ‘⊃’ as a logical particle.¹¹ The rules of inference governing a formal system are procedural; but as rules of procedure, they correspond, or express, a natural motion of the human mind, the power to move from one proposition to another.

Peano arithmetic is constructed from the Peano axioms,¹² but in the context of formal arithmetic, those axioms lose some of their incidental glamor and appear as axioms in virtue of being called axioms. They have been set apart by being set apart. The inference that has just led to Mierīgie ūdēņi ir tie dziļākie is modus ponens, and modus ponens is one of the two rules of inference that figure in Gödel’s argument. The second expresses the common understanding that what holds for anything holds for something. In these cases, to go inferentially from one formula to another is go somewhere at once. There are no intermediate stops. The provable formulas comprise the smallest set containing the axioms of Peano arithmetic and closed under the release of immediate inference.

In F_PA, a new mathematical object has come into being. Physical objects are described by the laws of physics. Their nature is disclosed. A formal system is determined by its formation rules, its rules of inference, and by the screening off that screens off its axioms. Its nature is induced. It is induced subject to a double standard of effectiveness. The well-formed formulas, the axioms, and the rules of inference make for three sets of formal objects. Standards for membership are strict. It must be possible to decide whether a given formula is well-formed and whether it is not. It must be possible to do both in a finite series of steps. And it must be possible to do as much for the axioms and the rules of inference.¹³

“Whatever withdraws us from the power of our senses,” Samuel Johnson observed, “whatever makes the past, the distant, or the future predominate over the present, advances us in the dignity of thinking beings.”¹⁴

The Recursive Scaffold

Peano arithmetic is a theory about the natural numbers, and these have remained unattended and unvoiced. They now come into their own. Gödel used the natural numbers to identify the formulas of a formal system, the identification so close that Gödel felt justified in referring to the basic signs of a formal system as natural numbers.¹⁵ To every basic sign, and then to every formula, and then to every sequence of formulas, and then to every series of such sequences, Gödel assigned a unique number. Basic signs are mapped to basic numbers:

‘0’ ↔ 1, ‘S’ ↔ 3, ‘~’ ↔ 5, ‘∨’ ↔ 7, ‘∀’ ↔ 9, ‘(’ ↔ 11, ‘)’ ↔ 13.

More complicated formulas are mapped to more complicated numbers. The basic signs appear in this list sheathed in single quotation marks. They are being mentioned, and not used. Those sheaths serve as their name, and their naming takes place from beyond F_PA. It is an outside baptism.¹⁶ Gödel numbering is ingenious because of the way it reverses the natural line of sight. The director’s eye normally goes from signs to numbers. Gödel numbering encourages a reversal, one that goes from numbers to signs. The coordination achieved suggests a Cartesian coordinate system, but something stranger, too, and more difficult to grasp.

The prolegomenon to Gödel’s proof consists of forty-six definitions. Each depends on the one that has come before, and each embodies a primitive recursive function.¹⁷ These functions admit of a peculiar kind of definition. Both Richard Dedekind and Peano made use of the technique. The addition of any two natural numbers is resolved into two clauses. The first establishes that adding x to zero goes nowhere beyond x: 0 + x = x. The second defines addition in terms of succession and downward descent: x + S(y) = S(x + y). Three plus four is the successor to three plus three. Downward descent follows: three plus three is the successor to three plus two. Descent continues until it achieves its appointed apotheosis in 0. Three plus four is the sevenfold successor of 0. Multiplication? The same. “As one can easily convince oneself,” Gödel writes, “the functions x + y, x ⋅ y, x^y and furthermore the relations x < y and x = y are primitive recursive.”¹⁸

Division does not figure in the Peano axioms.¹⁹ Gödel’s first definition brings it to life:

x/y =_df (∃z)(z ≤ x & x = y. z).

There are no surprises. Whatever the number x, it is divisible by y just in case there is a number z, less than or equal to x, such that x is the product of y and z. This is, after all, what division means. The sentence ‘x/y =_df (∃z)(z ≤ x & x = y. z)’—the whole thing—is no part of F_PA. Still, it is possible to think of ‘x/y’ as a derived sign, with ‘(∃z)(z ≤ x & x = y. z)’ indicating a path back to the basic signs of the system.

“We will now define a sequence of functions (relations),” Gödel goes on to write, “each of which is defined from the preceding ones.”²⁰ The definitions accumulate, one after another, each following from the one that has gone before, and each admitting the discipline of definition by primitive recursion. The expanding sequence of definitions very quickly encompasses concepts such as formula, axiom, and immediate consequence. These are not obviously arithmetical. They are not arithmetical at all. Gödel numbering shows this earthy view to be primitive. Relationships between signs may be mirrored by relationships between numbers.

Forty-five definitions having been given; the forty-sixth, and last, defines the predicate ‘Bew (x)’:

Bew (x) =_df (∃y)(y Bw x).

The sign ‘Bew (x),’ this definition affirms, may be replaced by ‘(∃y)(y Bw x).’ The sign ‘y Bw x’ is, in turn, defined by the forty-fifth definition, and so back to the first. The sign ‘Bw’ is by birth arithmetical. In the strictest of strict senses, it stands for nothing beyond itself. But by virtue of its birth, it is intended to designate a relationship between numbers. At the same time, ‘Bw’ enjoys a second interpretation by virtue of its place in logical society. It stands for the German Beweis, or proof. Under this interpretation, ‘y Bw x’ coordinates two numbers y and x, where y is the Gödel number of a proof of a formula whose Gödel number is x. These definitions fix in amber or aspic the arithmetic predicate ‘Bew (x)’ and the logical predicate ‘Bew (x)’. Peering into his own film, the director is now able to see himself peering into his own film.

A chain of definitions takes ‘Bew’ to the heart of F_PA and its basic signs. The definitions that precede the last are all primitive recursive. They depend on the definitions that have gone before until they empty themselves out at 0. The forty-sixth remains apart. It stakes a claim. It says that some x is Bew. Its existential quantifier is not bounded.²¹ It is the difference between a closed- and an open-ended search.

So far as primitive recursion goes, it is all the difference in the world.

A Step Before the Last

There is a tight connection between Gödel’s definitions and the formulas within F_PA. This is the subject of Gödel’s fifth theorem. It is a theorem in two parts. Suppose that R(n₁, …, n_n) is a primitive recursive function or predicate controlling the numbers n₁, …, n_n. The numbers, note—the real things. It follows that R(n₁, …, n_n) may be represented within F_PA by a formula in which signs stand where vernacular variables stood: R(n₁, …, n_n). Underlining serves to underscore the distinction between signs within the formal system and symbols about the formal system or the natural numbers. If R(n₁, …, n_n) is a primitive recursive function, predicate, or relation, there is always a translate R(n₁, …, n_n) within F_PA such that

1. if R(n₁, …, n_n) is true in ℕ, then R(n₁, …, n_n) is provable within F_PA.
2. If R(x₁, …, x_n) is false—then not.

As logicians say

ℕ ⊨ R(n₁, …, n_k) ⇒ F_PA ⊢ R(n₁, …, n_k)

ℕ ⊨ ~R(n₁, …, n_k) ⇒ F_PA ⊢ ~R(n₁, …, n_k).

This claim is compelling. If ‘2 + 2 = 4’ is true in N, then its translate is provable within F_PA. If not, of what use F_PA? The theorem does not, by itself, identify the translate.²² What can be said in its favor is that it exists. It is hard to imagine a tighter connection, but if the connection is tight, it is tight only for the primitive recursive functions. Proof is otherwise. It is not primitive recursive, satisfying 1. but not 2. The first forty-five of Gödel’s predicates and relations are strongly represented within F_PA. The forty-sixth, and last, weakly represented.

And this, too, is something logicians say.

Incompleteness

If Peano arithmetic is consistent, there is a formula within F_PA such that neither it nor its negation is provable in F_PA.²³ The formula is undecidable. Peano arithmetic is incomplete. Gödel’s proof of his great theorem is rebarbative—there is no other word. But in the opening paragraphs of his treatise, Gödel, writing with his own matchless concision and elegance, offers an accessible, if informal, account of his argument.

Consistency gives way in favor of the assumption that every provable formula is true. Suppose all the formulas of F_PA with one free variable x so arranged that the nth formula is designated R(n). A variable x is free if it does not lie within the scope of any quantifier, so that F(x) says neither that everything is F nor that something is F. The symbol [α; n] designates from beyond F_PA a formula deep in the bowels of F_PA. And more: it provides a recipe for its construction. It is the formula that results when x is replaced by n in α, the variable giving way to the numeral.²⁴

With this said, consider the class K of natural numbers such that

n ∈ K ≡ ~Bew[R(n); n].

The definition of K makes use only of concepts that have already been defined. It is of a piece with the forty-six definitions on record. It follows that there is a formula G(n) in F_PA that, if only it could talk, would say that n ∈ K. “There is not the slightest difficulty,” Gödel observes, “in writing out the formula G.”²⁵

The formula designated by G is within F_PA. Thus

G = R(q)

for some number q, since the formulas of F_PA have been gathered into a list in which everything is included and nothing is left out.

The conclusion of the incompleteness theorem is now budding on the bunched fingertips of this argument. [R(q); q] is an instance of [α; n]. The recipe enjoined by [α; n] is in force. [R(q); q] is the formula within F_PA that results when q replaces x in R(q). The Gödel number of R(q) is q. Whence by a chain of definitions

G(q) ≡ [R(q); q] ≡ q ∈ K ≡ ~Bew[R(q); q].

[R(q); q] is a mute collocation of signs. By itself, it says nothing, but like an ancient rune, when read rightly, it says that R(q) cannot be demonstrated.²⁶ But G = R(q). G says as much. It says it of itself. And it must exist.

The argument proceeds by contradiction. If true, then by I, it must be provable.²⁷ But since q ∈ K it must be unprovable as well.

It cannot be both.

The assumption that G is unprovable in F_PA leads again to contradiction. The argument, but not the proof, is over.

Inexpressible Truth

At much the same time as Gödel published his incompleteness theorems, Alfred Tarski published his treatise about the concept of truth in formalized languages.²⁸ Gödel and Tarski seem to have anticipated one another, circumstances that themselves convey an air of paradox. Formal arithmetic, having served as a system’s skeleton, must now acquire the musculature of real life—an interpretation in the natural numbers. Signs become symbols. An interpreted version of F_PA has among its symbols any number of individual variables, the usual sentential connectives and quantifiers, and, at most, denumerably many predicate variables of various finite ranks. Some home assembly is yet required. By a model, logicians mean an ordered pair M = < D, φ >, where D is the domain of M, and φ a function assigning to the predicate variables of F_PA relations of corresponding rank on D. An assignment α is a function that maps the individual variables of F_PA onto individuals in D. Whence

α satisfies S(x, …) in M,

defined by recursion on the length of S. A sentence is a formula with no free individual variables, and, as such, is either satisfied by every assignment or by none. It is True in M, or False in M. There is no wishy-washiness about it.

Tarski’s argument is scorpion shaped. Its sting is in its tail. The first few steps are obvious. A property or relation is definable within M if and only if there is a formula in F_PA defining it.²⁹ The number x is even if it is the sum of two identical numbers. The requisite formula is ‘∃y (x = y + y).’ A relation in M has been defined by a formula of F_PA. This is mildly marvelous, but no more than that.

Let Tr be the set of Gödel numbers of the true sentences of F_PA. Is Tr definable in M? If so, there must be a formula Tr(x) in F_PA such that Tr(x) is satisfiable in M only for the interpretation of Tr as Tr. Suppose Tr defined in F_PA so that for every sentence, there is a proof that Tr(S) ↔ S, where S is the name of S. Whereupon there is ~Tr(S) ↔ S, where S encodes the Gödel number of ‘~Tr(S).’³⁰

There is no formula Tr. That is the sting.

The Mind as a Machine

When Gödel’s treatise first appeared in English, John Lucas concluded that men were not machines.³¹

Gödel’s theorem must apply to cybernetical machines, because it is of the essence of being a machine, that it should be a concrete instantiation of a formal system. It follows that given any machine which is consistent and capable of doing simple arithmetic, there is a formula which it is incapable of producing as being true—i.e. the formula is unprovable-in-the-system—but which we can see [emphasis added] to be true. It follows that no machine can be a complete or adequate model of the mind, that minds are essentially different from machines.³²

Roger Penrose revived the claim and endowed it with the luster of his great reputation. “[H]uman understanding and insight,” he argued, “cannot be reduced to any set of computational rules.” This conclusion, Penrose insisted, followed from Gödel’s theorem. “[T]here must [emphasis added] be more to human thinking,” he added plaintively, “than can ever be achieved by a computer.”³³ Because this thesis expressed a common human hope, or, as much, a common human fear, it was rejected by a number of philosophers and logicians.

Very early on, Hilary Putnam argued that the Lucas–Penrose argument was flawed. What can legitimately be established by the incompleteness theorem is only the conclusion that

1. F_PA is consistent if and only if G is undecidable.

What is more, 1. may itself be demonstrated within F_PA. Absent a proof of the consistency of F_PA, 1. does nothing to show anything.³⁴ And by Gödel’s second incompleteness theorem, there can be no proof of the consistency of F_PA within F_PA.³⁵

No one, least of all Lucas or Penrose, considering them as two heads on one body, should have argued the contrary. It is easy to see that G must be true; difficult to see that F_PA is consistent; and in neither case is a proof forthcoming in F_PA. What can be demonstrated is 1.; what can be seen is G. These are two different claims. They belong to two different orders of thought.³⁶

On ne va tout de même pas pinailler pour si peu.

Nor does 1. demonstrate anything more than an incidental kinship between consistency and undecidability. They are provably equivalent within F_PA. They are not are generally the same. If they were, then any consistent system would, by definition, be incomplete. Presburger arithmetic stands as a case to the contrary. Consistency and incompleteness coincide for systems rich enough to generate whole number arithmetic.

Lumbering after Putnam, Panu Raatikainen has acquired his shadow. The Lucas–Penrose argument is invalid, Raatikainen argues, because

in general, we have no idea whether the Gödel sentence of an arbitrary system is true. What we can know is only that the Gödel sentence of a system is true if and only if the system is consistent, and this much is provable in the system itself.³⁷

The first of these claims is false, the second, incoherent. No idea? Gödel’s proof contains a strong, sustained, and powerful argument that G is not provable in F_PA. This is what G says. That should give anyone some idea whether G is true. Were G false in N its negation would be true in N, and, in that case, demonstrable in F_PA. This is so plainly an unwholesome conclusion that no one is disposed to endorse it, least of all Gödel: “From the remark that [R(q); q] says about itself that it is not provable, it follows at once that [R(q); q] is true, for [R(q); q] is indeed unprovable (being undecidable).”³⁸

There remains Raatikainen’s claim that “the Gödel sentence of a system is true [emphasis added] if and only if the system is consistent.” So far as it goes, no one might scruple. That “this much is provable in the system itself” is otherwise. It provokes scruples all around. And for every good reason. There is no way to express the truth of G within F_PA.³⁹

What has been neglected in this discussion is the reason that it began: the wish, or the need, to show that men are not machines. This conclusion remains as far from the premise of any argument as it ever was. We may allow Peano to become one with F_PA, and allow Lucas to see what Peano could not see and never saw. It hardly follows that Lucas may not be identified with a formal system, too, the both men, like eighteenth-century courtiers, immured in formality. There is not the slightest reason, Alonzo Church once remarked to me, that the system used to describe F_PA should not itself be formalized, resulting in some still more elaborate system, F_FPA, the superintendent of systems as much identified with F_FPA as Peano is with F_PA. In his course in mathematical logic at Princeton University, Church endeavored to do just that. It was a tedious exercise, Church, glacial and self-contained, in the end lecturing to one or two students.

The phenomenon of incompleteness led Gödel to a characteristically subtle affirmation:

Either mathematics is incompletable in this sense, that its evident axioms can never be comprised in a finite rule, that is to say, the human mind (even within the realm of pure mathematics) infinitely surpasses the powers of any finite machine, or else there exist absolutely unsolvable diophantine problems of the type specified.⁴⁰

If this affirmation is subtle, it is also mysterious. A mathematician, in contemplatively considering F_PA, is in a position to see something that cannot be expressed within F_PA. Just how does this entail the conclusion that the human mind “infinitely [emphasis added] surpasses the power of any finite machine?” The incompleteness theorems carry something like a poisoned seed. If F_FPA is a formal system, it, too, is open to incompleteness, the truth of its Gödel sentence luridly shimmering from the perspective of still some further system. Far from indicating that the human mind is not machinelike, Gödel’s argument shows only that nothing in the incompleteness theorems rules out the possibility that it is machines all the way up.

Gödel, who anticipated so much of the discussion, anticipated this as well:

Such a state of affairs would show that there is something nonmechanical in the sense that the overall plan for the historical development of machines is not mechanical. If the general plan is mechanical, then the whole [human] race can be summarized in one machine.⁴¹

Of this, all one can say is that either the general plan is mechanical or it is not, and no one knows which it is. The thesis that the human mind is a machine is returned to the same dark defile that has already entombed the study of consciousness. The defile is dark because there is nothing to be said, and it is a defile because everyone wishes to say it.

The Director’s Cut

Peano saw what he could see. We see in the light of the incompleteness theorems, and they have changed how things are seen. The truth is neither completely provable nor is it completely definable. These conclusions have retained their power to shock after ninety years. They were established at great expense. To establish these results, Gödel and Tarski needed to collapse multiple perspectives onto a single canvas, the mathematician looking at the natural numbers, the logician looking at the mathematician. But as in all great art, the incompleteness theorems demand, and as often receive, a still further perspective, the viewer beyond the canvas, the reader behind the proof, his vision, his point of view. The incompleteness theorems could not otherwise live in the minds of future generations. The process of withdrawal and encompassing reflection, if indefinite, is also endless. The incompleteness theorems provoke an intellectual experience only against the ever-receding background of a common language, a way of life, a culture of contemplation. No matter the degree to which things have been formalized, the formal objects that result are always described, and so discerned, amidst the inconvenience and distraction of the world in which we find ourselves explaining things to one another, specifying inferences, drawing conclusions, signing contracts, writing love letters, and, in general, getting on with life in ways that are inseparably a part of life.

No formal system explains itself. It cannot say anything and we cannot say everything.⁴²

If this is not a fact of logic, it is a fact of life, and so a feature of life. Every description of voluntary action is as incomplete as Peano arithmetic. No matter the network of causal influences acting on a human being, its description inevitably comes to seem incomplete, the strings in plain sight, the puppet master hidden. There can be no proof of this, of course, but it is something we sense, and it is true. I do not know that we can expect anything more from life, or from logic.

There it is: <P_A, ℕ>, the director’s cut.

So it is. So we are. Even so.