History and Mythology of Set Theory

Source file content/history/set-theory/set-theory.tex

Source file content/history/set-theory/infinitesimals.tex

Infinitesimals and Differentiation

Newton and Leibniz discovered the calculus (independently) at the end of the 17th century. A particularly important application of the calculus was differentiation. Roughly speaking, differentiation aims to give a notion of the “rate of change”, or gradient, of a function at a point.

Here is a vivid way to illustrate the idea. Consider the function $f(x) = \nicefrac{x^2}{4} + \nicefrac{1}{2}$source, depicted in black below:

Suppose we want to find the gradient of the function at $c = \nicefrac{1}{2}$source. We start by drawing a triangle whose hypotenuse approximates the gradient at that point, perhaps the red triangle above. When $\beta$source is the base length of our triangle, its height is $f(\nicefrac{1}{2}+\beta) - f(\nicefrac{1}{2})$source, so that the gradient of the hypotenuse is:

So the gradient of our red triangle, with base length $3$source, is exactly $1$source. The hypotenuse of a smaller triangle, the blue triangle with base length $2$source, gives a better approximation; its gradient is $\nicefrac{3}{4}$source. A yet smaller triangle, the green triangle with base length $1$source, gives a yet better approximation; with gradient $\nicefrac{1}{2}$source.

Ever-smaller triangles give us ever-better approximations. So we might say something like this: the hypotenuse of a triangle with an infinitesimal base length gives us the gradient at $c = \nicefrac{1}{2}$source itself. In this way, we would obtain a formula for the (first) derivative of the function $f$source at the point $c$source:

And, roughly, this is what Newton and Leibniz said.

However, since they have said this, we must ask them: what is an infinitesimal? A serious dilemma arises. If $\beta = 0$source, then $f'$source is ill-defined, for it involves dividing by $0$source. But if $\beta > 0$source, then we just get an approximation to the gradient, and not the gradient itself.

This is not an anachronistic concern. Here is Berkeley, criticizing Newton's followers:

To defend the infinitesimal calculus against Berkeley, one might reply that the talk of “infinitesimals” is merely figurative. One might say that, so long as we take a really small triangle, we will get a good enough approximation to the tangent. Berkeley had a reply to this too: whilst that might be good enough for engineering, it undermines the status of mathematics, for

The italicised passage is a near-verbatim quote from Newton's own Quadrature of Curves (1704).

Berkeley's philosophical objections are deeply incisive. Nevertheless, the calculus was a massively successful enterprise, and mathematicians continued to use it without falling into error.

Source file content/history/set-theory/limits.tex

Rigorous Definition of Limits

These days, the standard solution to the foregoing problem is to get rid of the infinitesimals. Here is how.

We saw that, as $\beta$source gets smaller, we get better approximations of the gradient. Indeed, as $\beta$source gets arbitrarily close to $0$source, the value of $f'(c)$source “tends without limit” to the gradient we want. So, instead of considering what happens at $\beta = 0$source, we need only consider the trend of $f'(c)$source as $\beta$source approaches $0$source.

Put like this, the general challenge is to make sense of claims of this shape:

which we can write more compactly as follows:

In the 19th century, building upon earlier work by Cauchy, Weierstrass offered a perfectly rigorous definition of this expression. The idea is indeed that we can make $g(x)$source as close as we like to $\ell$source, by making $x$source suitably close to $c$source. More precisely, we stipulate that $\lim_{x \rightarrow c} g(x) = \ell$source will mean:

The vertical bars here indicate absolute magnitude. That is, $|x| = x$source when $x \geq 0$source, and $|x| =-x$source when $x < 0$source; you can depict that function as follows:

So the definition says roughly this: you can make your “error” less than $\epsilon$source (i.e., $|g(x) - \ell| < \epsilon$source) by choosing arguments which are no more than $\delta$source away from $c$source (i.e., $|x - c| < \delta$source).

Having defined the notion of a limit, we can use it to avoid infinitesimals altogether, stipulating that the gradient of $f$source at $c$source is given by:

