▶︎ 0:00 Hi. I'm Joel David Hamkins, and I'd like to tell you about Galileo's Paradox and also the notion of equinumerosity. What does it mean to say that two sets, perhaps infinite sets, have the same size? And along the way, we'll discover some tension between some ideas about equinumerosity and Euclid's principle, which is the principle that the whole is greater than any proper part.
▶︎ 0:24 Let me begin with a story about young Gottlob Frege, when he was having a dinner party at his household and he happened to walk past the dining room which was laid out for the guests. And he could tell at a glance that the number of plates on the table was the same as the number of knives, that he wasn't counting them, but he knew that those two numbers were the same.
▶︎ 0:48 And how could he know that? Well, of course, it's simple, because he just observed that at every place setting there was one plate and one knife, and so we can make a kind of one-to-one correspondence between the plates and the knives, and thereby come to know that those two sets have the same size even if we didn't count them.
▶︎ 1:07 And so this is the principle underlying the definition of equinumerosity. Let me draw a picture here. We say that two sets, say, here's a set A, is equinumerous with a set B, and we write it with this symbol, if there's a one-to-one correspondence between the elements of A and the elements of B. So a kind of matching up of elements of A with elements of B, in such a way that every individual in A has a partner in B and vice versa, and it's never the case that two different individuals get matched to the same one. That's what it means to have a one-to-one correspondence between two sets. We say that A and B are equinumerous if there's a one-to-one correspondence between them in this kind of manner.
▶︎ 1:54 Frege had observed that the plates were equinumerous with the knives. But when I give a lecture, for example, and I look out at the lecture hall, I might be able to observe that the number of people in the classroom is the same as the number of noses in the classroom, simply because every person has a nose, and every nose is attached to a person, and nobody has some extra nose in their pocket or something. And so, even without counting the students in the classroom, I might come to know that the number of people is the same as the number of noses in the classroom.
▶︎ 2:29 And this brings us to this principle that I call the Cantor-Hume Principle, also known just by Hume's Principle, which says that we want to say that two sets have the same number of elements if, and only if, they can be put into one-to-one correspondence, if and only if they are equinumerous. So it justifies the terminology of equinumerosity. The Cantor-Hume Principle, to say it again, the Cantor-Hume Principle says two sets have the same number of elements if, and only if, there's a one-to-one correspondence between those sets.
▶︎ 3:05 It's named after Hume because Hume wrote about it in 1739. There's a sentence, "When two numbers are so combined as that one has always a unit answering to every unit of the other, we pronounce them equal." And Frege mentioned this sentence in his work at the end of the 19th century, and it came to be known as Hume's Principle in a lot of the philosophical literature. However, I prefer to call it the Cantor-Hume Principle in light of Cantor's work with the same idea.
▶︎ 3:39 It's really absolutely core and central to Cantor's thinking, particularly in the infinite case. Frege was working with Hume's Principle primarily in the finite case, and used it to found his theory of arithmetic, whereas Cantor did his spectacular work with equinumerosity in the infinite and even the uncountable case that we'll come to in some future lectures.
▶︎ 4:03 The concept of equinumerosity also figures in Galileo's work, particularly in his dialogues between Salviati and Simplicio in the Dialogue Concerning Two New Sciences in 1638. But actually, I want to go much further back and talk about the paradox of Aristotle's wheel before we get to this later work.
▶︎ 4:24 Let me tell you about Aristotle's wheel. Let's draw it here. There's the wheel. It has a center, and it has an axel, and it has a certain radius and circumference. And what we're going to do with Aristotle's wheel is we're going to kick it. I'm going to kick it and set it rolling on the ground. Here's the bottom point, and it rolls exactly one revolution around. So the whole thing rolled, and it comes to rest again on the other side here. And here's the axel.
▶︎ 5:06 So if the wheel was really rolling, then, here, let me label these points. The center is at A, and I'm going to call this point B, and the bottom point C. And after it has rolled exactly one revolution, we have a point here, D, E, and F. So now, it's easy to see that as the wheel turns, the circumference of the circle is laid off on this segment from C to F, and therefore the length of CF, that segment, should be the same as the circumference of the circle.
▶︎ 5:43 But now Aristotle looked at the situation and said, "Well, let's imagine also the path of the axel, the inner circle, the smaller circle." As the wheel turns, that circle also is rolling along, and it follows a path from B to E. And as the wheel turns, the angle of the wheel is laying out this inner circle exactly on this segment from B to E.
▶︎ 6:12 And now the paradox is that the inner circle seems to have a smaller circumference than the outer circle, and yet it is also laid off in exactly a one-to-one manner on this segment BE, but yet BE has the same length as CF. So the paradox is that the smaller inner circle here seems to be equinumerous with the segment BE. It has the same size as BE because as the wheel turns, the smaller circle is laid off on that segment. And the same for the larger segment. It's equinumerous. The points on the larger circle are laid off on the segment CF. So it seems that the inner circle should have the same size as the outer circle because they both have the same size as the corresponding segments, which have the same length. And that's a bit confusing to think about if we have this idea of Hume's principle, which of course came much later.
▶︎ 7:13 Now, one possible explanation of Aristotle's wheel is that, of course, if we kick the wheel and it's rolling on the bottom segment, then it's actually not rolling on this middle shelf segment. If we imagine two shelves and we sprinkled some dust on there, then if it was rolling on the bottom in such a way that it wasn't ever scraping, then actually this inner circle would have to be carried along a bit faster, and it would be slightly scraping this middle segment here. Or similarly, if the strong support was on this shelf here and we were rolling it here, of course it would complete one revolution in a much shorter time, and the big wheel would be spinning relatively faster and have to scrape against the bottom. But both of those things don't prevent there from being a one-to-one correspondence. There still is a one-to-one correspondence between this smaller wheel and this segment here, and so it is paradoxical from the point of view of the Cantor Hume principle.
▶︎ 8:16 Let me now turn to Galileo's analysis of the paradox of Aristotle's wheel. And what Galileo did was he changed the setup slightly. Galileo said, "Well, let's not imagine a circular wheel, but rather a hexagonal wheel." So he drew this hexagon. Let's see if I can draw it properly here. There's the hexagon. This is Galileo's wheel, and it has an axle, which is also a hexagon. And we're going to roll Galileo's wheel.
▶︎ 8:58 Of course, it doesn't really roll smoothly. If I kick it, then you can see what's going to happen is it's going to be tipped up slightly on this point and go ker-thump and fall onto the next segment. And then I do it again, and again, and again until every segment, all six sides have had a chance to fall, and then it will end up in some position like this. So this is the final state after we have turned it so that every segment gets a chance to rest on this edge.
▶︎ 9:29 So now the point is that, let's think about what happens with the inner axle, the hexagonal inner axle, as this turning happens. You can see that when we kick it and it goes ker-thump and this segment falls down like this, so the hexagon is sitting with its base right here, the inner hexagon is lifted slightly and then comes to rest again. And so actually this segment doesn't just fall flat right here, but rather it's lifted along with the whole hexagon, and it comes to rest right here. So this part here is, if you can see, then it falls exactly right here. And then on the next turn, what happens is, let's see. No, I want to go like this. So this segment is, oh, my picture's a mess here. The point is that every time you turn it, this next segment is lifted up and then comes to rest as the hexagon comes to rest again.
▶︎ 10:32 And so the point that Galileo emphasized is that there's these gaps between the segments as they land, yes? And so the total length of the segments as they arise from having fallen here, and then there's the final one here. The total length of the resting places will in fact be the circumference of this inner hexagon, and it will be less than the total length of the bottom segment, which doesn't have any gaps. Now, precisely because each of these segments is corresponding to one of these segments and there's these gaps in between that completely explain the lesser density of the correspondence of the inner axle with the segment that connects the two copies before and after.
▶︎ 11:22 And then Galileo imagined, "Well, suppose we don't use just six sides, but maybe we use 20 sides or 40 sides or 100 sides," and so on. As you increase the number of sides in the polygon, of course these gaps get smaller and smaller and the kerplunk part is much less emphasized. It's not raised up quite as much, and it becomes much more like a circular action. And you can see in the limit it turns into Aristotle's wheel, and yet the manner in which the inner figure, the axle is laid out on that segment is somehow less dense because for all the polygons, there are all these missing segments, which somehow, in the infinite case of the actual circle, disappear. So this is the paradox of Aristotle's wheel, and its answer by Galileo.
▶︎ 12:22 Let me now move to Bolzano's observations about equinumerosity of these sort of geometric figures. This is in Paradoxes of the Infinite, 1851. And what Bolzano observed is the following. Bolzano observed that, look, if you have a circular arc, a piece of a circle, and another circular arc, these two circular arcs, of course this one is larger. From a larger circle, it seems like it has a greater length.
▶︎ 13:01 And yet, we can make a one-to-one correspondence between these points because for any point on here, I can find a corresponding point out there by drawing the ray. Let me do it in red here. I can draw this correspondence here, and if I have another one here, every point on the inner circular arc is corresponding to one and only one point on the outer circular arc. If the arcs are similar so that the angle of each of them is the same, then that provides a one-to-one correspondence between the points on the smaller arc and the points on the larger arc. Even though those arcs have different sizes, there's a one-to-one correspondence between them, and maybe that's evidence against the counter-Hume principle.
▶︎ 13:45 Another example that he talked about is just having two circles, any two circles. If I lay them down concentrically, then of course I have a one-to-one correspondence between points on the smaller circle and points on the larger circle. Given any point on one, I can find the corresponding point on the other at the same angle.
▶︎ 14:06 Galileo observed a similar thing about line segments. This was about circles, but we can do a similar thing with line segments. He said, suppose you have a short line segment and you have a longer line segment. Well, I can imagine a foliation of lines between them, a fanning out of lines, that specifies a correspondence. So every point up here, the point that's halfway on the smaller segment will correspond to the point that's halfway on the larger segment. The point that's 10% of the way on the smaller segment will correspond to the point that's 10% of the way on the larger segment, and so on.
▶︎ 14:52 Every point up here gets mapped to a point down here in a one-to-one way, and so we have a one-to-one correspondence between this segment and this longer segment. And maybe that's confusing if you think that two sets that are equinumerous should have the same size. So, what it tells us maybe is that the length of a segment is not quite the same thing as the size of the segment, if we think of that segment as consisting of individual points.
▶︎ 15:20 We might want to say, "Well, look, these two segments have different lengths, but the number of points that they have is the same because of the one-to-one correspondence." If we wanted to hold on to the counter-Hume principle, that's what we would have to say.
▶︎ 15:35 Galileo gives another example. This is two finite segments, but he gives another argument where if you have a finite line segment, an open line segment, then we can actually build a correspondence with the infinite line. I've only drawn part of the infinite line here, but I really mean the infinite one, the actually infinite one. And I'm going to make a correspondence between this segment and this entire line, and the way that I'm going to do it is I'm going to draw in here first a semicircle, half a circle. And it has a center here.
▶︎ 16:06 Now, given any point on the segment up here, what I do is I first drop it down to the semicircle here, let's draw that point in blue, and then what I do is I project it out from the center of that circle onto the line. So, I take a green point on the segment, drop it to the point on the semicircle and then project that point out. So, if my original green point is very near the edge, then when it gets dropped down, it's going to be more extreme. Let's see. I'll get a blue point here, and then I project it out, and it's going to go quite far out here, to the red point.
▶︎ 16:56 So, the point is that every point on the line can be projected back to some point on the semicircle, because the collection of points that I get by projecting from the center of this semicircle will completely fill the line. So, this gives me a one-to-one correspondence between this segment and this entire line. Given any point on the segment, I get a point on the line, and given any point on the line, I can reverse it and find out where I came from on the line segment. So, a finite segment is equinumerous with the infinite line.
▶︎ 17:32 There's another example of this kind of paradoxical situation with equinumerosity, and this is called Galileo's Paradox, so let's get into that now. Galileo considered the natural numbers. I prefer to start with zero, so let's start with zero. Zero, one, two, three, and so on. These are the natural numbers. Some of those numbers are squares. For example, zero is zero squared and one is one squared, two squared is four and three squared is nine and so on. Four squared is 16 and so on. And if you notice, the squares, the perfect squares get farther and farther apart.
▶︎ 18:11 So, if I make a picture here, let's do it. We have the natural numbers zero, one, two, three, four, five, six, seven, and so on. And I can maybe circle the squares. So here's a square. Zero, zero squared. One is a square. Four is a square. Oh, I didn't go high enough here. So let's just draw a few more numbers here so I can get one more square. Eight, nine, and so on. So nine is a square.
▶︎ 18:45 So, it seems like there's more numbers than squares, because there's all the other numbers in between the squares, and furthermore the density of the squares gets less and less as you take higher and higher numbers. So it seems reasonable, maybe, to say that the number of numbers is strictly greater than the number of squares because there's all the numbers in between. This would be appealing to what's called Euclid's principle. Euclid's principle, the whole is greater than any proper part, strictly greater. So the whole of the numbers, according to Euclid's principle, the whole of the natural numbers is greater than the proper part consisting of the perfect squares.
▶︎ 19:27 And yet, Galileo observed, nevertheless, we can make a one-to-one correspondence between the numbers and the squares because zero squared is zero and one squared is one. Two squared is four. Three squared is nine, 16, 25, 36, and so on. So I can associate the numbers with the squares, and every square with its root. And therefore, by the Cantor-Hume principle, the number of numbers should be exactly the same as the number of perfect squares.
▶︎ 20:00 So this identifies a tension between the Cantor-Hume principle, which says that if two sets have a one-to-one correspondence then they have the same number of elements, and Euclid's principle on the other hand, which says that the whole is greater than any proper part. You can't really have both of those principles when you have this kind of situation, because we have the whole of the numbers is equinumerous with the proper part of itself. So are they the same size or not? That's what's at stake with Galileo's paradox. So, I want to read you what Galileo wrote in his lovely dialogue.
▶︎ 20:40 Of course, the dialogues are between these two characters, Salviati and Simplicio. And Salviati, of course, is the clever one, and you have the idea when you're reading these lovely dialogues that it's really Salviati. It's really Galileo talking, telling you. And Simplicio is the foil.
▶︎ 20:58 But what Salviati says in the dialogue about this situation is the following: "But if I inquire how many roots there are, it cannot be denied that there are as many as there are numbers, because every number is a root of some square. This being granted, we must say that there are as many squares as there are numbers, because they are just as numerous as their roots, and all the numbers are roots. Yet at the outset, we said there are many more numbers than squares, since the larger portion of them are not squares." All the numbers in between, right?
▶︎ 21:28 "Not only so, but the proportionate number of squares diminishes as we pass to larger numbers. Up to 100 we have only 10 squares. That is, the squares constitute one-tenth of the part of the numbers up to 100. But up to 10,000 we find only one one-hundredths part to be squares, and up to a million, only one one-thousandths part. On the other hand, in an infinite number, if one could conceive of such a thing, he would be forced to admit that there are as many squares as there are numbers taken all together."
▶︎ 22:00 And so you can see that Galileo, or Salviati, is committed to what we call the Cantor-Hume principle now. This is earlier than Hume. I mean earlier than Cantor, of course.
▶︎ 22:10 "So far as I can see," he continues, "we can only infer that the totality of all numbers is infinite, that the number of squares is infinite, and that the number of their roots is infinite. Neither is the number of squares less than the totality of all the numbers, nor the latter greater than the former. And finally, the attributes equal, greater, and less are not applicable to infinite, but only to finite quantities. When, therefore, Simplicio introduces several lines of different lengths and asks me how is it possible that the longer ones do not contain more points than the shorter, I answer him that one line does not contain more or less or just as many points as another, but that each line contains an infinite number."
▶︎ 22:51 So that's 1638 Galileo. He's throwing up his hands at the paradox. He doesn't have an answer. He's saying we cannot say that there are comparisons between infinite quantities precisely because we seem to be forced into this situation of saying both that the number of squares is the same as the number of numbers, but also that the number of squares is strictly less than the number of numbers. And so he finds it intolerable and refuses then to make such comparative judgments about infinite sets.
▶︎ 23:32 Despite Galileo's conclusion, of course thinkers progressed on this. The contemporary attitude in mathematics resolves the paradox by wholly taking the Cantor-Hume principle as basic. Two sets are equinumerous, two sets have the same number of elements if and only if there's a one-to-one correspondence between them, and they give up Euclid's principle that the whole is greater than any proper part.
▶︎ 24:06 Rather, it's accepted as a feature of infinity that sometimes sets, infinite sets in particular, can be the same size as a proper part of themselves, and that this is not a contradiction but rather this is part of the nature of infinity. Part of the nature of infinite sets is that the whole set can have the same size as a proper part, just as the natural numbers have the same size as the proper part of squares.
▶︎ 24:29 And so one way of slightly keeping Euclid's principle, because maybe Euclid's principle has quite a strong pull for you, maybe you want it, keep it as much as you can, and one way of keeping a lot of it is to say, "Well, the problem with Euclid's principle is this strictly greater part." Really, what maybe the most of the intuition in favor of Euclid's principle is concerned with the claim merely that the whole of any object is at least as great as any proper part. We don't want to give that up, and we don't have to give that up. In fact, that slight change in Euclid's principle is enough to make it compatible with the Cantor-Hume principle.
▶︎ 25:10 And so, generally the attitude in mathematics today and amongst most mathematicians is to say that the equinumerosity relation of one-to-one correspondence defines the notion of same size, and this is the idea that Cantor emphasized so strongly in his work. And we nevertheless continue with the idea that the whole is at least as great as any proper part, which introduces the idea of comparisons between infinities.
▶︎ 25:38 Let me continue now. One thing to observe is that the Cantor-Hume Principle, that's the principle that says two sets have the same number of elements just in case they can be put into one-to-one correspondence. It's providing an identity criteria for when two sets have the same number of elements, but it doesn't actually give us a criteria for saying when is one set at least as large as another. It's only about when they have the same number, not about when it's at least as large. But this reflexive Euclid principle that I proposed is about the comparative judgment.
▶︎ 26:17 And so I want to introduce what I call the comparative size principle, which is that we want to say that one set has at least as many elements as another if the other set is equinumerous with a subset of it. So let me just write that out or draw a kind of picture. To compare the sizes of two sets, possibly infinite sets, we want to say that X is less or equal Y in size, so Y is at least as large as X. If here's X and here's Y, if I can find a equinumerosity, a one-to-one correspondence between X and a part of Y, maybe all of Y or maybe just part of Y.
▶︎ 27:08 But if X is equinumerous with part of Y and there's other points left over, we don't say Y is strictly bigger, because maybe Y also is equinumerous with that proper part as it is the case with the numbers and the perfect squares. This is a reflexive notion. We say that X is less or equal Y in size if it's equinumerous with a part of Y, maybe the whole of Y, maybe just a proper part. So this is the definition of the comparative size of two sets, not for identity of size, but comparisons of size.
▶︎ 27:43 And when you take this notion, then you might want to say, "Well, when do we want to say that one set is strictly larger than another?" So we would say X is strictly less than Y or Y is strictly larger than X if and only if. Well, when you have a reflexive order or relation like this, then the corresponding strict order would be defined by saying, "Well, this should mean that X is less or equal Y and Y is not less or equal X." That's what it means to be strictly larger than X.
▶︎ 28:21 So we have a notion of comparative size in a reflexive sense. X is less or equal Y in size just in case it's equinumerous with a proper part of Y, and X is strictly smaller than Y if it's less or equal Y, but not the other way. So therefore we would say that Y is at least as large as X, but X is not at least as large as Y. That's what it means to be strictly larger.
▶︎ 28:48 And then a certain question arises when you start introducing these notions. Namely, let me just ask the question. If X is less or equal Y in size, which means that X is equinumerous with a part of Y, and Y is less or equal X in size, which means Y is equinumerous with part of X. I could draw a picture of this situation. Here's X and here's Y, and I have a correspondence. Let me use some colored chalk here. I have a correspondence of X with a part of Y, so I can map points of X here into Y in a one-to-one way. Let's see. Oh my gosh.
▶︎ 29:42 But also, this picture here so far is witnessing that X is less or equal Y because it's equinumerous with a part of Y, but then I also have that Y is equinumerous with part of X, which means I have a map going the other way. So let's draw that one in red. There's a part of X, and I can map points in Y into that part of X. The situation is that each of them is equinumerous with part of the other. And the question that one wants is then must X be equinumerous with Y? Of course, if this is a robust concept of comparative size, we absolutely want the answer to this question to be yes. We wanna say: if Y is at least as large as X and also X is at least as large as Y, then they have the same size. That's a principle, a rock-bottom principle that we want any notion of comparative size to obey.
▶︎ 30:43 But we've introduced a kind of technical meaning for this. X is less or equal Y in size just in case it's equinumerous with a part of Y, and similarly, Y is less or equal X in size just in case Y is equinumerous with a part of X. And so, is it true that whenever this situation arises, then you can make another picture between X and Y which has an exact one-to-one correspondence without missing any pieces on either side? Can you turn this kind of picture into this kind of picture? And if you can't, then that's evidence that this isn't really a robust notion, but if you can, then it's fulfilling a basic principle that you would want any notion of comparative size to have.
▶︎ 31:34 I can tell you the answer to this question. It's quite interesting. The answer is yes, and this is known as the Cantor-Schröder-Bernstein theorem, proved at the end of the 19th century. So it's a kind of missing piece of the analysis, I think, because in the philosophical literature, there's a huge literature on the Hume principle, or what I call the Cantor-Hume principle, about the number identity problem, when is it the case that we wanna say two concepts have the same number of instances? Well, if and only if those instances can be put into one-to-one correspondence. So there's a huge literature on the Cantor-Hume principle, but there's comparatively little literature, little discussion in the philosophical literature of the Cantor-Schröder-Bernstein result, which makes robust this concept of comparative size.
▶︎ 32:28 And so it's quite interesting, though. It was proved... Let's see. What is the history? It was proved by Cantor in 1887. Well, it was mentioned by him in 1887 without proof, but it was proved but not published by Dedekind in 1888, and then again by Cantor in 1895, but only assuming that cardinals are linear, that the sizes are linearly ordered, and that's a principle, actually, that's equivalent to the axiom of choice, which we'll discuss in a later lecture. But then finally, it was proved by Schröder in 1896 as a corollary to a certain theorem of Jevons, and then in 1897 independently, and then finally by Bernstein in 1897.
▶︎ 33:12 And so the earlier proofs, in fact, were using the axiom of choice, but you do not need the axiom of choice to prove this principle, and it's a quite lovely argument. It's not so difficult. It's challenging, but not so difficult. The situation is you have these two injective maps, these two one-to-one correspondences, and you need to assemble them together to make this one-to-one onto correspondence between X and Y, and it's possible, and the correspondence that you get here is built from pieces of these two mappings, these two associations that are delicately assembled in a certain way to make exactly a one-to-one correspondence between X and Y, and it's a quite beautiful argument.
▶︎ 33:53 So therefore, we do have a positive answer to this question. If X is less or equal Y in size and Y is less or equal X in size, then they have the same size. This is a basic principle of this notion of equinumerosity. So that's it for this lecture. I hope you enjoyed Galileo's paradox and a discussion of equinumerosity.