[proofplan] We prove the theorem by contradiction against an arbitrary [function](/page/Function) $f: X \to \mathcal{P}(X)$. From $f$ we form the anti-diagonal subset $S \subset X$ consisting of exactly those elements $x \in X$ which do not belong to their assigned subset $f(x)$. If $S$ were equal to $f(a)$ for some $a \in X$, then the membership statement $a \in S$ would be equivalent to its own negation, so $S$ cannot lie in the image of $f$. [/proofplan] [step:Construct the anti-diagonal subset associated to an arbitrary function] Let $f: X \to \mathcal{P}(X)$ be an arbitrary function from $X$ to its power set. Define the subset $S \subset X$ by \begin{align*} S = \{x \in X : x \notin f(x)\}. \end{align*} This is a subset of $X$ because each element of $S$ is selected from $X$ according to the property $x \notin f(x)$. [guided] We start with an arbitrary function \begin{align*} f: X \to \mathcal{P}(X). \end{align*} This means that for every $x \in X$, the value $f(x)$ is a subset of $X$. Hence the membership statement $x \in f(x)$ is meaningful for every $x \in X$. The diagonal construction records whether each element $x$ belongs to the subset assigned to it by $f$. We define \begin{align*} S = \{x \in X : x \notin f(x)\}. \end{align*} Since the defining condition is imposed only on elements $x \in X$, the resulting [set](/page/Set) $S$ is a subset of $X$. Therefore $S$ is an element of the power set $\mathcal{P}(X)$. [/guided] [/step] [step:Show that the anti-diagonal subset cannot be a value of the function] We prove that $S$ is not in the image of $f$. Suppose, for contradiction, that there exists $a \in X$ such that $f(a) = S$. By the definition of $S$, \begin{align*} a \in S \iff a \notin f(a). \end{align*} Using $f(a) = S$, this becomes \begin{align*} a \in S \iff a \notin S. \end{align*} If $a \in S$, then the equivalence gives $a \notin S$, a contradiction. If $a \notin S$, then the equivalence gives $a \in S$, also a contradiction. Hence no such $a \in X$ exists, and therefore $S \notin \{f(x) : x \in X\}$. [guided] We now prove that the subset $S$ constructed above cannot occur as any value of $f$. Assume, for contradiction, that there exists an element $a \in X$ such that \begin{align*} f(a) = S. \end{align*} Because $a \in X$, the definition of $S$ applies to $a$. Therefore \begin{align*} a \in S \iff a \notin f(a). \end{align*} Substituting the assumed equality $f(a) = S$ into the right-hand side gives \begin{align*} a \in S \iff a \notin S. \end{align*} This equivalence is impossible. If $a \in S$, then the implication from left to right gives $a \notin S$, contradicting $a \in S$. If $a \notin S$, then the implication from right to left gives $a \in S$, contradicting $a \notin S$. Thus the assumption that $f(a) = S$ for some $a \in X$ is false. Consequently, there is no element $a \in X$ with $f(a) = S$. Since $S \in \mathcal{P}(X)$, this means that $S$ is an element of the codomain of $f$ which is not in the image of $f$. [/guided] [/step] [step:Conclude that no surjection or bijection exists] Since $f: X \to \mathcal{P}(X)$ was arbitrary and we constructed an element $S \in \mathcal{P}(X)$ not in the image of $f$, no function from $X$ to $\mathcal{P}(X)$ is surjective. A bijection is, in particular, a surjection, so there is no bijection between $X$ and $\mathcal{P}(X)$. [/step]