You are a brilliant teacher. In the span of 15 minutes, I have shifted from a state of mind where I thought I might never be able grasp this concept (or want to), to a sense that it is very possible and coherent.
I have listened more than 100 teachers who are trying to teach this topic and this lecture is the best by far. Thanks for fast and clean lecture you are the best!
Wow, I can't say how thankful I am. My final is in a couple of days, and even though my professor just taught cardinality to us, it's expected to cover 25% of our exam. Now I can walk in more confident that I at least have a 25% lol...
0 is an element of the set of Natural numbers. Therefore, to test for countability, you should look for a one-to-one correspondence with the set of positive integers, Z^{+}, which is {1, 2, 3, ...}, i.e. what Rob defines to be the set of Natural numbers. Note that you could also look for a one-to-one correspondence with the Natural numbers, that is including the 0; just be cautious as to how you define the set you're comparing with, as it might cost you points.
I was a bit confused, wondering why an infinite set may be countable or uncountable. This helped a lot. It clicked in my brain hahaha. I love it when that happens.
This is very well done, you explained with utter most clarity. Thank you so much. @Robert Allen: I would suggest you review a course on Real Analysis to understand the Q-set
I was curious about this question so I did a little research and found a good explanation here. Note: The parentheses are the "greatest integer" symbol - in case you plug in values for n into the function and it seems like the output would be a fraction.(That's what happened to me at first.) Below is the link. math.stackexchange.com/questions/7643/produce-an-explicit-bijection-between-rationals-and-naturals
This is the first time i fully understood the Cantor's argument. So many bullshyt big words in analysis books that u get lost in that and never understand the damn thing that the book is actually written for....thanks mate.....
may i know the function that fulfills the criteria of f:Natural number -> rational number? f:Natural number -> integer can be fulfilled with (n/2) for positive value and -((n-1)/2) for negative value correct?
Hi +n ct, unfortunately it's not possible (as far as I know) to find a neat way of writing a bijection from the natural numbers to the rational numbers like you can with the integers. It's only possible to show (as I did in the video) that there is a systematic way of counting them. See this link for more info: mathforum.org/library/drmath/view/54199.html
This way of showing that you can match any size of infinite sets as long as they are countable using the natural numbers is known as a bijection. There is a stronger way of looking at the difference in sizes of infinite sets though. If we are considering two sets that contain the same elements, then we are allowed to discard all of them (because they are identical). This will leave all the elements that are not identical in both sets. If this clears the picture because one set is now empty and the other is not, then the nonempty set is bigger. This principle is called PW (part-whole) and was considered important by Galileo and Brentano. This fact leads to a contradiction if we consider equality of the two types to be the same. We don't have to do that though, we can only notice that PW is stricter than bijection, but is also a different size measure, just as you can measure size of sets into only two categories, finite and infinite, which is fine, just not as precise a measure of size as you would probably like. Using PW on the sets of N and Q, we can see that Q is strictly bigger, since it contains elements that are not in N, while N contains no elements that are not in Q (comparing values). So, if you use PW, you get a more precise way of comparing infinite sets than infinite bijetion. This is also clear if hyperreals are used as a measure of size, since they show a natural way of having size ordering between all hypernaturals (infinite sets of elements, the set of natural numbers plus or minus finite or infinite numbers of natural numbers).
@RobShone there is a problem with your argument for the reals. lets suppose after you make your list of real number decimals, the diagonal sequence comes out to be .088888... Now if we add 1 to each number of these numbers we get .199999... . but this is equal to 0.2 , now the contradiction does not work. we constructed a number that still could be in our list since 0.2 could be in our list.
+xoppa09 that's a good point. Another approach will avoid this problem, let's take xn = 5 if a(n,n) is not and xn = 7 if a(n,n) = 5. Now the argument works even in special cases like the one you describe. That proves the theorem.
Cut N in four infinite subsets. First of them is used to create a relation one to one between it and all possible finite subsets of N. This is possible thanks to my function based on the abstract concept called CLJA. But we dont stop here: with the CLJA (with just blue holes) we can assign L naturals to each possible finite subset of N. The second subset is just for add another argument... we pass of it for now (too large). The third subset (because we can assign three naturals to each finite subset) is to try this: assign one unique natural to each element of each possible infinite subset of N. If one element appears in two different subsets, it must have two differents naturals ok? Combining two different CLJAs we can do it in a brutal way. Ee really dont do that, we create infinite combinations of disjoint and unique naturals to each possible infinite subsets of N, for each possible case of “conflict”. For each possible case if conflict we can create an infinite subset (disjoint with anothers) to that particular case. The trick is we cant reach the case of infinite conflicts, because twi infinite subsets with infinite conflicts, are really the same subset. If we combine three CLJAs is a so big stuff that im still trying to figure out what it really means.. So P(N) is countable... and R is countable because they have the same cardinal. Is just a little exposition... and my english us not very good. But the functions exists and I have programmed them. The CLJA is an abstract trick that help us to create the functions. I am a programmer, not a mathematician, so the only proobe i can offer is the really simple theory about it and the check fir the first 10 000 000 million naturals not matching the same finite subset. (combination is impossible to represent easily, but CLJA is a really simple concept,and its properties are easy to see) I Know you think I am probably making a mistake in somewhere, or i am dont know really what im doing... but a function is a function, and its results are its results. Now a day, I can say the natural assigned to any finite subset. And the natural assigned to: The element e, when it belongs to the infinite subset ci1, when the value of k is x (k is the level of conflict that can not be infinite... not because i say it, because in that case we are talking if the same infinite subset). For each value of k, i have an infinite list of naturals for each infinite subset of N. If a list appears in one level, it does not appear in another level. Ni naturals repeated between levels, inside the same level,or with the other subset we use to “count” the finite subsets. And finally... all infinite subset are diferents... is impossible to find a level of conflict (list of elements repeated from the beginning if we put them in order) when i cant calculate a new, unique and infinite list of naturals for each possible infinite subsets. If you find two infinite subsets with a level of cnflict bigger... The same set of functions let you calculate a new list for each one. And that just combining two CLJAs... in the third level of combination... is like each element has the naturals enough to solve itself all the conflicts of all infinite subsets... but im working on it..
+xoppa09 the reason is because the set could be bigger if you allow it. N is certainly bigger than {0,1} but I can make a surjection from N to {0,1}, by saying f(n) is 0 if n is even and one if n isn't. Now I have infinitely many repeats, but the sets aren't of the same size. If you can make a surjection f: X->Y than the cardinality of X is bigger or equal to Y, that's not as strong a statement as saying the have the same cardinality, what you can conclude if f is a bijection.
Ive never understand the meaning of the fact that i can find a new number that wasnt on the list. I can also find a new number in the natural numbers that werent on the list, as well as integers, if i follow the same rules
also the last part i did not follow. you showed that (0,1) is uncountable. how do you get that R is uncountable. i guess you could argue, if (0,1) is uncountable, how much more so (0,1) plus extra elements is uncountable (the rest of R).
+xoppa09 well R must have at least the same cardinality as (0,1) as that is a subset of R. To show they are the same you should give a bijection between R and (0,1). This is where the inverse tangent function comes in. Take f(x) = taninv(pi*(x+1/2)), this is a bijection between (0,1) and R(check it yourself), hence (0,1) and R have the same cardinality.
+dekippiesip Hmm, this sounds as if you know a bit more about this topic. Maybe you can answer my question: Why can't I just have the following correspondence between N and R[0..1] ? 1 -> 0.1 | 53 -> 0.53 | 7428583 -> 0.7428583 | 14159265... -> PI - 3 This way, ALL of the real numbers between 0 and 1 are linked to the natural numbers. I can not find a real number, that is not in that list. The proof at 5:00 only gives you a number, that has yet not been on the list, but will be eventually...
Lord Balder obviously you only cover rational numbers, since the decimal expansion terminates at some point. You gave pi-3, but that is not an example, since the number 14159265..... must be infinity(pi has infinitely many decimals), so that 'number' is not a natural number itself. Hence, your bijection doesn't cover irrational numbers. So it is no bijection. The proof of 5:00 gives you a number that is no where on the list. Since the nth decimal of that number is different from the nth decimal of the nth number on your list per definition. So for eery n, your number differs in at least one decimal place with my number, therefore it isn't covered.
dekippiesip And that is exactly what I do not understand. 14159265... is infinity, but it should be still within the natural numbers, no matter how many digits you add. If that is not ok, then I do not even cover the rational numbers, since they can also have infinit many digits when written in decimal, like 1/3. With the proposed bijection, for every digit you add, there are 10 times "more" real numbers you get, which gives you something like (10^digits) entries in the list for every digit you complete. So if you get a number which is different in the 100th digit from all previous ones, this one will appear within the first 10^100 entries of the list. And if you go down the to that one and cover all 10^100 digits, you will get a number thats on the list within the first 10^100^100 entries. With infinite many digits, you only get an infinit large integer, but you will get one!
Hi +Lord Balder , I can see your argument, but in order for a set to be countable it must be possible to associate a *finite* natural number with any given member of that set. Using your proposed bijection, it wouldn't be possible to find a finite natural number for pi-3. You can't just say "if we were allowed to count far enough, we would count it eventually", because in fact that's not true - no matter how far your sequence goes, you will only ever get numbers with a finite (terminating) decimal representation, therefore you will never reach pi-3 since it has an infinite decimal representation. Hope that's clear!
What on Earth is dark numbers? Just because a specific function from natural numbers to rational numbers does not cover all rational numbers, that doesn't mean that no function does. You could have used the same "proof" to show that since the function n->n+1 or n->2*n does not cover all natural numbers, the set of all natural numbers can't be mapped one-to-one with itself. (Observe that the two functions are one-to-one functions between natural numbers and a strict subset thereof. That's something that you need to get comfortable wiy In another post, you define "dark numbers" as the set {0,ω}. How is this relevant? ω is not an element of the set of all natural numbers; ω *is* the set of all natural numbers. (In set theory the convention is that ω - the set of all natural numbers - includes 0.) The set {0,1,2,...,ω}=ω∪{ω} obviously can be mapped one-to-one with natural numbers (or with positive integers). The proof by induction works as follows: Suppose P(0) is true. Suppose the following is true for all natural numbers n: if P(n) is true, then P(n+1) is true. Then P(n) is true for every natural number (every element of ω). This *does* imply that P(0) is true - and it does so trivially, because P(0) is already taken as an assumption ("if P, then P" is always true). But it *does* not imply that P(ω) is true. In other words, you can't conflate the following claims: "P(n) is true for every finite case" and "P(n) is true in the infinite case". (As I have said, conflation of the two statements is the mistake that I like to call "magical induction", which could as well be used to prove that the set of all natural numbers is finite.) So: let f be a one-to-one function from a set of all natural numbers to a strict subset of some set X. Changing the value of f(n) for some natural number n will not produce a bijection between natural numbers and X. By induction, changing no finite number of values will produce a bijection between the two sets. But that *does not* prove that natural numbers can't be mapped one-to-one with X. As I have said, let f be the function n->n+1 (or n->2*n) on natural numbers. Do you think that this proves than the set of all natural numbers can't be mapped one-to-one with itself? The only thing this proves is that if natural numbers can be mapped one-to-one with the set X, then the bijection differs from f at infinitely many positions. (Induction *does not* prove that the proposition is true in the infinite case. It *does not* prove that just because changing finitely many values of the function will not produce a bijection, changing infinitely many values won't produce a bijection either. Observe that the real bijection - n->n - differs from each of the two functions at infinitely many positions.)
@@MikeRosoftJH Sorry, you have not understood, as I see from your commetn that {0,ω} is the set of dark numbers. That is completely wrong. Fact is this: All natural numbers can be removed collectively from {0,1,2,3,...,ω} with the result {0,ω}. (He does not count 0 as a natural number.) But all definable numbers n will leave infinitely many elements {0, ..., n+1, n+2, ..., ω}. That is the important difference between definable and dark. Sorry, your sentence "It does not prove that just because changing finitely many values of the function will not produce a bijection, changing infinitely many values won't produce a bijection either" is not acceptable in case of Mueckenheim's proof. He shows that for all infinitely many exchanges (not only for finitely many) the share of not indexed fractions remains constant. To believe that this would differ "in the infinite" is not a mathematical argument.
@@undercherries4659 I ask you once again: how does your supposed proof not apply to the functions n->n+1 or n->2*n on natural numbers? Would you claim that the set of all natural numbers can't be mapped one-to-one with itself? Obviously, you don't understand how natural numbers are defined in set theory, or what "finite" means. All natural numbers are finite; that's true by definition - a set is finite, if its number of elements is equal to some natural number. And ω is neither a natural number, nor a successor of some natural number. You claim that "All definable numbers n will leave infinitely many elements {0, ..., n+1, n+2, ..., ω}." That's inaccurate. Every natural numbers n will leave infinitely many elements - period. (Again, you are conflating the statements "P(n) is true for every natural number", and "P(n) is true for the set of all natural numbers as a whole".)
@@undercherries4659 Let's explain how natural numbers are defined for real. In set theory, the convention is to define natural numbers as follows: 0 is the empty set, 1 is the set {0}, 2 is the set {0,1}, 3 is the set {0,1,2}, and so on - any natural number is a set of all numbers less than itself. Observe that any natural number n is an n-element set, and the set n+1 is obtained by taking the set n, and adding n itself to it as an additional element - n+1=n∪{n}. (This set exists by the axiom of pairing and axiom of union.) Set theory has the axiom of infinity, which essentially says: "There exists a set containing all natural numbers." Precisely, the axiom says: there exists a set Ω, which has the following properties: 1) 0 (the empty set) is an element of Ω; and 2) for every element x, if x is an element of Ω, then x∪{x} is also an element of Ω. (Not: in set theory as usually axiomatized, all elements are themselves sets - there are no other objects than sets.) Now ω - the set of all natural numbers - is defined as follows: ω is the intersection of all sets that satisfy the axiom of infinity. That is: Let Ω be some set that satisfies the axiom of infinity; then ω is a set of all elements that have the following properties: 1) n is an element of Ω; and n is an element of every set that satisfies the axiom of infinity. (This set exists by the axiom of separation.) Observe that 1) the set ω is well-defined - no matter what set Ω we start with, we get the same result (by the axiom of extensionality - two sets are equal, if and only if they have the same elements), 2) ω is non-empty (for example, it contains 0); and 3) ω itself satisfies the axiom of infinity. Why are natural numbers defined in this way? So that the principle of induction is true for the set ω. Let P(n) be some proposition. Suppose P(0) is true. Suppose for every element of ω the following is true: if P(n) is true, then P(n+1) is true. Then P(n) is true for every element of ω. (Consider the set of all elements of ω for which P(n) is true: ω'={n: n is an element of ω and P(n) is true}. Obviously, ω' is a subset of ω. But observe that this is a set that satisfies the axiom of infinity; so by construction of ω every element of ω is an element of ω'. It follows that the set *is* in fact the same set as ω; in other words, P(n) is true for every element of ω.) From this principle, it can for example be proven that no two different elements of ω can be mapped one-to-one, and no element of ω can be mapped one-to-one with ω. We now define: A set is finite, if it can be mapped one-to-one with some element of ω. Again, it can be shown that every subset of ω is either finite, or it can be mapped one-to-one with ω. But again - and this is what you fail to understand - just because a proposition is true for every finite case, it doesn't mean that it is true for the infinite case as well. In other words: Suppose P(0) is true; and suppose for every element of ω the following is true: if P(n) is true, then P(n+1) is true. That does not mean that P(ω) is true; an obvious counter-example is: "n is finite".
Using the method employed, the conclusion is not a contradiction. You are assuming a square grid can contain all the elements of the list. This is impossible for the same setup with the same intuitive concepts applied. Take the complete list of a binary form, that forms a length of 1: List: { 0 1 } This is a complete, finite, countable set. List size is 2 ........................ Construct a square grid, why? because a grid that is infinity wide and infinity long is used to intuitively conclude a contradiction. Now assume that the grid can be populated with all the elements from the complete list. Because this is what we want to use as a contradiction ??? Ok ... Grid [1x1]: { [ 0 ] } We can see that the grid does not hold the complete list. The grid can only hold the same number of elements as its equal dimensions allow - and, 1 does not equal 2. What list does it hold? list composed of the elements of G: { 0 } Maybe taking an altered diagonal, d, will prove the contradiction that ... a square grid can contain the completed list. well, d = 1, which is clearly not contained by the grid itself. Well, we have proven that a contradiction exists ... therefore it is impossible to make a list at all? ................................. Maybe we just need to grow the grid size, the bigger the grid the more that will fit? Lets use the same binary components, but increase the length of an element to 2. List: { 00 01 10 11 } Construct a 2x2 grid and populate it with any arbitrary elements from the list. Grid [2x2]: { [ 0 1 ] [ 1 1 ] } Well the grid can only hold 2 elements of the list ... but lets assume it can hold all of them for some reason. List composed of the elements of the grid: { 01 11 } Make the altered diagonal, d = 10, This does not match any element in the list that was composed from the grid. Therefore we conclude that a complete list is impossible to make. ..................... These 2 examples for the smallest set, and the next smallest set, form an inductive proof that there exists NO square grid that can contain a complete, countable list using this method. We assume a square grid, and a countable list, and prove that the results are the same for all results; but then claim a contradiction exists when we obtain the same outcome?? ........... Considerations: Why a square grid? because that is defined by Cantors setup; assume the length of each element is countable, and assume the number of items listed is countable and complete. Spose we use a nonsquare grid. More columns then items, the diagonal produces an element that is not on the list to start with, its not long enough. Maybe we alter the length? but that is not a step in the method, only alterations to the digits are expressed; length remains the same. More items than columns? Then the diagonal has the same length, but it clearly will not effect all the items of the list. Maybe we list the items top to bottom instead of left to right? Then what does trying to add to the bottom of the list represent? It adds nothing to the list, and just changes the length of each item instead. Hence, the properties being addressed represents a square grid - with a list of elements of equal length.
The diagonal argument _does_ apply to finitely many digits, but you have to interpret the results _reasonably_ and not have a kneejerk reaction that doesn't make sense. For binary strings with n digits, there are clearly 2^n such strings, since we have 2 choices for each digit. Then, any list consisting of exactly n n-bit strings is incomplete, which shows that 2^n > n. It seems a bit silly to use this argument in the finite case, since we're used to working with ordinary arithmetic of finite numbers, and we have many ways to prove 2^n > n for finite "amounts" that are more in line with how one would try to show such a thing. What Cantor's Diagonal Argument shows is that 2^α > α is _still true_ even when α is infinite in value. Because there are still 2^α α-bit binary sequences (two choices for each element), but assuming that there are α-many α-bit binary strings leads to a contradiction - we can always construct an α-bit binary string not in our "list". So, just like in the finite case, we can conclude that 2^α > α. Why would Cantor need to imply such an argument? That's because things like 2n > n are true for finite n, but 2α = α is true for infinite "amounts of elements". So the ordinary arithmetic proofs don't work, and we need a different approach. Plus, it's a very common gut instinct that "all infinite sets are the same size," so it's not at all obvious that 2^α isn't just equal to α for infinite α. So there really is something to prove here, and Cantor's Diagonal Argument is a brilliant way to do this.
We can't assume we have a complete list of numbers, because we have posited the listbis infinite. We posit the set is infinite, and therefore is unending. To complete a list which is unending is not possible. To posit that you have a set which is an infinite, and posit that set ha been completed is a contradiction in the premises. Cantor did this with 3 proofs, and for some reason we are about 150 years later, and I'm the only person spotting this contradiction? #mathematiciansrdumb
Snatch n Grab, I have to agree totally that more critical thinking is needed here than to take Cantor's diagonal proof on face value. Here is one way to show it is flawed: The proof starts with the assumptions: 1) an exhaustive list of real numbers and 2) there is a bijection between this list and the natural numbers. Near the end, the orator tries to show that he found a new real number not in his exhaustive list and that real number does not have a partner in the natural numbers. So... did he or did he not have an exhaustive list of the real numbers at the start??? Obviously, the new-found real number existed somewhere on the real number line before the orator started the proof; he just didn't know about it. Suppose that he did manage to get the exhaustive list, then by assuming there is a bijection, he has already assigned a natural number partner to this real number that he didn't know about. But near the end, he contradicts this assumption by saying there is no partner for this new-found real number. WTF!!! In other words, if it is actually an exhaustive list, then the new-found real number is already on the list and there is a partner for it. Many on the Internet try to praise how simple and powerful this proof is, and how amazing that it can be done in less than 5 minutes. But what I think is that recycling this proof is one sure way to confuse and contradict oneself in less than 5 minutes.
Marvelous Whiskers That's generally how a proof by contradiction works, though. But when a new real is generated, it shows the unsound nature of the assumption(s), which is quite easily noticeable as saying the natural numbers were exhausted, finished, i.e. finite. Whatever real generated by the diagonal method can be paired to the next natural number. The Cantor Camp, if I may say that, always says, "but we used up the naturals", and I say, "no, you only asserted that you did, such a thing is not possible". The one to one correspondence can continue with nothing hindering it. Which then leads us to something entirely overturning that no one wants to hear it... bijection is not a tool to show size of sets, only density. We could then rephrase math so that density and size of sets are the same thing. This is not the case now, which births our current Hierarchy of Infinites and the Continuum Hypothesis. However, if that was accepted, we would then rebuild the hierarchy. The infinite set of odd natural numbers would be half the size of the infinite set of all natural numbers. The infinite set of reals would be infinitely more dense than set of naturals. Set theorists would still have a monkey to play with, the Continuum Hypothesis would be resolved, and we could make statements like "half of all natural numbers are evenly divisible by 2" AND provide a proof (which is currently proven to be impossible to prove or disprove with current maths, even though we know it's true).
Snatch n Grab, Yes, I think we are basically saying the same thing about this proof: that the assumptions are questionable and the orator is ignoring them by the end. I personally think the reals are countable, maybe not by conventional methods, but nonetheless maybe some other way. True or false, I do agree that Cantor's method and our current understanding of infinity is insufficient.
Marvelous Whiskers Hopefully we can find out in our lifetimes. I started with a Single Cardinality of Infinites Conjecture, but I felt that should be scrapped because I am learning that even though Cantor's mistake is quite obvious, we still have a use for the hierarchy. Thus I am moving to cardinality based in density. If I win a Nobel prize, I'll post a video.
I agree with what you both say. Would it be fair to say R is countable by: +- {d ; .d dd ; d.d ; .dd ddd ; dd.d ; d.dd ; .ddd dddd ; ddd.d ; dd.dd ; d.ddd ; .dddd . . . } where d is a digit 0-9. And just like showing Q is countable, not include any repeats. Does that work?
You are a brilliant teacher. In the span of 15 minutes, I have shifted from a state of mind where I thought I might never be able grasp this concept (or want to), to a sense that it is very possible and coherent.
I have listened more than 100 teachers who are trying to teach this topic and this lecture is the best by far. Thanks for fast and clean lecture you are the best!
this is by far one of the most clear explanation/tutorial i have seen on youtube! thank you!
After 8 weeks I think I finally understand, and not only understand the difference between countable and uncountable, but how to prove them as well.
Excellent. As Mr Burns would say
ive been reading my textbook and watching videos for days, but only this video made it click. thank you.
Easiest cardinality video to understand thanks man
Wonderful way to explain something my teacher failed to do in class. Many years later still helping the undergrad math majors!
This is extremely clear, I understand this more than my textbook! Thanks a ton! :)
This is clear quality explanation. Thank you!
Thank you!!!! I thought no one would be able to teach discrete math in a clear concise way.
excellent explanation. My textbook is so dry and overblown it's barely readable. You actually make the lesson clear and concise. Thank you.
I watched this video 3 times this year. Such a good video
Wow, I can't say how thankful I am. My final is in a couple of days, and even though my professor just taught cardinality to us, it's expected to cover 25% of our exam. Now I can walk in more confident that I at least have a 25% lol...
Hello! I have learnt a lot today from your tutorial. Am grateful for the knowledge i have acquired
and may you be blessed more.
wow. thumbs up. I watched 5 videos about this topic, you your explanation is the best! Good Job. Cheers
very clear explanation
Wow, so well and clearly explained.
0 is an element of the set of Natural numbers. Therefore, to test for countability, you should look for a one-to-one correspondence with the set of positive integers, Z^{+}, which is {1, 2, 3, ...}, i.e. what Rob defines to be the set of Natural numbers. Note that you could also look for a one-to-one correspondence with the Natural numbers, that is including the 0; just be cautious as to how you define the set you're comparing with, as it might cost you points.
Thanks a lot for this video. It helped me to get my head around countability and uncountability.
Thank you thank you thank you! So clear and easy to comprehend!
Thank you so much! This explained it so well, I was stuck. MY MAN.
you just made my work very easy now i can complete my assignment !!!! THANK YOU
Very easy to understand this......by your lecture.......
That was fantastic . Thanks!
I was a bit confused, wondering why an infinite set may be countable or uncountable. This helped a lot. It clicked in my brain hahaha. I love it when that happens.
This is very well done, you explained with utter most clarity. Thank you so much.
@Robert Allen: I would suggest you review a course on Real Analysis to understand the Q-set
how are 1 to 1 correspondence going on between natural numbers and intergers? means what function is used?
I was curious about this question so I did a little research and found a good explanation here. Note: The parentheses are the "greatest integer" symbol - in case you plug in values for n into the function and it seems like the output would be a fraction.(That's what happened to me at first.) Below is the link.
math.stackexchange.com/questions/7643/produce-an-explicit-bijection-between-rationals-and-naturals
This is the first time i fully understood the Cantor's argument. So many bullshyt big words in analysis books that u get lost in that and never understand the damn thing that the book is actually written for....thanks mate.....
brilliantly explained!
very clearly explained. thank you.
Please can you show how to write the closed formula for an injective mapping f: Q into Z or f: Q into N
may i know the function that fulfills the criteria of f:Natural number -> rational number?
f:Natural number -> integer can be fulfilled with (n/2) for positive value and -((n-1)/2) for negative value correct?
Hi +n ct, unfortunately it's not possible (as far as I know) to find a neat way of writing a bijection from the natural numbers to the rational numbers like you can with the integers. It's only possible to show (as I did in the video) that there is a systematic way of counting them. See this link for more info: mathforum.org/library/drmath/view/54199.html
This way of showing that you can match any size of infinite sets as long as they are countable using the natural numbers is known as a bijection. There is a stronger way of looking at the difference in sizes of infinite sets though. If we are considering two sets that contain the same elements, then we are allowed to discard all of them (because they are identical). This will leave all the elements that are not identical in both sets. If this clears the picture because one set is now empty and the other is not, then the nonempty set is bigger. This principle is called PW (part-whole) and was considered important by Galileo and Brentano.
This fact leads to a contradiction if we consider equality of the two types to be the same. We don't have to do that though, we can only notice that PW is stricter than bijection, but is also a different size measure, just as you can measure size of sets into only two categories, finite and infinite, which is fine, just not as precise a measure of size as you would probably like.
Using PW on the sets of N and Q, we can see that Q is strictly bigger, since it contains elements that are not in N, while N contains no elements that are not in Q (comparing values). So, if you use PW, you get a more precise way of comparing infinite sets than infinite bijetion. This is also clear if hyperreals are used as a measure of size, since they show a natural way of having size ordering between all hypernaturals (infinite sets of elements, the set of natural numbers plus or minus finite or infinite numbers of natural numbers).
@RobShone
there is a problem with your argument for the reals. lets suppose after you make your list of real number decimals, the diagonal sequence comes out to be .088888... Now if we add 1 to each number of these numbers we get .199999... . but this is equal to 0.2 , now the contradiction does not work. we constructed a number that still could be in our list since 0.2 could be in our list.
+xoppa09 that's a good point. Another approach will avoid this problem, let's take xn = 5 if a(n,n) is not and xn = 7 if a(n,n) = 5. Now the argument works even in special cases like the one you describe. That proves the theorem.
superb explanation
Very nice explanation
Sir how we generate 0 element in set of integers where (Z,+) is cyclic.
I never understood well the cantor's diagonalization theorem. My quest ends up finally :)
I heard Chuck Norris counted an uncountable set once.
That's too funny. It would even be pretty impressive to count a countable infinite set.
Awesome video. Thank you.
Were these formal or informal explanations?
Rob I bow to you
Finally made proof by diagonalization click, thank you.
if A is a countable set, and B is an uncountable set, then the most we can say about ( A union B) is that is . (please answer
This video helped me a lot thanks!!!
Cut N in four infinite subsets. First of them is used to create a relation one to one between it and all possible finite subsets of N. This is possible thanks to my function based on the abstract concept called CLJA. But we dont stop here: with the CLJA (with just blue holes) we can assign L naturals to each possible finite subset of N.
The second subset is just for add another argument... we pass of it for now (too large).
The third subset (because we can assign three naturals to each finite subset) is to try this: assign one unique natural to each element of each possible infinite subset of N. If one element appears in two different subsets, it must have two differents naturals ok?
Combining two different CLJAs we can do it in a brutal way. Ee really dont do that, we create infinite combinations of disjoint and unique naturals to each possible infinite subsets of N, for each possible case of “conflict”. For each possible case if conflict we can create an infinite subset (disjoint with anothers) to that particular case.
The trick is we cant reach the case of infinite conflicts, because twi infinite subsets with infinite conflicts, are really the same subset.
If we combine three CLJAs is a so big stuff that im still trying to figure out what it really means..
So P(N) is countable... and R is countable because they have the same cardinal.
Is just a little exposition... and my english us not very good. But the functions exists and I have programmed them.
The CLJA is an abstract trick that help us to create the functions. I am a programmer, not a mathematician, so the only proobe i can offer is the really simple theory about it and the check fir the first 10 000 000 million naturals not matching the same finite subset.
(combination is impossible to represent easily, but CLJA is a really simple concept,and its properties are easy to see)
I Know you think I am probably making a mistake in somewhere, or i am dont know really what im doing... but a function is a function, and its results are its results.
Now a day, I can say the natural assigned to any finite subset. And the natural assigned to:
The element e, when it belongs to the infinite subset ci1, when the value of k is x (k is the level of conflict that can not be infinite... not because i say it, because in that case we are talking if the same infinite subset).
For each value of k, i have an infinite list of naturals for each infinite subset of N.
If a list appears in one level, it does not appear in another level. Ni naturals repeated between levels, inside the same level,or with the other subset we use to “count” the finite subsets.
And finally... all infinite subset are diferents... is impossible to find a level of conflict (list of elements repeated from the beginning if we put them in order) when i cant calculate a new, unique and infinite list of naturals for each possible infinite subsets.
If you find two infinite subsets with a level of cnflict bigger... The same set of functions let you calculate a new list for each one.
And that just combining two CLJAs... in the third level of combination... is like each element has the naturals enough to solve itself all the conflicts of all infinite subsets... but im working on it..
Thank you for this! Super helpful!
awesome sir👍
Very clear. Thank you so much!
Very helpful.. thank you..
why are repeats not allowed, is it less convincing to say that two sets are equal in size if you repeat elements of one set?
+xoppa09 the reason is because the set could be bigger if you allow it. N is certainly bigger than {0,1} but I can make a surjection from N to {0,1}, by saying f(n) is 0 if n is even and one if n isn't. Now I have infinitely many repeats, but the sets aren't of the same size. If you can make a surjection f: X->Y than the cardinality of X is bigger or equal to Y, that's not as strong a statement as saying the have the same cardinality, what you can conclude if f is a bijection.
very much clarity
You are awesome thx!
thanks so much for this!!!
clear explaning
Ive never understand the meaning of the fact that i can find a new number that wasnt on the list.
I can also find a new number in the natural numbers that werent on the list, as well as integers, if i follow the same rules
Thank you!!!
also the last part i did not follow. you showed that (0,1) is uncountable. how do you get that R is uncountable. i guess you could argue, if (0,1) is uncountable, how much more so (0,1) plus extra elements is uncountable (the rest of R).
+xoppa09 well R must have at least the same cardinality as (0,1) as that is a subset of R. To show they are the same you should give a bijection between R and (0,1). This is where the inverse tangent function comes in. Take f(x) = taninv(pi*(x+1/2)), this is a bijection between (0,1) and R(check it yourself), hence (0,1) and R have the same cardinality.
+dekippiesip Hmm, this sounds as if you know a bit more about this topic. Maybe you can answer my question:
Why can't I just have the following correspondence between N and R[0..1] ?
1 -> 0.1 | 53 -> 0.53 | 7428583 -> 0.7428583 | 14159265... -> PI - 3
This way, ALL of the real numbers between 0 and 1 are linked to the natural numbers. I can not find a real number, that is not in that list. The proof at 5:00 only gives you a number, that has yet not been on the list, but will be eventually...
Lord Balder obviously you only cover rational numbers, since the decimal expansion terminates at some point. You gave pi-3, but that is not an example, since the number 14159265..... must be infinity(pi has infinitely many decimals), so that 'number' is not a natural number itself.
Hence, your bijection doesn't cover irrational numbers. So it is no bijection. The proof of 5:00 gives you a number that is no where on the list. Since the nth decimal of that number is different from the nth decimal of the nth number on your list per definition. So for eery n, your number differs in at least one decimal place with my number, therefore it isn't covered.
dekippiesip And that is exactly what I do not understand. 14159265... is infinity, but it should be still within the natural numbers, no matter how many digits you add. If that is not ok, then I do not even cover the rational numbers, since they can also have infinit many digits when written in decimal, like 1/3.
With the proposed bijection, for every digit you add, there are 10 times "more" real numbers you get, which gives you something like (10^digits) entries in the list for every digit you complete. So if you get a number which is different in the 100th digit from all previous ones, this one will appear within the first 10^100 entries of the list. And if you go down the to that one and cover all 10^100 digits, you will get a number thats on the list within the first 10^100^100 entries.
With infinite many digits, you only get an infinit large integer, but you will get one!
Hi +Lord Balder , I can see your argument, but in order for a set to be countable it must be possible to associate a *finite* natural number with any given member of that set. Using your proposed bijection, it wouldn't be possible to find a finite natural number for pi-3. You can't just say "if we were allowed to count far enough, we would count it eventually", because in fact that's not true - no matter how far your sequence goes, you will only ever get numbers with a finite (terminating) decimal representation, therefore you will never reach pi-3 since it has an infinite decimal representation. Hope that's clear!
Thanks Very Much
thanks its helpful
Thanks a lot....😊
best explain
I strongly agree with yaa GREat Video !! Thnx a lot
thaaank youuuuuuuuuuuu
Bless you
what if our diagonal series be like .9999..... an if we add 1 under mod 10 (which we require here) then it'll become .00000....
????
Thanks!!!
THANKYOU!!!!!
thank you!
good job
thanks
thanks
thnks
What about the dark numbers? Mueckenheim has shown that the rational numbers cannot be put in bijection with the natural numbers.
Where is that shown?
What on Earth is dark numbers? Just because a specific function from natural numbers to rational numbers does not cover all rational numbers, that doesn't mean that no function does. You could have used the same "proof" to show that since the function n->n+1 or n->2*n does not cover all natural numbers, the set of all natural numbers can't be mapped one-to-one with itself. (Observe that the two functions are one-to-one functions between natural numbers and a strict subset thereof. That's something that you need to get comfortable wiy
In another post, you define "dark numbers" as the set {0,ω}. How is this relevant? ω is not an element of the set of all natural numbers; ω *is* the set of all natural numbers. (In set theory the convention is that ω - the set of all natural numbers - includes 0.) The set {0,1,2,...,ω}=ω∪{ω} obviously can be mapped one-to-one with natural numbers (or with positive integers). The proof by induction works as follows: Suppose P(0) is true. Suppose the following is true for all natural numbers n: if P(n) is true, then P(n+1) is true. Then P(n) is true for every natural number (every element of ω). This *does* imply that P(0) is true - and it does so trivially, because P(0) is already taken as an assumption ("if P, then P" is always true). But it *does* not imply that P(ω) is true. In other words, you can't conflate the following claims: "P(n) is true for every finite case" and "P(n) is true in the infinite case". (As I have said, conflation of the two statements is the mistake that I like to call "magical induction", which could as well be used to prove that the set of all natural numbers is finite.)
So: let f be a one-to-one function from a set of all natural numbers to a strict subset of some set X. Changing the value of f(n) for some natural number n will not produce a bijection between natural numbers and X. By induction, changing no finite number of values will produce a bijection between the two sets. But that *does not* prove that natural numbers can't be mapped one-to-one with X. As I have said, let f be the function n->n+1 (or n->2*n) on natural numbers. Do you think that this proves than the set of all natural numbers can't be mapped one-to-one with itself? The only thing this proves is that if natural numbers can be mapped one-to-one with the set X, then the bijection differs from f at infinitely many positions. (Induction *does not* prove that the proposition is true in the infinite case. It *does not* prove that just because changing finitely many values of the function will not produce a bijection, changing infinitely many values won't produce a bijection either. Observe that the real bijection - n->n - differs from each of the two functions at infinitely many positions.)
@@MikeRosoftJH Sorry, you have not understood, as I see from your commetn that {0,ω} is the set of dark numbers. That is completely wrong. Fact is this: All natural numbers can be removed collectively from
{0,1,2,3,...,ω} with the result {0,ω}. (He does not count 0 as a natural number.) But all definable numbers n will leave infinitely many elements {0, ..., n+1, n+2, ..., ω}. That is the important difference between definable and dark.
Sorry, your sentence "It does not prove that just because changing finitely many values of the function will not produce a bijection, changing infinitely many values won't produce a bijection either" is not acceptable in case of Mueckenheim's proof. He shows that for all infinitely many exchanges (not only for finitely many) the share of not indexed fractions remains constant. To believe that this would differ "in the infinite" is not a mathematical argument.
@@undercherries4659 I ask you once again: how does your supposed proof not apply to the functions n->n+1 or n->2*n on natural numbers? Would you claim that the set of all natural numbers can't be mapped one-to-one with itself? Obviously, you don't understand how natural numbers are defined in set theory, or what "finite" means. All natural numbers are finite; that's true by definition - a set is finite, if its number of elements is equal to some natural number. And ω is neither a natural number, nor a successor of some natural number. You claim that "All definable numbers n will leave infinitely many elements {0, ..., n+1, n+2, ..., ω}." That's inaccurate. Every natural numbers n will leave infinitely many elements - period. (Again, you are conflating the statements "P(n) is true for every natural number", and "P(n) is true for the set of all natural numbers as a whole".)
@@undercherries4659 Let's explain how natural numbers are defined for real. In set theory, the convention is to define natural numbers as follows: 0 is the empty set, 1 is the set {0}, 2 is the set {0,1}, 3 is the set {0,1,2}, and so on - any natural number is a set of all numbers less than itself. Observe that any natural number n is an n-element set, and the set n+1 is obtained by taking the set n, and adding n itself to it as an additional element - n+1=n∪{n}. (This set exists by the axiom of pairing and axiom of union.)
Set theory has the axiom of infinity, which essentially says: "There exists a set containing all natural numbers." Precisely, the axiom says: there exists a set Ω, which has the following properties: 1) 0 (the empty set) is an element of Ω; and 2) for every element x, if x is an element of Ω, then x∪{x} is also an element of Ω. (Not: in set theory as usually axiomatized, all elements are themselves sets - there are no other objects than sets.) Now ω - the set of all natural numbers - is defined as follows: ω is the intersection of all sets that satisfy the axiom of infinity. That is: Let Ω be some set that satisfies the axiom of infinity; then ω is a set of all elements that have the following properties: 1) n is an element of Ω; and n is an element of every set that satisfies the axiom of infinity. (This set exists by the axiom of separation.) Observe that 1) the set ω is well-defined - no matter what set Ω we start with, we get the same result (by the axiom of extensionality - two sets are equal, if and only if they have the same elements), 2) ω is non-empty (for example, it contains 0); and 3) ω itself satisfies the axiom of infinity.
Why are natural numbers defined in this way? So that the principle of induction is true for the set ω. Let P(n) be some proposition. Suppose P(0) is true. Suppose for every element of ω the following is true: if P(n) is true, then P(n+1) is true. Then P(n) is true for every element of ω. (Consider the set of all elements of ω for which P(n) is true: ω'={n: n is an element of ω and P(n) is true}. Obviously, ω' is a subset of ω. But observe that this is a set that satisfies the axiom of infinity; so by construction of ω every element of ω is an element of ω'. It follows that the set *is* in fact the same set as ω; in other words, P(n) is true for every element of ω.) From this principle, it can for example be proven that no two different elements of ω can be mapped one-to-one, and no element of ω can be mapped one-to-one with ω. We now define: A set is finite, if it can be mapped one-to-one with some element of ω. Again, it can be shown that every subset of ω is either finite, or it can be mapped one-to-one with ω.
But again - and this is what you fail to understand - just because a proposition is true for every finite case, it doesn't mean that it is true for the infinite case as well. In other words: Suppose P(0) is true; and suppose for every element of ω the following is true: if P(n) is true, then P(n+1) is true. That does not mean that P(ω) is true; an obvious counter-example is: "n is finite".
yasss
god bless!
Top ten
goog rob
Using the method employed, the conclusion is not a contradiction. You are assuming a square grid can contain all the elements of the list. This is impossible for the same setup with the same intuitive concepts applied. Take the complete list of a binary form, that forms a length of 1:
List:
{
0
1
}
This is a complete, finite, countable set. List size is 2
........................
Construct a square grid, why? because a grid that is infinity wide and infinity long is used to intuitively conclude a contradiction.
Now assume that the grid can be populated with all the elements from the complete list. Because this is what we want to use as a contradiction ??? Ok ...
Grid [1x1]:
{
[ 0 ]
}
We can see that the grid does not hold the complete list. The grid can only hold the same number of elements as its equal dimensions allow - and, 1 does not equal 2.
What list does it hold?
list composed of the elements of G:
{
0
}
Maybe taking an altered diagonal, d, will prove the contradiction that ... a square grid can contain the completed list.
well, d = 1, which is clearly not contained by the grid itself. Well, we have proven that a contradiction exists ... therefore it is impossible to make a list at all?
.................................
Maybe we just need to grow the grid size, the bigger the grid the more that will fit? Lets use the same binary components, but increase the length of an element to 2.
List:
{
00
01
10
11
}
Construct a 2x2 grid and populate it with any arbitrary elements from the list.
Grid [2x2]:
{
[ 0 1 ]
[ 1 1 ]
}
Well the grid can only hold 2 elements of the list ... but lets assume it can hold all of them for some reason.
List composed of the elements of the grid:
{
01
11
}
Make the altered diagonal, d = 10, This does not match any element in the list that was composed from the grid. Therefore we conclude that a complete list is impossible to make.
.....................
These 2 examples for the smallest set, and the next smallest set, form an inductive proof that there exists NO square grid that can contain a complete, countable list using this method.
We assume a square grid, and a countable list, and prove that the results are the same for all results; but then claim a contradiction exists when we obtain the same outcome??
...........
Considerations:
Why a square grid? because that is defined by Cantors setup; assume the length of each element is countable, and assume the number of items listed is countable and complete.
Spose we use a nonsquare grid. More columns then items, the diagonal produces an element that is not on the list to start with, its not long enough. Maybe we alter the length? but that is not a step in the method, only alterations to the digits are expressed; length remains the same.
More items than columns? Then the diagonal has the same length, but it clearly will not effect all the items of the list.
Maybe we list the items top to bottom instead of left to right? Then what does trying to add to the bottom of the list represent? It adds nothing to the list, and just changes the length of each item instead.
Hence, the properties being addressed represents a square grid - with a list of elements of equal length.
The diagonal argument _does_ apply to finitely many digits, but you have to interpret the results _reasonably_ and not have a kneejerk reaction that doesn't make sense.
For binary strings with n digits, there are clearly 2^n such strings, since we have 2 choices for each digit. Then, any list consisting of exactly n n-bit strings is incomplete, which shows that 2^n > n. It seems a bit silly to use this argument in the finite case, since we're used to working with ordinary arithmetic of finite numbers, and we have many ways to prove 2^n > n for finite "amounts" that are more in line with how one would try to show such a thing.
What Cantor's Diagonal Argument shows is that 2^α > α is _still true_ even when α is infinite in value. Because there are still 2^α α-bit binary sequences (two choices for each element), but assuming that there are α-many α-bit binary strings leads to a contradiction - we can always construct an α-bit binary string not in our "list". So, just like in the finite case, we can conclude that 2^α > α.
Why would Cantor need to imply such an argument? That's because things like 2n > n are true for finite n, but 2α = α is true for infinite "amounts of elements". So the ordinary arithmetic proofs don't work, and we need a different approach. Plus, it's a very common gut instinct that "all infinite sets are the same size," so it's not at all obvious that 2^α isn't just equal to α for infinite α. So there really is something to prove here, and Cantor's Diagonal Argument is a brilliant way to do this.
👩🔧
At last I understand! Maybe they should ask Chuck Norris to solve the unsolvable problem of Continuity.
thanks I hate it
We can't assume we have a complete list of numbers, because we have posited the listbis infinite. We posit the set is infinite, and therefore is unending. To complete a list which is unending is not possible.
To posit that you have a set which is an infinite, and posit that set ha been completed is a contradiction in the premises.
Cantor did this with 3 proofs, and for some reason we are about 150 years later, and I'm the only person spotting this contradiction?
#mathematiciansrdumb
Snatch n Grab,
I have to agree totally that more critical thinking is needed here than to take Cantor's diagonal proof on face value. Here is one way to show it is flawed:
The proof starts with the assumptions: 1) an exhaustive list of real numbers and 2) there is a bijection between this list and the natural numbers. Near the end, the orator tries to show that he found a new real number not in his exhaustive list and that real number does not have a partner in the natural numbers.
So... did he or did he not have an exhaustive list of the real numbers at the start??? Obviously, the new-found real number existed somewhere on the real number line before the orator started the proof; he just didn't know about it. Suppose that he did manage to get the exhaustive list, then by assuming there is a bijection, he has already assigned a natural number partner to this real number that he didn't know about. But near the end, he contradicts this assumption by saying there is no partner for this new-found real number. WTF!!!
In other words, if it is actually an exhaustive list, then the new-found real number is already on the list and there is a partner for it.
Many on the Internet try to praise how simple and powerful this proof is, and how amazing that it can be done in less than 5 minutes. But what I think is that recycling this proof is one sure way to confuse and contradict oneself in less than 5 minutes.
Marvelous Whiskers That's generally how a proof by contradiction works, though.
But when a new real is generated, it shows the unsound nature of the assumption(s), which is quite easily noticeable as saying the natural numbers were exhausted, finished, i.e. finite.
Whatever real generated by the diagonal method can be paired to the next natural number.
The Cantor Camp, if I may say that, always says, "but we used up the naturals", and I say, "no, you only asserted that you did, such a thing is not possible". The one to one correspondence can continue with nothing hindering it.
Which then leads us to something entirely overturning that no one wants to hear it... bijection is not a tool to show size of sets, only density.
We could then rephrase math so that density and size of sets are the same thing. This is not the case now, which births our current Hierarchy of Infinites and the Continuum Hypothesis.
However, if that was accepted, we would then rebuild the hierarchy. The infinite set of odd natural numbers would be half the size of the infinite set of all natural numbers. The infinite set of reals would be infinitely more dense than set of naturals.
Set theorists would still have a monkey to play with, the Continuum Hypothesis would be resolved, and we could make statements like "half of all natural numbers are evenly divisible by 2" AND provide a proof (which is currently proven to be impossible to prove or disprove with current maths, even though we know it's true).
Snatch n Grab, Yes, I think we are basically saying the same thing about this proof: that the assumptions are questionable and the orator is ignoring them by the end. I personally think the reals are countable, maybe not by conventional methods, but nonetheless maybe some other way. True or false, I do agree that Cantor's method and our current understanding of infinity is insufficient.
Marvelous Whiskers Hopefully we can find out in our lifetimes. I started with a Single Cardinality of Infinites Conjecture, but I felt that should be scrapped because I am learning that even though Cantor's mistake is quite obvious, we still have a use for the hierarchy. Thus I am moving to cardinality based in density. If I win a Nobel prize, I'll post a video.
I agree with what you both say. Would it be fair to say R is countable by:
+- {d ; .d
dd ; d.d ; .dd
ddd ; dd.d ; d.dd ; .ddd
dddd ; ddd.d ; dd.dd ; d.ddd ; .dddd
.
.
.
}
where d is a digit 0-9. And just like showing Q is countable, not include any repeats. Does that work?
nice explaining . thanks but give some examples . if I want to ask some doubts.
you may give your email id .
very good explanation
thank you!