An intuitive way to see why the warm up excercise is true is to consider any subset . It either has 1 or it doesn't. It either has 2 or it doesn't. . . . It either has n or it doesn't. So we have 2 choices for each number, either its in the set or its not. So by the principal of counting we can have 2 to the power of n (2^n) possible subsets. The case where none of the numbers are in the set is the empty set. You could also write this argument out more rigoursly which is a fun excercise.
I think this isn't quite a bijection, because numbers with terminating expansions have an alternative expansion (e.g. 1/2 = 0.1000... = 0.0111...). However, there are only countably many numbers with that property since they form a subset of the rationals. Moreover they correspond to finite subsets of the naturals excluding the empty set (and their complements). There might be a way to patch the function, but I don't know how. Still, the function is injective since every real number gets mapped onto a different subset of the naturals. We can construct an injective function from P(ℕ) to [0,1] using base 3: - If the complement of the subset is not finite, use the same representation as in the video using 0's and 1's but in base 3. - If the complement of the subset is finite, use the the same representation as in the video for the complement of the subset using 0's and 2's. All elements of P(ℕ) will be mapped to a different number in [0,1] by this function. This way, we have an injection from ℝ to P(ℕ), and an injection form P(ℕ) to ℝ, so there must exist a bijection. (Edit: I had injective and surjective mixed up...)
How about sending decimal 0.5 to binary 0.1, and decimal 0.499... to binary 0.0111...? Then there is merely one exception that needs to be explicitly dealt with: decimals 1 and 0.999...
@@andyl.5998 that doesn’t help as .4999... =0.5 so by that function definition you are still mapping one number to 2 elements of the power set, hence not well defined. (There will presumably be a rigorous way to handle this in a text book.)
@@carl3260 Thanks for the reply! Yes .4999... = 0.5, but only because of the specific construction of ℝ that we implicitly assumed. If we explicitly state the assumed equivalence relation, we can set a similar equivalence relation on the power set, thus repairing the bijection.
@@andyl.5998 you can, but then you have a bijection from R to a subset of the power set, which is not the aim.. (ie injective wrt full power set, but not surjective). As others on here have said, an alternative proof is to find an injective function in each direction (which implies bijectivity). I think this works... Call the one stated f, which is injective R to P(N) and if a=b are diff binary representations, choose f(a), so well defined (remember the “b”s for later). For the reverse function, map each subset of N to .5a, its inverse image under f, if it has one, which map to [0,.5]; otherwise map to .5 + .5b (it’s “discarded” inverse image), which map into (0.5,1). This is injective. So overall there’s a bijection.
For your next video, you should prove the Continuum Hypothesis. :D Edit: considering the objection several of us have raised, perhaps your next video should be the Cantor-Schröder-Bernstein Theorem.
5:34 This isn't true for those reals which have a terminating binary expansion, viz. dyadic fractions. (Or should that be i.e.? But I digress.) E.g., 0.1000... = 0.0111.... However, this only affects countably many elements. (I haven't finished the video, so possibly you address this.)
Tom Kerruish this happens only countably many times as you said, so a way to fix this detail could be to enumerate this cases. Then for the countably many cases left just use a Hilbert Hotel-like argument
Well, if you take the equivalence relation(~) by saying two numbers are related if represent the same number you can define this function in R/~ and it would be well defined, although you have to prove this new set has the same cardinality of R, which is easy
Some care needs to be taken in defining f due to 1=0.1111.... in binary, to what subset is the real number 0.01111...=0.1 taken? {1} or {2,3,...} if you choose only one of them, the function is not surjective anymore too.
Choosing only one is enough because the irractonal numbers have only one binary representation. Since the cardinality of the irractonal numbers is equal to the real numbers, the bijection is enough.
Binary version of 1 = 0.9999... as 1 is the highest digit in binary. In general it can be easily shown that 0.ddddd... = 1 in any number system of base b when d = b - 1
Since completeness axiom implies nested interval theorem and this theorem implies the uncountability of R, we can see that the uncountability of R is a result of completeness axiom.
Right at the beginning it says that previously it has been shown that |(a.b)| = |[a,b]| does anyone have a link to the video where this is demonstrated?
Not sure about your mapping here. Many binary fractions can be represented in two ways. For example 1/2 = 0.1 or 0.011111111... These will map to different sets, one finite and the other infinite. So the cardinality of P(N) would seem to be greater than that of [0,1] Are you relying on the fact that twice the number of the continuum is still the same number? Any number in [0,1] having either one or two mappings. Or are you excluding the countably many multiples of powers of (1/2) that exhibit this duality? Either way you have to say so. It's not complete as given. In an exam this answer would get a reasonably good mark but still short of full marks, I suggest.
Это же пруф для Канторова множества, что его мощность равна 2^n. А то, что в видео, уже выводится с помощью Канторова множества и теоремы Кантора-Бернштейна. Хотя, наверное, можно и так, но мой вариант мне кажется показательнее
As others have noted, the binary expansions of dyadic fractions are not unique. E.g. ½ = 0.1 = 0.111... base 2. The fix to this proof is to instead note that f is a surjection. Then, make the same construction using decimal instead, so that g({1}) = 0.1 = 1/10 and g({2,3,4,...} = 0.0111... = 1/90, which are distinct. Note that g is an injection. So by Schröder-Bernstein, there exists a bijection betwee P(N) and R.
To fix the problem with the repeating numbers like 0.1111...=1 one way is numbering just the irrational numbers instead of all the real numbers, since both sets have same cardinality. This numbers have unique binary representation.
For uniqueness of the binary expansion: Consider two distinct expansions α=0.a1a2a3… and β=0.b1b2b3... of the irractional numbers α,β. As the expansions are distinct, there are indices k where ak≠bk. Let n be the smallest such index. Then ai=bi for 1≤i
Sir, first let me say that you are a really great lecturer. Keep it up. I don't want this come off as rude, but can you please address the comments that the others have brought up to clarify things? This will be greatly appreciated.
What result shows that all real numbers can be written with a (possibly infinite) binary (or decimal) expansion? From what I can tell, you've shown that the set of all numbers with such expansions is equinumerous to the power set of the natural numbers. The step I'm missing is probably very simple, and is certainly intuitively true...
but then you won't have a bijection with this function if set = {1,1,1,1....} cannot have an inverse image. as someone commented already, using shroder-berstein theorem helps (find two different injective functions, from P to R and from R to P).
Prof. Penn Here is a problem you should do in your next video If p,q,w are positive integers such that 1+p+q√3 = (2+√3)^(2w-1) then prove that p is a perfect square.
@@________6295 i noticed that p creates a series with p_{w} = (x_{w})^2 , which we can define as x_{w+1}=4x_{w}-x_{w-1}. Then expanding given binomial we can separate "sqrt 3" thing to get a sum. Then just using generating function we can write p_{w} in terms of that sum to prove that p is indeed a square. I guess there is a simplier solution, will see
it is easy to see that p_n=p_n, p_{n+1}=7(1+p_n)+12q-1 p_{n+2}=49(1+p_n)+84q+84q+48(1+p_n)=97(1+p_n)+168q-1, just by multiplying by (2+sqrt{3})^2=7+4sqrt{3}. So p_{n+2}=14*p_{n+1} - p_{n} + 12 with p_{0}=1, p_{1}=25 Let x_{n+2}=4*x_{n+1}-x_{n} and x_{0}=1, x_{1}=5 Claim: p_{n}=x_{n}^2 Pf.: strong induction on n; sps it is true for all i
I have really good question for you if alpha and beta are roots of equation x^2-x-1(Fibonacci equation) we define a function f(n)=alpha^n+beta^n then prove that f(n+1)=f(n)+f(n-1)
An intuitive way to see why the warm up excercise is true is to consider any subset .
It either has 1 or it doesn't.
It either has 2 or it doesn't.
.
.
.
It either has n or it doesn't.
So we have 2 choices for each number, either its in the set or its not. So by the principal of counting we can have 2 to the power of n (2^n) possible subsets.
The case where none of the numbers are in the set is the empty set.
You could also write this argument out more rigoursly which is a fun excercise.
I think this isn't quite a bijection, because numbers with terminating expansions have an alternative expansion (e.g. 1/2 = 0.1000... = 0.0111...). However, there are only countably many numbers with that property since they form a subset of the rationals. Moreover they correspond to finite subsets of the naturals excluding the empty set (and their complements). There might be a way to patch the function, but I don't know how.
Still, the function is injective since every real number gets mapped onto a different subset of the naturals. We can construct an injective function from P(ℕ) to [0,1] using base 3:
- If the complement of the subset is not finite, use the same representation as in the video using 0's and 1's but in base 3.
- If the complement of the subset is finite, use the the same representation as in the video for the complement of the subset using 0's and 2's.
All elements of P(ℕ) will be mapped to a different number in [0,1] by this function.
This way, we have an injection from ℝ to P(ℕ), and an injection form P(ℕ) to ℝ, so there must exist a bijection.
(Edit: I had injective and surjective mixed up...)
Yes, I also thought so, his function was actually ill-defined, because the binary-expansion ISNT unique 👍
How about sending decimal 0.5 to binary 0.1, and decimal 0.499... to binary 0.0111...?
Then there is merely one exception that needs to be explicitly dealt with: decimals 1 and 0.999...
@@andyl.5998 that doesn’t help as .4999... =0.5 so by that function definition you are still mapping one number to 2 elements of the power set, hence not well defined. (There will presumably be a rigorous way to handle this in a text book.)
@@carl3260 Thanks for the reply! Yes .4999... = 0.5, but only because of the specific construction of ℝ that we implicitly assumed. If we explicitly state the assumed equivalence relation, we can set a similar equivalence relation on the power set, thus repairing the bijection.
@@andyl.5998 you can, but then you have a bijection from R to a subset of the power set, which is not the aim.. (ie injective wrt full power set, but not surjective).
As others on here have said, an alternative proof is to find an injective function in each direction (which implies bijectivity). I think this works...
Call the one stated f, which is injective R to P(N) and if a=b are diff binary representations, choose f(a), so well defined (remember the “b”s for later). For the reverse function, map each subset of N to .5a, its inverse image under f, if it has one, which map to [0,.5]; otherwise map to .5 + .5b (it’s “discarded” inverse image), which map into (0.5,1). This is injective. So overall there’s a bijection.
Thanks!
I am so thankful this playlist is made public and free. Thanks so much Michael
For your next video, you should prove the Continuum Hypothesis. :D
Edit: considering the objection several of us have raised, perhaps your next video should be the Cantor-Schröder-Bernstein Theorem.
5:34 This isn't true for those reals which have a terminating binary expansion, viz. dyadic fractions. (Or should that be i.e.? But I digress.) E.g., 0.1000... = 0.0111.... However, this only affects countably many elements. (I haven't finished the video, so possibly you address this.)
Tom Kerruish this happens only countably many times as you said, so a way to fix this detail could be to enumerate this cases. Then for the countably many cases left just use a Hilbert Hotel-like argument
Well, if you take the equivalence relation(~) by saying two numbers are related if represent the same number you can define this function in R/~ and it would be well defined, although you have to prove this new set has the same cardinality of R, which is easy
Some care needs to be taken in defining f due to 1=0.1111.... in binary, to what subset is the real number 0.01111...=0.1 taken? {1} or {2,3,...} if you choose only one of them, the function is not surjective anymore too.
Choosing only one is enough because the irractonal numbers have only one binary representation. Since the cardinality of the irractonal numbers is equal to the real numbers, the bijection is enough.
how do we deal with 0.1 = 0.011111... ?
beacaue it is binary
Binary version of 1 = 0.9999... as 1 is the highest digit in binary.
In general it can be easily shown that 0.ddddd... = 1 in any number system of base b when d = b - 1
Since completeness axiom implies nested interval theorem and this theorem implies the uncountability of R, we can see that the uncountability of R is a result of completeness axiom.
Right at the beginning it says that previously it has been shown that |(a.b)| = |[a,b]| does anyone have a link to the video where this is demonstrated?
Not sure about your mapping here.
Many binary fractions can be represented in two ways. For example 1/2 = 0.1 or 0.011111111...
These will map to different sets, one finite and the other infinite. So the cardinality of P(N) would seem to be greater than that of [0,1]
Are you relying on the fact that twice the number of the continuum is still the same number? Any number in [0,1] having either one or two mappings.
Or are you excluding the countably many multiples of powers of (1/2) that exhibit this duality?
Either way you have to say so. It's not complete as given. In an exam this answer would get a reasonably good mark but still short of full marks, I suggest.
Это же пруф для Канторова множества, что его мощность равна 2^n. А то, что в видео, уже выводится с помощью Канторова множества и теоремы Кантора-Бернштейна. Хотя, наверное, можно и так, но мой вариант мне кажется показательнее
What is the probability that a 2 by 2 matrix has a zero determinant? Could you please solve this? I enjoy your explanations. Real cool.
In R it's 0.
Depends on the field
Also depends on the joint distribution of the components of the matrix. Otherwise, can be anything from 0 to 1.
As others have noted, the binary expansions of dyadic fractions are not unique. E.g. ½ = 0.1 = 0.111... base 2. The fix to this proof is to instead note that f is a surjection. Then, make the same construction using decimal instead, so that g({1}) = 0.1 = 1/10 and g({2,3,4,...} = 0.0111... = 1/90, which are distinct. Note that g is an injection. So by Schröder-Bernstein, there exists a bijection betwee P(N) and R.
oi Michael, have you tried learning some quantum computing, I think you'll find it interesting
Vc eh br?
@@arthurgames9610 O público aqui é majoritariamente brasileiro. Apenas ficamos disfarçados nas sombras.
To fix the problem with the repeating numbers like 0.1111...=1 one way is numbering just the irrational numbers instead of all the real numbers, since both sets have same cardinality. This numbers have unique binary representation.
For uniqueness of the binary expansion:
Consider two distinct expansions α=0.a1a2a3… and β=0.b1b2b3... of the irractional numbers α,β. As the expansions are distinct, there are indices k where ak≠bk. Let n be the smallest such index. Then ai=bi for 1≤i
Nicely explained! Thanks Michael :)
Sir, first let me say that you are a really great lecturer. Keep it up. I don't want this come off as rude, but can you please address the comments that the others have brought up to clarify things? This will be greatly appreciated.
What result shows that all real numbers can be written with a (possibly infinite) binary (or decimal) expansion? From what I can tell, you've shown that the set of all numbers with such expansions is equinumerous to the power set of the natural numbers.
The step I'm missing is probably very simple, and is certainly intuitively true...
So g({even naturals}) = 1/3; g({odd naturals}) = 2/3. I suppose g(A)+g(B)=1 if A and B are disjoint and AUB=N.
A way to avoid the 1 = 0.111... problem and get unique expansions is simply to forbid expansions that end with infinitely many ones.
but then you won't have a bijection with this function if set = {1,1,1,1....} cannot have an inverse image.
as someone commented already, using shroder-berstein theorem helps (find two different injective functions, from P to R and from R to P).
That effectively excludes all sets defined to contain all integers above some arbitrary N.
Prof. Penn
Here is a problem you should do in your next video
If p,q,w are positive integers such that 1+p+q√3 = (2+√3)^(2w-1) then prove that p is a perfect square.
This is pretty easy, not for entire video
@@zzz942
how did u do it?
@@________6295 i noticed that p creates a series with p_{w} = (x_{w})^2 , which we can define as x_{w+1}=4x_{w}-x_{w-1}. Then expanding given binomial we can separate "sqrt 3" thing to get a sum. Then just using generating function we can write p_{w} in terms of that sum to prove that p is indeed a square. I guess there is a simplier solution, will see
@@________6295 well... It can be easier...
it is easy to see that p_n=p_n,
p_{n+1}=7(1+p_n)+12q-1
p_{n+2}=49(1+p_n)+84q+84q+48(1+p_n)=97(1+p_n)+168q-1, just by multiplying by (2+sqrt{3})^2=7+4sqrt{3}. So p_{n+2}=14*p_{n+1} - p_{n} + 12 with p_{0}=1, p_{1}=25
Let x_{n+2}=4*x_{n+1}-x_{n} and x_{0}=1, x_{1}=5
Claim: p_{n}=x_{n}^2
Pf.: strong induction on n; sps it is true for all i
By the definition of function g introduced in video, g( {1} ) = 0.5, and g ({ 2,3,4,5, .. }) = 0.5 hmm.. i can't think the function g is bijection.
thaaaaanks👍👍
I have really good question for you if alpha and beta are roots of equation x^2-x-1(Fibonacci equation) we define a function f(n)=alpha^n+beta^n then prove that f(n+1)=f(n)+f(n-1)
This is complex af
You move so much that's distracting