I would say that the obviousness of this theorem is kind of cheating: the notation which is defined afterwards is very suggestive but the theorem is nontrivial. Keep in mind that you can ask similar question in _any_ category (instead of injection you take monomorphism in a suitable catgeory): for vector spaces, groups, algebraically closed fields, topological spaces, measurable spaces, Hilbert spaces, Banach spaces, C*-algebras ... for the listed above cases the answers are: yes,no,yes,no,no,yes,no,no
@@yfidalv since the notion of morphism in the context of Banach spaces is more restrictive: you need your map to be homeomorphism which is not required in the context for vector spaces (n fact it does not make sense to speak about homeomorphism in the context of plain vector spaces)
This video is immense! Thank you, Jared! I have been working through Abbott’s analysis by myself and got seriously impeded by the notation heavy proof in this section. Your video really bailed me out by giving much needed intuition.
this is great Jared. As a visual learner super helpful. Also the takeaways are the end are super goated: know the definition and accept where it takes you!!! keep them coming
Bravo!!! You have done an AMAZING job!!! I wanted to make a video on this subject myself so I went to look up what is already out there. I can only imagine how many hour of work you put into manim and synchronizing the video and the sound for a video of this length! 3b1b has set the standard bar very high and now it seems that viewers won't compromise for anything less than manim. This video deserved millions of views!
Really nice explanation! My real analysis professor drew some wild pictures on the board and left everyone confused; this, on the other hand, made it seem almost trivial :)
¡Amazing! It´s the first time I can understand the Cantor_Bernstein theorem Applying this method which is very Closed to the explanation using the approach of the two mirrors, which I never could understan before. Congratulations, dear Jared Bitz. Greetings from Bogotá, Colombia
wow this is cool; i'm also very surprised that you have 910 subscribers, when production of this quality deserves 50k. very interesting video, hopefully a video blows up one day! thanks for sharing this weird maths.
This proof does not use the axiom of choice. But the similar theorem with surjections instead of injections requires it. Another nontrivial application of the theorem is the fact that the set of continuous applications from R to R has the same cardinality as R (the continuous). To any real a associate the constant application with value a. This is clearly injective. On the other hand a continuous application is uniquely defined by its values at rational points, which are dense in R. This defines an injection from the set of continuous applications to the set of countably many reals, which is itself in bijection with R.
The injection from the positive rational numbers to the positive integers is not well defined. You have to assume that p and q are coprime. For expample: 1/2 gets mapped to 18, but 2/4 gets mapped to 324.
minor nitpick: you don't *have* to assume coprimality; you just have to select a unique representation for each rational, and it's easy to show that every rational has a unique coprime representation
can we tell anything about the "size" of a cartesian product of sets? is Z×Z larger than Z? can we match a ruler to a grid or a line to a surface? or a line to a grid?
|Z×Z|=|Z| is one of first things demonstrated about cardinality, and without any axiom of choice. Assuming axiom of choice, it can be shown |A×A|=|A| for any A. In fact, this statement can prove the axiom of choice in turn, so they're equivalent.
Is |P| (i.e. the "size of" set P) an operator on P, a function of P, or something else? What is the range of "size of"? If the range is (always) a number then the problem is trivial. Obviously that is not the case, so what other 'values' can "size of" take? P.S. I took university-level mathematics many years ago (& enjoyed it) but the subtleties of high-level math often elude me. :)
Well, you can define cardinality of a set in terms of the least ordinal number that can be bijected to a set. Using ZFC you can define all the ordinal numbers (even infinite ones). Now the very subtle part here is in the case of infinite sets because for those, there are many ordnals that can be associated with a set and this ordinals highly depend on how the elements are “arranged”. The ordinal associated for the typical arrangement of N and the one for Z are different ordinals. However, if you try to rearrange them you find that the least ordinal that corresponds them is omega or Aleph_0. At this point you cannot yet establish whether there will always be a corresponding “least” ordinal for every set or whether this type of construction is preserved by bijection but you can show that indeed cardinalities of sets form an equivalence relation so you can just pick a specific set, give it a symbol and make that your “standard” measurement of size and for future sets you just check if there is a bijection to that set or not to conclude its cardinality. Unfortunately, you cannot create a set that contains all the possible sizes (this will create lead to cantors paradox). So, if you define a function as a mapping from a set to a set then this “size of” operator is strictly not a function because it cannot have a range that is a set nor can it have a domain that is a set (otherwise its domain will be the “set of all sets”) but nonetheless any set will have a size because you can trivially pick the set as your measurement of its size and any set will either have a bijection with it or not which will then determine whether they belong to the same category in terms of their sizes. Interestingly, sizes defined this way needs the axiom of choice so that you can compare them. Without AoC you can have sets that have different sizes but you cannot find an injection from either one to another so essentially none is bigger than the other even though they’re different sizes.
After the definitions it still seems obvious: an injection from B->A means a surjection from A->B (map all points not pointed to by the injection to some specific point), and if you have an injection and a surgection you can make a bijection.
If you have an injection A->B then you don’t have a surjection B->A yet. For example, consider {1,2} and {1,2,3}. 1 -> 3 2 -> 2 …….1 You would have to arbitrarily assign the elements that were not mapped. For example, 1
@@galoomba5559 An injection from A to B *does* imply a surjection from B to A. (Let f be the injection; then let g(y)=f^-1(y) if y is an image of some x∈A; otherwise, let g(y) be an arbitrary element of A. For example: let A be rational numbers, and B be real numbers. Obviously, constant function is an injection from A to B. Now let g(y)=y if y is rational, otherwise g(y)=0. That's a surjection.) But obviously, this doesn't imply an existence of bijection between A and B. I think that what has confused you is: if there both exists an injection from A to B and a surjection from A to B, then there exists a bijection between the two sets. That's true, assuming axiom of choice.
How is the cardinality of N and Z same? Thinking intuitively, we know that for every natural number x, there are two integers x and -x. Also, 0 exists in Z. So this way the cardinality of Z must be one more than twice the cardinality of N.
The idea is that for every element in Z, we can make a function for which there's one and only one element in N that maps to it. Let's say that we want to disprove that one particular function forms a bijection, to do so we must find at least one element in Z that goes unpaired under our mapping function. With that in mind, take the function f(n) that maps N into Z, if n is even, f(n) = n/2; if n is odd, f(n) = -(n+1)/2. We can see that this function maps every even number in N to every positive number in Z and the element 0, while also mapping every odd element in N to every negative number in Z, and because every number in N is either even or odd, our function applies to every element in N, and because every number in Z is either positive, negative or 0, our function maps to every element in Z, thus, N has the same cardinality as Z.
I used to prefer the convention that 0 was not. Then when starting my graduate studies (PA), the convention there was that 0 was in N. Then with most programming languages, arrays are 0-based, so it becomes natural to start counting at 0. So these days I usually take N to include 0.
@@mhm6421 If you begin with Peano's axioms, which don't specify the multiplicative properties of the smallest natural number, it can make sense to start with any number whatsoever. The question you need to ask is whether nor there exists an additive identity.
0 should definitely be in N. N with 0 is a monoid. if you exclude 0 from N, there will be countless cases where you have to write "take the natural numbers including 0" which is very clunky. it's like saying "2 is not a prime number because it is even"
1 inch 1 foot you're wrong because scale only exists when there's an embedding dimension. the number 1 has absolutely no relationship to 11, or any other number, until after dimension is specified. this is even made explicit in the notation we use to describe Integers. for instance: -7 < +7, but both have the same number component, 7. so shouldn't -7 = +7? the basic equivocation you're making is so bad in fact that it is what causes Godel Incompleteness. Peano claimed that the Successor function gives us the Naturals, and thus the Naturals are ordered. but Godel used the Naturals as nominals to produce Godel numbers, from which he demonstrated that any mathematical foundation which includes the Naturals is necessarily incomplete. yet somehow nobody ever noticed that this incompleteness occurs because the Naturals have a self contradictory definition, meaning that no rigorous mathematical foundation should include the Naturals.
This is great! There's a small error starting at 00:32 -- "|Z|
I would say that the obviousness of this theorem is kind of cheating: the notation which is defined afterwards is very suggestive but the theorem is nontrivial. Keep in mind that you can ask similar question in _any_ category (instead of injection you take monomorphism in a suitable catgeory): for vector spaces, groups, algebraically closed fields, topological spaces, measurable spaces, Hilbert spaces, Banach spaces, C*-algebras ... for the listed above cases the answers are: yes,no,yes,no,no,yes,no,no
wait why would it be yes for vector spaces and no for Banach spaces, isnt a Banach space just a special vector space
@@yfidalv since the notion of morphism in the context of Banach spaces is more restrictive: you need your map to be homeomorphism which is not required in the context for vector spaces (n fact it does not make sense to speak about homeomorphism in the context of plain vector spaces)
This video is immense! Thank you, Jared! I have been working through Abbott’s analysis by myself and got seriously impeded by the notation heavy proof in this section. Your video really bailed me out by giving much needed intuition.
this is great Jared. As a visual learner super helpful. Also the takeaways are the end are super goated: know the definition and accept where it takes you!!! keep them coming
Bravo!!! You have done an AMAZING job!!! I wanted to make a video on this subject myself so I went to look up what is already out there. I can only imagine how many hour of work you put into manim and synchronizing the video and the sound for a video of this length! 3b1b has set the standard bar very high and now it seems that viewers won't compromise for anything less than manim.
This video deserved millions of views!
This video is really well made. Definitely deserves more views 🙌🏽
Really nice explanation! My real analysis professor drew some wild pictures on the board and left everyone confused; this, on the other hand, made it seem almost trivial :)
¡Amazing! It´s the first time I can understand the Cantor_Bernstein theorem Applying this method which is very Closed to the explanation using the approach of the two mirrors, which I never could understan before. Congratulations, dear Jared Bitz. Greetings from Bogotá, Colombia
wow this is cool; i'm also very surprised that you have 910 subscribers, when production of this quality deserves 50k.
very interesting video, hopefully a video blows up one day!
thanks for sharing this weird maths.
This proof does not use the axiom of choice. But the similar theorem with surjections instead of injections requires it. Another nontrivial application of the theorem is the fact that the set of continuous applications from R to R has the same cardinality as R (the continuous). To any real a associate the constant application with value a. This is clearly injective. On the other hand a continuous application is uniquely defined by its values at rational points, which are dense in R. This defines an injection from the set of continuous applications to the set of countably many reals, which is itself in bijection with R.
Applications? You mean functions?
@@galoomba5559 Yes, functions, if you prefer the term.
@@ahoj7720 "Prefer"? I've never seen the term "application" used in this sense.
Best explanation I've seen
Excellent video!
Great video!!
The injection from the positive rational numbers to the positive integers is not well defined. You have to assume that p and q are coprime. For expample: 1/2 gets mapped to 18, but 2/4 gets mapped to 324.
minor nitpick: you don't *have* to assume coprimality; you just have to select a unique representation for each rational, and it's easy to show that every rational has a unique coprime representation
nice explanation
Very good 👍
Brilliant♥👌
theres a mistake on 0:35
?
both are |Z|
Nice!
This was ab amazing vdeo
can we tell anything about the "size" of a cartesian product of sets?
is Z×Z larger than Z?
can we match a ruler to a grid
or a line to a surface?
or a line to a grid?
yes, with a similar argument to the "size of all rational numbers is equal to size of all natural numbers" argument
|Z×Z|=|Z| is one of first things demonstrated about cardinality, and without any axiom of choice. Assuming axiom of choice, it can be shown |A×A|=|A| for any A. In fact, this statement can prove the axiom of choice in turn, so they're equivalent.
@@stevenfallinge7149 Any *infinite* A, of course.
Is |P| (i.e. the "size of" set P) an operator on P, a function of P, or something else? What is the range of "size of"?
If the range is (always) a number then the problem is trivial. Obviously that is not the case, so what other 'values' can "size of" take?
P.S. I took university-level mathematics many years ago (& enjoyed it) but the subtleties of high-level math often elude me. :)
Well, you can define cardinality of a set in terms of the least ordinal number that can be bijected to a set. Using ZFC you can define all the ordinal numbers (even infinite ones). Now the very subtle part here is in the case of infinite sets because for those, there are many ordnals that can be associated with a set and this ordinals highly depend on how the elements are “arranged”. The ordinal associated for the typical arrangement of N and the one for Z are different ordinals. However, if you try to rearrange them you find that the least ordinal that corresponds them is omega or Aleph_0. At this point you cannot yet establish whether there will always be a corresponding “least” ordinal for every set or whether this type of construction is preserved by bijection but you can show that indeed cardinalities of sets form an equivalence relation so you can just pick a specific set, give it a symbol and make that your “standard” measurement of size and for future sets you just check if there is a bijection to that set or not to conclude its cardinality. Unfortunately, you cannot create a set that contains all the possible sizes (this will create lead to cantors paradox). So, if you define a function as a mapping from a set to a set then this “size of” operator is strictly not a function because it cannot have a range that is a set nor can it have a domain that is a set (otherwise its domain will be the “set of all sets”) but nonetheless any set will have a size because you can trivially pick the set as your measurement of its size and any set will either have a bijection with it or not which will then determine whether they belong to the same category in terms of their sizes. Interestingly, sizes defined this way needs the axiom of choice so that you can compare them. Without AoC you can have sets that have different sizes but you cannot find an injection from either one to another so essentially none is bigger than the other even though they’re different sizes.
After the definitions it still seems obvious: an injection from B->A means a surjection from A->B (map all points not pointed to by the injection to some specific point), and if you have an injection and a surgection you can make a bijection.
If you have an injection A->B then you don’t have a surjection B->A yet.
For example, consider {1,2} and {1,2,3}.
1 -> 3
2 -> 2
…….1
You would have to arbitrarily assign the elements that were not mapped. For example,
1
It doesn't seem obvious to me that an injection and a surjection implies a bijection. What's the construction?
@@galoomba5559 An injection from A to B *does* imply a surjection from B to A. (Let f be the injection; then let g(y)=f^-1(y) if y is an image of some x∈A; otherwise, let g(y) be an arbitrary element of A. For example: let A be rational numbers, and B be real numbers. Obviously, constant function is an injection from A to B. Now let g(y)=y if y is rational, otherwise g(y)=0. That's a surjection.) But obviously, this doesn't imply an existence of bijection between A and B.
I think that what has confused you is: if there both exists an injection from A to B and a surjection from A to B, then there exists a bijection between the two sets. That's true, assuming axiom of choice.
How is the cardinality of N and Z same? Thinking intuitively, we know that for every natural number x, there are two integers x and -x. Also, 0 exists in Z. So this way the cardinality of Z must be one more than twice the cardinality of N.
The idea is that for every element in Z, we can make a function for which there's one and only one element in N that maps to it. Let's say that we want to disprove that one particular function forms a bijection, to do so we must find at least one element in Z that goes unpaired under our mapping function.
With that in mind, take the function f(n) that maps N into Z, if n is even, f(n) = n/2; if n is odd, f(n) = -(n+1)/2. We can see that this function maps every even number in N to every positive number in Z and the element 0, while also mapping every odd element in N to every negative number in Z, and because every number in N is either even or odd, our function applies to every element in N, and because every number in Z is either positive, negative or 0, our function maps to every element in Z, thus, N has the same cardinality as Z.
Its just about infinities, moreover, NxNxN…(a finite number of times) equal to N
come back the world needs you
Wow amazing sharing ❤New friend here. Please stay connected 😊 🙏
why not be obvious.
You use terms size and count as a reference to _cardinality_ which is misleading.
One correction- 0 shouldn't be there in Natural Numbers set.
Good explanation, Thanks a lot. 😊
Depends on the convention, some say it does, some say it doesn’t.
I used to prefer the convention that 0 was not. Then when starting my graduate studies (PA), the convention there was that 0 was in N. Then with most programming languages, arrays are 0-based, so it becomes natural to start counting at 0. So these days I usually take N to include 0.
Solution: Don't use natural numbers
@@mhm6421 If you begin with Peano's axioms, which don't specify the multiplicative properties of the smallest natural number, it can make sense to start with any number whatsoever. The question you need to ask is whether nor there exists an additive identity.
0 should definitely be in N. N with 0 is a monoid. if you exclude 0 from N, there will be countless cases where you have to write "take the natural numbers including 0" which is very clunky. it's like saying "2 is not a prime number because it is even"
1 inch 1 foot
you're wrong because scale only exists when there's an embedding dimension. the number 1 has absolutely no relationship to 11, or any other number, until after dimension is specified. this is even made explicit in the notation we use to describe Integers. for instance:
-7 < +7, but both have the same number component, 7. so shouldn't -7 = +7?
the basic equivocation you're making is so bad in fact that it is what causes Godel Incompleteness. Peano claimed that the Successor function gives us the Naturals, and thus the Naturals are ordered. but Godel used the Naturals as nominals to produce Godel numbers, from which he demonstrated that any mathematical foundation which includes the Naturals is necessarily incomplete. yet somehow nobody ever noticed that this incompleteness occurs because the Naturals have a self contradictory definition, meaning that no rigorous mathematical foundation should include the Naturals.