We need to draft Dr Su into a revised and high definition recording of this wonderful course. His is the best intro to real analysis on the web! It is just so hard to read the chalkboard in many places during the lectures... encore! encore!
“R is uncountable, yet the set of computer programs is countable, so you know what this means. It means that there are some real numbers that can never be the output of a computer program.” Amazing!!!
17:25 "It says that there are some real numbers that can never be the output of a computer program." There is also the hardware issue. Since hardware is discrete (bits are on or off), floating point representations can only take certain values anyway. So the machine epsilon for a given floating point number (i.e., the "next" number) will skip uncountably many values. But the maths way of showing this is also cool.
@@HabibuMukhandi Pi can be the output of a program in the sense that you can say “give me n digits of pi” and the program can do it correctly as long as n is a finite number. It is not an output in the sense that you can output every digit of pi- the program would run forever. Any representation of pi is an estimate but when looking at the set of computable numbers pi is not “skipped over” because its digits can be generated to any desired level of precision. The difference in cardinality between the set of computer programs and the set of real numbers shows there must be numbers for which this level of arbitrary precision is not possible
The reason as to why it's uncountable is its cardinality. It turns out there are some numbers called transfinite numbers, used to measure or cardinality of infinite sets. Uncountable sets are sets whose cardinality is above the N's cardinality (Aleph-null). I'm afraid I don't know enough to tell you why exactly, but you can always search on the internet!
@38:00-@42:00 I think there may be a small mistake in his notes on the board, or maybe it's just not clear to me. Consider the element x in B. If x is in B then x is not in f(x). If x is not in B then x is in f(x). There implies the contradiction.
The rationals are indeed countable. Consider a infinite diagonal matrix with the first row being 1/1, 2/1, 3/1,... the second row being 1/2, 2/2, 3/2,....,and so on for all naturals. Then the matrix contains all positive rationals (since rational numbers are defined as the set of all numbers p/q with p/q being integers). Now remove all duplicate entries such as 2/4, 4/6, etc. If we count them all diagonally we can index each remaining entry as 1, 2, 3,..so a bijection exists with the naturals
Thanks Prof ! I could possibly understand the concept of Metric Spaces with different distances defined with it. hope I could apply them appropriately while solving Exercises ! Thanks Again !
So we have described both the set of all positive rationals and the set of all negative rationals as countable. Now consider the set containing only the number 0. This is a countable set with one element. The set of rationals can be described as the union of the set of positive rationals, the set of negative rationals, and the set with only 0. The union of countable sets is countable, so the rational numbers are countable.
Thanks for sharing such amazing lectures professor! I have one doubt regarding the proof of different cardinality between a set and a powerset. I thought it was more obvious to asign each element of A the subset 2^A of that one element, then we would exhaust the elements of A and still have elements in 2^A
I think what you are constructing is a mapping which is not bijection. "One mapping not being a bijection" does not prove "No mappings are not bijections". Professor is trying to prove there aren't any mappings are bijections. For example, similar to your method, we could also say that to prove that set of even numbers don't have the same cardinality as set of natural numbers, we could use the mapping F(x in evens) = same x in naturals, which exhausts all evens but doesn't exhaust all naturals, and conclude these two sets don't have the same cardinality. But we know this is not true.
Thanks public, that clears it up/ now I know what to google, etc. Are the rationals countable? I'm intrigued by irrational numbers. can any 2 irrationals be added to get a rational? (besides trivial examples like sqrt 2 + (1- sqrt 2) etc.) Or can they be multiplied to get a rational? What's that famous equation, something like e to the power of pi equals 1 or something? Also, besides irrationals and (presumably) transfinites, what other sets are uncountable?
The general proof that |X| < |2^X|, by Cantor, is related to the famous "Russell's Paradox". We can use |X| < |2^X| for another proof that |N| < |R| (N=integers, R=reals). Consider all binary representations of real numbers x, with 0
A set is infinite and countable if there exists a bijection from the natural numbers to that set. If there does not exists such a bijection then the set is uncountable. The Cantor diagonalization argument proves that you cannot count the irrational numbers, thus the Reals are uncountable (since the set of the reals is the union of the rational numbers and the irrational numbers). Therefore it the reals are uncountable since they contain an uncountable set.
Now consider the same argument with for all negative rationals by making each entry in the matrix of positive rationals a negative. By the same argument a bijection exists between the naturals and this set. Then this set is also countable.
Maybe I missed something, but it wasn't proven that changing elements of any set, countable or not, would make it uncountable. e.g., Let A = {all letters of the alphabet}. Then this should be countable, but if I take out S and put in -Z, then it's uncountable. So we can do this for every set. So, to reiterate, prove how changing the elements of a countable set wouldn't change it's countability status. Seems like it would since if we're allowed to change elements at random, no set is safe from this violation.
Here is a proof that |N| < |R| (N=integers, R=reals) based on their properties as ordered sets, without reference to their algebraic structure. Call an ordered set S "dense" if, given w and y in S with w
Instead of using a zig zag argument, can't you show U[A_n] is countable with induction? A_1 U A_2 is countable (as shown when we combined positive and negative rationals into "the rationals") assuming An=U[A_n] from 0 to n is countable, then An U A_n+1 is also countable thus U[A_n+1] from 0 to n+1 is countable. Therefore by induction the union of a countable number of countable sets is countable.
I don't understand 17:25. He claims that a real number is computable if there exists some computer program who can output that number up to k decimal expansions. However, if we are granting that it is sufficient to come up with k digits (rather than the whole thing) then the desired object is simply a k-pair, and the set of all k-pairs is countable. Hence, the k approximation of a real number is computable because there is a one to one correspondence between the set of computer programs and the set of k approximations of real numbers.
What he's saying is 100% correct. There is a subtle point that you missed. k is not predetermined, but it is an *input* to the computer program. We call computations that take such an input an 'arbitrary-precision computation.' Consider such a program P that computes some irrational constant r. So P(k) = r truncated to k decimal digits. Construct sets Ai = {q in Q : q < P(i)} Now consider A = A0 u A1 u A2 u ... The set A is in fact the Dedekind cut that represents r. Put another way, r can also be thought as the supremum of all possible outputs of P. So having the program P that computes an arbitrarily precise approximation of r is as good as having the real number r, and we can safely say that program P "computes" r. Since there are many more irrational numbers than there are computer programs, some irrationals are not computable to an arbitrary precision. Therefore, some reals are not computable to an arbitrary precision. ("arbitrary precision" is the keyword.)
No. The set of reals is uncountable, but not because it is infinite. the set of natural numbers is infinite, but countable. I believe the rationals are also countable and infinite (not sure, because rationals 0 to 1 are infinite too). I think The reals are uncountable because of their inclusion of irrationals, but I'm not sure why this is so.
The sum of any number with an irrational number is always an irrational number. This is easy to prove. Consider that all irrational numbers have infinitely repeating decimal expansions. Then the sum of any number with an irrational will also have an infinitely repeating decimal expansion. So that number is not rational, since all rational numbers have terminating decimal expansions.
The sum of "2 - squareroot of 2" and "the squareroot of 2" is a rational not an irrational so your statement that it is easy to prove that their sum is irrational is false. (You started off by saying the "sum of any number with an irrational" and I chose "any number" to have the value I want it to have.)
We need to draft Dr Su into a revised and high definition recording of this wonderful course. His is the best intro to real analysis on the web! It is just so hard to read the chalkboard in many places during the lectures... encore! encore!
Aamen
Agreed
he has lecture notes on the site that have some of what he put on the board plus additional things.
@@SequinBrain Which site has lecture notes?
@@Helmutandmoshe it's in the details. click the school link, then click the lecture notes tab.
Cantor Diagonalization is one of the most amazing things I've come across in Math. Right up there with Godel.
This is an amazing lecture series
“R is uncountable, yet the set of computer programs is countable, so you know what this means. It means that there are some real numbers that can never be the output of a computer program.” Amazing!!!
metric spaces starts at 51
17:25 "It says that there are some real numbers that can never be the output of a computer program."
There is also the hardware issue. Since hardware is discrete (bits are on or off), floating point representations can only take certain values anyway. So the machine epsilon for a given floating point number (i.e., the "next" number) will skip uncountably many values. But the maths way of showing this is also cool.
But he also says Pi can be an output of a computer program, how do you explain that?
@@HabibuMukhandi Pi can be the output of a program in the sense that you can say “give me n digits of pi” and the program can do it correctly as long as n is a finite number. It is not an output in the sense that you can output every digit of pi- the program would run forever. Any representation of pi is an estimate but when looking at the set of computable numbers pi is not “skipped over” because its digits can be generated to any desired level of precision.
The difference in cardinality between the set of computer programs and the set of real numbers shows there must be numbers for which this level of arbitrary precision is not possible
The reason as to why it's uncountable is its cardinality. It turns out there are some numbers called transfinite numbers, used to measure or cardinality of infinite sets. Uncountable sets are sets whose cardinality is above the N's cardinality (Aleph-null). I'm afraid I don't know enough to tell you why exactly, but you can always search on the internet!
@38:00-@42:00 I think there may be a small mistake in his notes on the board, or maybe it's just not clear to me.
Consider the element x in B.
If x is in B then x is not in f(x).
If x is not in B then x is in f(x).
There implies the contradiction.
Thank you Professor Su for your helpful videos.
Thank you for sharing these videos. I really hope that you would consider uploading Real Analysis II. :-)
These lectures are 💯💯💯💯💯💯....... Uncountably good 😊👌
Thanks so much, Professor Su,
For those looking for Metric spaces jump to minute 51 of the recording.
The rationals are indeed countable. Consider a infinite diagonal matrix with the first row being 1/1, 2/1, 3/1,... the second row being 1/2, 2/2, 3/2,....,and so on for all naturals. Then the matrix contains all positive rationals (since rational numbers are defined as the set of all numbers p/q with p/q being integers). Now remove all duplicate entries such as 2/4, 4/6, etc. If we count them all diagonally we can index each remaining entry as 1, 2, 3,..so a bijection exists with the naturals
Thanks Prof ! I could possibly understand the concept of Metric Spaces with different distances defined with it. hope I could apply them appropriately while solving Exercises ! Thanks Again !
An uncountable set is a set that countains too many elements to count. R, for example, is uncountable, because there are infinite elements in it.
So we have described both the set of all positive rationals and the set of all negative rationals as countable. Now consider the set containing only the number 0. This is a countable set with one element. The set of rationals can be described as the union of the set of positive rationals, the set of negative rationals, and the set with only 0. The union of countable sets is countable, so the rational numbers are countable.
Thanks for sharing such amazing lectures professor! I have one doubt regarding the proof of different cardinality between a set and a powerset. I thought it was more obvious to asign each element of A the subset 2^A of that one element, then we would exhaust the elements of A and still have elements in 2^A
I think what you are constructing is a mapping which is not bijection. "One mapping not being a bijection" does not prove "No mappings are not bijections". Professor is trying to prove there aren't any mappings are bijections.
For example, similar to your method, we could also say that to prove that set of even numbers don't have the same cardinality as set of natural numbers, we could use the mapping F(x in evens) = same x in naturals, which exhausts all evens but doesn't exhaust all naturals, and conclude these two sets don't have the same cardinality. But we know this is not true.
Thanks public, that clears it up/ now I know what to google, etc. Are the rationals countable? I'm intrigued by irrational numbers. can any 2 irrationals be added to get a rational? (besides trivial examples like sqrt 2 + (1- sqrt 2) etc.) Or can they be multiplied to get a rational? What's that famous equation, something like e to the power of pi equals 1 or something?
Also, besides irrationals and (presumably) transfinites, what other sets are uncountable?
The general proof that |X| < |2^X|, by Cantor, is related to the famous "Russell's Paradox". We can use |X| < |2^X| for another proof that |N| < |R| (N=integers, R=reals). Consider all binary representations of real numbers x, with 0
A set is infinite and countable if there exists a bijection from the natural numbers to that set. If there does not exists such a bijection then the set is uncountable.
The Cantor diagonalization argument proves that you cannot count the irrational numbers, thus the Reals are uncountable (since the set of the reals is the union of the rational numbers and the irrational numbers). Therefore it the reals are uncountable since they contain an uncountable set.
Excellent lecture series...
If the number of infinite cardinalities is uncountably infinite then how can we index the aleph numbers by natural numbers?
Now consider the same argument with for all negative rationals by making each entry in the matrix of positive rationals a negative. By the same argument a bijection exists between the naturals and this set. Then this set is also countable.
hello folks, check out his link. The lectures have notes that clear up most of the issues with reading the boards.
51:20 Metric Spaces
Maybe I missed something, but it wasn't proven that changing elements of any set, countable or not, would make it uncountable. e.g., Let A = {all letters of the alphabet}. Then this should be countable, but if I take out S and put in -Z, then it's uncountable. So we can do this for every set. So, to reiterate, prove how changing the elements of a countable set wouldn't change it's countability status. Seems like it would since if we're allowed to change elements at random, no set is safe from this violation.
@1:04:30 writes GATTACA and says "I just made that up!" lol
excellent lecture
Here is a proof that |N| < |R| (N=integers, R=reals) based on their properties as ordered sets, without reference to their algebraic structure. Call an ordered set S "dense" if, given w and y in S with w
video quality is too low.
He must be using the book "Understanding Analysis" by Stephen Abbott.
+56jmoney the class book is baby rudin
Abbott doesn't construct the reals until the last chapter
Instead of using a zig zag argument, can't you show U[A_n] is countable with induction?
A_1 U A_2 is countable (as shown when we combined positive and negative rationals into "the rationals")
assuming An=U[A_n] from 0 to n is countable, then An U A_n+1 is also countable thus U[A_n+1] from 0 to n+1 is countable.
Therefore by induction the union of a countable number of countable sets is countable.
I don't understand 17:25. He claims that a real number is computable if there exists some computer program who can output that number up to k decimal expansions. However, if we are granting that it is sufficient to come up with k digits (rather than the whole thing) then the desired object is simply a k-pair, and the set of all k-pairs is countable. Hence, the k approximation of a real number is computable because there is a one to one correspondence between the set of computer programs and the set of k approximations of real numbers.
What he's saying is 100% correct. There is a subtle point that you missed. k is not predetermined, but it is an *input* to the computer program. We call computations that take such an input an 'arbitrary-precision computation.'
Consider such a program P that computes some irrational constant r. So P(k) = r truncated to k decimal digits.
Construct sets Ai = {q in Q : q < P(i)}
Now consider A = A0 u A1 u A2 u ...
The set A is in fact the Dedekind cut that represents r. Put another way, r can also be thought as the supremum of all possible outputs of P.
So having the program P that computes an arbitrarily precise approximation of r is as good as having the real number r, and we can safely say that program P "computes" r. Since there are many more irrational numbers than there are computer programs, some irrationals are not computable to an arbitrary precision. Therefore, some reals are not computable to an arbitrary precision. ("arbitrary precision" is the keyword.)
What's NOT countable?
my brain is damaged by little's..
No. The set of reals is uncountable, but not because it is infinite. the set of natural numbers is infinite, but countable. I believe the rationals are also countable and infinite (not sure, because rationals 0 to 1 are infinite too). I think The reals are uncountable because of their inclusion of irrationals, but I'm not sure why this is so.
The sum of any number with an irrational number is always an irrational number. This is easy to prove. Consider that all irrational numbers have infinitely repeating decimal expansions. Then the sum of any number with an irrational will also have an infinitely repeating decimal expansion. So that number is not rational, since all rational numbers have terminating decimal expansions.
It's been 8 years but sqrt(2) - sqrt(2) = 0 which is rational.
1:05:25 A GAT CAT 😾🔫😤😤
The sum of "2 - squareroot of 2" and "the squareroot of 2" is a rational not an irrational so your statement that it is easy to prove that their sum is irrational is false. (You started off by saying the "sum of any number with an irrational" and I chose "any number" to have the value I want it to have.)
are you with me?
Are you with me?
Ok, just to confirm: is there an excuse for him not teaching it exactly how you want it?
Why is this prof so slow?