A number larger than every number

An infinite tree with finite branching has an infinite path, and the same argument, applied to formulas instead of tree nodes, is the compactness theorem: if every finite subset of a collection of first-order sentences has a model, the whole collection has one. That essay ended with the consequence that is hardest to believe, stated in a sentence. This one takes the sentence apart.

The consequence is that the whole numbers cannot be described. Every attempt to write down, in first-order logic, the properties that make $0, 1, 2, \dots$ what they are — including every true sentence about them there is — also describes structures with more in them. And the extra elements are not small additions at the edges. They are infinite numbers, sitting after all the ordinary ones, obeying all the same laws.

Asking for more than any numeral #

Take the language of arithmetic — $0$, $1$, $+$, $\times$, $<$ — and add one new constant symbol $c$. Write down every sentence in the original language that is true of the ordinary whole numbers. Then add, for every numeral, the sentence saying $c$ is larger:

$$c > 0, \quad c > 1, \quad c > 1 + 1, \quad c > 1 + 1 + 1, \quad \dots$$

Any finite subset of that collection mentions only finitely many numerals, so it has a model: the ordinary whole numbers, with $c$ interpreted as one more than the largest numeral mentioned. The true sentences are true there because they are true of the whole numbers, and the finitely many demands on $c$ are met by choosing $c$ large enough.

So by compactness the entire collection has a model. Call it $M$. Every first-order sentence true of the ordinary whole numbers is true in $M$, because all of them were in the collection. And $M$ contains an element $c$ that is larger than $0$, larger than $1$, larger than every numeral — an element no ordinary number can be.

The argument is so short that its conclusion is easy to misread. $M$ is not a crude approximation of the whole numbers that some sentence exposes. No first-order sentence distinguishes $M$ from the whole numbers: they are elementarily equivalent, agreeing on everything the language can state. They differ only in a property — every element is reached from 0 by finitely many successors — that the language cannot state, because “finitely many” is not a first-order notion.

Indistinguishable, measured by a game #

“No sentence distinguishes them” can be made to sound vague, and there is a way to make it concrete that has already been built. An Ehrenfeucht–Fraïssé game on two structures lets one player pick elements trying to expose a difference and the other answer trying to keep the two sides matched; the second player can survive $n$ rounds exactly when no sentence with $n$ nested quantifiers tells the structures apart.

For the ordinary numbers and $M$, the second player has a winning strategy for every fixed number of rounds, because the two structures agree on every sentence of every quantifier depth. When the first player picks $c$ in $M$, a suitable ordinary number answers it — one large enough, and with enough of the right divisibility and residues, that the remaining rounds cannot expose the swap — in the same way that a sentence can see only a bounded distance into a structure. What the first player would need is a game of unbounded length, which is the same as a sentence of unbounded length, and neither exists.

That also places this model beside two worlds that obey the same rules. There, a statement was shown independent of a list of axioms by exhibiting two models that disagree on it. Here the two models agree on every first-order statement and still differ, so the difference between them is not independence of any sentence. It is something the language has no sentence for at all.

A structure that has one, and can be drawn #

The model compactness produces is guaranteed to exist and is described by no construction. It is worth seeing a concrete structure with an infinite element, even though — for a reason that comes later — it cannot satisfy everything $M$ does.

The elements are expressions like $7$, $X$, $X + 3$, $2X - 5$ and $X^2 + X$ — anything whose highest term has a positive coefficient, together with $0$. Addition and multiplication are the usual ones for polynomials. One polynomial is smaller than another when their difference has a negative leading coefficient. Under that rule $X - 1000$ is still larger than $1000$, because the difference $X - 2000$ leads with $+X$; so $X$ is larger than every ordinary number, and so is everything in its neighbourhood.

The structure satisfies a good deal of arithmetic. Addition and multiplication behave as they do on whole numbers. The order is total and respects both operations. It is discrete: nothing lies strictly between an element and one more than it. Every non-zero element is one more than something. Those are the laws a theorist calls $PA^-$, and they are enough to prove a surprising amount — but not everything.

The induction it fails #

Every ordinary whole number is even or odd, and the proof is an induction: 0 is even; if $n$ is even, $n + 1$ is odd; if $n$ is odd, $n + 1$ is even. The statement “every $x$ is $y + y$ or $y + y + 1$ for some $y$” is a first-order sentence, true of the whole numbers, and the polynomial structure fails it. $X$ has no half.

