The arithmetic that loses subtraction

For finite collections, counting supports arithmetic. Two collections of five and three have eight between them; removing the three leaves five; and every one of those statements can be run backwards. That reversibility is what makes counting useful rather than merely descriptive.

Almost none of it survives the move to infinite collections, and the way it fails is more interesting than the fact that it does. Addition and multiplication survive and become trivial. Subtraction and division do not survive at all.

What “the same size” is going to mean #

Two collections have the same size when their members can be paired off with nothing left over on either side. That is the only definition available once counting stops finishing, and it is Cantor’s rather than an arbitrary choice — it agrees with counting on finite collections and it is the only thing that does.

Everything below is a consequence of adopting it. None of the results is a discovery about infinity so much as a discovery about what that definition commits its user to, and the standing objection — surely there are more whole numbers than even ones — is an objection to the definition rather than to any theorem proved from it.

The smallest infinity is the size of the whole numbers. Call a collection countable when it has that size: when its members can be put in a single list, first, second, third, with every member appearing exactly once.

Adding one, and adding infinitely many #

One more makes no difference. Put the new member first and shift everybody along: the list still exists, so the sizes are equal. Adding any finite number is the same trick with a longer shift.

Two countable collections make one. Interleave the two lists — first of one, first of the other, second of one, second of the other. Every member of both appears exactly once, so the union is countable.

Countably many countable collections make one. This is the grid in the figure: put the $i$-th collection along row $i$ and walk the antidiagonals. Every cell is reached in finite time, so the union is a list.

The last of those has a hidden cost worth naming now rather than later. To walk the grid, each collection has to be given a listing, and choosing one listing out of each of infinitely many collections is an application of the axiom of choice. The first two do not need it; the third does, and the version of set theory without choice cannot prove it.

And multiplying, which is the same picture #

The grid says more than the union statement. It says the pairs $(m, n)$ of whole numbers can be listed, which is $\aleph_0 \times \aleph_0 = \aleph_0$ — the smallest infinity times itself is itself.

Repeating gives triples, quadruples, and every finite tuple. So the collection of all finite sequences of whole numbers is countable, and with it every collection whose members can be described by finitely many whole numbers: the fractions, the polynomials with whole-number coefficients, the finite strings over any finite alphabet.

That last is worth stating for its consequences. There are only countably many sentences, formulas, definitions, computer programs and proofs, in any notation whatever, because each is a finite string over a finite alphabet. Everything anybody will ever write down is on one list.

Counting the walk two ways #

The figure does not merely draw the walk; it counts what the walk keeps, and it counts it twice.

The cells on the antidiagonal $p + q = s$ are the pairs adding to $s$, and the ones in lowest terms are those with $\gcd(p, q) = 1$. Since $\gcd(p, s - p) = \gcd(p, s)$, the ones kept are exactly the numbers below $s$ that share no factor with $s$ — which is $\varphi(s)$, Euler’s totient.

So the number of fractions the walk has listed by the time it finishes antidiagonal $s$ is

$$\varphi(2) + \varphi(3) + \dots + \varphi(s),$$

and the figure computes that sum by trial division and compares it against the length of the list the walk actually produced. Two routes to one number, and the assertion is that they agree.

This is the site’s standing habit rather than decoration. A picture of a listing is easy to draw wrongly — a walk that misses a cell, or visits one twice, looks exactly like one that does not — and an independent count is the only thing that would notice.

Order and size are different questions #

There is a second arithmetic of infinity, it is not this one, and confusing the two is the commonest way to get a wrong answer about either.

Cardinal arithmetic counts, and it is what this essay is about. It sees only whether a pairing exists, so $1 + \aleph_0 = \aleph_0 + 1 = \aleph_0$.

Ordinal arithmetic counts in order, and it is what a sequence that explodes and still stops is about. It sees the arrangement as well as the members, so $1 + \omega = \omega$ — one thing placed before an infinite run is an infinite run — while $\omega + 1 \ne \omega$, because a run with something after it has a last member and a run does not.

