I'm studying computation theory, and I think that this method of using the injection's contrapositive is exactly how we're supposed to disprove turing decidability. Thank you.
9:44 Wth, why is f(a) supposed to have anything to do with subsets??? How is running a function on every element of a set supposed to make it its powerset???
The question is: can a set be mapped one-to-one with its powerset (set of all its subsets)? And the answer is: no, it can't. Given any function from set A to P(A), there is some element of P(A) (some subset of A) which this function doesn't cover. And that set is precisely the diagonal set of this function. For example, let f be the function x->{x} (on some set A); then the diagonal set of this function (set of all elements of A, such that f(x) doesn't contain the element x) is the empty set; and indeed no element of A is mapped to the empty set - any element is mapped to a set containing exactly one element. In fact, there are many subsets of A which the function doesn't cover. If A is an infinite set which can be mapped one-to-one with two copies of itself (assuming axiom of choice, this is true for all infinite sets), then given any function from A to P(A), the set of all elements of P(A) which the function does not cover can be mapped one-to-one with P(A).
It doesn't matter whether or not D is empty. The empty set is still a subset of A. As such, if the empty set is not in the image of f, then f doesn't hit everything.
That is only ONE way to find relations between N and R, and a trick is used... we are not using all the semantic power using Naturals. Naturals are naturals, they have their cardinal, okey, but we can configure it in incredible ways using what i call the CLJA. The LJA construction. I can change a little that relation, just to show they have the same cardinal, so you need to define a new relations, and i can change it again to make them equal... I have the inverse diagonal: i have a countable set, and I can create a relation between N and a set with a cardinal equal to R, or N1, in a similar way. Always, i have naturals outside that relation, and all the other elements, from the other set, are in the relation. {0,1} ^W You can change the realtion like i do in "diagonal argument", but in my relation, you can never reach the infinite, but your set is "equal" to R :D. Is pretty similar argument... Thanks, because I was trying to find the proof about surjection was impossible, it's the diagonal argument. So now, i can say it pretty sure. The only thing i need to find is the STRONG proof, that is not diagonal (I suppouse). The problem with the diagonal argument is... IT'S TRUE... but that things happens with sets with equal cardinal. You can find "bad" relations between them that makes one, aparently, bigger than the other: 1) f(n) = n*2 + 2 Naturals -> Pairs 2) {0,1} -> R Take decimal digit in groups of three. 0,ABCABCABCABCABC A: Z digits from the real number, complete with zeros the rest. B: decimal digits from the real number, complete with zero, in case of a number that belongs to I, we have infinite positions. C: ONE digit, always the same.. example: "1" 34,565745 -> 0,351461051071041051 In that case we still have the other reals with the rest of digits in positions C, and we have a pair for all the real numbers. ¿There is another proof that are not the diagonal argument? (About surjection is impossible) Thanks for your time.
The constructed sequence is different from every member of the list because it is the last member of the list, which doesn’t exist just as the last member of 1,2,3,... doesn’t exist because it is an infinite, endless, sequence. And how do you construct an infinite (endless) list in the first place?
No. The diagonal set *isn't* the last element of an infinite sequence. You *don't* construct the diagonal set in stages; you define it in a single step as a whole. And nothing in the proof depends on the set being a set of all natural numbers. The set can be *any* set whatsoever. It could be the set of all real numbers, or the set of all functions on real numbers, or - in absence of axiom of choice - something exotic like a set whose cardinality is incomparable with natural numbers (in other words, which is infinite but doesn't contain a countably infinite subset). And that an infinite set exists is a consequence of the axiom of infinity, which essentially says: there is a set which contains all natural numbers. (But that's beside the point; nothing in the proof depends on whether the set is finite or infinite. The diagonal set is constructed using the axiom of separation.)
@@MikeRosoftJH The axiom of separation says the set exists, it doesn’t say you can construct it. And the axiom of infinity only guarantees the existence of a set containing the natural numbers.
@@wernerhartl2069 Okay, can you "construct" the number googolplex? In set theory "constructing a set" is generally understood to mean defining it with a formula; and here the set in question indeed is definable with a formula (and that a set satisfying the formula exists is a consequence of the axiom of separation; and that it's unique follows from the axiom of extensionality). Besides, it's nowhere given that every set needs to be definable with a formula. For example, from the axiom of choice it follows that every set can be well-ordered (such that every two elements are comparable, and every its non-empty subset has a unique minimum). So it follows that real numbers can be well-ordered (observe that the usual numeric order on real numbers is not a well-ordering relation). The notion that ~ is a well-ordering relation on real numbers *is* definable with a formula. But it's not possible to define a specific well-ordering relation on reals, in the following sense - there's no formula for which the following can be proven: there exists exactly one set satisfying this formula, and that set is a well-ordering of real numbers. Axiom of infinity (together with the axiom of separation) allows us to define (or "construct") the set of all natural numbers as an intersection of all sets which satisfy the axiom of infinity.
I never really found this proof very convincing. It comes down to how we define things. Can something that takes infinite steps to be constructed exist ? Because I believe anything that takes infinite time to come into existence cannot exist. For the number to exist, you have to stop at some point to add it back to the set. But the paradox is that you can't stop. I see a lot of people saying, we don't construct it we define it. I mean what's the difference ? Also how is this different from let's say a theorem that scans all the numbers in the set and adds 1 to the highest number in that set. This way we can prove that natural numbers are also not countable.
@@TomasAragorn From en.m.wikipedia.org/wiki/Cantor%27s_diagonal_argument Section Uncountable Sets. “Cantor considered the set T of all infinite sequences of binary digits.” “If s1, s2, ... , sn, ... is any enumeration of elements from T,[note 2] then an element s of T can be constructed that doesn't correspond to any sn in the enumeration.” 1) What is the definition of infinity? 2) What is an enumeration? 3) How do you construct it?
@@wernerhartl2069 I don't think it's worth trying to explain it to you, since plenty of people have already done so (including me) on your nonsensical videos. Maybe delete those videos
No, Cantor's Theorem does not rely on the Axiom of Choice. There is only one choice to be made: selecting the subset D of A. Informally, (some version of) the Axiom of Choice is only necessary when you have to make infinitely many choices. You don't need the Axiom of Choice to make finitely many choices.
The video makes precisely the same mistake as above; you don't construct the diagonal set in stages - you define it as a whole. That the diagonal set exists is a consequence of the axiom of separation. (And conveniently, you have disabled comments on the video so that nobody could challenge you.)
![1.11.7 The Halting Problem: Video [Optional]](http://i.ytimg.com/vi/WQHOImO0pX0/mqdefault.jpg)
![1.11.7 The Halting Problem: Video [Optional]](/img/tr.png)
I'm studying computation theory, and I think that this method of using the injection's contrapositive is exactly how we're supposed to disprove turing decidability. Thank you.
Isn't 3.33... 11.0101... in binary, instead of 111.0101?
Yeah...
Oh my gosh it finally snapped! Thanks for this!!!
19:58 cat
So clear. What a wonderful, enthusiastic educator. I will look for more of his tutorials.
There is a hole in the argument: if a is not in f(a) then a is maybe in f(b) for some b in Set A
It is very helpful that you use binary system as opposed to whole numbers. Helps me visualize the diagonalization argument. Thank you for this.
Thanks for explaining this. It really helped me understand the purpose of Cantor's Diagonal Argument, and the cat is very entertaining.
16:28 cat!
amazing lecture sir, thank you so much
9:44 Wth, why is f(a) supposed to have anything to do with subsets??? How is running a function on every element of a set supposed to make it its powerset???
The question is: can a set be mapped one-to-one with its powerset (set of all its subsets)? And the answer is: no, it can't. Given any function from set A to P(A), there is some element of P(A) (some subset of A) which this function doesn't cover. And that set is precisely the diagonal set of this function. For example, let f be the function x->{x} (on some set A); then the diagonal set of this function (set of all elements of A, such that f(x) doesn't contain the element x) is the empty set; and indeed no element of A is mapped to the empty set - any element is mapped to a set containing exactly one element.
In fact, there are many subsets of A which the function doesn't cover. If A is an infinite set which can be mapped one-to-one with two copies of itself (assuming axiom of choice, this is true for all infinite sets), then given any function from A to P(A), the set of all elements of P(A) which the function does not cover can be mapped one-to-one with P(A).
Nice lecture, thanks!
18:50 How do we know we will hit every possible inifinite string?
That was awesome
how do we know that the set D is not empty?
It doesn't matter whether or not D is empty. The empty set is still a subset of A. As such, if the empty set is not in the image of f, then f doesn't hit everything.
That is only ONE way to find relations between N and R, and a trick is used... we are not using all the semantic power using Naturals. Naturals are naturals, they have their cardinal, okey, but we can configure it in incredible ways using what i call the CLJA. The LJA construction. I can change a little that relation, just to show they have the same cardinal, so you need to define a new relations, and i can change it again to make them equal...
I have the inverse diagonal: i have a countable set, and I can create a relation between N and a set with a cardinal equal to R, or N1, in a similar way. Always, i have naturals outside that relation, and all the other elements, from the other set, are in the relation. {0,1} ^W
You can change the realtion like i do in "diagonal argument", but in my relation, you can never reach the infinite, but your set is "equal" to R :D. Is pretty similar argument...
Thanks, because I was trying to find the proof about surjection was impossible, it's the diagonal argument. So now, i can say it pretty sure. The only thing i need to find is the STRONG proof, that is not diagonal (I suppouse).
The problem with the diagonal argument is... IT'S TRUE... but that things happens with sets with equal cardinal. You can find "bad" relations between them that makes one, aparently, bigger than the other:
1) f(n) = n*2 + 2 Naturals -> Pairs
2) {0,1} -> R
Take decimal digit in groups of three. 0,ABCABCABCABCABC
A: Z digits from the real number, complete with zeros the rest.
B: decimal digits from the real number, complete with zero, in case of a number that belongs to I, we have infinite positions.
C: ONE digit, always the same.. example: "1"
34,565745 -> 0,351461051071041051
In that case we still have the other reals with the rest of digits in positions C, and we have a pair for all the real numbers.
¿There is another proof that are not the diagonal argument? (About surjection is impossible)
Thanks for your time.
Fistro Man I don't understand your examples. How do you say that one set is bigger than the other using your examples?
The constructed sequence is different from every member of the list because it is the last member of the list, which doesn’t exist just as the last member of 1,2,3,... doesn’t exist because it is an infinite, endless, sequence.
And how do you construct an infinite (endless) list in the first place?
No. The diagonal set *isn't* the last element of an infinite sequence. You *don't* construct the diagonal set in stages; you define it in a single step as a whole. And nothing in the proof depends on the set being a set of all natural numbers. The set can be *any* set whatsoever. It could be the set of all real numbers, or the set of all functions on real numbers, or - in absence of axiom of choice - something exotic like a set whose cardinality is incomparable with natural numbers (in other words, which is infinite but doesn't contain a countably infinite subset).
And that an infinite set exists is a consequence of the axiom of infinity, which essentially says: there is a set which contains all natural numbers. (But that's beside the point; nothing in the proof depends on whether the set is finite or infinite. The diagonal set is constructed using the axiom of separation.)
@@MikeRosoftJH The axiom of separation says the set exists, it doesn’t say you can construct it.
And the axiom of infinity only guarantees the existence of a set containing the natural numbers.
@@wernerhartl2069 Okay, can you "construct" the number googolplex? In set theory "constructing a set" is generally understood to mean defining it with a formula; and here the set in question indeed is definable with a formula (and that a set satisfying the formula exists is a consequence of the axiom of separation; and that it's unique follows from the axiom of extensionality). Besides, it's nowhere given that every set needs to be definable with a formula. For example, from the axiom of choice it follows that every set can be well-ordered (such that every two elements are comparable, and every its non-empty subset has a unique minimum). So it follows that real numbers can be well-ordered (observe that the usual numeric order on real numbers is not a well-ordering relation). The notion that ~ is a well-ordering relation on real numbers *is* definable with a formula. But it's not possible to define a specific well-ordering relation on reals, in the following sense - there's no formula for which the following can be proven: there exists exactly one set satisfying this formula, and that set is a well-ordering of real numbers.
Axiom of infinity (together with the axiom of separation) allows us to define (or "construct") the set of all natural numbers as an intersection of all sets which satisfy the axiom of infinity.
I never really found this proof very convincing.
It comes down to how we define things. Can something that takes infinite steps to be constructed exist ? Because I believe anything that takes infinite time to come into existence cannot exist.
For the number to exist, you have to stop at some point to add it back to the set. But the paradox is that you can't stop.
I see a lot of people saying, we don't construct it we define it. I mean what's the difference ?
Also how is this different from let's say a theorem that scans all the numbers in the set and adds 1 to the highest number in that set. This way we can prove that natural numbers are also not countable.
Kitty!!!
So CDA leads to the following conclusion: There is a countably infinite sequence not in the list of all countably infinite sequences. CDA fails.
No, you fail in understanding Cantor
@@TomasAragorn
From
en.m.wikipedia.org/wiki/Cantor%27s_diagonal_argument
Section Uncountable Sets.
“Cantor considered the set T of all infinite sequences of binary digits.”
“If s1, s2, ... , sn, ... is any enumeration of elements from T,[note 2] then an element s of T can be constructed that doesn't correspond to any sn in the enumeration.”
1) What is the definition of infinity?
2) What is an enumeration?
3) How do you construct it?
@@wernerhartl2069 I don't think it's worth trying to explain it to you, since plenty of people have already done so (including me) on your nonsensical videos. Maybe delete those videos
@@TomasAragorn How can you do a construction on a set of undefined objects, infinite binary sequences.
@@wernerhartl2069 they are not undefined. Infinite binary sequences are simply functions from the natural numbers to the set {0,1}
Is Cantor theorem using Axiom of Choice?
No, Cantor's Theorem does not rely on the Axiom of Choice.
There is only one choice to be made: selecting the subset D of A. Informally, (some version of) the Axiom of Choice is only necessary when you have to make infinitely many choices. You don't need the Axiom of Choice to make finitely many choices.
You may want to watch ua-cam.com/video/989BsBAECVY/v-deo.html which argues against Cantor's theorem
The video makes precisely the same mistake as above; you don't construct the diagonal set in stages - you define it as a whole. That the diagonal set exists is a consequence of the axiom of separation. (And conveniently, you have disabled comments on the video so that nobody could challenge you.)
incredibly hard to follow as the professor jumps from one thought to another, changes the speed, and mumbles a lot.
This is so tupid