Countable, and everywhere

A listing is a very restrictive-sounding thing to have. Every member gets a place, the places run first, second, third, and there is no room for anything else — so a listable collection ought to be thin.

It is not, and the cleanest demonstration is a collection that is both listable and present in every interval however short: the numbers that are roots of polynomials with whole-number coefficients.

The listing, built rather than asserted #

That the algebraic numbers are countable is usually established in one sentence — each is named by a finite tuple of whole numbers, and those are countable — and the sentence is correct and hides the construction. Here is the construction.

Give a polynomial $a_d x^d + \dots + a_0$ the height $d + |a_d| + \dots + |a_0|$. Then:

• only finitely many polynomials have any given height, because the degree is bounded by the height and each coefficient is bounded by it too;
• a polynomial with a rational root has that root among the divisors of its constant term, so the low batches can be checked by hand;
• each polynomial of degree $d$ has at most $d$ real roots;
• so only finitely many numbers are roots of a polynomial of a given height.

Sweep the heights in order — $2$, then $3$, then $4$ — listing at each height the roots that have not already appeared. Every algebraic number appears, because it is a root of some whole-number polynomial and that polynomial has some height. The list is a listing.

The figure runs exactly that: it generates every integer polynomial of each height, finds its real roots by bisection on sign changes, and reports the batch. The counts under the drawing are the lengths of lists the figure built, not values looked up.

And it is in every interval #

Now the other half. Between any two real numbers, however close, there is a fraction — and every fraction $p/q$ is a root of $qx - p$, which is a whole-number polynomial. The Stern–Brocot tree produces all of them and is the cleanest evidence that they leave no gap. So the algebraic numbers are dense: every interval of the line, of any length, contains infinitely many of them.

That is the whole of the second half and it takes two lines. Its consequence is worth stating slowly:

A listable collection can be present in every interval. So being listable says nothing about being sparse, nothing about occupying little of the line, and nothing about there being gaps.

The picture makes it visible: the marks on the line thicken as the heights are swept, and every stretch of the axis fills. If the sweep were continued the marks would come arbitrarily close to every point drawn, and the whole of that is compatible with the collection being a list.

Two properties that keep being confused #

The result separates a pair of ideas that everyday language runs together, and the separation is the point of the essay.

Countable is about how many: the members can be paired with the whole numbers.

Dense is about where: every interval contains one.

Of measure zero is about how much: the members can be covered by intervals of total length as small as desired.

Nowhere dense is about how sparse: the closure has an empty interior.

The algebraic numbers are countable, dense, and of measure zero. The Cantor set is uncountable, nowhere dense, and of measure zero. The irrationals are uncountable, dense, and of full measure. Every combination that is not outright contradictory occurs, and no two of the four notions determine a third.

That the algebraic numbers have measure zero follows from countability directly, which is the one implication in the list that does hold: cover the $n$-th member by an interval of length $\varepsilon/2^n$ and the total is $\varepsilon$. So countable does imply measure zero — and implies nothing else on the list.

The third notion, which is neither of the first two #

Countability, density and measure are three questions and there is a fourth, of a different kind, that this collection also answers unexpectedly.

A set is meagre when it is a countable union of sets that are nowhere dense. Baire’s theorem says the line is not meagre, so a meagre set is small in a sense that has nothing to do with length: it is small in the sense of being a countable union of things with no interior.

The algebraic numbers are meagre — each single point is nowhere dense, and they are a countable union of points. So they are small by measure and small by category, and dense all the same.

That gives a fourth combination and a fourth independence. There are sets of full measure that are meagre, and sets of measure zero that are not meagre, and each of the two notions of smallness has cases the other misses. Nothing about a set’s size in one sense determines its size in another, which is the general form of what this rung is about.

Where the notions do agree is on the specific fact that started all of this: a countable set is small by every one of the four measures. Countable implies measure zero, implies meagre, implies not the whole line. What it does not imply is anything about where the members are, and density is entirely a question about where.

The consequence Cantor drew #

Put the listing beside the fact that the reals cannot be listed and something falls out immediately: there are real numbers that are roots of no whole-number polynomial.

That is the counting proof of the existence of transcendental numbers, from 1874, and it is thirty years later than Liouville’s construction and enormously stronger. Liouville exhibits one number and shows it is transcendental. Cantor shows that the transcendental numbers cannot be listed while the algebraic ones can, so the transcendentals are the overwhelming majority — and names none of them.

The strength and the weakness are the same feature. The argument sees only sizes, so it reaches a conclusion about all numbers at once and cannot say anything about any particular one. Whether $\pi$ is transcendental is not a question this argument can even approach; it was settled eight years later by machinery with no counting in it.

A number picked at random from an interval is transcendental with probability one, which is the measure-theoretic reading of the same fact, and is the sentence that makes clear how unusual the numbers anybody can name really are.

What the batches actually contain #

It is worth looking at the low heights by hand, because the enumeration’s first few stages are recognisable and the recognition is what makes the construction believable.

Height 2 allows degree one with the coefficients summing in size to one: $x$, giving $0$; and $\pm x \pm 1$ is height three, not two. So the first batch is a single number.

