Two lists that are one order

A countable field that passes for the line showed that the real line cannot be pinned down by first-order sentences: the real algebraic numbers satisfy every one of them and are countable. Two structures can agree on everything the language says and still be different sizes. That is the Löwenheim–Skolem theorem’s lesson, and it sounds like a failure of the language.

This essay is the other side of it: a case where the language does pin its structure down, completely, as long as the size is fixed. The structure is an ordering, and the sentences are the ones about which of two things comes first. Take any countable set arranged in a line so that between any two elements there is a third — dense — and with no first and no last element. The rationals are one such set. The fractions between nought and one whose denominator is a power of two are another. So are the numbers that solve a quadratic equation with small whole coefficients. Georg Cantor proved in 1895 that all of them are the same order: each can be matched with each other one element for element, so that every comparison is kept.

The figure below is the matching being built. The rationals between nought and one on top, the dyadic fractions below, and twelve lines joining matched pairs. No two lines cross, which is what keeping every comparison means. And every element of either list will be joined to something at some finite step.

A zigzag between two lists #

The construction needs only three ingredients: a list of each set, density, and the absence of ends.

List the rationals between nought and one by denominator — $\tfrac12, \tfrac13, \tfrac23, \tfrac14, \tfrac34, \tfrac15, \ldots$ — and the dyadic fractions by level — $\tfrac12, \tfrac14, \tfrac34, \tfrac18, \tfrac38, \ldots$. Start with nothing matched. At the first step, take the first unmatched rational and match it with the first dyadic fraction in the list that fits: at the start anything fits, so $\tfrac12$ goes to $\tfrac12$. At the second step, reverse the roles: take the first unmatched dyadic fraction, $\tfrac14$, and match it with the first rational that sits in the same position relative to everything matched so far — below the partner of $\tfrac12$ — which is $\tfrac13$. Then forth again, back again, alternating.

The only thing that could go wrong is that, at some step, the gap on the other side is empty — there is nothing between the partners of the two neighbours. Density rules that out between two matched elements, and the absence of ends rules it out below the smallest or above the largest. So every step succeeds, and every step keeps the matching order-preserving, which the figures check pair by pair after every step.

After infinitely many steps, every rational has been taken on some forth step and every dyadic fraction on some back step: each list’s $n$-th element is matched by the $2n$-th step at the latest. The union of all the finite matchings is a bijection that keeps order. The two orders are one order, relabelled.

Why the back steps are needed #

It is tempting to think the forth steps alone would do: keep taking rationals and placing them among the dyadic fractions, order preserved. They would produce a map that keeps order and is one-to-one. They would not, in general, produce one that reaches every dyadic fraction.

The map $x \mapsto x/2$ copies the rationals between nought and one into their own lower half, keeping every comparison, and never reaches anything above one half. A dense order has room to embed itself in any of its pieces, so an embedding proves nothing. What proves that two orders are the same is a map that is also onto, and the back steps are exactly the device that forces it: each element of the second list is taken, in turn, as the thing to be matched.

This is the order-theoretic cousin of two injections making a bijection. There, an injection each way was enough to prove two sets the same size, and the proof threaded the two maps together into one. Here the maps must also keep order, and threading two order-embeddings together does not work: the rationals in $[0, 1]$ and the rationals in $[0, 1)$ each embed in the other, keeping order, and they are not the same order, as the figure of the four kinds below shows. So the matching is built from scratch, alternating, with order kept at every stage.

The quadratic numbers, relabelled #

The same zigzag works between any two countable dense orders without ends, however different the elements look.

The countable field met earlier contained the square roots and the roots of quadratics, numbers most of which are irrational. As an order, the set of them between nought and one is still countable, still dense and still without ends, so it is the rationals. Among the three sets matched on this page, one contains only fractions with a power of two below, one all fractions, and one mostly irrational numbers. The language of order cannot tell them apart and — this is the new point — not because the language is weak, but because there is nothing to tell. They are isomorphic.

Contrast that field. There, the real algebraic numbers and the real line agreed on every first-order sentence about addition and multiplication, and they were not isomorphic — one countable, one not. Here the countable structures agree on every sentence because they are isomorphic. Agreement on sentences is called elementary equivalence; isomorphism is much stronger, and the zigzag is the tool that turns the first into the second.

Every countable order fits inside the rationals #

The forth steps alone, which could not prove two orders the same, prove something else that is just as striking: every countable linear order, dense or not, can be copied into the rationals keeping every comparison.

List the order’s elements and place them one at a time. Each new element lies above some of those already placed and below the others, so it belongs in a definite gap among their images in the rationals; the rationals are dense and have no ends, so that gap contains a rational, and the first one in some fixed list of the rationals will do. Nothing needs to be onto, so no back steps are needed, and the construction never gets stuck.

So the rationals contain a copy of every countable order there is. They contain the whole numbers, the integers, and the ordinal that sits one step in front of infinitely many — take $1 - 1/n$ for each $n$ and then $1$ itself. They contain orders far stranger than any of these: every countable ordinal, however long, and orders with no least element anywhere. The rationals are the countable order that is universal, containing every other, and homogeneous, looking the same around every point, and the zigzag shows it is the only countable order with both properties. The graph that coin tosses always make has the same pair of properties, universal and homogeneous, in a graph.

Any list of the rationals serves. The figures use denominators, but the Stern–Brocot tree, which produces every positive fraction exactly once by taking mediants, is another, and it has the advantage that its order of listing already respects the order of the numbers level by level. The zigzag does not care. It needs some list, and density, and nothing at the ends.

Countable, dense, and nowhere to hide #

