[proofplan]
We argue by contradiction using Cantor's diagonal construction. Assuming $\mathcal{P}(X)$ is countable yields a surjection $f: \mathbb{N} \to \mathcal{P}(X)$ after embedding a countably infinite copy of $\mathbb{N}$ into $X$ (available because $X$ is infinite). The diagonal set $D = \{n \in \mathbb{N} : n \notin f(n)\}$ is then an element of $\mathcal{P}(X)$ that cannot be in the range of $f$: any preimage $m$ of $D$ produces the contradictory equivalence $m \in D \iff m \notin D$. Hence no such surjection exists and $\mathcal{P}(X)$ is uncountable.
[/proofplan]
[step:Embed a countably infinite copy of $\mathbb{N}$ inside $X$]
Since $X$ is infinite, by the [Axiom of Countable Choice](/theorems/???) there exists an injection
\begin{align*}
\iota: \mathbb{N} &\to X.
\end{align*}
Let $N := \iota(\mathbb{N}) \subseteq X$; the restriction $\iota: \mathbb{N} \to N$ is a bijection. We identify $n \in \mathbb{N}$ with $\iota(n) \in N \subseteq X$; under this identification, any subset $A \subseteq \mathbb{N}$ corresponds to the subset $\iota(A) \subseteq X$, and in particular $\iota(A) \in \mathcal{P}(X)$.
[/step]
[step:Set up the contradiction by assuming $\mathcal{P}(X)$ is countable]
Suppose for contradiction that $\mathcal{P}(X)$ is countable. Since $\mathcal{P}(X)$ contains $X$ and hence is nonempty, there exists a surjection
\begin{align*}
f: \mathbb{N} &\to \mathcal{P}(X).
\end{align*}
Fix such an $f$ for the remainder of the argument.
[/step]
[step:Construct the diagonal subset $D$ of $\mathbb{N}$ and lift it to $X$]
Define the diagonal set
\begin{align*}
D &:= \{n \in \mathbb{N} : n \notin f(n)\} \subseteq \mathbb{N}.
\end{align*}
This is well-defined: for each $n \in \mathbb{N}$, the statement $n \in f(n)$ uses the identification $n \leftrightarrow \iota(n) \in X$ and the fact that $f(n) \in \mathcal{P}(X)$ is a subset of $X$, so $\iota(n) \in f(n)$ is either true or false.
Let $D^X := \iota(D) \subseteq X$. Then $D^X \in \mathcal{P}(X)$.
[guided]
The diagonal construction requires comparing the natural number $n$ with the set $f(n) \subseteq X$. These live in different universes, so we need a bridge: the injection $\iota: \mathbb{N} \to X$ identifies each $n$ with a specific element $\iota(n) \in X$. Under this identification we can ask whether $\iota(n) \in f(n)$, which is a well-defined yes/no question because $f(n)$ is a subset of $X$.
The set $D$ collects those $n$ for which the answer is "no". To stay in $\mathcal{P}(X)$ we transport $D$ along $\iota$ to $D^X := \iota(D) \subseteq X$. The resulting element $D^X \in \mathcal{P}(X)$ is the candidate for the set that $f$ cannot hit.
[/guided]
[/step]
[step:Derive a contradiction from surjectivity of $f$]
Since $f$ is surjective onto $\mathcal{P}(X)$ and $D^X \in \mathcal{P}(X)$, there exists $m \in \mathbb{N}$ with
\begin{align*}
f(m) &= D^X.
\end{align*}
We ask whether $m \in D$.
Case 1: $m \in D$. By definition of $D$, this is equivalent to $\iota(m) \notin f(m) = D^X = \iota(D)$. But $m \in D$ implies $\iota(m) \in \iota(D) = D^X$, so $\iota(m) \in f(m)$, contradicting $\iota(m) \notin f(m)$.
Case 2: $m \notin D$. By definition of $D$, this is equivalent to $\iota(m) \in f(m) = D^X = \iota(D)$. Since $\iota$ is injective, $\iota(m) \in \iota(D)$ implies $m \in D$, contradicting $m \notin D$.
Either case produces a contradiction.
[guided]
This is the diagonal contradiction in its purest form. The key is that $D$ is designed so membership of $m$ in $D$ is logically equivalent to non-membership of $m$ in $f(m)$. If $f(m) = D^X$ (the transported version of $D$), then this equivalence becomes the self-referential pair
\begin{align*}
m \in D \;\iff\; \iota(m) \notin f(m) \;\iff\; \iota(m) \notin D^X \;\iff\; m \notin D,
\end{align*}
where the last step uses injectivity of $\iota$ to pass between $m \in D$ and $\iota(m) \in D^X$. A statement equivalent to its own negation is false in classical logic, so the assumption that $f(m) = D^X$ must fail; but $f$ was supposed to be surjective. This is the contradiction.
[/guided]
[/step]
[step:Conclude that $\mathcal{P}(X)$ is uncountable]
The assumption that $f: \mathbb{N} \to \mathcal{P}(X)$ is a surjection leads to a contradiction. Therefore no such surjection exists, and $\mathcal{P}(X)$ is not countable, i.e., $\mathcal{P}(X)$ is uncountable.
[/step]