That locates exactly what the polynomial structure lacks. It has the algebra and not the induction schema — the infinite family of axioms saying that any property expressible in the language which holds of $0$ and passes from each number to the next holds of everything. Peano arithmetic is $PA^-$ plus that schema, and the model compactness produced satisfies it, because every instance is a true sentence about the whole numbers.

So the polynomial structure is a picture of the idea and not of $M$. It shows that an element beyond every numeral is logically harmless for the algebra. It does not show what induction forces such an element’s surroundings to look like, and that turns out to be a great deal.

What induction forces: galaxies #

In $M$, induction proves every theorem of ordinary arithmetic, and several of those theorems constrain the infinite elements tightly.

Every non-zero element has a predecessor, and every element a successor, so the infinite element $c$ sits in a chain $\dots, c - 2, c - 1, c, c + 1, c + 2, \dots$ running both ways without end. None of those can be an ordinary number, since an ordinary number plus an ordinary number is ordinary. That chain is a copy of the integers, and it is called the galaxy of $c$.

Every element is even or odd, since induction proves it. So $c$ has a half, $\lfloor c/2 \rfloor$, and that half is infinite too — if it were ordinary, doubling it would give an ordinary number within one of $c$. And $c/2$ is not in the galaxy of $c$, because $c - c/2 = c/2$ is infinite, not a finite distance. So there is a galaxy below $c$’s. Halving again gives another below that. There is no lowest galaxy.

Doubling gives $2c$, infinitely far above $c$, and there is no highest galaxy either. And for any two galaxies containing $a < b$, the element $\lfloor (a + b)/2 \rfloor$ is infinitely far from both — so between any two galaxies there is a third.

A countable ordered set with no first element, no last element, and an element between any two is, by a theorem of Cantor, a copy of the rational numbers. So every countable nonstandard model of arithmetic has the same order type: the ordinary whole numbers, followed by a copy of the integers for each rational number, arranged in the order of the rationals. The picture in the figures is not one possible nonstandard model’s order; it is all of them.

The ordinary numbers cannot be singled out #

The galaxy picture raises a question that looks as if it should have an easy answer. Inside $M$, is there a formula that picks out exactly the ordinary numbers — true of $0, 1, 2, \dots$ and false of every infinite element?

There is not, and the reason is induction. Such a formula would hold of $0$, and whenever it held of $n$ it would hold of $n + 1$, since the successor of an ordinary number is ordinary. By the induction schema it would then hold of everything, including $c$. The standard part of a nonstandard model is not definable in it.

The contrapositive is a useful tool with a memorable name. If a formula holds of every ordinary number, it must also hold of some infinite one — the property overspills into the nonstandard part. Overspill is how facts about the infinite elements are actually proved: find a property that holds for arbitrarily large ordinary numbers, and conclude that it holds for some infinite number too, whose existence then has consequences back among the ordinary ones.

Some consequences are pleasantly strange. The sentence “for every $x$ there is a prime larger than $x$” is true of the ordinary numbers, so it is true in $M$, and applied to $c$ it gives an infinite prime — in fact primes in every galaxy far enough along. The factorial is definable by induction, so $c!$ exists in $M$, and since “$n$ divides $x!$ whenever $1 \le n \le x$” is a true sentence, $c!$ is divisible by $1$, by $2$, by $3$, by every ordinary number at once. A single element divisible by everything ordinary is impossible among the ordinary numbers and inevitable in $M$.

Why no figure can show one #

Every figure in this essay is computed: each element is a finite object, and addition, multiplication and comparison are procedures that finish. The polynomial structure is computable in exactly that sense, which is why it can be drawn — and it fails induction.

That is not an accident of the example. Stanley Tennenbaum proved in 1959 that no countable nonstandard model of Peano arithmetic has computable addition, or computable multiplication. The model compactness guarantees exists, but its operations cannot be carried out by any algorithm, on any coding of its elements as finite strings. The galaxy picture describes its order; its arithmetic can be proved to exist and never displayed.

So the situation is sharply divided. There are computable structures with infinite elements, like the polynomials, and they fail some instance of induction. There are structures satisfying all of arithmetic with infinite elements, and they cannot be computed. The only computable model of full arithmetic is the ordinary whole numbers themselves.

Two logics, and what each gives up #

