A question regarding the Power set

Question

In the proofs that I have seen so far for showing that the power set $2^X$ of a set $X$ cannot be in bijection to $X$, the common idea is to assume that there exists a surjection $f \colon X \to 2^X$ and then consider the set $$ B = \{ x \in X \mid x \notin f(x)\} $$

Then the argument proceeds by saying that this set is contradictory, because its pre-image (say $y \in X$, i.e. $f(y) = B$) satisfies both $y \in B$ and $y \notin B$.

On Wikipedia, this method is said to be analogous to Cantor's diagonal argument that is used to show that the interval $(0,1)$ of real numbers between $0$ and $1$ is uncountable. Here we assume that there exists an enumeration. Representing a number $x \in (0,1)$ in its unique decimal expansion, we obtain a list \begin{align} x_1 &= 0.a_{11}a_{12}a_{13}... \\ x_2 &= 0.a_{21}a_{22}a_{23}... \\ x_2 &= 0.a_{31}a_{32}a_{33}... \\ x_2 &=0.a_{11}a_{12}a_{13}... \\ \vdots \end{align} where $a_{ij} \in \{0,1,\dots,9\}$ for each $i \in \mathbb{N}$ and $j \in \mathbb{N}$. Then one constructs an element from $(0,1)$ that is not in this list. For example, one can take the number $x = 0.b_{1}b_{2}b_{3}\dots$ where \begin{equation} b_i = \begin{cases} 1 & \text{if } a_{ii} = 5 \\ 5 & \text{if } a_{ii} \ne 5 \end{cases} \end{equation}

Here, the number $x$ that is generated is well defined as an element of $(0,1)$, and it does not appear in the list above so we've reached a contradiction.

On the other hand, for the argument above regarding the power set, assuming $f$ exists implies the object $B$ is not well defined as an element of $2^X$ since it is not the image of a function from $X$ to the set $\{0,1\}$ (it is multi-valued, namely the preimage of $B$ evaluates both to $0$ and $1$). In other words, I cannot use this object $B$ to derive a contradiction. What I can derive is that, if $f$ exists then $B$ is not a set, and if $B$ is a set for each function $f \colon 2^X \to X$ then no such $f$ can be surjective.

The latter is what the proofs claim to be the only option, in other words this object $B$ must be a well defined set by some other reason - what am I missing?

Answer 1

Cantor's theorem is indeed very close to the diagonal argument.

The idea is a generalization of the following concept. We write a table: $$\begin{array}{|c|c|c|c|c} \hline \quad & f(x_1) & f(x_2) & f(x_3) & \ldots\\\hline x_1 & 0 & 1 & 0 & \ldots\\\hline x_2 & 1 & 1 & 0 & \ldots\\\hline x_3 & 0 & 0 & 1 & \ldots\\\hline \vdots \end{array}$$ Where $(x,f(x))$ is $0$ if $x\notin f(x)$ and $1$ otherwise. The diagonal argument is to traverse across the diagonal, and consider those which have $0$ there. Collect this set, and you can in fact show that it is not $f(x)$ for any $x$.

This $B$, as you denote it, or rather its indicator function (if you prefer considering $2^X$ rather than $\mathcal P(X)$ for one reason or another) exists because we define it. We explicitly gave a description of its members. Ordered pairs of the form $\langle x,i\rangle$ where $i=0$ if $x\in f(x)$ and $1$ otherwise.

One of the earliest principles of set theory is comprehension. It's an important principle, mathematically and philosophically. If we can describe a collection then we want it to exist. And while the unrestricted comprehension (all the describable collections are sets) is inconsistent, when axiomatic set theory was formulated this was limited in the following sense:

If $A$ is a set, and $\varphi(x,u_1,\ldots,u_n)$ is a formula, then for every choice of parameters, $p_1,\ldots,p_n$ the set $\{a\in A\mid\varphi(a,p_1,\ldots,p_n)\}$ exists.

This is known as the axiom schema of specification as mentioned in the comments, and also as "restricted comprehension" and "separation" sometimes. Why does that help us? Well, if we assume that $X$ is a set, then we have defined a subset (from the parameter $f$) and therefore it exists. If you prefer the functional version, then consider the set $X\times\{0,1\}$ and apply the same argument.

Therefore we proved that $B$ exists, and there is no surjection from a set onto its power set.