It is important, though, to realise why our definition needs the caveat “where a limit exists”. To take a simple example, consider $f(x) = |x|$source, whose graph we just saw. Evidently, $f'(0)$source is ill-defined: if we approach $0$source “from the right”, the gradient is always $1$source; if we approach $0$source “from the left”, the gradient is always $-1$source; so the limit is undefined. As such, we might add that a function $f$source is differentiable at $x$source iff such a limit exists.

We have seen how to handle differentiation using the notion of a limit. We can use the same notion to define the idea of a continuous function. (Bolzano had, in effect, realised this by 1817.) The Cauchy--Weierstrass treatment of continuity is as follows. Roughly: a function $f$source is continuous (at a point) provided that, if you demand a certain amount of precision concerning the output of the function, you can guarantee this by insisting upon a certain amount of precision concerning the input of the function. More precisely: $f$source is continuous at $c$source provided that, as $x$source tends to zero, the difference between $f(c + x)$source and $f(c)$source itself tends to $0$source. Otherwise put: $f$source is continuous at $c$source iff $f(c) = \lim_{x \rightarrow c} f(x)$source.

To go any further would just lead us off into real analysis, when our subject matter is set theory. So now we should pause, and state the moral. During the 19th century, mathematicians learnt how to do without infinitesimals, by invoking a rigorously defined notion of a limit.

Source file content/history/set-theory/pathologies.tex

Pathologies

However, the definition of a limit turned out to allow for some rather “pathological” constructions.

Around the 1830s, Bolzano discovered a function which was continuous everywhere, but differentiable nowhere. (Unfortunately, Bolzano never published this; the idea was first encountered by mathematicians in 1872, thanks to Weierstrass's independent discovery of the same idea.)Footnote: The history is documented in extremely thorough footnotes to the Wikipedia article on the Weierstrass function (external resource; internet required). This was, to say the least, rather surprising. It is easy to find functions, such as $|x|$source, which are continuous everywhere but not differentiable at a particular point. But a function which is continuous everywhere but differentiable nowhere is a very different beast. Consider, for a moment, how you might try to draw such a function. To ensure it is continuous, you must be able to draw it without ever removing your pen from the page; but to ensure it is differentiable nowhere, you would have to abruptly change the direction of your pen, constantly.

Further “pathologies” followed. In January 5 1874, Cantor wrote a letter to Dedekind, posing the problem:

But, in 1877, Cantor proved that he had been wrong. In fact, a line and a square have exactly the same number of points. He wrote on 29 June 1877 to Dedekind “je le vois, mais je ne le crois pas”; that is, “I see it, but I don't believe it”. In the “received history” of mathematics, this is often taken to indicate just how literally incredible these new results were to the mathematicians of the time. (The correspondence is presented in Fernando Q. Gouvêa (2011), and we return to it in the section More Myth than History. Cantor's proof is outlined in the section Cantor on the Line and the Plane.)

Inspired by Cantor's result, Peano started to consider whether it might be possible to map a line smoothly onto a plane. This would be a curve which fills space. In 1890, Peano constructed just such a curve. This is truly counter-intuitive: Euclid had defined a line as “breadthless length” (Book I, Definition 2), but Peano had shown that, by curling up a line appropriately, its length can be turned into breadth. In 1891, Hilbert described a slightly more intuitive space-filling curve, together with some pictures illustrating it. The curve is constructed in sequence, and here are the first six stages of the construction:

In the limit---a notion which had, by now, received rigorous definition---the entire square is filled in solid red. And, in passing, Hilbert's curve is continuous everywhere but differentiable nowhere; intuitively because, in the infinite limit, the function abruptly changes direction at every moment. (We will outline Hilbert's construction in more detail in the appendix on Hilbert's space-filling curves.)

For better or worse, these “pathological” geometric constructions were treated as a reason to doubt appeals to geometric intuition. They became something approaching propaganda for a new way of doing mathematics, which would culminate in set theory. In the later myth-building of the subject, it was repeated, often, that these results were both perfectly rigorous and perfectly shocking. They therefore served a dual purpose: as a warning against relying upon geometric intuition, and as a demonstration of the fertility of new ways of thinking.

Source file content/history/set-theory/mythology.tex