The failure to pin down the whole numbers is specific to first-order logic, and it can be repaired — at a price.

Dedekind showed in 1888 that the induction axiom, stated once with a quantifier over all subsets rather than as a schema over formulas, determines the whole numbers completely: any structure satisfying it is a copy of $0, 1, 2, \dots$. There is no room for galaxies, because the set of ordinary numbers would be a subset containing 0 and closed under successor, and the axiom would force it to be everything. The schema could only speak about the subsets some formula defines, and the standard part is precisely a subset no formula defines — which is how galaxies slip through the schema and not through the axiom. One quantifier over all subsets, where the schema had one instance per formula, is the whole difference between a theory with nonstandard models and a theory without them. That axiom is second-order: it quantifies over sets, not just numbers.

The cost is proof. First-order logic has a complete proof system — every sentence true in all models is provable — and compactness is a consequence of that completeness. Second-order logic, with its full semantics, has no complete proof system at all, and no compactness. So there is a genuine choice: a logic weak enough to have a complete, checkable notion of proof cannot describe the whole numbers, and a logic strong enough to describe them cannot have one. The incompleteness theorem is the same trade-off seen from the side of proofs; nonstandard models are what it looks like from the side of structures.

Infinitely small, by the same argument #

The argument does not care that the structure is the whole numbers. Apply it to the real numbers — every true first-order sentence about $\mathbb R$ with $+$, $\times$, $<$ and names for every real, plus $0 < \varepsilon < 1/n$ for every whole number $n$ — and compactness produces a field that satisfies every such sentence and contains a positive element smaller than every positive real.

That element is an infinitesimal, and Abraham Robinson made this construction the foundation of nonstandard analysis in the 1960s. Leibniz’s infinitely small quantities, banished from calculus in the nineteenth century as incoherent, came back as elements of a structure no first-order sentence can distinguish from the real line. The slope at a single point can then be computed as an honest quotient of infinitesimals, with the standard part taken at the end, and every theorem proved that way is a theorem about the ordinary reals.

What the drawings cannot carry #

The polynomial structure is drawn because it can be, and it is not a model of arithmetic. Every picture of an element beyond the numerals in this essay is either that structure or a schematic of an order type; neither is the object compactness produces, and by Tennenbaum’s theorem nothing drawn by computation could be.

The galaxy diagram shows a handful of galaxies and a claim about all of them. The density — a galaxy between any two — is proved by the halving argument and illustrated by placing galaxies at a few dyadic positions; the fact that the full order is exactly that of the rationals needs Cantor’s theorem on countable dense orders, which no finite picture displays.

And the sampled checks of the semiring laws are checks on four hundred triples of polynomials of low degree. The laws hold for every polynomial by algebra, not by sampling, and the sample’s job is only to make the contrast with the parity statement’s failures concrete.

Still open: what bounded induction can prove about primes #

The polynomial structure fails induction altogether and full arithmetic has all of it. Between them lie theories with induction for some formulas and not others, and they are where some of the most stubborn questions about arithmetic live.

The theory $I\Delta_0$ allows induction only for formulas whose quantifiers are all bounded — “for all $y$ less than $x$”, never “for all $y$”. It is too weak to prove that exponentiation is always defined, and it is a natural formal model of reasoning that never uses very large numbers. Whether $I\Delta_0$ proves that there are infinitely many primes is not known. Euclid’s argument multiplies all the primes up to $n$ together, which produces a number far too large for the theory to be sure exists. Paris, Wilkie and Woods showed in 1988 that adding a mild axiom guaranteeing $x^{\log x}$ exists is enough, by replacing Euclid’s product with a counting argument in the style of Chebyshev’s bounds. Without that axiom the question is open, and it amounts to asking whether some nonstandard model of bounded induction has a largest prime.

An element nothing can rule out #

The compactness argument costs two sentences and delivers a structure that no first-order sentence can tell from the whole numbers, containing numbers larger than every numeral. Induction then shapes those numbers into galaxies ordered like the rationals, forbids any formula from separating them from the ordinary numbers, and — through Tennenbaum’s theorem — ensures their arithmetic can never be computed.

What it shows about the whole numbers is less about infinity than about description. A first-order theory can say that every number has a successor, that the operations obey their laws, that induction holds for every property it can express. It cannot say and there is nothing else, and a structure with something else satisfies it just as well.