|
:<math>B=\{x\in A \mid x\not\in f(x)\}.</math>
This means, by definition, that for all ''<math>x'' ∈ ''\in A''</math>, ''<math>x'' ∈ ''\in B''</math> if and only if ''<math>x'' ∉ ''\notin f''(''x'')</math>. For all ''<math>x''</math> the sets ''<math>B''</math> and ''<math>f''(''x'')</math> cannot be the sameequal because ''<math>B''</math> was constructed from elements of ''<math>A''</math> whose [[Image (mathematics)|images]] (under ''<math>f'')</math> did not include themselves. MoreFor specifically, consider anyall ''<math>x'' ∈ ''\in A'', then</math> either ''<math>x'' ∈ ''\in f''(''x'')</math> or ''<math>x'' ∉ ''\notin f''(''x'')</math>. InIf the<math>x\in formerf(x)</math> case,then ''<math>f''(''x'')</math> cannot equal ''<math>B''</math> because ''<math>x'' ∈ ''\in f''(''x'')</math> by assumption and ''<math>x'' ∉ ''\notin B''</math> by the construction of ''B''definition. InIf the<math>x\notin latterf(x)</math> case,then ''<math>f''(''x'')</math> cannot equal ''<math>B''</math> because ''<math>x'' ∉ ''\notin f''(''x'')</math> by assumption and ''<math>x'' ∈ ''\in B''</math> by the constructiondefinition of ''<math>B''</math>.
Equivalently, and slightly more formally, we have just proved that the existence of ξ<math>\xi ∈\in ''A ''</math> such that ''<math>f ''( ξ)\xi )= ''B ''</math> implies the following [[contradiction]]: ▼
▲Equivalently, and slightly more formally, we just proved that the existence of ξ ∈ ''A'' such that ''f''(ξ) = ''B'' implies the following [[contradiction]]:
:<math>\begin{aligned}
\xi\in B &\iff \xi\notin f(\xi) && \text{(by definition of }B\text{)}; \\
\xi \in B &\iff \xi \in f(\xi) && \text{(by assumption that }f(\xi)=B\text{)};. \\
\end{aligned}</math>
Therefore, by [[reductio ad absurdum]], the assumption must be false.<ref name="Priest2002"/> Thus there is no ξ<math>\xi ∈\in ''A''</math> such that ''<math>f''(ξ)\xi )= ''B''</math> ; in other words, ''<math>B''</math> is not in the image of ''<math>f''</math> and ''<math>f''</math> does not map toonto every element of the power set of ''<math>A''</math>, i.e., ''<math>f''</math> is not surjective.
Finally, to complete the proof, we need to exhibit an injective function from ''<math>A''</math> to its power set. Finding such a function is trivial: just map ''<math>x''</math> to the singleton set <math>\{''x''\}</math>. The argument is now complete, and we have established the strict inequality for any set ''<math>A''</math> that <math>\operatorname{card}(''A'') < \operatorname{card}(𝒫\mathcal{P}(''A''))</math>.
Another way to think of the proof is that ''B'', empty or non-empty, is always in the power set of ''A''. For ''f'' to be [[Surjective function|onto]], some element of ''A'' must map to ''B''. But that leads to a contradiction: no element of ''B'' can map to ''B'' because that would contradict the criterion of membership in ''B'', thus the element mapping to ''B'' must not be an element of ''B'' meaning that it satisfies the criterion for membership in ''B'', another contradiction. So the assumption that an element of ''A'' maps to ''B'' must be false; and ''f'' cannot be onto.
| 