Great video! I guess the general Cantor diagonalization argument would go like this: Suppose S is a set and f : S -> P(S) is a bijection. Then consider T = {s in S such that s is not in f(s)}, which is a subset of S. Since f is a bijection, there must exist t in S with f(t) = T. Now let's ask the question, is t in T? If it is, then it isn't; if it isn't, then it is. Contradiction! Hence f cannot exist and P(S) has strictly greater cardinality than S.
Or else, let f be any function from S to P(S); then it is not onto P(S), and T is precisely the counter-example. (If S is an infinite set which can be mapped one-to-one with two copies of itself, then a stronger result can be proven: given any function from S to P(S), the set of elements of P(S) which the function does not cover can be mapped one-to-one with P(S).)
Enjoyed this video a lot. Fun to think about interval [0,1] in binary form and that relating to all possible power sets of N. Plus intro to cardinality and countable/uncountable infinities. Thanks for clear teaching. I came back to watch this video again. Am up to #70. Nearing end of course.
Great video, very nice explanation of using cantors diagonalisation for this power set example. We recently used this similar process to talk about orders of chaotic dynamical systems. It's great to see the same ideas used in lots of different applications!
No need for ruminate- That's Russell's paradox, and Cantor said that the universal set was too big to be consider a set itself, so no P(U);) according to its own creator.·.
On the final thoughts by the end of the video: In axiomatic set theory (I'm referring to the axioms of ZFC in particular) we start considering a relation, i.e. a predicate of 2 variables, called the ∈-relation such that x, y are sets if, and only if, ∈(x,y) is either True or False, meaning: it can't be both True and False (much less being neither) as in the following example: Let u be a colection such that for any set x: If ∈(x,x) is False, then ∈(x,u) is True. However, it's easy to check (relying only on the Axiom of the ∈-relation) that u is not a set because ∈(u,u) is both True and False. The Axiom of Foundation states that for any set x, ∈(x,x) is False, which makes u the colection of all sets and therefore, the colection of all sets is not a set. So, anything that follows the False premisse that the colection of all sets is a set can be either True or False and the implication will always be True. Great video by the way, +1 sub.
Even without the axiom of regularity there can't be the set of all sets (under the rest of ZF axioms). For contradiction, suppose that U is the set of all sets; then by axiom of separation there exists a set U' = {x: x∈U and x∉x} = {x: x∉x}; and such a set cannot exist (both U'∈U' and U'∉U' contradict the definition of the set). It can also be proven constructively from the bottom up: let A be any set. Let B the set: {x: x∈A and x∉x} (which exists by the axiom of separation). By construction, B∉B (otherwise, B would contain a set which contains itself). B∉A (we have already proven that B∉B; so if B∈A, it would from construction follow that B∈B, contradicting the result that it's not). Finally, A∉B (because B is a subset of A, it would follow that A∈A, contradicting the definition of set B - it would contain a set which contains itself). So: we have proven that given any set A, the set A is not a set of all sets - in particular, it doesn't contain the set B = {x: x∈A and x∉x}. (The proof only uses the axiom of separation, and perhaps implicitly axiom of extensionality. There are other set theories, like 'New Foundations', which allow for the existence of the set of all sets, and don't use axiom of separation in this form.)
In the context of preparing for international olympiads,jee,etc... Can u please explain exactly step by step how to read a question solution actively *introspectively* such that u r thinking how the person who wrote the solution came up with each step and u r trying to find out his/her thought process...basically such that ur gaining smthg from that solution... Can u do this with the help of some example questions from topics like PnC,Probability,Sequence nd series,circles,etc [maybe jee advanced questions]...like can u also mention the algorithm/logic/patterns memorization part along with the logical reasoning part.... Like from understanding+memorizing theory...to actually mastering the art of problem solving for multiple topics
Love it! I am re-learning a lot! BUT: 2 comments... 1. Perhaps some gremlins are randomly adjusting your volume knobs. 2. There is a lot of room echo that makes it hard for and old guy, like me, from understanding your words. Please use a close microphone or sound absorbing wall coverings.
Sir you should have mentioned that cardinality of Natural numbers is called Aleph Naught 🤗. Another video like this I would suggest you should make is how Cantor set has cardinality=continuum but the Cantor set is measurable having a measure zero. 👍🏻
But if you mapped the 0/1 choice for n to the 2^n place of a base 2 integer, then doesn't |P(n)| correspond to the countably infinite set of integers? That is, does its being countably vs uncountably infinite depend on whether we're placing the 0s and 1s in places that are more and more significant or less and less significant?
It doesn't quite work out because while it is clear what an infinite decimal expansion is, an integer number with infinitely many places is less clear what that means.
@@erichpatrickenke2848 Yes. The 2-adic numbers are set-isomorphic to the real numbers. The only distinction is they are defined by different topologies.
Note video at 10:34 and this is something I am struggling with. 1. I understand how P(N) is uncountably infinite, that is | P(N) | > | N | 2. I understand how P(R) is uncountably infinite, that is | R | > | N | A. For the life of me I do not understand how this binary representation of real numbers between [0, 1] guarantees that that there is a mapping of a binary representation of any number in that interval. How about (PI - 3)? That is the infinite decimal 0.141592653...? Why is this guaranteed to have a binary expansion of 1s and 0s that EXACTLY matches the VALUE represented by (PI - 3)? In other words why does 1. and 2. imply | P(N) | = | R |. Why is there guaranteed to always be a mapping? B. If the answer is that any eventual binary expansion of (PI - 3) is guaranteed to result in an infinite binary number that eventually can be mapped to P(N), then why can't this same argument be used to Map the real interval [0,1] to the integers by simply writing out every decimal expansion of each R number in a matrix similar to the diagnal argument?
The cardinality of the set ℕ of all _natural_ numbers (countable infinity) is called ℵ₀ (aleph null) or ℶ₀ (beth null), which is the same: |ℕ| = ℵ₀ = ℶ₀
The cardinality of the power set 𝑷(ℕ) of the set ℕ of all _natural_ numbers is equal to the cardinality of the set ℝ of all _real_ numbers (the continuum 𝔠 or 𝒄): |𝑷(ℕ)| = |ℝ| = 2^ℵ₀ = 2^ℶ₀ = ℶ₁ = 𝒄 > ℵ₀ = |ℕ| (beth one)
And the cardinality of the power set 𝑷(ℝ) of the set ℝ of _real_ numbers is equal to the cardinality of all functions from ℝ to ℝ (with discontinuities): |𝑷(ℝ)| = 2^ℶ₁ = ℶ₂ > 𝒄 = |ℝ| (beth two)
I feel like there is a gap in the logic at 9:52. We have a map from the power set to the decimals containing 0 and 1. How to you jump from that to claiming we have a map to the interval [0,1]? How was 0.555555… obtained?
Well any number in [0,1] can be written using binary numbers with 0=0.0000... and 1=0.11111111111. The choice of binary or decimal or anything else doesn't matter.
"Infinity" is not a size in the same way that "finity" is not a size either, but there are various finite sizes, and there also are various infinite sizes.
@@wernerhartl2069 A set is finite, if its cardinality (number of elements) is equal to some natural number; any other set is infinite. Two sets have the same cardinality, if they can be mapped one-to-one. Under that definition, natural numbers can't be mapped one-to-one with real numbers (but they can be injected into real numbers); so natural numbers have a strictly lesser cardinality than real numbers.
@@MikeRosoftJH The set of natural numbers satisfies your definition for infinite set. Prove there is another set which satisfies your definition. You haven’t proven the natural numbers can’t be mapped one to one to the real numbers. CDA assumes there is an infinite set other than the natural numbers which it purportedly tries to prove. It is a circular argument and therefore wrong.
TQ doctor. U made my life in uni much more doable, I love your teaching style. Unfortunately for this video the audio is kinda low though.
Wow! This tutorial is absolutely phenomenal. Great for 1st year real analysis! Thanks so much!
Great video! I guess the general Cantor diagonalization argument would go like this: Suppose S is a set and f : S -> P(S) is a bijection. Then consider T = {s in S such that s is not in f(s)}, which is a subset of S. Since f is a bijection, there must exist t in S with f(t) = T. Now let's ask the question, is t in T? If it is, then it isn't; if it isn't, then it is. Contradiction! Hence f cannot exist and P(S) has strictly greater cardinality than S.
Or else, let f be any function from S to P(S); then it is not onto P(S), and T is precisely the counter-example. (If S is an infinite set which can be mapped one-to-one with two copies of itself, then a stronger result can be proven: given any function from S to P(S), the set of elements of P(S) which the function does not cover can be mapped one-to-one with P(S).)
Enjoyed this video a lot. Fun to think about interval [0,1] in binary form and that relating to all possible power sets of N. Plus intro to cardinality and countable/uncountable infinities. Thanks for clear teaching. I came back to watch this video again. Am up to #70. Nearing end of course.
Great video, very nice explanation of using cantors diagonalisation for this power set example.
We recently used this similar process to talk about orders of chaotic dynamical systems. It's great to see the same ideas used in lots of different applications!
No need for ruminate- That's Russell's paradox, and Cantor said that the universal set was too big to be consider a set itself, so no P(U);) according to its own creator.·.
On the final thoughts by the end of the video: In axiomatic set theory (I'm referring to the axioms of ZFC in particular) we start considering a relation, i.e. a predicate of 2 variables, called the ∈-relation such that x, y are sets if, and only if, ∈(x,y) is either True or False, meaning: it can't be both True and False (much less being neither) as in the following example: Let u be a colection such that for any set x: If ∈(x,x) is False, then ∈(x,u) is True. However, it's easy to check (relying only on the Axiom of the ∈-relation) that u is not a set because ∈(u,u) is both True and False. The Axiom of Foundation states that for any set x, ∈(x,x) is False, which makes u the colection of all sets and therefore, the colection of all sets is not a set. So, anything that follows the False premisse that the colection of all sets is a set can be either True or False and the implication will always be True. Great video by the way, +1 sub.
Even without the axiom of regularity there can't be the set of all sets (under the rest of ZF axioms). For contradiction, suppose that U is the set of all sets; then by axiom of separation there exists a set U' = {x: x∈U and x∉x} = {x: x∉x}; and such a set cannot exist (both U'∈U' and U'∉U' contradict the definition of the set).
It can also be proven constructively from the bottom up: let A be any set. Let B the set: {x: x∈A and x∉x} (which exists by the axiom of separation). By construction, B∉B (otherwise, B would contain a set which contains itself). B∉A (we have already proven that B∉B; so if B∈A, it would from construction follow that B∈B, contradicting the result that it's not). Finally, A∉B (because B is a subset of A, it would follow that A∈A, contradicting the definition of set B - it would contain a set which contains itself). So: we have proven that given any set A, the set A is not a set of all sets - in particular, it doesn't contain the set B = {x: x∈A and x∉x}. (The proof only uses the axiom of separation, and perhaps implicitly axiom of extensionality. There are other set theories, like 'New Foundations', which allow for the existence of the set of all sets, and don't use axiom of separation in this form.)
Nice video, although the audio quality wasn’t that good to be honest 😊
Sorry, my main mic died:( will be back to normal for the next one
Nice video Trefor. I’d love to see you go into some modern algebra
oh I'd like that too!
Thanks, I finally understood this proof
In the context of preparing for international olympiads,jee,etc...
Can u please explain exactly step by step how to read a question solution actively *introspectively* such that u r thinking how the person who wrote the solution came up with each step and u r trying to find out his/her thought process...basically such that ur gaining smthg from that solution...
Can u do this with the help of some example questions from topics like PnC,Probability,Sequence nd series,circles,etc [maybe jee advanced questions]...like can u also mention the algorithm/logic/patterns memorization part along with the logical reasoning part....
Like from understanding+memorizing theory...to actually mastering the art of problem solving for multiple topics
Love it! I am re-learning a lot! BUT: 2 comments... 1. Perhaps some gremlins are randomly adjusting your volume knobs. 2. There is a lot of room echo that makes it hard for and old guy, like me, from understanding your words. Please use a close microphone or sound absorbing wall coverings.
Excellente Problem
Great video.
Sir you should have mentioned that cardinality of Natural numbers is called Aleph Naught 🤗. Another video like this I would suggest you should make is how Cantor set has cardinality=continuum but the Cantor set is measurable having a measure zero. 👍🏻
But if you mapped the 0/1 choice for n to the 2^n place of a base 2 integer, then doesn't |P(n)| correspond to the countably infinite set of integers? That is, does its being countably vs uncountably infinite depend on whether we're placing the 0s and 1s in places that are more and more significant or less and less significant?
It doesn't quite work out because while it is clear what an infinite decimal expansion is, an integer number with infinitely many places is less clear what that means.
@@DrTrefor Is the same true for a 2-adic number?
@@erichpatrickenke2848 Yes. The 2-adic numbers are set-isomorphic to the real numbers. The only distinction is they are defined by different topologies.
2^N
Is this the part ofvdiscrete math playlist?
Yup! Well, the first half. I say it in the video, but power sets are standard topics but the continuum part is not.
@@DrTrefor are there more topics like continuum, that can be blended with discrete math?
Note video at 10:34 and this is something I am struggling with.
1. I understand how P(N) is uncountably infinite, that is | P(N) | > | N |
2. I understand how P(R) is uncountably infinite, that is | R | > | N |
A. For the life of me I do not understand how this binary representation of real numbers between [0, 1] guarantees that that there is a mapping of a binary representation of any number in that interval. How about (PI - 3)? That is the infinite decimal 0.141592653...? Why is this guaranteed to have a binary expansion of 1s and 0s that EXACTLY matches the VALUE represented by (PI - 3)? In other words why does 1. and 2. imply | P(N) | = | R |. Why is there guaranteed to always be a mapping?
B. If the answer is that any eventual binary expansion of (PI - 3) is guaranteed to result in an infinite binary number that eventually can be mapped to P(N), then why can't this same argument be used to Map the real interval [0,1] to the integers by simply writing out every decimal expansion of each R number in a matrix similar to the diagnal argument?
It's not quite clear what your second statement denotes.
The cardinality of the set ℕ of all _natural_ numbers (countable infinity) is called ℵ₀ (aleph null) or ℶ₀ (beth null), which is the same:
|ℕ| = ℵ₀ = ℶ₀
The cardinality of the power set 𝑷(ℕ) of the set ℕ of all _natural_ numbers is equal to the cardinality of the set ℝ of all _real_ numbers (the continuum 𝔠 or 𝒄):
|𝑷(ℕ)| = |ℝ| = 2^ℵ₀ = 2^ℶ₀ = ℶ₁ = 𝒄 > ℵ₀ = |ℕ| (beth one)
And the cardinality of the power set 𝑷(ℝ) of the set ℝ of _real_ numbers is equal to the cardinality of all functions from ℝ to ℝ (with discontinuities):
|𝑷(ℝ)| = 2^ℶ₁ = ℶ₂ > 𝒄 = |ℝ| (beth two)
And getting a _binary_ expansion of a number is similar to getting a _decimal_ expansion of a number (as well as any other base expansion).
very interesting video but i think you might need a new lav mic, it was hard to make out what you were saying at certain points.
Thanks supwe awEsOmeeeeeeeee
Sir can you guide me to write research papers in semigroup theory .
I feel like there is a gap in the logic at 9:52. We have a map from the power set to the decimals containing 0 and 1. How to you jump from that to claiming we have a map to the interval [0,1]? How was 0.555555… obtained?
Well any number in [0,1] can be written using binary numbers with 0=0.0000... and 1=0.11111111111. The choice of binary or decimal or anything else doesn't matter.
@@DrTrefor Oh, I see. The reason I was having a hard time thinking about that is because I was still mapping 1 ->1
Bit interesting and confusing too ..
Ok
There is no surjection between a smaller and larger set. Infinity is not a size.
"Infinity" is not a size in the same way that "finity" is not a size either, but there are various finite sizes, and there also are various infinite sizes.
Infinite: unending. Countable infinity is defined. There is no other “infinity.”
@@wernerhartl2069 False. You do not get to just make assertions you cannot prove.
@@wernerhartl2069 A set is finite, if its cardinality (number of elements) is equal to some natural number; any other set is infinite. Two sets have the same cardinality, if they can be mapped one-to-one. Under that definition, natural numbers can't be mapped one-to-one with real numbers (but they can be injected into real numbers); so natural numbers have a strictly lesser cardinality than real numbers.
@@MikeRosoftJH The set of natural numbers satisfies your definition for infinite set. Prove there is another set which satisfies your definition. You haven’t proven the natural numbers can’t be mapped one to one to the real numbers.
CDA assumes there is an infinite set other than the natural numbers which it purportedly tries to prove. It is a circular argument and therefore wrong.