So ordinal addition is not commutative and cardinal addition is. Both are correct, they answer different questions, and each is the wrong tool for the other’s. The reason the distinction is easy to lose is that they agree completely on the finite numbers, where an arrangement of $n$ things is determined by $n$ — and every intuition anybody has about counting was formed there.

The cardinal question is how many; the ordinal question is in what order. Absorption is a cardinal phenomenon; the failure of commutativity is an ordinal one. This essay is entirely about the first, and every result in it becomes false if read as a statement about the second.

Where the arithmetic breaks #

Everything so far has been a way of saying that the smallest infinity absorbs whatever is done to it. The price is now due.

Subtraction is not defined. The whole numbers minus the even ones leaves the odd ones, which is a countable collection. The whole numbers minus the numbers above ten leaves eleven of them, which is finite. The whole numbers minus the whole numbers leaves none. All three are $\aleph_0 - \aleph_0$, and they give three different answers, so the expression names nothing.

Division is not defined either, for the same reason and the same examples read multiplicatively.

Cancellation fails. From $\aleph_0 + 1 = \aleph_0 + 0$ it does not follow that $1 = 0$, which is false. An equation between infinite sizes cannot be cancelled, which means the ordinary manipulations of arithmetic — move a term across, divide both sides — are all unavailable.

“How many are left” is not a question. This is the practical form of the loss, and it is what makes infinite counting feel unlike counting. Removing members from an infinite collection does not determine how many remain; it depends on which were removed, and the size of what was removed does not decide it.

A working test for countability #

The results above assemble into something practical: a short list of moves that preserve countability, and a collection is countable as soon as it can be reached by them from the whole numbers.

A subset of a countable collection is countable. Run the list and keep what is wanted; the kept members are still in a list.

The image of a countable collection is countable. Apply a function to each member of the list and delete the repeats.

A finite product of countable collections is countable. The grid, iterated.

A countable union of countable collections is countable — with the choice caveat above.

Anything whose members are named by finite strings over a finite alphabet is countable, because those strings are.

That last one does nearly all the practical work, and it is worth applying once. The algebraic numbers — the roots of polynomials with whole-number coefficients — are countable, because each is named by a finite tuple of coefficients together with an index saying which root. So the numbers a polynomial can catch can be listed, and the next rung but one is about how thoroughly they fill the line while doing so.

What is not on the list of moves is the one that matters: the collection of all subsets of a countable collection. That operation leaves countability behind, and it is the diagonal argument that says so — the single place where the absorption stops.

The reason it is not a defect #

An arithmetic that loses two of its four operations sounds broken, and it is worth saying carefully why it is not.

What is left — addition and multiplication of sizes — is still well defined, still associative and commutative, and still agrees with ordinary arithmetic on the finite sizes. The operations that were lost were lost because the sizes stopped being a cancellative structure, and that is a fact about the collection of sizes rather than a failure of the definitions.

Compare a case with no infinity in it. In arithmetic modulo six, division by two is not defined, because $2 \times 0$ and $2 \times 3$ are both zero. Nobody calls modular arithmetic broken; the observation is that its multiplication is not cancellative and that the invertible elements are exactly the ones coprime to the modulus. The situation here is the same shape and the diagnosis is the same.

What is genuinely surprising is the absorption: the failure is not that some sums are ambiguous but that almost all of them collapse to one answer. $\aleph_0 + \aleph_0 = \aleph_0 \times \aleph_0 = \aleph_0$, and that flatness is what leaves subtraction with nothing to recover.

The hotel, and why the story is not the argument #

The standard illustration is a hotel with a room for every whole number, always full and always able to take another guest, or a coach of them, or infinitely many coaches.

