Suppose there is a planet where infinitely many people live. They form every possible group. Every group is uniquely named after a person who is not in that group. Now take the group where there are all the people who have groups named after them. What's the name of it then? This would lead to a contradiction so the power set is bigger than the set.
No. It proves the non-existence of the set of all sets. It proves that given any set A there is a set with strictly greater cardinality than A; but it also proves that given any set A, there is a set with strictly greater cardinality than any set in A. Let A be any set. Let B be the union of all sets in A. Let B' be the set of all subsets of B. B' has a strictly greater cardinality than B; because every set in A is a subset of B, B' also has strictly greater cardinality than any set which is an element of A. So it follows that B' can't be an element of A. Nor can P(B') (the powerset of B'), P(P(B')), P(P(P(B'))), and so on. So given any set A, there is some set (and in fact arbitrarily many such sets) which are not an element of A; it follows that the set of all sets can't exist. (And more generally, there can't be a set containing sets of all cardinalities.)
4:20 What does that have to do with surjectivity? Isn't that just a restatement of the premise that f is a function on the entire set N and not just on an actual subset of N?
Yah, the two lines after that are just wrong. (For example: the function f: N->P(N), given by f(x)={x} that Papa Flammy used earlier satisfies f(x) in P(N) for all x in N, but it's certainly *not* surjective!).
How can I use Cantor's theorem to prove that the powerset of a countably infinite set is uncountably infinite? Or that the powerset of a countable set is uncountable. Not sure which of my questions assumes a correct statement, the test review has some typos.
It's by definition. No set can be mapped one-to-one with the set of all its subsets (given any function from X to P(X), there is some element of P(X) - subset of X - which the function does not cover). A set is countably infinite, if it can be mapped one-to-one with natural numbers. So powerset of this set has strictly greater cardinality than natural numbers. (It can also be shown that this set can be mapped one-to-one with real numbers.) If there's any non-trivial statement here - assuming that we know that Cantor's theorem is true - it's that if X can be mapped one-to-one with Y, then P(X) can be mapped one-to-one with P(Y). "Countable" can be used to mean either "countably infinite", or "at most countable" (either finite or countably infinite).
Was spricht dagegen einfach zu sagen, dass ∅ in der Potenzmenge enthalten ist, um Surjektivität zu wiederlegen? Dann muss man nur zeigen ∅={} kein element enthält, damit auch nicht aus N abgebildet werden kann und man kann mit dem Schubfachprinzip argumentieren. (English translation:) Isn't it enough to show that ∅ is contained in P(N), to rule out surjectivity? After that one only needs to show that ∅={} contains no element and therefore cant be in the image, so one can finish the proof by utilizing the Pigeonhole principle (?) .
No, it's not enough to prove that one specific function from A to P(A) doesn't cover all subsets of A; it's necessary to show that none of them does. Consider for example the function n->n+1 on natural numbers. This function does not cover all natural numbers; does it show that the set of all natural numbers can't be mapped one-to-one with itself? Of course not. (An infinite set can be mapped one-to-one with its strict superset or subset; precisely, a set can be mapped one-to-one with its strict superset or subset, if and only if it has a countably infinite subset.) The function n->{n} was only given as an example of a function from a set to the set of all its subsets, and of how the diagonal set is constructed (for this function the diagonal set is the empty set).
If Sn={1,2,....n}, P(Sn) has (2^n)-1 members, no matter what n is. Therefore the power set of the natural numbers is countable. Cantor’s diagonal argument is not valid because the constructed member doesn’t exist because it is the last member of Cantor’s list, which has no last member.
You need to be careful when talking about infinite sets. You could have as well claimed that the set {0} is finite, the set {0,1} is finite, the set {0,1,2} is finite, and so on for any n; therefore, the set of all natural numbers is finite. Let's cover your argument in more detail. Yes, powerset of an n-element set is a finite set. Take a union of all these sets over all natural numbers. This is a union of countably many finite sets. This union is countably infinite. (In general, you need a weak version of axiom of choice to prove that a union of countably many finite sets is countable; but in this case all sets in question can be readily ordered, so axiom of choice is not needed.) But this union is not the set of all sets of natural numbers; it's the set of all finite sets of natural numbers. And that's the crucial difference; set of all finite sets of natural numbers is countably infinite, but set of all sets (finite or infinite) of natural numbers is uncountably infinite.
papa flammy, how many licks, I mean, how many whole radius's do I need to go around a circle such that I end at the exact spot that I began on a circle? wouldn't it be infinite?
If N={1,2,3...n}, P(N) is defined and countable for ALL n. P(N) is undefined for n “=“ infinity. Coming up with axioms to prove otherwise is simply to create meaningless language with the implication of interpretation in meaningful terms, like the “4th” dimension. f(n) = 1/n is meaningless for n “=“ infinity. Only the operation lim has meaning. How can something be true for every member of a set but not be true for the set?
You are conflating infinity in the sense of a limit, and an actual infinite set. The set of all subsets of a given set indeed exists (that's the axiom of powerset), and that's including when the set is infinite. For example, let ω be the set of all natural numbers, then P(ω) contains the set {0}, and the set {1}, and the set {2,3,4}, and the set of all even natural numbers, and the set of all primes, and ω itself (every set is a subset of itself), and so on. It doesn't contain the set {ω}, or the set ω∪{ω} (set obtained from the set of all natural numbers by adding the set itself to it as an additional element).
The line you write at 4:20 is incorrect. I'm not sure why you even wrote it because you didn't even use it. Also, at 6:30, C_D should not have replaced y as the quantifier variable. It is just one specific instance of a set that is an element of the power set of N. You should probably redo the video if you don't want people to get stuck on that part and remain confused. other than that, you did a good job, and it is a clever proof that I can agree works for finite sets. However, on a personal level, I am skeptical about a possible existence of a set of all natural numbers that does not contain a largest natural number.
Flammable Maths Yeah, i know. I do watch your video regularly and i really like it. But the problem is that the t-shirt costs about 23 dollars, which is about Rs. 1610😅😅
That depends on whether or not you believe in the axiom of choice. For example, consider the set of all infinite sequences of the numbers 0 and 1. This is a set with cardinality of the continuum. On this set, let ~ be the relation: x~y, if sequences x and y differ from each other at finitely many places. This is an equivalence relation, which splits the set into equivalence classes: each class is a countably infinite set, and there are uncountably many classes. But just about how many equivalence classes are there? It can be shown that there are at least continuum-many: Let positions of the sequence be indexed by positive integers. Now split positive integers into the following subsets: * A1 = the set of numbers which are not divisible 2: {1, 3, 5, ...} * A2 = the set of numbers which are divisible by 2, but not by 4: {2, 6, 10, ...} * A3 = the set of numbers which are divisible by 4, but not by 8: {4, 12, 20, ...} * A4 = the set of numbers which are divisible by 8, but not by 16: ... * A5 = ... * ... This splits positive integers into a countably infinite collection of countably infinite sets. Any positive integer belongs to exactly one of these sets. Now consider the sequences, which have the following property: if n and m belong to the same subset, then the value of n-th and m-th value of the sequence is the same. In other words, it's the set of sequences of the following form: ABACABADABACABAEABACABADABACABAF..., where A, B, C, ... are digits 0 and 1. So we have obtained a set of continuum-many sequences (any sequence from this set is defined by an infinite sequence of digits 0 and 1); and it can be seen that no two sequences of this set differ from each other at finitely many positions (therefore, each belongs to a different equivalence class). So: the set of sequences can be injected into the set of equivalence classes. But can the set of equivalence classes be injected into the set of sequences? (That would prove that sequences and equivalence classes can be mapped one-to-one, by Cantor-Bernstein theorem.) Assuming axiom of choice, yes: pick a single element from each equivalence class. But without axiom of choice this can't be proven - there's a model of set theory where equivalence classes of this relation can't be injected into a set with cardinality of the continuum (in other words, where a set with cardinality of the continuum can be split into more subsets - disjoint and non-empty - than it has elements). Another relation with the same property is the following relation on real numbers: x~y, if x-y is a rational number.
You could prove this inequation using the fact that a set N with a elements has 2^a subsets. So, the cardinality of the power set of N is 2^a and for every real value of a, 2^a is strictly bigger than a. Am I right, Papa? Great video btw, keep it up :D
Caio Tomas, the problem is that infinite cardinals, in general, are way bigger than the set of real numbers. Hence, you’ll never be able to prove facts about large sets by looking at proofs only having to do with the real numbers. For instance, if S is an infinite set, then card(Sx{0,1})=card(S). This is despite the fact that lim 2a-a = a = infinity, as a goes to infinity.
You can tell if x is a member of an infinite defined set such as {1/n}, all n, but not of an infinite random set because you would have to compare x to every member of a set which has no end. CDA uses random sets. And how do you construct a list that doesn’t end?
@@wernerhartl2069 You don't need to determine if x an element of a set; the only thing you need to know is that either x is an element of the set, or x is not element of the set (x∈A is either true, or false). And how do you construct an infinite list? You can surely define one: f(n)=1/n. That's a function from positive integers to real numbers (in other words, an infinite sequence). And it doesn't matter whether or not the sequence can be defined with a formula; the theorem holds for all sequences (no function from natural numbers to real numbers can cover all real numbers - given any such function, there is some real number which it does not cover).
No, it doesn't matter. The empty set is a subset of every set, and in particular, must therefore be a subset of N. Whether or not Cd is empty, it is still a subset of N which is not hit by f.
So what? Nobody disputes that. Let x be some element of N. f(x) is some element of P(N). An element of P(N) is some subset of N. Either x is an element of this subset (of f(x)), or it's not. We pick such elements y of N, such that y is not an element of f(y). This set exists by the axiom of separation; and by the construction of this set it's not the same set as f(y) for any y being an element of N. Therefore, the function f does not cover all subsets of N. (And nothing in the proof depends on N being the set of natural numbers - it can be any arbitrary set. It can be the set of all real numbers, or the set of all functions on reals, or - in absence of axiom of choice - it may be some set which can't even be well-ordered.)
@@MikeRosoftJH “x maps to ALL the sets which include x.” Watch the video. That is not a function. f(x1)=f(x2) -> x1=x2 only if f is an injection. So you are assuming what you are trying to prove, ie, a circular argument.
@@wernerhartl2069 If you mean the part at 1:53, then you misunderstood what he was saying. He was giving one example of a function from N to P(N): x -> {x}. That is: every element x of the set N is mapped to a one-element set, whose only element is x itself. It can be easily seen that in this case the diagonal set is empty (x is an element of f(x) for every x). And indeed no element is mapped to an empty set - every element is mapped to a set containing exactly one element. (And note that 0 - the empty set, with no elements - and {0} - set whose only element is the empty set - are different sets.) And the proof doesn't depend on whether or not the function f is an injection (though obviously the example function is - no two different x are mapped to the same set). And in any case, this is not my video. Let me once again post the proof: * Let A be any arbitrary set. P(A) is the powerset of A - set of all subsets of A. * Let f be any arbitrary function from A to P(A); f(x), for x∈A, is a subset of A. * Consider the set D={x: x∈A and x∉f(x)}. (That is: for any x∈A, f(x) is a subset of A. There are exactly two options: either x∈f(x), or x∉f(x). D is the set of all elements x of A, such that x is not an element of f(x).) This set exists by the axiom of separation. * By construction, set D is not equal to f(y) for any y∈A. Let y be any element of A: either y∈f(y), in which case y∉D; or y∉f(y), in which case y∈D. Either way, f(y) is a different set than D. (Note: by the axiom of extensionality, two sets are equal if and only if they have the same elements.) * Therefore, the function f does not cover all elements of P(A) - in particular, it does not cover the set D. * Therefore (because I have made no assumption about either the set A or the function f), the same holds for every set A, and every function from A to P(A) - no set can be mapped one-to-one with the set of all its subsets. QED. Is there some step that you disagree with or that you don't understand?
@@MikeRosoftJH My apologies. x maps to the set whose only element is x. I was confused by the verbiage but I understand now how it could be expressed that way, What do you mean by the diagonal set is empty in this case? I am reviewing your proof. I do note that if you disallow induction in your argument you are essentially assuming what you want to prove.
@@wernerhartl2069 So once again: Let A be any set. Let f be the function x -> {x} on the set A. The diagonal set of the function f is the set of all elements of A, such that x is not an element of f(x). But for every x in A is x an element of f(x) (f(x) is the set {x} - the set which contains exactly one element - x itself); so the diagonal set contains no elements. And that's a perfectly valid subset of the set A - empty set is (by definition) a subset of every set. (Distinguish the 'subset' and the 'element' relation.) Is that OK? And the proof that no set can be mapped one-to-one with the set of all its subsets does not use induction at all. It just uses the axioms of set theory. Where do you think I am assuming what I was trying to prove? Which step doesn't follow from the previous steps?
Well explained papa Flammy, just one note, i know the proof myself, your reasoning is kinda awkward, you have to show that no bijection exist (not that your one particular f isn't a bij.) example f:R->R, f(x) = arctg(x) has no pre-images in, say (5,6), but this clearly doesn't imply |R|
Hi, it's a bit late, but i'll try to explain it by my own intuition. First, is that if we know nothing about set N and its power set P(N), construct such a set C_d that contain those x elements that could be exist or not (reminding that C_d is a set contain all elements belong to N but their image don't belong to P(N)) . Then there will be 2 cases: Case 1: if there exist some x ( there's one x or more) then function f could be easily proved to not be surjective cos there are f(x) left out. This is the straightfoward case, and it simply is nothing more than saying f is not a surjective function because I say it's not. Case 2: But because we know nothing about these two set N and P(N), the thing we try to prove could be wrong and there could exist no such x inside the C_d set. Still although there is no element in set C_d, set C_d could still be existed as a empty set, and this empty set that contain empty itself (not "empty set", just "empty, nothing) cant be an image of f, cos f has to act on "something", so in other word the empty set C_d has been left out, so utimately the f function is still not a surjective function. I think the intuition here is that, without any fancy math language, when we think about a set and its power set, we know that even if we only consider the sets that contain every single elements of the original set inside the power set (for example set N={1,2,3} then we only care about 3 elements set of P(N): {1}, {2}, {3}; which made the cardinal of those 2 set "at least" equal, they all contain 3 elements), then the power set will always still has more element than the original set precisely because the power set will always contain the empty set which the original set doesn't have (mind you that empty "set" is counted in cardinal, but empty "element" isn't). I dont know what the thought process to created such a monstrous abomination, but i think this "empty set" intuition is what happening when I considering the above case 2, and i think it's the reason to construct the set C_d.
You once again miss the point. For *any* set - be it finite or infinite - the set of all its subsets can't be mapped one-to-one with it; no function from a set to the set of all its subsets can cover all subsets of the original set. And this is a theorem of set theory as usually axiomatized (ZF or ZFC); regardless of your philosophical objections, there *is* a powerset (set of all subsets) of any set, including when the set in question is infinite - this is an axiom of powerset. And for any function f from any set A to P(A) there exists (by the axiom of separation) a diagonal set, which is different from f(x) for any x∈A. And {n} is not an n-element set; it's a one-element set whose only element is n.
It seems correct: we have a function f from N to P(N), and claim that it covers all elements of P(N) - for every y∈P(N) there exists x∈N, such that f(x)=y. (We then reach a contradiction - that it doesn't in fact cover all elements of P(N).) I prefer not to do the proof as a proof by contradiction, because I don't actually need the assumption that f covers all elements of P(N). Let f be any arbitrary function from N to P(N); then there exists a particular subset of N, which the function f does not cover. That set is: {x: x∈N and x∉f(x)} - that is, the set of all elements of N, which the function f maps to a set which doesn't contain that element. (This set exists by the axiom of specification.) And because I have made no assumptions about either the set N or the function f, it follows that this holds for every set N, and every function from N to the set of all subsets of N. (If statement F(x) can be proven, then so can ∀x: F(x).) For infinite sets the result can be strengthened: if set N can be mapped one-to-one with two copies of N (assuming axiom of choice, this is true for all infinite sets), then given any function from N to P(N), the set of all subsets of N which the function does not cover can be mapped one-to-one with P(N).
This misses the point. The function n->{n} is just *one example* of a function from a set to the set of all its subsets, and of the construction of the diagonal set. The real point is that *every* function from a set to the set of all its subsets has its diagonal set, and the function cannot cover its diagonal set (for no n is f(n) the diagonal set).
@@MikeRosoftJH All of a sudden the statement is made, “assume f is surjective in P(N).” It obviously isn’t. Let m be the inverse of a member of P(N) which isn’t {m}. m obviously exists and f{m} = {m}. I agree that in this context P(N) could be any set that included the natural numbers, like {x} and three different shoes. A proof by contradiction only works if the contradiction is intelligent.
@@wernerhartl2069 Again, you are missing the point of the proof by contradiction. The function x -> {x} was *just an example* of a function from a set to the set of all its subsets. Let f be *any function whatsoever* from set A to P(A); then there exists a diagonal set {x: x∈A and x∉f(x)}, which can't be the same set as f(y) for any y∈A. Therefore, the function isn't a one-to-one function between A and P(A). (In particular, for function x->{x}, the diagonal set is the empty set, and indeed no element is mapped to the empty set; and yes, empty set is a subset of every set.) Got it already?
@@MikeRosoftJH If f is just one function, why don’t you pick one that works as a logical contradiction. A contradiction is meaningless if it is obviously wrong. All people are happy. Proof: The contradiction, all people are unhappy, is obviously wrong.
@@wernerhartl2069 What on Earth do you mean? And no, P(N) can't be any set that contains all natural numbers; the proof *specifically depends* on it being the set of all subsets of N. And it doesn't depend on N being the set of all natural numbers, either; N can be *any arbitrary set* .
You don't? The theorem is that no set can be mapped one-to-one with the set of all its subsets. (Regardless of if the original set is finite or infinite.)
At 10:21 what you say is not what you write. You write “x maps to {x}” in which case f is not a surjection, and you say “x maps to all the sets which contain x” in which case f isn’t a function. Suppose N={1,2} P(N)={{1},{2},{1,2}} f(1)={1}, f(2)=(2) f is an injection but not a surjection.
You got the timestamp wrong, and you misunderstand what he was saying (maybe he has misspoken). He was giving one example of a function from a set to its powerset: x -> {x} (every element maps to a one-element set containing precisely that element). And the whole point is that the function f can't be a surjection - it can't cover all subsets of the original set. And the powerset of the set {1,2} is not {{1},{2},{1,2}}; it's {{},{1},{2},{1,2}} - you forgot the empty set. Observe that for every element of the original set there are exactly two possibilities: either the subset contains the element, or it doesn't contain the element; so a finite set with n elements has 2^n different subsets. (That empty set exists follows for example from the axiom of separation. And that's regardless of your philosophical objection to empty set; this is a theorem of set theory as usually axiomatized - ZF or ZFC. The same for powerset of an infinite set - axiom of powerset says that for *every* set there exists a set of all its subsets.)
@@MikeRosoftJH That f can’t be a surjection is obvious, but it’s treated as a possibility later on as I recall. Proof that empty set is a subset is vacuous, which means it can be proved either way. That’s simple, fundamental, logic. See wiki article on “Vacuous Truth.” If you want to make something which you can’t prove an axiom in order to prove something, help yourself, prove anything you want. If E
@@wernerhartl2069 Do you know what is a proof by contradiction? The proof that no set (finite or infinite) can be mapped one-to-one with the set of all its subsets is often given as a proof by contradiction: Let A be some set. Suppose there exists a one-to-one function f between A and P(A); then there exists some subset of A - the diagonal set of the function - which the function does not cover (for no x∈A is f(x) equal to the diagonal set). This is a contradiction, so the assumption cannot be true (A can't be mapped one-to-one with P(A)). But I prefer *not* to state the proof as a proof by contradiction (I don't actually need the assumption that f is a bijection between A and P(A)). So: Let f be any arbitrary function from A to P(A). Then there exists a subset of A - the diagonal set of function f - which the function does not cover; so f is not a bijection. (And this proves the theorem, because I have made no assumption about the function f.) The function x->{x} was given just as an illustration of the construction of the diagonal set. And what is your point about the empty set? Yes, empty set is by definition a subset of every set, including itself. In particular, it is a subset of the set {1,2}; so this set has four different subsets, not three (note that every set is a subset of itself). This is why the subset relation symbol is often written as ⊆ rather than ⊂ (as an analogy of ≤ relation). (Distinguish the element and the subset relation - empty set is a subset of every set, but it's not an element of every set! For example, it's not an element of the set {1,2} - the only elements of this set are 1 and 2. It's also not an element of itself - empty set has no elements, and that means none at all. For no x is it true that x∈{}.) Now as an exercise for you, to ensure that you understand it: what is the powerset of the empty set (P(0) or P({}))? How many elements does it have?
As far as I can tell, the video says nothing but "the diagonal set does not exist, because I say so". (And conveniently, he has disabled comments in his video.)
But how much does a bijection ...weigh? Hey, vsauce. Coming from behind here
Certainly more than the color of the universe
stfu
Suppose there is a planet where infinitely many people live. They form every possible group. Every group is uniquely named after a person who is not in that group. Now take the group where there are all the people who have groups named after them. What's the name of it then?
This would lead to a contradiction so the power set is bigger than the set.
Shut up show off
One of the coolest proofs!It uses very simple mathematics but also is mindblown ,wow!
This theorem prove, without the shadow of a doubt, the existence of the Set of all Sets. Take that, Atheists. ;)
I don't get this, EXPLAIN. :D
No. It proves the non-existence of the set of all sets. It proves that given any set A there is a set with strictly greater cardinality than A; but it also proves that given any set A, there is a set with strictly greater cardinality than any set in A.
Let A be any set. Let B be the union of all sets in A. Let B' be the set of all subsets of B. B' has a strictly greater cardinality than B; because every set in A is a subset of B, B' also has strictly greater cardinality than any set which is an element of A. So it follows that B' can't be an element of A. Nor can P(B') (the powerset of B'), P(P(B')), P(P(P(B'))), and so on. So given any set A, there is some set (and in fact arbitrarily many such sets) which are not an element of A; it follows that the set of all sets can't exist. (And more generally, there can't be a set containing sets of all cardinalities.)
Papa Flammys Advent Calendar *O I A A A A A A Ha*
Those bois and grills are lucky they have you as a teacher ^.^
Don't forget to tell them to subscribe :P
Learned it this summer actually in a book, so it's amazing to now have a video by you about this topic😂 thanks Papa, keep up the great content
Thanks mate, I'm having a presentation about the set theory in my highschool and this video helped me a lot!
Glad it helped!
I thought my professor was on crack when he explained it in class (I didn't understand a thing). This video cleared it all up, thanks!
4:20
What does that have to do with surjectivity?
Isn't that just a restatement of the premise that f is a function on the entire set N and not just on an actual subset of N?
Yah, the two lines after that are just wrong. (For example: the function f: N->P(N), given by f(x)={x} that Papa Flammy used earlier satisfies f(x) in P(N) for all x in N, but it's certainly *not* surjective!).
Exactly.
I too was wondering if anyone else noticed that. Those two lines are true by the very definition of a function.
How can I use Cantor's theorem to prove that the powerset of a countably infinite set is uncountably infinite? Or that the powerset of a countable set is uncountable. Not sure which of my questions assumes a correct statement, the test review has some typos.
It's by definition. No set can be mapped one-to-one with the set of all its subsets (given any function from X to P(X), there is some element of P(X) - subset of X - which the function does not cover). A set is countably infinite, if it can be mapped one-to-one with natural numbers. So powerset of this set has strictly greater cardinality than natural numbers. (It can also be shown that this set can be mapped one-to-one with real numbers.) If there's any non-trivial statement here - assuming that we know that Cantor's theorem is true - it's that if X can be mapped one-to-one with Y, then P(X) can be mapped one-to-one with P(Y).
"Countable" can be used to mean either "countably infinite", or "at most countable" (either finite or countably infinite).
Was spricht dagegen einfach zu sagen, dass ∅ in der Potenzmenge enthalten ist, um Surjektivität zu wiederlegen? Dann muss man nur zeigen ∅={} kein element enthält, damit auch nicht aus N abgebildet werden kann und man kann mit dem Schubfachprinzip argumentieren.
(English translation:)
Isn't it enough to show that ∅ is contained in P(N), to rule out surjectivity? After that one only needs to show that ∅={} contains no element and therefore cant be in the image, so one can finish the proof by utilizing the Pigeonhole principle (?) .
No, it's not enough to prove that one specific function from A to P(A) doesn't cover all subsets of A; it's necessary to show that none of them does. Consider for example the function n->n+1 on natural numbers. This function does not cover all natural numbers; does it show that the set of all natural numbers can't be mapped one-to-one with itself? Of course not. (An infinite set can be mapped one-to-one with its strict superset or subset; precisely, a set can be mapped one-to-one with its strict superset or subset, if and only if it has a countably infinite subset.) The function n->{n} was only given as an example of a function from a set to the set of all its subsets, and of how the diagonal set is constructed (for this function the diagonal set is the empty set).
I wonder if there is a way to prove this without using LEM? It's not exactly the nicest given that the continuum hypothesis makes it questionable.
You mean *infinite*?
note that despite of the requirement of sets being finite. the cantor's theorem holds for infinite sets as well
If Sn={1,2,....n}, P(Sn) has (2^n)-1 members, no matter what n is.
Therefore the power set of the natural numbers is countable.
Cantor’s diagonal argument is not valid because the constructed member doesn’t exist because it is the last member of Cantor’s list, which has no last member.
You need to be careful when talking about infinite sets. You could have as well claimed that the set {0} is finite, the set {0,1} is finite, the set {0,1,2} is finite, and so on for any n; therefore, the set of all natural numbers is finite. Let's cover your argument in more detail. Yes, powerset of an n-element set is a finite set. Take a union of all these sets over all natural numbers. This is a union of countably many finite sets. This union is countably infinite. (In general, you need a weak version of axiom of choice to prove that a union of countably many finite sets is countable; but in this case all sets in question can be readily ordered, so axiom of choice is not needed.) But this union is not the set of all sets of natural numbers; it's the set of all finite sets of natural numbers. And that's the crucial difference; set of all finite sets of natural numbers is countably infinite, but set of all sets (finite or infinite) of natural numbers is uncountably infinite.
Second
Papa always destroying every theorm possible
Our professor doesn't teach this. How did you derive this?
papa flammy, how many licks, I mean, how many whole radius's do I need to go around a circle such that I end at the exact spot that I began on a circle? wouldn't it be infinite?
papa best, one of ur vids helped me on my discrete math colloquium 2day, yay!
If N={1,2,3...n}, P(N) is defined and countable for ALL n. P(N) is undefined for n “=“ infinity. Coming up with axioms to prove otherwise is simply to create meaningless language with the implication of interpretation in meaningful terms, like the “4th” dimension.
f(n) = 1/n is meaningless for n “=“ infinity. Only the operation lim has meaning.
How can something be true for every member of a set but not be true for the set?
You are conflating infinity in the sense of a limit, and an actual infinite set. The set of all subsets of a given set indeed exists (that's the axiom of powerset), and that's including when the set is infinite. For example, let ω be the set of all natural numbers, then P(ω) contains the set {0}, and the set {1}, and the set {2,3,4}, and the set of all even natural numbers, and the set of all primes, and ω itself (every set is a subset of itself), and so on. It doesn't contain the set {ω}, or the set ω∪{ω} (set obtained from the set of all natural numbers by adding the set itself to it as an additional element).
i think you should show that no surjective function g exists. don't use the same letter f.
Ugh this question was on my set theory course final.
Please Papa flammy dont come again from behind 😂😂😂
I see what you did there ;)
The line you write at 4:20 is incorrect. I'm not sure why you even wrote it because you didn't even use it. Also, at 6:30, C_D should not have replaced y as the quantifier variable. It is just one specific instance of a set that is an element of the power set of N. You should probably redo the video if you don't want people to get stuck on that part and remain confused. other than that, you did a good job, and it is a clever proof that I can agree works for finite sets. However, on a personal level, I am skeptical about a possible existence of a set of all natural numbers that does not contain a largest natural number.
From where i can get that T-shirts???
Flammable Maths Yeah, i know. I do watch your video regularly and i really like it.
But the problem is that the t-shirt costs about 23 dollars, which is about Rs. 1610😅😅
Flammable Maths No then its about 240 off, so it's about Rs1370
Cool proof. But I don't quite get it because couldn't this proof be used show that any function between two sets isn't surjective?
No. The set C_D doesn't even make sense unless f maps a set N to its power set P(N).
@@MuffinsAPlenty Thanks.
Thanks! This is very helpful in understanding the proof for a history of math course I am currently taking :-)
Can the image of a function greater over A have a greater cardinality of A? Or a quotient set with cardinality larger than its union? Hmmm?
That depends on whether or not you believe in the axiom of choice. For example, consider the set of all infinite sequences of the numbers 0 and 1. This is a set with cardinality of the continuum. On this set, let ~ be the relation: x~y, if sequences x and y differ from each other at finitely many places. This is an equivalence relation, which splits the set into equivalence classes: each class is a countably infinite set, and there are uncountably many classes.
But just about how many equivalence classes are there? It can be shown that there are at least continuum-many: Let positions of the sequence be indexed by positive integers. Now split positive integers into the following subsets:
* A1 = the set of numbers which are not divisible 2: {1, 3, 5, ...}
* A2 = the set of numbers which are divisible by 2, but not by 4: {2, 6, 10, ...}
* A3 = the set of numbers which are divisible by 4, but not by 8: {4, 12, 20, ...}
* A4 = the set of numbers which are divisible by 8, but not by 16: ...
* A5 = ...
* ...
This splits positive integers into a countably infinite collection of countably infinite sets. Any positive integer belongs to exactly one of these sets. Now consider the sequences, which have the following property: if n and m belong to the same subset, then the value of n-th and m-th value of the sequence is the same. In other words, it's the set of sequences of the following form: ABACABADABACABAEABACABADABACABAF..., where A, B, C, ... are digits 0 and 1. So we have obtained a set of continuum-many sequences (any sequence from this set is defined by an infinite sequence of digits 0 and 1); and it can be seen that no two sequences of this set differ from each other at finitely many positions (therefore, each belongs to a different equivalence class). So: the set of sequences can be injected into the set of equivalence classes. But can the set of equivalence classes be injected into the set of sequences? (That would prove that sequences and equivalence classes can be mapped one-to-one, by Cantor-Bernstein theorem.) Assuming axiom of choice, yes: pick a single element from each equivalence class. But without axiom of choice this can't be proven - there's a model of set theory where equivalence classes of this relation can't be injected into a set with cardinality of the continuum (in other words, where a set with cardinality of the continuum can be split into more subsets - disjoint and non-empty - than it has elements).
Another relation with the same property is the following relation on real numbers: x~y, if x-y is a rational number.
best proof ever..thanks
I want to say power set is not just the set which contains all sets that include x it also contains phi
You doing a Masters or PhD now flammy?
Flammable Maths cool what’s it in?
Most likely poetry and arts
You could prove this inequation using the fact that a set N with a elements has 2^a subsets. So, the cardinality of the power set of N is 2^a and for every real value of a, 2^a is strictly bigger than a. Am I right, Papa? Great video btw, keep it up :D
Caio Tomas, that works for finite sets, but this result holds for infinite sets, as well.
@@alexandersanchez9138 True, didn't think about that xD Thx!
@@alexandersanchez9138 I could also take the limit of 2^a - a when a goes to infinity, couldn't I? Since it goes to infinity, card(P(N))>card(N)
@@caiotomas2347 "going to infinity"≠"infinite set"
Caio Tomas, the problem is that infinite cardinals, in general, are way bigger than the set of real numbers. Hence, you’ll never be able to prove facts about large sets by looking at proofs only having to do with the real numbers. For instance, if S is an infinite set, then card(Sx{0,1})=card(S). This is despite the fact that lim 2a-a = a = infinity, as a goes to infinity.
Set theory is love, set theory is life.
Now that's some JUICY theorem
How do you determine whether x belongs to a set if the set is infinite- has no end?
Using the defining condition of the set.
You can tell if x is a member of an infinite defined set such as {1/n}, all n, but not of an infinite random set because you would have to compare x to every member of a set which has no end. CDA uses random sets.
And how do you construct a list that doesn’t end?
@@wernerhartl2069 You don't need to determine if x an element of a set; the only thing you need to know is that either x is an element of the set, or x is not element of the set (x∈A is either true, or false). And how do you construct an infinite list? You can surely define one: f(n)=1/n. That's a function from positive integers to real numbers (in other words, an infinite sequence). And it doesn't matter whether or not the sequence can be defined with a formula; the theorem holds for all sequences (no function from natural numbers to real numbers can cover all real numbers - given any such function, there is some real number which it does not cover).
@@MikeRosoftJH You can’t construct the last number of an infinite (endless) set because the last number doesn’t exist.
@@MikeRosoftJH How do you determine whether or not x is in or not in a random endless set.
What is the real number it does not cover?
[C]ompact [D]isc is something [C]ompletly [D]ifferent
sneaky
OMG papa Flammy is an IT teacher!? I need u teacher!!!!
Papa, why you do this to me? I had to try and understand this proof last year. Why couldnt have you made this earlier? But seriously nice vid!
Make vedios on combinatorics
*bijection intensifies*
@@PapaFlammy69 Sadly tru
@@PapaFlammy69 less than 3
This makes no sense
Does it matter if the set Cd is empty?
No, it doesn't matter. The empty set is a subset of every set, and in particular, must therefore be a subset of N. Whether or not Cd is empty, it is still a subset of N which is not hit by f.
coming in from behind, you didn't expect that probably. No, I didn't.
:^D
Compacc Discc
A function from an element of N to P(N) can only map to one element of P(N), by definition of function.
So what? Nobody disputes that. Let x be some element of N. f(x) is some element of P(N). An element of P(N) is some subset of N. Either x is an element of this subset (of f(x)), or it's not. We pick such elements y of N, such that y is not an element of f(y). This set exists by the axiom of separation; and by the construction of this set it's not the same set as f(y) for any y being an element of N. Therefore, the function f does not cover all subsets of N. (And nothing in the proof depends on N being the set of natural numbers - it can be any arbitrary set. It can be the set of all real numbers, or the set of all functions on reals, or - in absence of axiom of choice - it may be some set which can't even be well-ordered.)
@@MikeRosoftJH “x maps to ALL the sets which include x.” Watch the video. That is not a function.
f(x1)=f(x2) -> x1=x2 only if f is an injection. So you are assuming what you are trying to prove, ie, a circular argument.
@@wernerhartl2069 If you mean the part at 1:53, then you misunderstood what he was saying. He was giving one example of a function from N to P(N): x -> {x}. That is: every element x of the set N is mapped to a one-element set, whose only element is x itself. It can be easily seen that in this case the diagonal set is empty (x is an element of f(x) for every x). And indeed no element is mapped to an empty set - every element is mapped to a set containing exactly one element. (And note that 0 - the empty set, with no elements - and {0} - set whose only element is the empty set - are different sets.) And the proof doesn't depend on whether or not the function f is an injection (though obviously the example function is - no two different x are mapped to the same set). And in any case, this is not my video. Let me once again post the proof:
* Let A be any arbitrary set. P(A) is the powerset of A - set of all subsets of A.
* Let f be any arbitrary function from A to P(A); f(x), for x∈A, is a subset of A.
* Consider the set D={x: x∈A and x∉f(x)}. (That is: for any x∈A, f(x) is a subset of A. There are exactly two options: either x∈f(x), or x∉f(x). D is the set of all elements x of A, such that x is not an element of f(x).) This set exists by the axiom of separation.
* By construction, set D is not equal to f(y) for any y∈A. Let y be any element of A: either y∈f(y), in which case y∉D; or y∉f(y), in which case y∈D. Either way, f(y) is a different set than D. (Note: by the axiom of extensionality, two sets are equal if and only if they have the same elements.)
* Therefore, the function f does not cover all elements of P(A) - in particular, it does not cover the set D.
* Therefore (because I have made no assumption about either the set A or the function f), the same holds for every set A, and every function from A to P(A) - no set can be mapped one-to-one with the set of all its subsets. QED.
Is there some step that you disagree with or that you don't understand?
@@MikeRosoftJH My apologies. x maps to the set whose only element is x. I was confused by the verbiage but I understand now how it could be expressed that way, What do you mean by the diagonal set is empty in this case?
I am reviewing your proof. I do note that if you disallow induction in your argument you are essentially assuming what you want to prove.
@@wernerhartl2069 So once again: Let A be any set. Let f be the function x -> {x} on the set A. The diagonal set of the function f is the set of all elements of A, such that x is not an element of f(x). But for every x in A is x an element of f(x) (f(x) is the set {x} - the set which contains exactly one element - x itself); so the diagonal set contains no elements. And that's a perfectly valid subset of the set A - empty set is (by definition) a subset of every set. (Distinguish the 'subset' and the 'element' relation.) Is that OK?
And the proof that no set can be mapped one-to-one with the set of all its subsets does not use induction at all. It just uses the axioms of set theory. Where do you think I am assuming what I was trying to prove? Which step doesn't follow from the previous steps?
Well explained papa Flammy, just one note, i know the proof myself, your reasoning is kinda awkward, you have to show that no bijection exist (not that your one particular f isn't a bij.) example f:R->R, f(x) = arctg(x) has no pre-images in, say (5,6), but this clearly doesn't imply |R|
What's intuition behind construction of set C_d
Hi, it's a bit late, but i'll try to explain it by my own intuition. First, is that if we know nothing about set N and its power set P(N), construct such a set C_d that contain those x elements that could be exist or not (reminding that C_d is a set contain all elements belong to N but their image don't belong to P(N)) . Then there will be 2 cases:
Case 1: if there exist some x ( there's one x or more) then function f could be easily proved to not be surjective cos there are f(x) left out. This is the straightfoward case, and it simply is nothing more than saying f is not a surjective function because I say it's not.
Case 2: But because we know nothing about these two set N and P(N), the thing we try to prove could be wrong and there could exist no such x inside the C_d set. Still although there is no element in set C_d, set C_d could still be existed as a empty set, and this empty set that contain empty itself (not "empty set", just "empty, nothing) cant be an image of f, cos f has to act on "something", so in other word the empty set C_d has been left out, so utimately the f function is still not a surjective function.
I think the intuition here is that, without any fancy math language, when we think about a set and its power set, we know that even if we only consider the sets that contain every single elements of the original set inside the power set (for example set N={1,2,3} then we only care about 3 elements set of P(N): {1}, {2}, {3}; which made the cardinal of those 2 set "at least" equal, they all contain 3 elements), then the power set will always still has more element than the original set precisely because the power set will always contain the empty set which the original set doesn't have (mind you that empty "set" is counted in cardinal, but empty "element" isn't). I dont know what the thought process to created such a monstrous abomination, but i think this "empty set" intuition is what happening when I considering the above case 2, and i think it's the reason to construct the set C_d.
This is very helpful, thankwww so much, may God bless you. ☺️
Lagrangian mechanics yes. I find this difficult. I have math gaps. I need to do some work.
There is obviously no bijection between {n} and P(n), for all n. So what? Is P(3) uncountable?
You once again miss the point. For *any* set - be it finite or infinite - the set of all its subsets can't be mapped one-to-one with it; no function from a set to the set of all its subsets can cover all subsets of the original set. And this is a theorem of set theory as usually axiomatized (ZF or ZFC); regardless of your philosophical objections, there *is* a powerset (set of all subsets) of any set, including when the set in question is infinite - this is an axiom of powerset. And for any function f from any set A to P(A) there exists (by the axiom of separation) a diagonal set, which is different from f(x) for any x∈A.
And {n} is not an n-element set; it's a one-element set whose only element is n.
Thank you
It‘s not the same without that legendary intro :( (weird voice sayin: Papa flammys advent calendar o y aaaaaaa i heee)
yes I have question regarding this proof-
*excuse me what the feck*
I don' know whether to br amazed or confused either 😂
Useful but his accent is a bit distracting to me. Where is he from??
4:10 makes no sense. Doesn't look like an equivalent definition of surjective function.
It seems correct: we have a function f from N to P(N), and claim that it covers all elements of P(N) - for every y∈P(N) there exists x∈N, such that f(x)=y. (We then reach a contradiction - that it doesn't in fact cover all elements of P(N).)
I prefer not to do the proof as a proof by contradiction, because I don't actually need the assumption that f covers all elements of P(N). Let f be any arbitrary function from N to P(N); then there exists a particular subset of N, which the function f does not cover. That set is: {x: x∈N and x∉f(x)} - that is, the set of all elements of N, which the function f maps to a set which doesn't contain that element. (This set exists by the axiom of specification.) And because I have made no assumptions about either the set N or the function f, it follows that this holds for every set N, and every function from N to the set of all subsets of N. (If statement F(x) can be proven, then so can ∀x: F(x).)
For infinite sets the result can be strengthened: if set N can be mapped one-to-one with two copies of N (assuming axiom of choice, this is true for all infinite sets), then given any function from N to P(N), the set of all subsets of N which the function does not cover can be mapped one-to-one with P(N).
J popstars instantaneously wet, ready to extinguish the Daddy Flamma
Hmmmm Cantor is happy.
Despite this proof, I'm just not convinced...
simply because *P(N)⬌2^N⬌N,* no?
"2^N⬌N"
Why do you think these are the same?
The proof proceeds exactly as if P(N) = {{1},{2},{3},........}, which obviously has the same cardinality as N.
This misses the point. The function n->{n} is just *one example* of a function from a set to the set of all its subsets, and of the construction of the diagonal set. The real point is that *every* function from a set to the set of all its subsets has its diagonal set, and the function cannot cover its diagonal set (for no n is f(n) the diagonal set).
@@MikeRosoftJH All of a sudden the statement is made, “assume f is surjective in P(N).” It obviously isn’t. Let m be the inverse of a member of P(N) which isn’t {m}. m obviously exists and f{m} = {m}.
I agree that in this context P(N) could be any set that included the natural numbers, like {x} and three different shoes.
A proof by contradiction only works if the contradiction is intelligent.
@@wernerhartl2069 Again, you are missing the point of the proof by contradiction. The function x -> {x} was *just an example* of a function from a set to the set of all its subsets. Let f be *any function whatsoever* from set A to P(A); then there exists a diagonal set {x: x∈A and x∉f(x)}, which can't be the same set as f(y) for any y∈A. Therefore, the function isn't a one-to-one function between A and P(A). (In particular, for function x->{x}, the diagonal set is the empty set, and indeed no element is mapped to the empty set; and yes, empty set is a subset of every set.) Got it already?
@@MikeRosoftJH If f is just one function, why don’t you pick one that works as a logical contradiction. A contradiction is meaningless if it is obviously wrong.
All people are happy.
Proof: The contradiction, all people are unhappy, is obviously wrong.
@@wernerhartl2069 What on Earth do you mean? And no, P(N) can't be any set that contains all natural numbers; the proof *specifically depends* on it being the set of all subsets of N. And it doesn't depend on N being the set of all natural numbers, either; N can be *any arbitrary set* .
It seems to be taken from ROBERT BARTLE
I like cantor 😍.. Awesome set theory.. Sorry I'm late
Where did you use finiteness of N?
You don't? The theorem is that no set can be mapped one-to-one with the set of all its subsets. (Regardless of if the original set is finite or infinite.)
At 10:21 what you say is not what you write. You write “x maps to {x}” in which case f is not a surjection, and you say “x maps to all the sets which contain x” in which case f isn’t a function.
Suppose N={1,2}
P(N)={{1},{2},{1,2}}
f(1)={1}, f(2)=(2)
f is an injection but not a surjection.
You got the timestamp wrong, and you misunderstand what he was saying (maybe he has misspoken). He was giving one example of a function from a set to its powerset: x -> {x} (every element maps to a one-element set containing precisely that element).
And the whole point is that the function f can't be a surjection - it can't cover all subsets of the original set.
And the powerset of the set {1,2} is not {{1},{2},{1,2}}; it's {{},{1},{2},{1,2}} - you forgot the empty set. Observe that for every element of the original set there are exactly two possibilities: either the subset contains the element, or it doesn't contain the element; so a finite set with n elements has 2^n different subsets. (That empty set exists follows for example from the axiom of separation. And that's regardless of your philosophical objection to empty set; this is a theorem of set theory as usually axiomatized - ZF or ZFC. The same for powerset of an infinite set - axiom of powerset says that for *every* set there exists a set of all its subsets.)
@@MikeRosoftJH That f can’t be a surjection is obvious, but it’s treated as a possibility later on as I recall.
Proof that empty set is a subset is vacuous, which means it can be proved either way. That’s simple, fundamental, logic. See wiki article on “Vacuous Truth.” If you want to make something which you can’t prove an axiom in order to prove something, help yourself, prove anything you want.
If E
@@MikeRosoftJH Ok. The time stamp is 1:51. Thanks. And I quoted it.
@@wernerhartl2069 Do you know what is a proof by contradiction? The proof that no set (finite or infinite) can be mapped one-to-one with the set of all its subsets is often given as a proof by contradiction: Let A be some set. Suppose there exists a one-to-one function f between A and P(A); then there exists some subset of A - the diagonal set of the function - which the function does not cover (for no x∈A is f(x) equal to the diagonal set). This is a contradiction, so the assumption cannot be true (A can't be mapped one-to-one with P(A)). But I prefer *not* to state the proof as a proof by contradiction (I don't actually need the assumption that f is a bijection between A and P(A)). So: Let f be any arbitrary function from A to P(A). Then there exists a subset of A - the diagonal set of function f - which the function does not cover; so f is not a bijection. (And this proves the theorem, because I have made no assumption about the function f.) The function x->{x} was given just as an illustration of the construction of the diagonal set.
And what is your point about the empty set? Yes, empty set is by definition a subset of every set, including itself. In particular, it is a subset of the set {1,2}; so this set has four different subsets, not three (note that every set is a subset of itself). This is why the subset relation symbol is often written as ⊆ rather than ⊂ (as an analogy of ≤ relation). (Distinguish the element and the subset relation - empty set is a subset of every set, but it's not an element of every set! For example, it's not an element of the set {1,2} - the only elements of this set are 1 and 2. It's also not an element of itself - empty set has no elements, and that means none at all. For no x is it true that x∈{}.) Now as an exercise for you, to ensure that you understand it: what is the powerset of the empty set (P(0) or P({}))? How many elements does it have?
@@MikeRosoftJH For a proof by contradiction, ck out:
th-cam.com/video/3xlOzbzJXo8/w-d-xo.html
It’s short, simple, and easy to follow.
Hy, you can make understand easily
left wing: destroyed
Wtf
Please don't use the R-word
You may want to see th-cam.com/video/989BsBAECVY/w-d-xo.html which argues against Cantor's theorem.
As far as I can tell, the video says nothing but "the diagonal set does not exist, because I say so". (And conveniently, he has disabled comments in his video.)
First