It is worth saying why the rationals are such a natural example, since they are countable and yet everywhere: between any two real numbers there are infinitely many rationals, and yet the rationals can be listed. The zigzag needs exactly those two properties at once. Density supplies a partner in every gap; countability supplies a list, so that every element is eventually reached.

The real numbers have the first property and not the second. No list of them exists — the diagonal argument produces a number missing from any proposed list — and so the zigzag has no way to be sure every real is eventually taken. That is the whole of the difference between the countable case, where there is one dense order without ends, and the uncountable case, where there are more than can be counted. The failure is not in the density or the ends; it is in the list.

Only the ends can differ #

Drop the requirement that there be no ends, and the zigzag still works with one adjustment: match the ends first.

A countable dense order has a least element or not, and a greatest element or not: four possibilities. Two orders with the same answers can be matched — pair the ends, if there are any, then zigzag on what is left, which is dense with no ends. Two with different answers cannot, since a least element must go to a least element. So there are exactly four countable dense orders up to isomorphism.

That count has a consequence for sentences. Take the axioms of dense order without ends: a strict linear order, a third element between any two, nothing smallest, nothing largest. Every countable structure satisfying them is the rationals. Any sentence in the language of order is therefore either true in the rationals, and then true in every countable model of the axioms, or false in it, and then false in every one. By the downward Löwenheim–Skolem theorem, a sentence false in some model of the axioms is false in a countable one. So every sentence is either provable from the axioms or refutable from them: the theory is complete. This is the Łoś–Vaught test, found independently by Jerzy Łoś and Robert Vaught in 1954, and it turns a statement about isomorphism into a statement about proof.

A procedure that decides #

Completeness has a practical side. A complete theory with a list of axioms is decidable: to find out whether a sentence is true in the rationals, search simultaneously for a proof of it and a proof of its negation from the axioms; one of the searches will end.

For dense orders there is a much faster method, and it is visible in the zigzag. Every formula about order is equivalent to one with no quantifiers at all — a statement about which of the named elements are equal and which is smaller than which. “There is a $z$ between $x$ and $y$” is equivalent to “$x < y$”, because density supplies the $z$ whenever there is room. Eliminating quantifiers one at a time turns any sentence, which names no elements, into true or false. The same idea, with much more work, is how arithmetic with addition alone was decided and how Tarski decided the real field.

The connection with the game that decides what can be said is direct. The zigzag is a strategy in an Ehrenfeucht–Fraïssé game of infinitely many rounds: the challenger picks an element on either side, the defender answers on the other, and the defender wins if the answers always keep order. On two countable dense orders without ends the defender never loses, and a defender who never loses in a game of every finite length is exactly what makes two structures agree on every sentence; one who never loses in the infinite game on countable structures makes them isomorphic.

Where the zigzag stops: uncountable orders #

The argument used a list of each set. An uncountable set has no list, and the conclusion fails.

The real line and the real line with nought removed are both dense, both without ends, both of the size of the continuum. No order-preserving matching joins them. In the first, the set of negative numbers has a least upper bound; in the second it does not, because the number that would be it has been removed. A matching that kept order would carry the bound across and produce one where there is none.

So the axioms of dense order pin down the countable model and not the uncountable ones: there are many dense orders without ends of the size of the continuum, differing in where their gaps are and how many there are. A theory with exactly one model of a given infinite size is called categorical in that size — the opposite of the situation in two worlds that both obey the rules, where a theory’s two different models proved a statement independent of it — and dense order is categorical in the countable size and in no other. Michael Morley proved in 1965 that for a theory in a countable language, categoricity in one uncountable size forces categoricity in all of them — so theories fall into a small number of patterns, and dense order is the standard example of the pattern “countable only”.

What a finite zigzag cannot show #

Every figure matches finitely many elements, and the claim is about all of them. The finite matchings are checked for order at every step, which verifies the construction; that the union is onto is the argument about each list’s $n$-th element being taken by the $2n$-th step, which no finite drawing can show.

The figures also use particular lists — rationals by denominator, dyadic fractions by level, quadratic roots by height — and different lists give different matchings. There are uncountably many isomorphisms between any two of these orders, and the zigzag produces the one determined by the lists and by the rule “first element that fits”. Nothing about the order singles it out.

The zigzag is also more than an existence proof, and that is worth noticing because most arguments about infinite structures are not. Each step is a finite search through a list for the first element in a gap, so if the two lists can be computed, so can the matching: given any rational, a program can find its dyadic partner in finitely many steps. Orders with this property — any two computable copies joined by a computable matching — are called computably categorical, and dense order is the standard example. Many isomorphic structures are not: there are computable copies of the same graph, or the same linear order with ends, between which every isomorphism is uncomputable.

And the gap figure shows one uncountable pair that differ. The theorem that there are, in fact, $2^{\mathfrak c}$ different dense orders without ends of the size of the continuum is a counting argument about gaps, and the figure illustrates only the simplest difference a gap can make.

Still open: how many countable models a theory can have #

Dense order without ends has one countable model. A complete theory in a countable language can have more — the theory of the integers with the successor function has countably many countable models, one for each number of copies of the integers laid side by side, and richer theories have as many as there are real numbers — and Vaught proved in 1961 that it can never have exactly two.

Vaught’s conjecture says the number of countable models of a complete theory in a countable language is either countable or exactly the size of the continuum — never strictly in between, a possibility that set theory without the continuum hypothesis leaves open. It has been proved for many classes of theories, including all theories of orders with extra unary predicates and all theories of trees, and Morley showed the number is at most $\aleph_1$ or exactly $2^{\aleph_0}$. The general case has been open since 1961, and a claimed counterexample announced in 2016 has not been accepted. The zigzag is where every count of countable models starts: two countable models are the same exactly when some back-and-forth system joins them, and counting models is counting the ways such systems can fail.