A countable field that passes for the line

Compactness adds elements: ask for a number beyond every numeral and a structure indistinguishable from the whole numbers supplies one. The other half of the story runs in the opposite direction, and it is stranger, because it takes elements away.

Start from a structure that is enormous — the real line, with uncountably many points — and ask whether a much smaller structure could satisfy exactly the same first-order sentences. The answer, for every structure in a countable language, is yes: there is always a countable one. That is the downward Löwenheim–Skolem theorem, proved by Leopold Löwenheim in 1915 and cleaned up by Thoralf Skolem in 1920, and its most famous consequence is a paradox about set theory that is not a contradiction but looks exactly like one.

A witness for every existential claim #

The construction is a closure argument, and its engine is the existential quantifier.

Suppose a structure satisfies a sentence of the form “there exists an $x$ such that …”. A substructure hoping to satisfy the same sentences must contain a witness — some $x$ that makes the claim true. More generally, for every formula with parameters already in the substructure, if the big structure has a witness, the substructure needs one too.

So build the substructure in stages. Start with the constants the language names. At each stage, for every formula and every choice of parameters from what is already there, add one witness from the big structure. There are countably many formulas, and at each stage countably many choices of parameters, so each stage adds countably many elements. After countably many stages, take the union.

The union is countable, as a countable union of countable sets. And it satisfies exactly the same first-order sentences as the big structure — it is an elementary substructure — by an induction on formulas whose only non-trivial step is the existential quantifier, which is precisely the step the witnesses were added for. The construction is called the Skolem hull of the starting set.

There is a question hidden in “add one witness”. When a formula has many witnesses in the big structure, which one goes in? In general the construction has to choose, for every formula and every choice of parameters, and making all those choices at once is an application of the axiom of choice — the functions that make them are called Skolem functions, and the full downward theorem for arbitrary structures is known to need a weak form of choice. For the real line nothing needs to be chosen. The witnesses the construction wants are roots of polynomials, and the roots of a polynomial come in a definite order along the line, so “the smallest root” or “the second root” names one without any arbitrariness at all.

The check that the result really is an elementary substructure has a name too, the Tarski–Vaught test: a subset of a structure is an elementary substructure exactly when every existential formula with parameters from the subset that has a witness in the big structure already has one in the subset. The whole construction is that test turned into a recipe. It never looks at universal statements, conjunctions or negations, because the test shows they take care of themselves once the existential ones are satisfied.

The figure’s version adds only witnesses for quadratic equations, which is enough to show the mechanism and not enough to finish. Run for every polynomial equation — and every first-order formula over $+$, $\times$ and $<$ reduces, over the reals, to statements about polynomial roots — and the hull of $\{0, 1\}$ is a very particular set.

The real algebraic numbers #

The real numbers that are roots of non-zero polynomials with whole-number coefficients are the real algebraic numbers. Listed by height — the size of a polynomial’s degree and coefficients — they form a countable set, since each height admits only finitely many polynomials and each polynomial only finitely many roots, and they lie densely in the line.

They form a field — sums, products and quotients of algebraic numbers are algebraic — and they are closed under the operations the Skolem hull needs: every positive algebraic number has an algebraic square root, and every polynomial of odd degree with algebraic coefficients has an algebraic real root. A field with those two properties is called real closed.

Alfred Tarski proved in the 1930s, and published in full in 1948, that any two real closed fields, one inside the other, satisfy exactly the same first-order sentences in the language of $+$, $\times$ and $<$. His method was to eliminate quantifiers: every formula in that language is equivalent to one with no quantifiers at all, a Boolean combination of polynomial inequalities, and a quantifier-free statement about elements of the small field has the same truth value in the large one. So the real algebraic numbers are an elementary substructure of the real line — a countable field that passes for the line in every first-order respect.

The table is seven sentences out of infinitely many, and Tarski’s theorem is what covers the rest. It also makes the theory of the real line decidable: quantifier elimination is an algorithm, so there is a procedure that takes any first-order sentence about real addition, multiplication and order and returns whether it is true. That is in exact contrast with the whole numbers, whose first-order theory is undecidable. Adding the requirement that numbers be whole makes arithmetic harder, not easier.

