▶︎ 0:00 Hi, I'm Joel David Hamkins, and I want to talk about the infinite and the finite. What does it mean to say that something is infinite, that a set is infinite, or that a set is finite? Maybe it seems obvious, but actually I think it's not so clear, and in history, we've had many different proposed definitions of the infinite and the finite. And so, let's get into it.
▶︎ 0:20 If we want to understand the infinite, maybe we think that's too difficult, and so I might ask instead, "Well, what does it mean to say that a set is finite?" And perhaps you reply, "Well, that's absurd. Of course we know what it means for a set to be finite." But do we really?
▶︎ 0:37 And in fact, I claim that these two concepts of the finite and the infinite are equally hard because they carve the same joint between the finite and the infinite. To define the finite is to define the infinite because those are the things that are not finite, and to define the infinite is to define the finite because those would be the sets that are not infinite. And so actually it's just as hard to define the finite as it is to define the infinite.
▶︎ 1:02 If we think about what Aristotle said about the infinite, he defined the infinite as that which proceeds without end, and of course, as we discussed in another lecture on potentialism, he had a potentialist understanding of the infinite. Namely, something is infinite or a set is infinite, there are infinitely many numbers in the sense that you can have more and more, as many as you like, but you never have all of them. And so this is the sense of proceeding without end. It's connected with those ideas on potentialism. And we had mentioned that Galileo was an early prominent critic of potentialism.
▶︎ 1:38 Almost everyone was potentialists up until about the end of the 19th century when this sea change occurred in potentialism, but Galileo objected and we discussed in the lecture on Galileo's paradox the idea, the observation that the number of numbers is the same as the number of perfect squares. So this is based on the idea that a set can be equinumerous with a proper part of itself. We have the numbers zero, one, two, three, and so on. Those are the natural numbers and they can be equinumerous with the set of perfect squares, zero, one, four, nine, 16, 25, and so on. So that situation is paradoxical because it identifies this tension between Euclid's principle and the Cantor Schön principle that sets have the same number of elements when they can be placed into one-to-one correspondence.
▶︎ 2:30 But how are we to respond to that? Well, Dedekind, Richard Dedekind in the late 19th century proposed that we simply take this as a definition of the infinite, so a set is Dedekind infinite exactly when it is equinumerous with a proper part of itself. So the natural numbers are Dedekind infinite because they are equinumerous with the perfect squares, which are a proper part of itself. Of course, it's not just about squares. We could have used other proper parts like the even numbers. There's just as many numbers as there are even numbers because we can double any given number and make an even number.
▶︎ 3:00 There's a lot of different proper parts that are equinumerous with the whole of the natural numbers, and for all of those reasons, any one of them suffices. The set of natural numbers is Dedekind infinite. But do we take this as a definition of infinite? Do we expect for any infinite set there should be some proper part of it that's equinumerous? Maybe you have the idea, well, finite sets are definitely not like that. We can't ever find an equinumerosity between a finite set and a proper part, but do we expect that every infinite set is equinumerous with a proper part of itself? Maybe for some kind of strange amorphous kind of set you might think it's infinite because it doesn't have finitely many elements, although we don't yet know what that means, and yet one cannot find an equinumerosity with a proper part.
▶︎ 3:52 Let me turn to some alternative order theoretic conceptions of the infinite. Maybe being infinite has to do with how we can put the set into an order. Let's think about various proposals. There's quite a number. Maybe one naive initial idea is that we want to say a set is finite, a finite set is one such that we can place it into a linear order, so that it has a first element and a last element and every point in between has a next element and a previous element.
▶︎ 4:25 This is what it would mean to be a discrete linear order with endpoints. So the situation would be maybe, this is the naive proposal, if you can put a set into a linear order, so it has a first element and a next point and so on, a next point and so on, and then finally we come to the last point. So there's a first point and a last point, and every point in the middle has a next point and a previous point. Maybe you might think, "Well, yeah, that's what it means to be finite." But that's the problem with this proposal. It doesn't actually work. It's wrong. And it's wrong for the following kind of counterexamples.
▶︎ 5:02 Let me describe a situation that would obey that principle and yet is clearly infinite. What I'm going to do is I'm going to make a linear order of points here that get smaller and smaller, infinitely many. And then I'm going to come down from the top at the same time, smaller and smaller. So maybe these are the natural numbers going up, like zero, one, two, three, four, five and so on, and maybe I put the negative ones up here. What the heck? Let's just put the negative numbers on top. So negative one, negative two, negative three, negative four, and so on going down.
▶︎ 5:39 This is a linear order. I've just put the negative numbers on top of the positive numbers for this order, this strange order. And there's a first number in this order, this one, and a last one, negative one, and every number in between is either coming from this part or this part and it has a next number and a previous number and the same over here. There's a next number in the order and a previous one. So this is a discrete linear order with endpoints, and yet it's obviously not a finite set, and so that naive idea doesn't quite work because merely having a discrete order doesn't actually force the order to be finite in the intuitive sense that we want, and so it will not serve as a definition of the finite. So what does it mean to say that a set is finite?
▶︎ 6:21 Let's look at some other proposals. One problem with this order you can see is that I could rearrange it. For example, if I look at this dividing point in between here, and I take this whole part of it and put it on the top, then I get something that looks like this. If I interchange the two pieces, then this part would appear on the right like this going up, perhaps getting smaller and smaller, and then this part would appear on the left going down, perhaps getting smaller and smaller. Now it's just actually like the integers, because they're zero, one, two, three, and so on going up, and -1, -2, -3, -4 going down, so it's really just the integers.
▶︎ 7:07 But the feature I want to identify is that this set had a rearrangement with a linear order that had no largest element, and so according to Aristotle's conception that something is infinite when it proceeds without end, here's a linear order that has no largest element. It's proceeding without end, and so we want to regard this as infinite. So maybe we can just say that a set is, let's see, what's the terminology that I have here? A set is order infinite if it has a linear order with no largest element, so this set is order infinite because I could rearrange it. This order wasn't any good because it did have a largest element, but it had a rearrangement that does not have a largest element, and so therefore this set we want to say is order infinite because it has a linear order with no largest element.
▶︎ 7:59 So is that a good definition of the infinite? We want to say a set is infinite if it has a linear order with no largest element. Of course, any set that has such a linear order with no largest element would be infinite according to our intuitive idea because there's no largest element. It's proceeding without end. But do we actually think that every infinite set should have such a linear order? Does every infinite set have an order at all? What's the principle by which you would deduce?
▶︎ 8:31 If I have an infinite set, maybe it's quite a strange set, maybe it doesn't have a linear order at all, in which case it would not have a linear order with no largest element, and so it would vacuously count as finite according to that definition. So if there were a weird set that could not have a linear order at all, then that definition, that order infinite, it wouldn't fulfill the order infinite definition because to be order infinite, remember, means to have a linear order with no largest element. So if I have a set that doesn't have a linear order at all, then it doesn't have such an order, and so it wouldn't be order infinite. But we wouldn't want to say that it's finite because we also have the idea maybe that every finite set should in fact have a linear order. I should be able to maybe count off the set with the numbers, and that would give me an order on the set. So therefore, the order infinite concept maybe seems to have some difficulty if there are these very strange sets that don't have any linear orders at all.
▶︎ 9:31 But are there such sets? In this way, you see that the definition of finite is depending on the nature of the set theory that we're talking about. What are the set theoretic principles that we're working under? What kind of sets are there? What is the nature of set theoretic ontology? These are going to have consequences in the definition of finite and infinite.
▶︎ 9:55 So in light of that objection though, maybe we can fix it by saying this. A set is linearly finite if it has a linear order and yet all linear orders have a final element. So I just insist that it has a linear order. So a set is, let me say it again. A set is linearly finite if it has a linear order, it can be put into an order, a linear order. Linear just means that for any two points, one of them is appearing before the other.
▶︎ 10:23 So if it has a linear order, but every linear order has a final element, that's what it means to be linearly finite. So for example, this set has a linear order. They're the same set, I just rearranged them, but not every linear order of this set has a final element because here's a linear order of the set which has no final element, and so this set is not linearly finite, therefore counts as infinite according to that account of finiteness.
▶︎ 10:58 Here's a slightly different definition. We could say that a set is discretely finite if it has a linear order but all of the linear orders of it are discrete. Discretely finite means a set is discretely finite if it has a linear order but it only has discrete linear orders, so it won't ever have an order that's not discrete. These orders were both discrete, but this set, I claim, is not discretely finite because I can make another order of it that's not discrete.
▶︎ 11:34 Let me show you how to do that. Here's a discrete linear order of the integers, but what I could do is let's just take one of these points, this one, say, and put it right in the middle, so I get an order that looks like this. It has the bottom part converging up, and then I put this big point right in the middle, right in that gap, filling that gap, and then it has the other points remaining, proceeding down. All I did was take this point, I picked it up, and I put it in this gap between the two halves, so there it's sitting right there.
▶︎ 12:11 This is a set. It has a linear order, but it's not true that every linear order is discrete because this order is not discrete. It's mostly discrete, because these points all have a next one and a previous one and so on, and these points all have a next one and a previous one except for the top, it doesn't have a next one yet. So every point that's not extreme has a next one and a previous one except for this one.
▶︎ 12:32 Because these points are going down here and there's no smallest number in this top segment, this point in the gap has no next point. It also has no previous point because these numbers are going up, up, up, up, up, up here in this lower half and there's no largest number amongst these, so there's no immediate predecessor to this point. So this order is not a discrete order because this point is in the middle but it has no next point and no previous point. In fact, either one of those would suffice for it to not be a discrete order. That set is not discretely finite because it has linear orders but it's not true that every linear order is a discrete order.
▶︎ 13:17 Here's another definition that was proposed by Paul Stäckel in the late 19th century. A set is Stäckel finite if it has a linear order with the property that every non-empty subset of it has a greatest element. Or a least and a greatest element, I'm sorry. It has a linear order such that every non-empty subset of the set has a least and greatest element. This set is not Stäckel finite because it has this order does not show that it's Stäckel finite because it has a subset like this that has no greatest element. If I just take the bottom half, it has no greatest element. It also has a set with no least element, namely this one.
▶︎ 14:07 This concept of every non-empty subset having a least element is what's known as a well order. And so Stäckel is saying that a set is Stäckel finite if it has an ordering that's a well order but also its inverse is a well order, because every non-empty set has both a least and a greatest element. So for Stäckel, a set is finite if it can be well ordered in such a way that the inverse order is also a well order. Well, that's, come on. All that seems so complicated to just define the notion of finite. Why is it so difficult to say what we mean by finite, with all these very subtle notions about different kinds of orders?
▶︎ 14:49 Here's another one. Tarski wrote a paper in the early 20th century providing five different order theoretic accounts of what it means to be finite. He was concerned with collections of subsets of the set. So for example, a set is Tarski finite if every non-empty family of subsets of the set has a minimal such set. So it's sort of well founded. Every non-empty family of subsets of the set has a minimal set in the family. And there's other alternatives that he proposed.
▶︎ 15:20 Those are various order theoretic ways of trying to come to terms with the notion of finite. And I didn't say so but it's true that many of those order theoretic notions are equivalent to each other but they're not all provably equivalent to each other in the standard Zermelo-Fraenkel set theory unless you also have the axiom of choice, in which case they are all equivalent to each other, in fact. But you need the axiom of choice in order to prove these equivalences. And we're going to talk about the axiom of choice as a fundamental principle of set theory in a later lecture.
▶︎ 15:52 Let me turn now to another definition of finite, an alternative definition, and this is numerically finite. What does it mean to be numerically finite? A set is numerically finite. Here I'm just drawing a picture of the set. If you can count it off with numbers, with finite numbers. I can label the points with a finite number. That's what it means to be numerically finite.
▶︎ 16:28 I think it fits the intuition of the shepherd counting the sheep. We count them, one, two, three, maybe we start at one. I'm sorry, habitually I always start at zero, for me, naturally I'm gonna start with zero. But maybe when you're counting the sheep, you would start with one. One, two, three, four, and so on up to 117 or however many sheep you have. If you're wealthy, I guess you have that many. A set is numerically finite if it can be counted off with the numbers. Let's say from one up to n, we would wanna say it has n elements.
▶︎ 17:02 But the objection, of course, is, come on, isn't this hopelessly circular? Because I've said a set is numerically finite if you can count off the elements using the numbers up to a finite number. I used the word "finite" when I said a finite number, but what is that, and do we need to know what does it mean to be a finite number? We would need a totally independent account of what it means to be a finite number in order for the definition of numerically finite to succeed. Otherwise, it's circular.
▶︎ 17:31 Because I wouldn't wanna say, "Well, a number is finite if it's numerically finite." That's completely circular and inadequate. So do we have a concept of finite number that stands independently of our concept of finite set? You might say, "Well, a finite number is one that's the number of elements in a finite set." But then that would be circular.
▶︎ 17:54 Frege grappled deeply with this question of what does it mean to say that a number is finite, and he embarked on his logicist program, this attempt to reduce all of mathematics to logic. And so he wanted to ground in basic logical principles the entire foundation of mathematics, on which the rest of mathematics could be built on this purely logical foundation, and he gave us a concept of finite number. He started with the concept of the number zero, which is the number of elements in the empty set. If you have a contradictory property, then the extension of that concept has no instances because it's contradictory. So it's the empty set basically, and the number of elements for that concept is what he called zero. Zero is the number of elements that are in an empty set, a set with no elements.
▶︎ 18:48 And he also had a concept of the successor relation. If you have a number of elements, if you have a set and it has a number of elements, then the successor number would be the number of elements in a set that you get by adding one more element to that set. He took these as primitive, that we have a concept of zero and we have a concept of successor relation, and then he defined that a finite number is a number that has all the properties that zero has that are also transferred from every number to its successor. We had prior notions of successors. So let me say it again. For Frege, a number is a finite number if it has every property that zero has which is also always transferred from any number to its successor.
▶︎ 19:42 Now of course being finite is such a number because zero of course is a finite number, it's the smallest finite number, and also if N is a finite number then N plus one is a finite number. This fits with our intuition. And so finiteness is one of these properties, but Frege is defining that property of being always, having every property of zero that's always transferred from every number N to its successor N plus one, is sort of saying that the finiteness property is the most minimal conception that is always transferred in that way. It's the smallest property.
▶︎ 20:18 And if you think about it, I think you'll realize that Frege's definition amounts to what we would call induction. Frege is basically saying, "Well look, zero is finite, and if N is finite then I want to say N plus one is also finite." And so this quantification over all the properties, for Frege is amounting to a kind of induction principle. To be finite means that the finite numbers fulfill the inductive property, because whenever a property holds at zero and is always transferred from N to N plus one, then it holds of all the finite numbers.
▶︎ 20:57 Let's talk about Dedekind's approach. Dedekind is great because he gave us two different concepts of finite, in fact. I already mentioned the concept of Dedekind finite and Dedekind infinite, which is a set is Dedekind infinite when it's equinumerous with a proper part, and it's Dedekind finite if it's not. But he also gave us a concept of finite number, and this is with his theory of Dedekind arithmetic.
▶︎ 21:22 Let me tell you about the theory of Dedekind arithmetic. I want to write down the axioms. So this is Dedekind arithmetic. Dedekind arithmetic is about the structure of the natural numbers where we have a constant for zero and we have the successor operation, the plus one operation. And Dedekind wrote down the most fundamental axioms of this successor relation.
▶︎ 22:01 The first axiom says that zero is never the successor of something. Zero is not a successor. There's no number smaller than zero. There's no predecessor to zero. And the second one is that the successor function is one-to-one. So in other words, if the successor of X is equal to the successor of Y, then X equals Y. So if two numbers have the same successor, then they were the same number to begin with.
▶︎ 22:31 And the third one is saying essentially that every number is obtained from zero by applying the successor operation. And one way of saying it is like this. So, if I have a set of numbers and zero is one of them, and whenever N is in the set then the successor of N is in the set, then every number is in the set. And if you look at this, what it's saying is that if being in the set is expressing a certain property, it's saying if zero has the property and if whenever a number has the property then the successor has the property, then all numbers have the property. This is induction. This is the basic induction principle. And this theory here is called Dedekind arithmetic and it certainly we expect it to be true of our conception of the natural numbers with the successor operation.
▶︎ 23:38 Dedekind proved a remarkable theorem about this theory. Namely, he proved that the theory is what's called categorical. In other words, any two models of this theory, if you have two different structures. Suppose I have my conception of the natural numbers and my zero and my successor operation, and you have your natural number conception and your zero and your successor operation, but both of them fulfill these axioms. Then, Dedekind showed that our two number systems are just copies of one another. They're isomorphic.
▶︎ 24:15 There's a kind of transfer from my number system to your number system, or the other way, that preserves all of the structural features. So in a sense, the theory is categorical, it means that there's only one model of this theory up to isomorphism. The theory totally captures the structural situation of the intended model. The way that Dedekind proved this is by showing on the basis of these axioms that one can undertake definition by recursion. Definition by recursion means you define a certain function by reference to earlier instances of the same function. So let me show you how that concept leads to the categoricity result.
▶︎ 25:13 Maybe I have my number system. Let me say M, zero, S. And maybe you have your number system. Let me say N bar, zero bar, S bar. The individual numbers for you are constituted by maybe different objects or maybe there's some overlap, it doesn't matter, or maybe the particular identity of zero is a different object for you, and the nature of this successor operation is maybe different. That's the question, is whether we do think that there could be different copies or not with fundamentally different features. But what I'm supposing is both of them satisfy the principles of Dedekind arithmetic.
▶︎ 25:54 Then Dedekind defines an isomorphism, let me just call it pi, a mapping from my numbers to your numbers. And how do we do it? What should pi do? Obviously it has to take zero, my zero, to your zero. So pi is going to map zero, my zero, to your zero. And then, of course, it's going to map the successor of zero, my successor of my zero, it's going to get mapped to your successor of your zero, and so on.
▶︎ 26:35 So if pi maps some number N, one of my numbers, to some number pi of N, then it should map the successor of that number to your successor of the corresponding number over there. I could write N bar instead. No, let's just keep it pi. So the point is that this formula, basically we're saying pi of SN is equal to S bar of pi of N. That's a recursive definition, because I'm defining pi at an instance in terms of pi at the previous instance.
▶︎ 27:17 And Dedekind proved that definitions by recursion are legitimate in his theory. In the theory of Dedekind arithmetic you can validly make definitions by recursion, and we can prove the categoricity result that way by undertaking the recursive definition of the isomorphism. According to Dedekind this definition succeeds, and so every one of my numbers has a corresponding number on your side. And we might ask, is it a one-to-one and onto map? In other words, have I hit every one of your points in order to know that your number system is a perfect copy of mine, I would need to know that every one of your numbers is pi of something, pi of one of my numbers.
▶︎ 28:02 But that's going to be true, because if I think about the numbers that are used by this map pi, that's a subset of your numbers, and it includes zero bar. And furthermore, it's closed under your successor operation precisely because the S bar of something in the range of pi is also in the range of pi. So the numbers in the range of the mapping satisfy the induction property in axiom three, and therefore it must be all of your numbers. So what we've proved is that if we have two number systems that both fulfill Dedekind's axioms, then we can define this mapping between them which shows that actually they're isomorphic, they are identical structurally, they have exactly the same structure, they are copies of one another. And that's what it means for the theory to be categorical.
▶︎ 28:55 What's the significance of that for the notion of finite? The point is that the categoricity result shows that Dedekind's theory identifies the concept of finite number. To be a finite number means to be one of the numbers in a model of this theory. That's exactly what it means to be a finite number. And in that theory we never use the word finite. It's not circular. We have an independently standing concept of finite number. A finite number is a number that occurs in a model of Dedekind arithmetic.
▶︎ 29:30 And once you have this model of Dedekind arithmetic with the successor operation, then what you get from it is the entirety of number theory, because you can prove that you can define addition by recursion from the successor relation, and you can define multiplication by recursion on addition, and you can define exponentiation, and you can define primes, and you can define the order, and you can define all of the familiar number theoretic concepts that you would see in the development of number theory. They all follow deductively from Dedekind's theory.
▶︎ 30:00 Peano famously wrote a treatise doing exactly that, and he mentioned Dedekind's theory. So he wrote down these axioms and showed in a quite elegant, beautiful manner how to develop the entirety of elementary number theory on the basis of Dedekind's theory. And actually this is how a lot of number theory is introduced. At an elementary level you prove things by induction and so on. You prove associativity of addition and commutativity of multiplication and so on. All the familiar basic facts about number theory, all of them can be proved in Dedekind's theory. I wanna show you a little
▶︎ 30:38 a bit about how those proofs go, just to see. Sometimes people think of induction as maybe a kind of curiosity used to prove certain recursive formulas or something, because oftentimes in, say, high school or something, induction is treated in that way. But I think this is completely wrong, because the perspective that grows out of Dedekind and Peano's work shows that induction is not some curiosity. It is a core principle at the very foundation of our ideas about number. And essentially, all of the most basic facts, the most fundamental facts of number theory, are proved using induction.
▶︎ 31:20 So let me just do some examples to show you that. Let's say we have the concept of fractions, like three-fourths or five-sixths or three-sixths. Sometimes fractions aren't in lowest terms. Three-sixths is the same as one-half. Or five-fifteenths is the same as one-third. I can cancel and reduce to find the lowest terms. But can every fraction be placed in lowest terms? So that's the question. It's a basic fact. In elementary school, we put fractions in lowest terms and we always succeed when we try to do that. But why is it that we should expect to always succeed? Is it a theorem that every fraction can be placed in lowest terms? So how is it that we would prove something like that? Well, we prove it by induction.
▶︎ 32:15 So let me explain how to do that. Actually, I want to just back up a little bit and talk about forms of induction. This form of induction that I wrote in axiom three of Dedekind's theory is what might be called common induction. So common induction is the principle that says if you want to prove every number has a certain property, then you should prove it holds of zero, and then you should also prove the implication that if it holds of a number N, then it holds of the next number, N plus one. Then you get to conclude, and that's the content of the induction principle, the common induction principle, it holds for all numbers. So in other words, if something holds of zero and it's always transferred from a number to its successor, then it holds of all numbers. That's the common induction principle.
▶︎ 33:03 But there's another form of induction, and this other form of induction, for example, there's this strong induction. And strong induction is the following principle. You want to prove a certain property holds of every number. So what you do is you just prove one case. You prove one principle, namely that if for a given number it holds below that number, then it holds at that number. So you don't have to prove it separately for zero, because actually, the case of zero would follow from it, because there isn't anything below zero, and so it's vacuously the case that it holds of all the numbers below zero, because that case has no instances, and so it's vacuously true. So therefore, it follows without stipulating that it hold, that it must hold of zero. But therefore, then it holds of one, because if it holds of zero, then it holds of every number less than one. So therefore, by the strong induction principle, it should hold of one. But therefore, it holds of every number less than two, so therefore, by the strong induction principle, it should also hold of two.
▶︎ 34:02 So it's a different way of talking about induction. Common induction says you prove something for all numbers by proving it at zero, and you prove that if it holds at N then it holds at N plus one. And you get to conclude that it holds of all numbers. The zero case is called the anchor case, and the implication from N to N plus one is called the induction step. So with strong induction, we don't have an anchor case. We just say, we assume it holds below a number, prove it holds at the number. Then this is strong induction, so we're assuming more, not just, in the common induction you only get to hold when you're proving it for N plus one, you only get to assume it at N, but maybe you don't get to assume it before that. In strong induction, you have this stronger assumption. Not only does it hold in the immediate preceding case, but it holds in all the earlier cases. So it's a stronger assumption that you get to make for the induction step, and that's why it's called strong induction.
▶︎ 34:58 But in fact, the two principles are equivalent. We could have formulated Dedekind arithmetic using a strong induction concept instead of the common induction principle. There's another form of induction which is called the least number principle, and the least number principle says if you have a non-empty set of numbers, then there's a smallest one. A least one. And this is related to strong induction, because if we want to prove that the least number principle is equivalent to the strong induction principle, for example, sometimes people call the least number principle the, when using strong induction, really what you want to do is show that it's not the case that there's, well, people use this phrase, there's no minimal criminal.
▶︎ 35:48 So in other words, you want to show that every number has a property by strong induction. Suppose you have a number N and it holds all the way below, but not at N. That would be a criminal, because it's not holding at N. But it's minimal, because it holds below. So what you're really doing when you're proving that if it holds below, then it holds at N is you're proving that there are no minimal criminals. So you're proving that the set of counterexamples can't have a least member. That's exactly a different way of stating the strong induction principle. But on that point of view, it's just equivalent to the least number principle.
▶︎ 36:26 So if you want to prove something by strong induction and you have the least number principle, then you just take the set of counterexamples, and if that's nonempty, there would have to be a least member, the minimal criminal, the least counterexample. But that would violate the strong induction hypothesis because it's true below that minimal guy, and so it would have to be true at that guy, so he wouldn't be a counterexample after all. So in this way, you can see that the strong induction principle is equivalent to the least number principle, and they're all equivalent to the common induction principle. So all these different ways of talking about induction are equivalent.
▶︎ 37:01 Let's now return to this lowest terms claim. Every fraction can be put in lowest terms. How do I know that? Well, suppose I have a fraction P over Q. Maybe it's not in lowest terms yet, but I want to know that I can put it in lowest terms.
▶︎ 37:16 So what I'm going to do is, I'm going to look at the set of all possible numerators that I could make. So I have P over Q, but maybe it's equal to a lot of different P prime over Q prime, yeah? So I look at the set of all the P primes that can arise that way, that can arise as a numerator in an equivalent representation of P over Q. But by the least number principle, there must be a smallest instance. So there's a smallest possible numerator that I can use to write a fraction that's equivalent to my given fraction, P over Q.
▶︎ 37:52 But I claim that smallest numerator, I would have P prime over Q prime, and it's equal to P over Q. I claim if P prime is really smallest amongst all such representations, then it has to be in lowest terms, because if it wasn't, I would be able to get a smaller instance by dividing out a common factor, yeah? To be in lowest terms means there's no common factor between the numerator and the denominator, so if it wasn't in lowest terms, there would be something to divide out, and that would make a smaller numerator. But there can't be any smaller numerator, because P prime already was the smallest one. So what I've shown is that there can't be a minimal criminal in this case, so by induction, every fraction can be put in lowest terms.
▶︎ 38:35 Let me do another example. The fundamental theorem of arithmetic says that every number, every natural number, every positive integer has a factorization into primes, a unique factorization into primes, the prime factorization of the number. And so let me prove the... Really, the fundamental theorem of arithmetic is two claims. It's an existence claim and it's also a uniqueness claim. We're saying there is a factorization of the number, but also that there's only one. All the factorizations use the same primes. Maybe they change the order, but it's unique in terms of the multiplicity of the primes that appear in it.
▶︎ 39:21 Let's prove the existence part of the fundamental theorem of arithmetic by induction, by strong induction. What I'm going to do is, I suppose that every number less than my number n... I have a number n, and I'm supposing by strong induction that it's true for all the smaller numbers, that they have prime factorizations. And I want to prove that the number n itself has a prime factorization. Well, maybe the number n is itself prime, in which case that is its prime factorization already, if the number is prime already.
▶︎ 39:56 And if it's not prime, then the number n can be written as a times b, for some smaller numbers a and b. But those smaller numbers fall under my induction hypothesis. I can factor them as products of primes, so I can write a as p1 times p2, and so on, up to pn. And I can write b as q1 times q2, and so on, up to some qm. So a and b can be written as products of primes, and n is equal to a times b. So I just put those primes together, and now I've got a prime factorization for n.
▶︎ 40:32 So the point is that if I know already that all the smaller numbers have prime factorizations, then I know that my number n has a prime factorization, and therefore, by the principle of strong induction, every number has a prime factorization. So that's the existence part of the fundamental theorem of arithmetic. So I hope I've convinced you that the principle of induction is really a core idea, and used to prove these sort of fundamental facts of number theory.
▶︎ 41:02 There's one more example that I want to talk about, and that is the pigeonhole principle. The pigeonhole principle asserts that if you have finitely many pigeons, but you have more pigeons than pigeonholes, and you put all the pigeons into the pigeonholes, then there's at least one pigeonhole that has at least two pigeons in it. Let me say it again. You have finitely many pigeons, and you have a fewer number of pigeonholes, and you put the pigeons into the pigeonholes, then it must have some doubling up. You can't fit all the pigeons into that fewer number of holes.
▶︎ 41:36 It's obvious, isn't it? It's just completely clear, except this is the kind of principle that's expressing a really basic fact which is hard to think about how you would prove such a fact, because maybe you think it's obvious, it doesn't need proof. But of course, everything needs proof, ultimately, from the fundamental principles.
▶︎ 41:53 Actually, I want to make a slightly stronger argument, and that is, we have a ton of evidence against the pigeonhole principle from ordinary experience. For example, suppose that on this table, there was an enormous heap of pennies, and you and I set ourselves the task of counting them. I count one, two, three, four. Maybe there's many, many thousands of pennies, and I count them, and then you count them. Do we get the same number?
▶︎ 42:24 I think there's been situations when one person counts a certain number of objects and another person counts the same objects, but they come up with different numbers. But that's basically evidence against the pigeonhole principle. If they're both right, then it would be a counterexample to the pigeonhole principle. Of course, when that situation happens, we attribute it to human error, like one of us miscounted or we slipped and missed one of the pennies, or one slipped past us, or something like that. Human error is what we usually explain, except this situation occurs, and it could be taken as evidence against the pigeonhole principle.
▶︎ 43:01 Or, for example, if there's an election and then there's a recount, it's almost never the case that the recount numbers are, in every case, perfectly identical with the original count. Usually, they're different. So this also could be seen as evidence against the pigeonhole principle.
▶︎ 43:16 All right, I'm not fully serious about denying the pigeonhole principle because, of course, I know that it's a fundamental principle of number theory. And furthermore, we can prove it, and so let's prove the pigeonhole principle by the principle of induction. If there were a counterexample to the pigeonhole principle, then there would have to be a smallest one, the minimal criminal. So if I have a counterexample to the pigeonhole principle, there's some number of pigeons that fit into a smaller number of pigeonholes. They fit in a one-to-one way without doubling up any pigeons.
▶︎ 43:52 So now what I'm going to do is I'm going to remove one of the pigeons and I'm going to remove the pigeonhole that that pigeon landed in. And now I've still got a counterexample because I subtracted one both from the number of pigeons and from the number of pigeonholes. And so the smaller instance is a number of pigeons with a still smaller number of pigeonholes, and yet they fit. So therefore, from any counterexample to the pigeonhole principle, you can produce a smaller counterexample to the pigeonhole principle is what I'm arguing.
▶︎ 44:21 But that violates induction because the strong induction principle says, "Look, if there's any counterexample at all, then there has to be a smallest one." That's the least number principle. And therefore, we've proved using the least number principle of strong induction, however you want to formulate it, that the pigeonhole principle is correct.
▶︎ 44:39 Let's go back to this concept of Dedekind finite. Dedekind finite, remember, it was a proposal, not Dedekind's account of the finite numbers, which we're going to use to define numerically finite, but rather Dedekind infinite. A set is Dedekind infinite if it's equinumerous with a proper part of itself. Like in the Galileo paradox situation, the numbers are equinumerous with the perfect squares, so that's why that set is Dedekind infinite. But maybe you have another set that's equinumerous with a proper part, and that makes it Dedekind infinite. And so the question is, is the concept of Dedekind finite, that's the opposite of Dedekind infinite, is it the same as numerically finite?
▶︎ 45:25 The pigeonhole principle says that if you have more than N pigeons, you can't put them into N pigeonholes. So it's basically saying that no finite number N is equinumerous with a proper part of itself. And therefore, every numerically finite set is in fact Dedekind finite. So we have an implication from numerically finite to Dedekind finite. But is the converse true? Suppose you have a Dedekind finite set, so it's not equinumerous with any proper part. Then, why does that mean you can count it off? Where is this counting going to come from? So that's the question.
▶︎ 46:09 And in fact, one can show that the two notions are equivalent if you have a certain principle called the axiom of choice. So let me explain the argument now. Suppose I have a set X and it has a copy inside of it, a copy of the natural numbers inside of it. So it has, say, a point X0, another point X1, X2, X3, and so on. For every natural number N, it has X of N. That's a subset of X. Then I claim I can make an equinumerosity from all of X to a proper part.
▶︎ 47:02 And what I do is I just take that copy of the natural numbers and I associate each point with the next point. So I shift in that copy of the natural numbers inside the set. And points outside of that are just associated with themselves. So what have I done? I've taken the whole of X and I've built a one-to-one correspondence of the whole of X with a proper part of X because now nothing is going to get associated with X sub zero because I shifted in that copy of N inside X, and outside I just kept everybody. So the subset, the proper part of X that I'm going to be equinumerous with is going to be everything except for X0. So in this way, we can see that, in fact, it's true. Being Dedekind infinite is equivalent to the property of having a countably infinite subset.
▶︎ 48:00 And now we can see that, suppose I have an infinite set, well, let's try to build a countably infinite subset of it because then we would know that it's not Dedekind finite. If I have an infinite set, I'm just going to pick an element, X0, any element, pick whatever you like. And that's not all of the points because I said it was an infinite set, so in particular, it's not numerically finite. And now, so I can pick another element, let's call it X1. Amongst the points that remain, I'm going to pick one. And this isn't all the points because it's an infinite set, but I only have two here. So then amongst the points that remain, I'm going to pick another one and so on. And I can just keep doing that. At no point will I have exhausted the set because it was an infinite set. And therefore, what I'm arguing is that every infinite set has a countably infinite subset. And therefore, it is not Dedekind finite, because I can do that shifting and that's going to give me a correspondence of the whole set with the proper part, namely the part that's missing the first point X0.
▶︎ 49:09 So the question is what did I mean when I said, pick any point you like? The question is, is that picking process legitimate or not? And that's a topic that the axiom of choice is all about. And we're going to have a whole lecture discussing it more. But in situations when the axiom of choice is true, if that's part of your conception of mathematical reality that it fulfills the axiom of choice, then the notion of Dedekind finite and numerically finite are equivalent, and they're equivalent to all of the other notions of finite that we've discussed.
▶︎ 49:43 Nevertheless, there are models we can prove, set theorists can prove, by quite sophisticated arguments that there are models of the Zermelo-Fraenkel axioms of set theory without the axiom of choice that have infinite sets that are Dedekind finite. And in particular, they do not have any countably infinite subset. So therefore, the notions are not provably equivalent. The notion of Dedekind finite and numerically finite are distinct notions in the context where you do not have the axiom of choice. You don't need the full axiom of choice, but weaker forms, countable choice is enough.
▶︎ 50:19 If we come back to the main question, what does it mean to say that a set is finite? We had a lot of different concepts on offer. We had Dedekind finite, linearly finite, discretely finite, Steagall finite, Tarski finite, numerically finite, and so on. And in certain situations, we can prove equivalences between these various notions. But one thing that we can prove is that numerically finite implies all the other ones.
▶︎ 50:48 A set is numerically finite if you can count it off with a finite number, and we have a concept, an independently standing concept of finite number that comes from Dedekind arithmetic. Precisely because the concept of numerically finite implies all of the other notions of finite, and it's clearly acceptable as a notion of finite, then that's a reason to take it as the primary notion. And that's what mathematicians generally do today. So today, if you ask a mathematician, "What does it mean to be finite?" then they'll say, "It means to be equinumerous with a set of predecessors of a natural number, which is to say that it's numerically finite."
▶︎ 51:30 So we want the strongest notion that still has the property that the conventional numbers would all count as finite, and that's exactly the notion of numerically finite. And so this has won. The concept of numerical finiteness has won the contest in how to define our notions of finiteness. And it's quite interesting, to my way of thinking, it's quite interesting how these different concepts of finite tear apart when you start giving up certain principles in the foundations of mathematics, such as the axiom of choice.
▶︎ 52:04 This third axiom, this induction axiom, if you notice carefully, it wasn't an axiom that involved only quantifiers over the numbers themselves, but rather we were quantifying over sets of numbers. Because we said for every set A, if it contains zero, and if it's closed under the successor operation, then A has all the numbers in it. And that's what's called a second order assertion. Dedekind arithmetic is a theory that's expressible in second order logic, and it's not, in fact, expressible in first order logic. In other words, it's not expressible by principles that only quantify over the individuals. We really do need to quantify over sets of individuals in order to attain this categoricity result.
▶︎ 52:50 That's a consequence of the developments that arose much later on in the 20th century in model theory, and in the development of first order logic. For example, the Löwenheim-Skolem theorem says that no first order theory, a theory that's expressed by quantifying only over individuals, can properly define the notion of finiteness. Because every theory that has a model also has models of arbitrarily large size, uncountable size. And similarly, the Skolem paradox is really at the core of that, which shows that, if the models of set theory, if the axioms of set theory are consistent, then there's a model of set theory that is countable, and that, for example, other models of set theory that are wrong and disagree with the notion of finiteness and so on, and all of these kind of intricate counterexamples show just how delicate and difficult it is to express the concept of finiteness.
▶︎ 53:45 So it's no surprise at all that our account of the finite numbers in Dedekind arithmetic's theory was a second order axiom. And in fact, this is definitely required for any such successful notion of defining numerically finite.