More Myth than History?

Looking back on these events with more than a century of hindsight, we must be careful not to take these verdicts on trust. The results were certainly novel, exciting, and surprising. But how truly shocking were they? And did they really demonstrate that we should not rely on geometric intuition?

On the question of shock, Fernando Q. Gouvêa (2011) points out that Cantor's famous note to Dedekind, “je le vois, mais je ne le crois pas” is taken rather out of context. Here is more of that context (quoted from Fernando Q. Gouvêa):

Cantor knew his result was “so unexpected, so new”. But it is doubtful that he ever found his result unbelievable. As Fernando Q. Gouvêa points out, he was simply asking Dedekind to check the proof he had offered.

On the question of geometric intuition: Peano published his space-filling curve without including any diagrams. But when Hilbert published his curve, he explained his purpose: he would provide readers with a clear way to understand Peano's result, if they “help themselves to the following geometric intuition”; whereupon he included a series of diagrams just like those provided in the section Pathologies.

More generally: whilst diagrams have fallen rather out of fashion in published proofs, there is no getting round the fact that mathematicians frequently use diagrams when proving things. (Roughly put: good mathematicians know when they can rely upon geometric intuition.)

In short: don't believe the hype; or at least, don't just take it on trust. For more on this, you could read Marcus Giaquinto (2007).

Source file content/history/set-theory/cantor-plane.tex

Cantor on the Line and the Plane

Some of the circumstances surrounding the proof of Schröder-Bernstein tie in with the history we discussed in the section Pathologies. Recall that, in 1877, Cantor proved that there are exactly as many points on a square as on one of its sides. Here, we will present his (first attempted) proof.

Let $\unitline$source be the unit line, i.e., the set of points $[0,1]$source. Let $\unitsquare$source be the unit square, i.e., the set of points $\unitline \times \unitline$source. In these terms, Cantor proved that $\cardeq{\unitline}{\unitsquare}$source. He wrote a note to Dedekind, essentially containing the following argument.

Unfortunately, as Dedekind pointed out to Cantor, this does not answer the original question. Consider $0.\dot{1}\dot{0} = 0.1010101010\ldots$source. We need that $f(a,b) = 0.\dot{1}\dot{0}$source, where:

But $a = 0.\dot{1}\dot{1} = 1$source. So, when we say “write $a$source and $b$source in binary notation”, we have to choose which notation to use; and, since $f$source is to be a function, we can use only one of the two possible notations. But if, for example, we use the simple notation, and write $a$source as “$1.000\ldots$source”, then we have no pair $\tuple{a, b}$source such that $f(a, b) = 0.\dot{1}\dot{0}$source.

To summarise: Dedekind pointed out that, given the possibility of certain recurring decimal expansions, Cantor's function $f$source is an injection but not a surjection. So Cantor has shown only that $\cardle{\unitsquare}{\unitline}$source and not that $\cardeq{\unitsquare}{\unitline}$source.

Cantor wrote back to Dedekind almost immediately, essentially suggesting that the proof could be completed as follows:

But of course, Cantor could not complete the last line in these terms, for the Schröder-Bernstein Theorem was not yet proved. Indeed, although Cantor would subsequently formulate this as a general conjecture, it was not satisfactorily proved until 1897. (And so, later in 1877, Cantor offered a different proof of the theorem that the unit interval and unit square have equal cardinality, which did not go via Schröder--Bernstein.)

Source file content/history/set-theory/hilbert-curve.tex

Appendix: Hilbert's Space-filling Curves

In chapter the section Pathologies, we mentioned that Cantor's proof that a line and a square have exactly the same number of points (the theorem that the unit interval and unit square have equal cardinality) prompted Peano to ask whether there might be a space-filling curve. He obtained a positive answer in 1890. In this section, we explain (in a hand-wavy way) how to construct Hilbert's space-filling curve (with a tiny tweak).Footnote: For a more rigorous explanation, see Nicholas J Rose (2010). The tweak amounts to the inclusion of the red parts of the curves below. This makes it slightly easier to check that the curve is continuous.

