Last night, Chase and I were talking about how we know there are infinitely many integers. It seems obvious enough. We can count as long as we like and, when we get tired of counting, somebody can add one to whatever number we reached. That is a perfectly good practical way to think about the integers, but mathematics asks for something a little more substantial. We want to know why there cannot be a last one.
I suggested a proof by contradiction. Suppose there are only finitely many integers. If there are exactly (n) of them, consider the sum
This is an integer, since it is a sum of integers. We also know that (n) must be at least two, because zero and one are distinct integers. Accordingly, the sum includes (n) and at least one positive integer in addition to it, so (S>n).
We need to be a little careful here. The number (n) is how many integers we supposed existed, not necessarily the largest integer. But the list (1,2,\ldots,n) already contains (n) distinct integers. Under our assumption, that list must therefore contain all the integers. The sum is an integer larger than anything in the list, giving us at least (n+1) distinct integers. We have contradicted the assumption that there were only (n).
We could use the familiar formula for triangular numbers,
although the formula does no real work in the proof. It is enough to observe that we have added positive integers to (n). And there is an even shorter version. If (m) is supposedly the largest integer, then (m+1) is also an integer, and it is larger than (m). This is a perfectly ordinary proof that there can be no largest integer.
The interesting part begins when we ask what these proofs have assumed.
The Problem with Induction
We could probably construct a proof involving mathematical induction, but that introduces a problem if our objective is to establish the foundations of arithmetic. Induction is a way of proving that a proposition holds for the natural numbers. It begins with a base case, ordinarily zero or one, and shows that if the proposition holds for one natural number, it also holds for its successor.
The natural numbers are already part of the machinery. Using induction to establish their existence would therefore require us to examine what we had assumed in setting up induction in the first place.
This does not make induction circular whenever we use it. Within an established system of arithmetic, the Peano axioms describe the natural numbers and include an induction principle. We can use those axioms to establish all sorts of other statements. The difficulty comes when we ask the axioms to justify the existence of the very mathematical objects they are describing, without admitting that the objects and rules have been assumed.
In fact, we do not need induction to establish that the natural numbers cannot form a finite collection. The successor operation is enough, provided it has the right properties.
Let (s(n)) denote the successor of (n), ordinarily written (n+1). The relevant Peano conditions say that every natural number has a natural-number successor, that different numbers have different successors, and that zero is not the successor of any number. If the natural numbers formed a finite set, the successor operation would map that finite set into itself, never produce zero, and never map two different numbers to the same result.
That is impossible. An injective function from a finite set to itself must also be surjective, which means every element must occur as an output. But zero cannot occur as an output. The contradiction comes from the properties of the successor operation, without requiring an inductive proof.
These properties are doing more work than it might initially appear. On a twelve-hour clock, adding one to twelve returns us to one. This gives us a finite system with an addition-like operation, but it does not satisfy the relevant Peano conditions. The sequence cycles back to a number we have already used. Ordinary natural-number arithmetic does not permit this.
So the infinite character of the natural numbers follows from the rules we have assigned to the successor operation. That is a mathematical result within the system. It is not yet an explanation of why we are entitled to assume the system exists.
Making Numbers from Nothing
In The Trouble with Zero, I discussed how the meaning of zero depends on what we are measuring. Zero Celsius is a useful physical reference, but it is not the absence of thermodynamic temperature. Here, zero has another job. We can use it as the starting object from which the natural numbers are constructed.
One standard method is the von Neumann construction of the natural numbers. We begin by representing zero as the empty set:
The empty set is not the absence of a mathematical object. It is a set containing no elements, and we can use it to construct another set. A set whose sole element is the empty set represents one:
For two, we have the set containing both zero and one:
And three is the set containing zero, one, and two. The general construction is
Here, ({n}) is the set containing (n) as its single element. We take all the elements already in (n) and add (n) itself. Consequently, each von Neumann natural number contains precisely the smaller natural numbers. A mathematical object constructed from the empty set turns out to have exactly the number of elements its name suggests.
This is a wonderful construction, partly because it gives us a concrete interpretation of the successor operation instead of treating addition as something handed to us ready-made. We can create zero, then one, then two, and continue constructing any particular finite number in this way.
But there is a distinction between being able to construct the next number and having constructed the set of all natural numbers. The rules we have used so far let us obtain each finite stage. They have not, by themselves, produced a single set containing every stage.
Where Zermelo Objects
This is the point at which Ernst Zermelo enters the picture. His work on the axiomatization of set theory addresses precisely the issue we have been approaching. Within that setting, there is a difference between showing that no finite collection exhausts the natural-number constructions and asserting the existence of an infinite set containing all of them.
The axiom of infinity supplies an existence claim. In the usual modern formulation, it says that there exists a set (I) containing the empty set and closed under the successor operation:
Strictly speaking, this is the modern formulation of the axiom, using von Neumann’s successor operation. Zermelo’s original 1908 formulation used a different operation, (x\mapsto{x}), which produces a different set-theoretic representation of the numbers. Both provide a way to assert the existence of an infinite collection. The distinction is discussed in Set Theory: An Open Introduction, and it is a nice reminder that a mathematical number need not have only one representation as a set.
This says more than that we can write down a rule for making the next number. It says there is an actual set in which zero and all the results of repeatedly applying the rule are present. From such a set we can then define the set of natural numbers, generally written (\omega), as the smallest set containing zero and closed under successor.
It is possible to work with finite constructions without assuming such a set exists. The important distinction is explained particularly clearly in notes on Zermelo set theory from Johns Hopkins: establishing the existence of arbitrarily many finite sets is not the same as establishing the existence of a set with infinitely many members.
The distinction is sometimes described as one between potential infinity and actual infinity. Potential infinity concerns a process that can always continue, while actual infinity treats an infinite collection as a completed mathematical object. These terms have a long philosophical history, and their meanings vary somewhat with context, but they capture the issue here. Our arithmetic argument rules out a final number. Zermelo’s axiom guarantees a set containing the entire natural-number sequence.
There is another subtlety in our first proof. When we say there are exactly (n) integers, we are already using finite numbers to count the supposed collection of numbers. That is an entirely reasonable assumption for an elementary proof within arithmetic. For a foundational inquiry into where number comes from, it is part of what we are trying to account for. The original proof is not wrong; it is answering a question within a framework that already permits finite counting and ordinary arithmetic.
The distinction matters because mathematical proofs are always conditional on something. We begin with definitions, axioms, and earlier results, then establish what follows. No proof starts with literally nothing, not even a proof about zero.
Back to the Integers
We started with integers, although the set-theoretic construction has given us natural numbers. This is easily addressed once the natural numbers are available.
Integers add negative numbers to the natural numbers, and we can construct them using pairs of natural numbers. Think of the ordered pair ((a,b)) as representing the difference (a-b). The pair ((3,1)) represents the same integer as ((5,3)), because both describe a difference of two. We formalize this by treating two pairs as equivalent whenever
This construction does not require us to have already defined subtraction for arbitrary natural numbers. It defines integers through equivalence classes of pairs, and arithmetic on those classes can then be established consistently. Once the natural numbers form an infinite set, the integers constructed from them are infinite as well.
We have come a considerable distance from adding up (1+2+\cdots+n). The sum established that our proposed finite list was inadequate. The successor axioms showed why the arithmetic structure cannot cycle or stop. The set-theoretic construction showed how zero and the successor operation can be represented using sets. Finally, the axiom of infinity supplied an existence principle for the complete collection.
These are related arguments, but they are not identical arguments. In particular, a proof that we can always obtain another number is not automatically a proof that every number belongs to some set we have already established exists.
I still like the original sum as an introduction. It gives a student something to manipulate and an immediate contradiction to understand. But the better lesson is what happens afterward, when we begin checking which assumptions made that proof possible.
Zermelo might object to the original explanation. He would also have a point. But if he’s so smart, how come he’s dead?