A decision procedure that robots use #

Tarski’s elimination was an existence proof in practice: the algorithm he described was so slow that nobody could run it on anything but toy problems. George Collins found a far better one in 1975, cylindrical algebraic decomposition, which cuts space into finitely many cells on each of which every polynomial in a problem has constant sign, and decides a sentence by checking one sample point in each cell. The sample points are real algebraic numbers, stored exactly — a polynomial together with an interval containing exactly one of its roots — which is how computer algebra systems represent the numbers in the second figure.

The method is still expensive, doubly exponential in the number of variables in the worst case, and that cost is known to be unavoidable in general. But it is exact, and it has a surprising practical home. Whether a robot arm can move from one position to another without hitting an obstacle is a question about whether two points lie in the same connected piece of a region defined by polynomial inequalities, and Schwartz and Sharir showed in 1983 that cylindrical decomposition answers it. A theorem proved to show that a countable field passes for the real line became, forty years later, a way of planning motion through the real world.

That is also a sharp illustration of what the countability buys. A computer cannot store an arbitrary real number, and it does not need to: every question it can ask about real polynomial arithmetic has the same answer in the countable field of algebraic numbers, each of which it can store exactly.

What the countable field is missing #

The real algebraic numbers and the real line agree on every first-order sentence and are nonetheless very different. The real line is complete; the algebraic numbers are full of holes.

The set of lower truncations is bounded above within the algebraic numbers — by 4, by 3.2, by every upper truncation — and it has no least upper bound there, because its least upper bound in the reals is $\pi$, and $\pi$ satisfies no polynomial equation with whole-number coefficients. The least-upper-bound property fails in the algebraic numbers and holds in the reals, and Tarski’s theorem says no first-order sentence can notice.

The resolution is that the least-upper-bound property is not first-order. It says every bounded set has a least upper bound, and “every set” quantifies over subsets of the structure, not over its elements. A first-order sentence can only quantify over elements, and the algebraic numbers have every property of the reals that can be stated that way. Completeness is the point at which the real line’s definition has to reach for sets — which is the same move that, applied to induction, was the only way to pin down the whole numbers.

Why the listing does not contradict the line #

The algebraic numbers can be listed. The real line cannot, by Cantor’s diagonal argument: any list of real numbers misses the number built to differ from the $k$-th entry in its $k$-th digit. Run on a list of all the algebraic numbers, the argument produces a real number on no row — a transcendental number, constructed.

So one structure is countable and the other is not, and they satisfy the same sentences. There is no contradiction, because “uncountable” is not expressible in the first-order language of fields. To say a set is uncountable is to say there is no function from the whole numbers onto it, and neither functions nor the whole numbers are elements of an ordered field. The two structures differ in size exactly as the whole numbers and a nonstandard model differ in having galaxies: in a property the language has no words for.

That seems safe as long as the language is too weak to talk about size. The paradox arrives when the same theorem is applied to a theory whose whole business is talking about size.

Skolem’s paradox #

Zermelo–Fraenkel set theory is a first-order theory in a countable language — one symbol, $\in$ — and if it is consistent it has a model. By the downward Löwenheim–Skolem theorem it then has a countable model $M$: a countable collection of objects with a membership relation, satisfying every axiom.

Set theory proves Cantor’s theorem, so $M$ satisfies “the set of real numbers is uncountable” — there is an object $r$ in $M$ that $M$ believes is the set of reals, and $M$ satisfies “no function from $\omega$ onto $r$ exists”. Yet $M$ is countable, so $r$ has only countably many members from outside, and there is a function from the whole numbers onto them.

Skolem pointed this out in 1922, and the resolution is that the function exists outside $M$ and not inside it. “Uncountable” in $M$ means “no function in $M$ maps $\omega$ onto $r$”. The model contains only countably many functions, and the enumeration that would expose $r$ as countable is not among them. Nothing is contradicted; the word uncountable simply means different things when evaluated inside and outside the model.

The miniature is honest about what is going on and about where the analogy stops. In it, two sets that are the same size look different inside a model because the model lacks the functions that would match them. Skolem’s paradox is that phenomenon for an infinite set and the whole numbers: the countable model lacks the enumeration. What the miniature cannot reproduce is the part that makes the paradox disturbing — that a model can satisfy all the axioms of set theory, which were written to capture size, and still be wrong about size in this way.