We must define a function, $h$source, as the limit of a sequence of functions $h_1$source, $h_2$source, $h_3$source, dots We first describe the construction. Then we show it is space-filling. Then we show it is a curve.

We will take $h$source's range to be the unit square, $\unitsquare$source. Here is our first approximation to $h$source, i.e., $h_1$source:

To keep track of things, we have imposed a $2 \times 2$source grid on the square. We can think of the curve starting in the bottom left quarter, moving to the top left, then to the top right, then finally to the bottom right. Here is the second stage in the construction, i.e., $h_2$source:

The different colours will help explain how $h_2$source was constructed. We first place scaled-down copies of the non-red bit of $h_1$source into the bottom left, top left, top right, and bottom right of our square (drawn in black). We then connect these four figures (with green lines). Finally, we connect our figure to the boundary of the square (with red lines).

Now to $h_3$source. Just as $h_2$source was made from four connected, scaled-down copies of the non-red bit of $h_1$source, so $h_3$source is made up of four scaled-down copies of the non-red bit of $h_2$source (drawn in black), which are then joined together (with green lines) and finally connected to the boundary of the square (with red lines).

And now we see the general pattern for defining $h_{n+1}$source from $h_n$source. At last we define the curve $h$source itself by considering the point-by-point limit of these successive functions $h_1$source, $h_2$source, dots That is, for each $x \in \unitsquare$source:

We now show that this curve fills space. When we draw the curve $h_n$source, we impose a $2^n \times 2^n$source grid onto $\unitsquare$source. By Pythagoras's Theorem, the diagonal of each grid-location is of length:

and evidently $h_n$source passes through every grid-location. So each point in $\unitsquare$source is at most $2^{(\frac{1}{2}-n)}$source distance away from some point on $h_n$source. Now, $h$source is defined as the limit of the functions $h_1$source, $h_2$source, $h_3$source, dots So the maximum distance of any point from $h$source is given by:

That is: every point in $\unitsquare$source is $0$source distance from $h$source. In other words, every point of $\unitsquare$source lies on the curve. So $h$source fills space!

It remains to show that $h$source is, indeed, a curve. To show this, we must define the notion. The modern definition builds on one given by Jordan in 1887 (i.e., only a few years before the first space-filling curve was provided):

This is fairly intuitive: a curve is, intuitively, a “smooth” map which takes a canonical line onto the plane $\Real^2$source. Our function, $h$source, is indeed a map from $\unitline$source to $\Real^2$source. So, we just need to show that $h$source is continuous. We defined continuity in the section Rigorous Definition of Limits using $\epsilon$source/$\delta$source notation. In the vernacular, we want to establish the following: If you specify a point $p$source in $\unitsquare$source, together with any desired level of precision $\epsilon$source, we can find an open section of $\unitline$source such that, given any $x$source in that open section, $h(x)$source is within $\epsilon$source of $p$source.

So: assume that you have specified $p$source and $\epsilon$source. This is, in effect, to draw a circle with centre $p$source and radius $\epsilon$source on $\unitsquare$source. (The circle might spill off the edge of $\unitsquare$source, but that doesn't matter.) Now, recall that, when describing the function $h_n$source, we drew a $2^n \times 2^n$source grid upon $\unitsquare$source. It is obvious that, no matter how small $\epsilon$source is, there is some $n$source such that some individual grid-location of the $2^n \times 2^n$source grid on $\unitsquare$source lies wholly within the circle with centre $p$source and radius $\epsilon$source.

So, take that $n$source, and let $I$source be the largest open part of $\unitline$source which $h_n$source maps wholly into the relevant grid location. (It is clear that $(a,b)$source exists, since we already noted that $h_n$source passes through every grid-location in the $2^n\times 2^n$source grid.) It now suffices to show to show that, whenever $x \in I$source the point $h(x)$source lies in that same grid-location. And to do this, it suffices to show that $h_m(x)$source lies in that same grid location, for any $m > n$source. But this is obvious. If we consider what happens with $h_m$source for $m > n$source, we see that exactly the “same part” of the unit interval is mapped into the same grid-location; we just map it into that region in an increasingly stretched-out, wiggly fashion.