Set Theory (Part 7): Natural Numbers and Induction
Вставка
- Опубліковано 3 січ 2025
- Please feel free to leave comments/questions on the video and practice problems below!
In this video, I discuss the von Neumann construction of the natural numbers and relate the idea of natural numbers to inductive sets. The axiom of infinity is also introduced here as one of the ZFC axioms.
YESYESYES, it's 1:40 a.m. and i'm extremely happy to find you and this quality, detailed explanation!
One thing to keep in mind when seeing these set theoretical definitions of natural numbers the first time is that these are supposed to be cardinality. So, the empty set has cardinality 0 since it contains nothing, and the set 1 = { {} } has cardinality 1, since if you took a cup and stacked a cup inside that cup then you have a set that contains a cup. But the cup contains nothing. So this is how these cardinal definitions work, *however* there is still the intuitive notion of the natural numbers based on *sense-perception* in order to come up with this set theoretical definition of natural numbers. So, *in many ways these definitions do not explain where the natural numbers come from or why they are the way they are.* What they *do* is provide a logical foundation for the study of size of number systems, and give us a means to construct the real and complex numbers later on. The idea is, as long as our intuition is correct about natural numbers, then the construction of real and complex numbers has to follow logically; this is the logical conditional, ie. "if then statement" that set theory allows us to make.
One more neat thing is that we can prove cardinalities by putting sets into one-to-one correspondence with the natural numbers. The idea being that if you have a set of 5 toothpicks and a set of 4 toothpicks, then because you can't put these two sets into one-to-one correspondence then one must be larger than the other. So the set of 5 toothpicks is greater than the set of 4 toothpicks. This is the reason why the even natural numbers have the same cardinality as all the natural numbers, as do the rationals, but the reals do not. Therefore the reals are larger than the naturals, and etc.
We call any set that can be put into one-to-one correspondence with the natural numbers "countable" so therefore the set of real numbers is "uncountable" since it can not be put into one-to-one correspondence with the natural numbers.
We call any infinite set "infinite;" any set that obeys the induction principle is infinite, so therefore the natural numbers are infinite. Therefore any set that can be put into one to one correspondence with the natural numbers are also infinite. So we call such sets "countably infinite." Any set that can not be put into one-to-one correspondence with the natural numbers is either countably finite (if smaller) or uncountably infinite (if larger). Thus the real numbers are uncountably infinite since they are larger than the naturals.
The Axiom Of Infinity (by words, based on Wikipedia): "There is set A
(the set which is postulated to be infinite), such that the empty set is
a member of A, and such that whenever any x is a member of A, the set
formed by taking the union of x with its singleton {x}, is also a member
of A."
Please pay attention that given any A successor, it is finite since it
is constructed exactly by all the finitely many previous A members, by
induction.
But there is nothing in induction that guarantees infinitely many
members in A just because it is our wishful thinking, so no axiom that
is based on induction guarantees infinitely many members.
For example, let's take N (the set of natural numbers).
The inability to show some n that is not already a member of N,
can't be used alone in order to conclude that N is a complete and infinite set,
exactly because the inability to define the biggest member of N, also must be considered.
Since the biggest number of N does not exist, |N| accurate value is actually undefined.
It is claimed that order is irrelevant in case of sets, but it is easily
understood that order does not change the cardinality (the number of
members) of a given set, so the inability to define the biggest member
of N has a direct influence about its cardinality and in the considered case
|N| accurate value is actually undefined.
What is that "clicking" sound I hear every couple seconds? I thought it was an off-screen remote but it sounds like you're smacking your lips.
what a great video, thank you so much
At 20:20 Is a circular definition for set A allowed (since A is defined in terms of itself!)?
+Theo vdW
Let me look into this since it's been a while since I made this video. At first glance, the set does exist by the subset axiom because it's just some subset of natural numbers.
I also have been thinking about this, and like to share my thoughts with you. A predicate \phi that is used to construct a subset from another set should have 1 free variable, x say. Then the subset is defined as {x \in superset | \phi(x)}.
In this example, there is a second free variable: a. So we have a predicate \phi(a,x). Then the expression defining the set {x \in \Natural numbers | \phi(a,x)} still has as a as a free variable. So then a = {x \in \Natural numbers | \phi(a,x)} is an equation in variable a, and the question would be: does this equation have a unique solution?
But wouldn't it be sufficient to have the predicate \phi(x) = x=0 \lor \exists_y x=y+ ?
Thnks a lot!
But id like to ask you,
By definition, natural number is a subset of 'every' inductive subset's'.
And could you tell me another example of inductive subset except the set of natural number and prove that it has a subset which contains all natural numbers?
Thanks a lot. Ive been really enjoying your videos so much!
Any limit ordinal is an inductive set (e.g. ω+ω). The set of all natural numbers is *defined* as the intersection of all inductive sets (this set exists by the axiom of separation), so any inductive set contains natural numbers as a subset.
Another excellent lecture!
In this video I can't shake the feeling that the Axiom of Infinity and the theorem of the existence of the set omega are circular. So we are saying that inductive sets exist, and the set of natural numbers is one particular inductive set. It only appears we are saying something new when we define a natural number as a set belonging to all inductive sets. But don't all the possible inductive sets originate from the infinite set of natural numbers? After all, we constructed the natural numbers using the empty set and the idea of the successor. All that is left is to say is that this can continue infinitely and put that down as an axiom. It seems that we might just take the existence of natural numbers as an axiom.
Watching this lecture series answered many question I had about set theory. Before I started I had only the Venn diagram notion of it, but now I have a good idea of what set theory is about. Also it has clarified for me where I might stand on the question of whether mathematics is discovered or invented. I am leaning toward the view that mathematical objects and relations are definitely not discovered in the sense that we are uncovering Reality as it really is. We do relate to it but through our human interaction with it. Given this then, it seems to me it is no longer such a problem, as it was with David Hilbert and others, to live with the fact that we can't have certainty, or that we can't have a complete axiomatic system, or that a consistent axiomatic system can't prove its own consistency.
Again, thanks so much for your excellent lectures! I have learned a lot and thought about the meta-mathematical questions in a more coherent way. I will look forward to the rest of your set theory lectures. I wish you success to all your future endeavors!
John Ok Glad you enjoyed the video. I wouldn't say that the existence of the set of the natural numbers is construed in circular reasoning for the reason that if you accept the axiom of infinity, which asserts that there is at least one inductive set, then it's demonstrable that the set of natural numbers exists. Also, you could imagine having an inductive set with objects that aren't natural numbers, so all inductive sets house the natural numbers but can have more stuff in them besides the natural numbers. This is true because for inductive sets, we need the empty set and for all the elements, we need the successor in that set. But since the definition of successor is sufficiently abstract, we could have a set that looks like this (call it A and let ' mean the successor) A = {0,1,2,3,....,Bieber, Bieber',Bieber'',...}. This is admittedly bizarre but it is still well-defined since if you have Bieber, then Bieber' is just Bieber unioned with {Bieber}, and so on. I guess you could just take the naturals as an axiom and I don't have a good motivation for first positing the axiom of infinity then extracting the naturals, but perhaps one might want to use the idea of induction for objects which aren't natural numbers, perhaps "Biebers" (but I haven't thought about that point before).
John Ok In case you're ever bored, check out this channel: njwildberger. He's got some great stuff on mathematical foundations plus some criticism of things like infinite sets and other non-intuitive mathematical objects.
mdphdguy1 (Darn, I forgot to click "Reply" and have to write this reply again!)
I did think about whether inductive sets could be sets of objects. I wasn't sure because you talked only about numbers in the video. I thought since physical objects are finite in number, how could they form an inductive set? Also, what would Bieber' or Bieber" and so on mean? It would be just the successor operation generating the next thing and the next thing. So I restricted myself to numbers.
I did think that the infinite set of natural numbers is just one among all the possible inductive sets. So it seems more logical to posit the existence of an inductive set, namely, the Axiom of Infinity, and then derive the existence of natural numbers through a theorem. But I asked what is the difference between the infinite set of natural numbers and any other inductive set, limiting myself to numbers. For example, the set of all prime numbers. The numbers are constructed using the empty set and the union axiom, so that's the same. The subsequent elements are generated using the successor operation under the conditions imposed (in the case of the set of prime numbers, the condition is the prime numbers), so that's the same. That the generation of subsequent elements can go on endlessly, that's the same too. So I thought why can't we simply put it down as an axiom that the successor operation doesn't have to come to a stop? But then I just looked at the axioms that you covered in Part 2, and I see that they all have to do with sets. And the axiom I propose would not be directly related to sets.
Anyway, I feel I must be missing something here, but it made me think, and that's what's important, right? Thanks again for your detailed responses.
(Man, I wrote this reply under the wrong response. Sorry about that.)
I will check out the channel. Thanks a lot.
John Ok Of course, we're getting into philosophical ground when considering whether a set of physical objects could form an inductive set, but I would object because the "empty set" and "successor" don't refer to anything physical. But one thing to point out is that the set of primes isn't inductive because the set of primes is a subset of the naturals and the smallest inductive subset is all the naturals.
Lectures excellent, Thank you.
The Sound of the voice in each video is a bit annoying. It sounds like a bubble coming from beneath a water tank. It bothers me when I listen to the entire video.
I was just going over my notes again and I don't completely get the following. You define that a natural number is a set which belongs to every inductive set. An inductive set, by definition, has the empty set and other members that are generated by some successor function. So I understand that some or all natural numbers will be found in every inductive set, at the least the empty set, i.e., zero. But then you go on to say that the natural numbers are a subset of all inductive sets. By this do you mean that the complete infinity omega, that is, the infinite set of 0,1,2,3,... is found in every inductive set? The set of positive even integers, that is, 0,2,4,6,... is an inductive set, but ALL of omega is not in there, is there? I know that Cantor showed us that the cardinality of these two sets here is the same, namely, aleph-null, because the members of the two sets can be paired with one-to-one correspondence. But this is not what you mean? Also, in those inductive sets whose members are objects, not numbers, where is the infinite set of natural numbers there? I would appreciate it if you could clarify this point.
John Ok Sorry, I should have re-read your replies that were posted three weeks ago. You said that the set of natural numbers is the smallest inductive set; so, that would mean that the set of positive even integers is not an inductive set. I am equating "inductive set" with "infinite set." Is that wrong? But why isn't {0,2,4,6,...} inductive according to your definition? It has the empty set and a+ is a+2; that is, the successor function is adding 2 to each predecessor.
John Ok Certainly all inductive sets have to be infinite but the even integers wouldn't be inductive because, as one counter-example, 0 is in the set, but 0+ or 1 is not. In addition, the statement "{0,2,4,6...} is inductive" is in contradiction with "omega is the smallest inductive set". What I think you're getting at is the set of even numbers, with this new successor function, is isomorphic to the natural numbers. That is, this set equipped with the zero element and this new successor function of adding two, is a Peano system. Also, the set omega is as a whole is not a natural number (it would have to be included in itself, haha), but each of omega's elements have to be found in all inductive sets. It doesn't matter what inductive set you give me, but it must have the elements 0,1,2,3... in it.
John Ok Also, I'm speaking loosely when saying "smallest" inductive set. As you say, omega and the set of evens have the same cardinality, but clearly the evens are a subset of the natural numbers.
Proofs by induction can be so powerful, they almost feel like cheating