Non-existence of a Surjective Function from a Set to Its Subsets (Cantor's theorem)
Cantor's theorem states:
Suppose that $A$ is a set and $f\colon A\to\mathcal P(A)$ is any function, then $f$ is not surjective.
The proof is quite simple, and constructive!
Proof. Suppose that $f\colon A\to\mathcal P(A)$ is a function, we define $D=\{a\in A\mid a\notin f(a)\}$. This is a good definition, since $f(a)$ is a subset of $A$, and $a$ is an element of $A$, we can ask whether or not $a\in f(a)$. So $D$ is the set of those elements of $A$ which do not have this property.
Of course that $D\in\mathcal P(A)$ since it is clearly a subset of $A$. We will show that $f(a)\neq D$ for all $a\in A$.
- If $a\in D$ then, by definition of $D$, $a\notin f(a)$. So $f(a)\neq D$, since the element $a$ belongs to D but not to $f(a)$.
- If $a\notin D$ then, by definition of $D$, $a\in f(a)$. By the same argument, again $f(a)\neq D$.
Either way, $D\neq f(a)$ for all $a\in A$. Therefore $f$ is not surjective. $\square$
Note that for different functions we have different $D$'s. It is possible that $D=A$ (e.g. if $f(a)=\varnothing$ for all $a$), or it could be $\varnothing$ (e.g. if $f(a)=\{a\}$ for all $a$). However regardless to its value it will not be in the range of $f$.
Look up Cantor's Theorem. There are several versions of this theorem. The basic version is to the effect that there is no bijection between a set $A$ and its power set $P(A)$. One of the proofs goes by showing there is no surjection from $A$ to $P(A)$. What one does is to assume there is, so that for each $a$ there is a subset $f(a)$ in the power set. Then one defines a set $B$ by saying that $x$ is in $B$ if and only if $x$ is NOT in the set $f(x)$. Now you ask: Is $x$ in $B$? If it is, it isn't, and if it isn't then it is... either way you get a contradiction!
For those who are looking for an explanation for the answer given by Asaf Karagila:
Given a set of any non-zero size, it is possible to create a larger set by taking the set of subsets of the original. Suppose we have a set N, consisting of {A,B,C,D}. We can then identify set S as the set of all subsets of N. We can conduct a little mental experiment by writing the members of N in a row and then the members of S in another row below the first, like so:
N A B C D
S {} {A} {B} {A} {D} {AB} {AC} {AD} {BC} {BD} {CD} {ABC} {ABD} {ACD} {BCD} {ABCD}
Next, we randomly take four elements of S and match them up with the elements of N. Say we take {A} {AB} {BD} {ACD} and match them with A B C D of N respectively. We can find an element of S that is not matched up checking whether an element of set N is matched with a subset that contains it. For example, “yes” for A, “no” for B, “no” for C, and “yes” for D. With this information, we can be sure that the subset {BC} has not been matched with any member of N. Because every element of N has been matched with an element of S, and there is at least one “leftover” element of S, we can say that S is definitely larger than N. Note that we did not have to count the members of either set to figure this out.
Let’s again attempt to match up every member of N with a member of D. We can ask the “yes or no” questions from before to find out which members of N are paired up with subsets that contain them. Let’s say that any members of N for which the answer is “no” go into a new set called W. The set W is then the subset of N containing members that are not paired up with a subset that contains them. Because W is a subset of N, it must be in S, which is the set of all subsets of N. Can W be matched up with some element of N? Let’s say that w, a member of N, is matched up with W. If w is in W, then it is matched up with a subset that contains it, which by definition means that it cannot be in W; therefore, we have a logical contradiction.
Source: (read section 3.6) https://www.google.com/url?sa=t&source=web&rct=j&url=https://www.learner.org/wp-content/uploads/2019/02/MathIlluminated_03_txt.pdf&ved=2ahUKEwiNyeffwrjoAhUPU30KHTgoCfQQFjAAegQIARAB&usg=AOvVaw0HWmjFKYKJ1GsOjko3Fk7f