What set theory can and cannot fix #

It helps to remember why set theory is a first-order axiom system at all. Naive set theory, in which any describable collection is a set, collapses under Russell’s paradox, and the Zermelo–Fraenkel axioms were written to allow exactly the sets needed for mathematics and no more. Writing them as first-order sentences was a deliberate choice, made because first-order logic has a complete proof system in which proofs can be checked mechanically. Skolem’s paradox is the price of that choice, paid at the moment the axioms were written down: a first-order theory of sets inherits every model-theoretic property of first-order theories, including countable models.

Skolem drew a sceptical conclusion: set-theoretic notions like countability are relative, and first-order set theory cannot determine them absolutely. Most set theorists draw a narrower one. Within a single model, countability behaves exactly as it should; what the theorem shows is that no first-order axiom system can guarantee that its models get the sets they talk about “right” when viewed from outside.

The upward Löwenheim–Skolem theorem completes the picture from the other side. Any theory with an infinite model has models of every infinite cardinality — one the size of the reals, one larger than any set of reals, and so on. So first-order theories with infinite models never pin down the size of their models at all. The whole numbers have countable nonstandard models and uncountable ones; the real line’s theory has countable models, like the algebraic numbers, and gigantic ones containing infinitesimals. How large a set is turns out to be something set theory itself leaves open in some cases, and something no first-order theory can enforce on its models in any case.

What the drawn stages leave out #

The Skolem hull in the first figure adds witnesses only for quadratic equations and only inside a window, and after three stages it has 158 elements. The real hull adds witnesses for every formula, runs for infinitely many stages, and is the whole of the real algebraic numbers. The drawing shows how the construction grows and cannot show what it grows into. Its window also hides the growth: the stages outside $[-3, 3]$ are discarded, and without that cut every later stage would be far larger than the drawn ones, with most of its new elements far from the origin. A countable union can be enormous at every finite stage and still be countable; the picture shows the first property and has to take the second on trust.

The sentence table checks seven sentences. The claim that every first-order sentence has the same truth value in both fields is Tarski’s quantifier elimination, which is an algorithm with a proof and not a list of cases, and the table illustrates it rather than supports it.

And the supremum rows show rational truncations of $\pi$ approaching a point that is not algebraic. That $\pi$ is not algebraic is Lindemann’s theorem of 1882, a deep result that nothing in the figure demonstrates — the picture would look identical for $\sqrt 2$, which is algebraic, except that the algebraic numbers would then contain the least upper bound.

Still open: whether adding the exponential keeps the line decidable #

Tarski’s theorem decides every sentence about $+$, $\times$ and $<$ on the real line. Tarski asked in 1948 whether the same remains true when the exponential function $e^x$ is added to the language — whether there is an algorithm that decides every first-order sentence about real addition, multiplication, order and exponentiation.

Quantifier elimination fails once the exponential is present, so his method does not extend. In 1996 Angus Macintyre and Alex Wilkie proved that the theory is decidable, provided Schanuel’s conjecture is true — a conjecture about the algebraic independence of exponentials that would, among other things, imply that $e$ and $\pi$ are algebraically independent. Without it, the question Tarski asked remains open. The countable structure that would pass for the real line with its exponential is known to exist by Löwenheim and Skolem; whether its sentences can be decided depends on a conjecture about which numbers are related to which.

Too small to be the line, and indistinguishable from it #

The downward theorem is the mirror image of compactness. One adds infinite numbers that no sentence can object to; the other removes uncountably many points and leaves a structure no sentence can tell from the original. Between them they show that first-order sentences constrain structures only up to a kind of equivalence that ignores size altogether.

The real algebraic numbers are the concrete face of the downward theorem, and they are a satisfying one, because they are not an artificial construction. They are the numbers that polynomial equations produce, they are what exact computer algebra represents, and every first-order fact about the real line is already true of them. What they lack is only what the language could never have asked for: the completeness that fills the gaps, and the uncountably many transcendental numbers that live in those gaps.