Height 3 allows $x \pm 1$ and $2x$ and $\pm 2x$: the roots are $\pm 1$ and $0$ again. New: $\pm 1$.

Height 4 brings $2x \pm 1$ and $x^2 - 1$ and their relatives, so $\pm 1/2$ and $\pm 2$ arrive.

Height 5 is where it becomes interesting: $x^2 - 2$ has height five, so $\pm\sqrt2$ appears — the first number in the enumeration that is not a fraction, and the one the bottom of the irrationality ladder is about.

Height 6 brings $x^2 - x - 1$, so the golden ratio arrives, along with $\pm\sqrt3$, $\pm 1/3$ and $\pm 3$.

The figure asserts that each of those landmarks is among the roots its enumeration found, rather than trusting that a search over polynomials will happen to produce the numbers everybody expects. That is the site’s standing check on a computed list: a listing that has silently lost a case looks exactly like one that has not, and naming the members it must contain is the only thing that would notice.

Two enumerations of the same collection #

The height sweep is one listing of the algebraic numbers and it is not the only one, and comparing two makes clear how little a listing determines.

By height, as above: sweep the polynomials in order of degree plus coefficient size, and take the new roots at each stage. The batches are natural and the arithmetic of the enumeration is the arithmetic of the numbers.

By the grid, as the rung below does it: a polynomial is a finite tuple of whole numbers, finite tuples of whole numbers can be listed by a zig-zag, and a root is a polynomial together with an index. The batches are meaningless and the construction is shorter.

Both are listings and they visit the numbers in wildly different orders. Nothing distinguishes them from the point of view of countability, which is exactly the point: countability is the existence of some pairing, and a collection with one pairing has infinitely many.

That is why the question which is the natural listing? has no answer, and why the height version was introduced above as a construction rather than as the definition. The height matters because it measures complexity, not because it enumerates; the enumeration would work just as well with a measure that meant nothing.

The listing is not an order #

There is a trap in the construction and it is worth naming, because it is where the intuition that listable means sparse actually comes from.

The list built above is not increasing. Height $2$ contributes $\pm 1$ and $0$; height $3$ contributes $\pm 2$ and $\pm 1/2$; the list jumps about the line rather than sweeping along it, and it must, because the algebraic numbers in their own order have no first member above zero and no next member after any of them.

So a listing imposes an order that has nothing to do with the line’s order, and every intuition about a list — that it starts somewhere, that it proceeds, that its members can be visited in turn along the axis — is an intuition about the wrong order.

A listing is a pairing, not a walk. The rung below makes the same point about the fractions, where the listing is a walk over a grid and the fractions come out in an order no reader would call natural. Here the disorder is more visible because the members are marked on the line and the sweep colours them by batch: the colours interleave completely.

Where the height ordering is genuinely useful #

The height is not only a device for proving countability. It is the standard way to do arithmetic with algebraic numbers, and it is worth saying so because it makes the construction less artificial than it looks.

Every algebraic number has a unique monic minimal polynomial with rational coefficients, and the height of that polynomial is a measure of the number’s complexity. Bounding the height bounds the number of candidates, which turns many questions into finite searches: whether a given number is a root of some polynomial of bounded degree and coefficient size is decidable by exhaustion, and the algorithms that identify a decimal as an algebraic number work exactly that way.

The same measure appears in Liouville’s theorem as the source of the constant. How well a fraction can approach an algebraic number depends on the polynomial’s coefficients, and the height is the natural way to bound them — so the enumeration used here for counting is the same quantity used there for approximation.

A device introduced to make a set countable turns out to be its natural complexity measure. That is not a coincidence: an enumeration by increasing complexity is what a listing of a structured set almost always is, and the useful part is the complexity rather than the listing.

What the picture cannot show #

The figure draws finitely many heights and the argument needs all of them. It cannot show density, which is a statement about every interval, and the visible thickening is suggestive rather than evidential — a collection could thicken in the drawn window and leave a gap outside it.

It cannot show the numbers that are missing, which is the whole conclusion. Between any two marks there are continuum-many transcendental numbers and the drawing has no way of indicating them; the picture of almost every number is a blank stretch of axis, and a blank stretch of axis looks exactly like an unpopulated one.

And the roots are found by bisection on sign changes, which finds real roots and misses complex ones. The algebraic numbers include roots that are not on the line at all, and the figure is a window on the real ones — a restriction it has to make and one that hides most of the collection.

Where the ladder goes next #

Above: the size beyond the continuum, and the question of what if anything sits between it and the countable. That is the last rung and it is the one where the answer turns out not to exist.

One debt. Every algebraic number here is real, and the complex ones are the majority — a degree-$d$ polynomial has $d$ roots in the plane and may have none on the line. The picture of the algebraic numbers as a countable dense subset of the plane, with the same height enumeration, is a better figure than this one and is not drawn.

What listability turned out not to mean #

A collection can be countable and still meet every interval, so being listable is not being sparse.

The confusion the result dispels is a real one and it comes from finite intuition: a finite set has gaps, and a list feels like a finite set that keeps going. It is not. A listing is a pairing with the whole numbers, it destroys the order the collection had, and the resulting arrangement can be spread through the line as thoroughly as anything is — while still being, from the point of view of counting, as small as an infinite collection can be.