Infinite Sets — Read

Hilbert's Hotel

The set of the natural numbers is obviously infinite. So, if we do not want to help ourselves to the natural numbers, our first step must characterize an infinite set in terms that do not require mentioning the natural numbers themselves. Here is a nice approach, presented by Hilbert in a lecture from 1924. He asks us to imagine

[…] a hotel with a finite number of rooms. All of these rooms should be occupied by exactly one guest. If the guests now swap their rooms somehow, [but] so that each room still contains no more than one person, then no rooms will become free, and the hotel-owner cannot in this way create a new place for a newly arriving guest […]

Now we stipulate that the hotel shall have infinitely many numbered rooms $1$source 26, $2$source 26, $3$source 26, $4$source 26, $5$source 26, …, each of which is occupied by exactly one guest. As soon as a new guest comes along, the owner only needs to move each of the old guests into the room associated with the number one higher, and room $1$source 29 will be free for the newly-arriving guest.

Nine numbered guests are shown moving from room n to room n plus one, leaving room one empty; ellipses indicate the infinite continuation.

source 32

(published in David Hilbert 2013, 730; our translation)

The crucial point is that Hilbert's Hotel has infinitely many rooms; and we can take his explanation to define what it means to say this. Indeed, this was Dedekind's approach (presented here, of course, with massive anachronism; Dedekind's definition is from 1888):

Dedekind Algebras

We not only want natural numbers to be infinite; we want them to have certain (algebraic) properties: they need to behave well under addition, multiplication, and so forth.

Dedekind's idea was to take the idea of the successor function as basic, and then characterise the numbers as those with the following properties:

1. There is a number, $0$source 20, which is not the successor of any number i.e., $0\notin \mathrm{ran}\left(s\right)$source 21 i.e., $\forall xs\left(x\right)\ne 0$source 22

2. Distinct numbers have distinct successors i.e., $s$source 24 is an injection i.e., $\forall x\forall y\left(s\right(x)=s(y)\to x=y)$source 25

3. Every number is obtained from $0$source 27 by repeated applications of the successor function.

The first two conditions are easy to deal with using first-order logic (see above). But we cannot deal with condition three, repeated application of the successor function just using first-order logic. Dedekind's breakthrough was to reformulate condition three, repeated application of the successor function, set-theoretically, as follows:

1. 3 $\text{'}$source 34.

   The natural numbers are the smallest set that is closed under the successor function: that is, if we apply $s$source 36 to any element of the set, we obtain another element of the set.

But we shall need to spell this out slowly.

So ${\mathrm{clo}}_f\left(o\right)$source 48 is the intersection of all the $f$source 48-closed sets with $o$source 49 as an element. Intuitively, then, ${\mathrm{clo}}_f\left(o\right)$source 50 is the smallest $f$source 50-closed set with $o$source 50 as an element. This next result makes that intuitive thought precise;

Using this, we can say:

Since $A={\mathrm{clo}}_f\left(o\right)$source 91, our earlier result tells us that $A$source 92 is the smallest $f$source 92-closed set with $o$source 92 as an element. Clearly a Dedekind algebra is Dedekind infinite; just look at clauses placing o outside the range and requiring f to be injective of the definition. But the more exciting fact is that any Dedekind infinite set can be turned into a Dedekind algebra.

Dedekind Algebras and Arithmetical Induction

Crucially, now, a Dedekind algebra—indeed, any Dedekind algebra—will serve as a surrogate for the natural numbers. This is thanks to the following trivial consequence:

Since induction is characteristic of the natural numbers, the point is this. Given any Dedekind infinite set, we can form a Dedekind algebra, and use that algebra as our surrogate for the natural numbers.

Admittedly, the arithmetical induction theorem formulates induction in set-theoretic terms. But we can easily put the principle in terms which might be more familiar:

In this result, we spoke of a formula “having parameters”. What this means, roughly, is that for any objects $c_1,\dots ,c_k$source 52, we can work with $\phi (x,c_1,\dots ,c_k)$source 53. More precisely, we can state the result without mentioning “parameters” as follows. For any formula $\phi (x,v_1,\dots ,v_k)$source 55, whose free variables are all displayed, we have: $$\begin{array}{cc}\forall v_1\dots \forall v_k\left(\right(& \phi (o,v_1,\dots ,v_k)\wedge \\ & (\forall x\in N)\left(\phi \right(x,v_1,\dots ,v_k)\to \phi (s\left(x\right),v_1,\dots ,v_k\left)\right))\to \\ & (\forall x\in N)\phi (x,v_1,\dots ,v_k))\end{array}$$source 57 Evidently, speaking of “having parameters” can make things much easier to read. (In the Set Theory part, we will use this device rather frequently.)

Returning to Dedekind algebras: given any Dedekind algebra, we can also define the usual arithmetical functions of addition, multiplication and exponentiation. This is non-trivial, however, and it involves the technique of recursive definition. That is a technique which we shall introduce and justify much later, and in a much more general context. (Enthusiasts might want to revisit this after the Ordinal Arithmetic chapter, or perhaps read an alternative treatment, such as Michael Potter 2004, pp. 95–8.) But, where $N,s,o$source 73 comprise a Dedekind algebra, we will ultimately be able to stipulate the following: $$\begin{array}{cccccccccc}a+o& =a& & & a\times o& =o& & & a^o& =s\left(o\right)\\ a+s\left(b\right)& =s(a+b)& & & a\times s\left(b\right)& =(a\times b)+a& & & a^{s\left(b\right)}& =a^b\times a\end{array}$$source 76 and show that these behave as one would hope.

Dedekind's “Proof” of the Existence of an Infinite Set

In this chapter, we have offered a set-theoretic treatment of the natural numbers, in terms of Dedekind algebras. In the reflections section of Arithmetization, we reflected on the philosophical significance of the arithmetisation of analysis (among other things). Now we should reflect on the significance of what we have achieved here.

Throughout the Arithmetization chapter, we took the natural numbers as given, and used them to construct the integers, rationals, and reals, explicitly. In this chapter, we have not given an explicit construction of the natural numbers. We have just shown that, given any Dedekind infinite set, we can define a set which will behave just like we want $\mathbb{N}$source 26 to behave.

Obviously, then, we cannot claim to have answered a metaphysical question, such as which objects are the natural numbers. But that's a good thing. After all, in the reflections section of Arithmetization, we emphasized that we would be wrong to think of the definition of $\mathbb{R}$source 32 as the set of Dedekind cuts as a discovery, rather than a convenient stipulation. The crucial observation is that the Dedekind cuts exemplify the key mathematical properties of the real numbers. So too here: the crucial observation is that any Dedekind algebra exemplifies the key mathematical properties of the natural numbers. (Indeed, Dedekind pushed this point home by proving that all Dedekind algebras are isomorphic (1888, Theorems 132–3). It is no surprise, then, that many contemporary “structuralists” cite Dedekind as a forerunner.)

Moreover, we have shown how to embed the theory of the natural numbers into a naïve simple set theory, which itself still remains rather informal, but which doesn't (apparently) assume the natural numbers as given. So, we may be on the way to realising Dedekind's own ambitious project, which he explained thus:

In science nothing capable of proof ought to be believed without proof. Though this demand seems reasonable, I cannot regard it as having been met even in the most recent methods of laying the foundations of the simplest science; viz., that part of logic which deals with the theory of numbers. In speaking of arithmetic (algebra, analysis) as merely a part of logic I mean to imply that I consider the number-concept entirely independent of the notions or intuitions of space and time—that I rather consider it an immediate product of the pure laws of thought. (Richard Dedekind, 1888, preface)

Dedekind's bold idea is this. We have just shown how to build the natural numbers using (naïve) set theory alone. In the Arithmetization chapter, we saw how to construct the reals given the natural numbers and some set theory. So, perhaps, “arithmetic (algebra, analysis)” turn out to be “merely a part of logic” (in Dedekind's extended sense of the word “logic”).

That's the idea. But hold on for a moment. Our construction of a Dedekind algebra (our surrogate for the natural numbers) is conditional on the existence of a Dedekind infinite set. (Just look back to the theorem that a Dedekind-infinite set yields a Dedekind algebra.) Unless the existence of a Dedekind infinite set can be established via “logic” or “the pure laws of thought”, the project stalls.

So, can the existence of a Dedekind infinite set be established by “the pure laws of thought”? Here was Dedekind's effort:

My own realm of thoughts, i.e., the totality $S$source 76 of all things which can be objects of my thought, is infinite. For if $s$source 77 signifies an element of $S$source 78, then the thought $s\text{'}$source 78 that $s$source 78 can be an object of my thought, is itself an element of $S$source 79. If we regard this as an image $\phi \left(s\right)$source 80 of the element $s$source 80, then … $S$source 80 is [Dedekind] infinite, which was to be proved. (Richard Dedekind, 1888, §66)

This is quite an astonishing thing to find in the middle of a book which largely consists of highly rigorous mathematical proofs. Two remarks are worth making.

First: this “proof” scarcely has what we would now recognize as a “mathematical” character. It speaks of psychological objects (thoughts), and merely possible ones at that.

Second: at least as we have presented Dedekind algebras, this “proof” has a straightforward technical shortcoming. If Dedekind's argument is successful, it establishes only that there are infinitely many things (specifically, infinitely many thoughts). But Dedekind also needs to give us a reason to regard $S$source 96 as a single set, with infinitely many elements, rather than thinking of $S$source 97 as some things (in the plural).

The fact that Dedekind did not see a gap here might suggest that his use of the word “totality” does not precisely track our use of the word “set”.Indeed, we have other reasons to think it did not; see Michael Potter (2004), p. 23. But this would not be too surprising. The project we have pursued in the last two chapters—a “construction” of the naturals, and from them a “construction” of the integers, reals and rationals—has all been carried out naïvely. We have helped ourselves to this set, or that set, as and when we have needed them, without laying down many general principles concerning exactly which sets exist, and when. But we know that we need some general principles, for otherwise we will fall into Russell's Paradox.

The time has come for us to outgrow our naïvety.

Appendix: Proving Schröder-Bernstein

Before we depart from naïve set theory, we have one last naïve (but sophisticated!) proof to consider. This is a proof of Schröder-Bernstein (the Schröder-Bernstein theorem in Size of Sets): if $A\preccurlyeq B$source 12 and $B\preccurlyeq A$source 12 then $A\approx B$source 12; i.e., given injections $f:A\to B$source 13 and $g:B\to A$source 13 there is a bijection $h:A\to B$source 14.

In this chapter, we followed Dedekind's notion of closures. In fact, Dedekind provided a lovely proof of Schröder-Bernstein using this notion, and we will present it here. The proof closely follows Michael Potter (2004), pp. 157–8, if you want a slightly different but essentially similar treatment. A little googling will also convince you that this is a theorem—rather like the irrationality of $\sqrt{2}$source 22—for which many interesting and different proofs exist.

Using similar notation as the definition of closure generated from one element, let $${\mathrm{Clo}}_f\left(B\right)=\bigcap \{X:B\subseteq X\text{and}X\text{is}f\text{-closed}\}$$source 27 for each set $B$source 31 and function $f$source 31. Defined thus, ${\mathrm{Clo}}_f\left(B\right)$source 32 is the smallest $f$source 32-closed set containing $B$source 32, in that:

We need one last fact to get to Schröder-Bernstein:

Finally, here is the proof of the main result. Recall that given a function $h$source 86 and set $D$source 86, we define $h\left[D\right]=\{h\left(x\right):x\in D\}$source 86.