It is a good story and it is worth being explicit that it is an illustration rather than a proof. What the hotel does is make the shifting vivid — everybody moves along one, everybody moves to twice their number, the coach passengers take the odd rooms — and the shifting is exactly the bijection. Anyone who follows the story has followed the argument.

Where the story misleads is in suggesting that time is involved. The guests do not move one after another; the bijection is a single function, given all at once, and there is no moment at which the hotel is inconsistent. A version told as a sequence of steps invites the objection but the last guest never arrives, and the objection is against the telling rather than against the mathematics.

What a listing is worth once it exists #

A countable collection is one that can be put in a list, and it is worth asking what that buys, because the answer is more than it looks and less than it is often taken to be.

It buys induction. A property that holds of the first member and passes from each member to the next holds of all of them. That is the whole of why listability matters in practice: an argument by stages reaches everything on a list and reaches nothing off one.

It buys a search that terminates when it succeeds. Anything on a list can be found by running the list, so a countable collection is one whose members can be enumerated — and a property that some member has will be discovered, eventually, by checking each in turn. It does not buy the converse: a property no member has is never discovered, because the search does not finish.

It does not buy an order that behaves. The listing of the fractions in the figure is in no sense increasing; the fractions in their own order have no first member above zero and no next member after any of them. A listing is a pairing with the whole numbers and nothing more, and it destroys whatever order the collection had.

That destruction is the point of the definition and it is also its cost. Cardinality was defined to see only whether a pairing exists, which is why it can compare collections with nothing in common — and why every question about how the members sit relative to one another has to be asked with different machinery.

The picture and its history #

The grid argument is Cantor’s, from 1873, and it is the first result of the subject. What is worth noticing about it is that the listing came before the impossibility.

Cantor’s letters to Dedekind that autumn work in the order the mathematics does: first the fractions can be listed, then finite tuples, then the algebraic numbers — each result more surprising than the last and all pointing the same way, toward the conclusion that infinity has one size and the notion is not interesting. Then in December the diagonal argument arrived and reversed everything.

The two months are the reason the subject was taken seriously. A theory that produced only absorption results would have been a set of curiosities about the hotel; a theory that produces absorption and a strict hierarchy above it is a theory of size. Every result on this page is the first half of that, and it reads correctly only with the second half in view.

What the picture cannot show #

The figure draws a finite corner of an infinite grid and the argument is about the whole of it. That the walk reaches every cell is a statement about all of them, and it is proved by observing that the cell $(p, q)$ is reached on antidiagonal $p + q$ — which is prose, and is the only part that matters.

It cannot show the absorption, either. A picture of a grid being walked shows a list being built; it does not show that the built list is the same length as one of its own rows, which is the actual content. Two infinite lists look alike, and looking alike is not the argument.

And the skipped cells are a feature of this listing of the fractions rather than of the fractions. A different walk keeps different cells, and there is a listing that never has to skip anything — the Stern–Brocot tree produces every fraction exactly once with no repeats to discard, which is a better construction and a worse illustration of the grid.

Where the ladder goes next #

Above this rung: whether the dimension of a collection affects its size, which it does not, and where the correspondence that shows so breaks down. Then the question of what a countable collection can look like — because countable does not mean sparse. And then the size above the first, and the gap between them that no proof closes.

One debt. The third absorption result — countably many countable collections make one — uses the axiom of choice and this essay names that in a sentence. The exact strength needed is the countable axiom of choice, which is strictly weaker than the full one, and the model in which it fails and the union is uncountable is worth drawing and is not drawn here.

What was traded #

The smallest infinity absorbs addition and multiplication, and the price is subtraction and division.

That is not a curiosity about infinity; it is what happens to any arithmetic whose operations stop being cancellative, and the same trade is made in modular arithmetic, in the arithmetic of ideals, and anywhere else a structure is collapsed on purpose. What makes this instance startling is how complete the absorption is: nearly every sum and product of infinite sizes gives back the larger of the two, and an arithmetic that flat has almost nothing left to invert.