Problem understanding the Cantor Theorem's proof

Question

I can intuitevely picture the power set of A to be of a greater cardinality than A, as it permits multiple combinations of elements of A. However, I couldn't understand the usual proof that comes with the theorem. I tried looking for other proofs but couldn't find any. The proof assumes that in any bijective function f we choose, there's going to be elements of A that map into subsets they're not member of in P(A). And then we would use these as a contradiction.

My problem is the following: what if we choose a function f such that elements of A only map into subsets they're member of? Is this possible? Am I missing something? Wouldn't the proof fail with this kind of, but my understanding is that this f shouldn't exist, then why?

Thank you!

Answer 1

That's not what Cantor's diagonal argument says. What it says? We take a function from $A$ to $P(A)$. Then, for each element $x$ of $A$, we ask a question - is $x$ an element of $f(x)$? Construct a new set $B\subset A$ as follows; its elements are precisely those $x$ for which we answered no. In other words, $x\in B$ if $x\not\in f(x)$ and $x\not\in B$ if $x\in f(x)$. This $B$ is a subset of $A$, so it's in $P(A)$. We then argue that it can't be in the image of $f$. If $y\in B$, $y\not\in f(y)$ by the definition of $B$, and $B\neq f(y)$. If $y\not\in B$, $y\in f(y)$ by the definition of $B$, and $B\neq f(y)$. Repeat over all $y$, and $B$ isn't in the image of $f$.

So, what if we choose $f$ such that $x\in f(x)$ for all $x\in A$? Then $B$ is empty, and it's not in the image of $f$ - because everything in the image of $f$ has at least one element.

Answer 2

The proof I know goes as follows; Assume we have a Set A and a bijection f from A onto P(A). Now given this (fixed) bijection we may determine the subset of Elements of A whose projection( some subset of A) does not include themselves. Now there must be some element of A which is projected onto that subset since f is bijective. It can now be shown that this element is both a member and not a member of said subset, which is a contradiction.

Answer 3

No, nothing goes wrong if we use such a map as our listing.

For example, one such map - arguably the simplest - is $$f:A\rightarrow P(A):a\mapsto\{a\}.$$ The "antidiagonal set" associated to $f$ is $$Cantor(f)=\{a:a\not\in f(a)\}=\{a:a\not\in\{a\}\}=\emptyset.$$ But this is fine: $Cantor(f)$ is indeed a subset of $A$, and it is indeed not in the range of $f$. So nothing's gone wrong.