どの集合 \(X\) も、そのべき集合 \(℘X\) より真に小さい。

1 準備

word(ss,p) … \(\stackrel{\#}\le\)  \(\stackrel{\#}<\)
≤#. … \(X \stackrel{\#}\le Y \Longleftrightarrow \exists A \subset Y . X \stackrel{\#}= A\)
<#. … \(X \stackrel{\#}< Y \Longleftrightarrow X \stackrel{\#}\le Y , X \stackrel{{\tt /}}{\stackrel{\#}=} Y\)
一元集合の族 \(A = \{\{x\} \mid x \in X\}\) は \(\wp X\) の部分集合で、\(x \mapsto \{x\}\) は \(X\) と \(A\) の全単射になる。
\(X \stackrel{\#}\le \wp X\) \(\blacktriangleleft\) \(\mathbb{W}.\) ，ax_s

2 主定理

2.1 証明①

全単射 \(f : X \to \wp X\) があると仮定し、 \(A = \{x \in X \mid x \notin f(x)\}\) とおくと \(A \in \wp X\)。
\(A = f(a)\) となる \(a \in X\) があれば \(a \in A \iff a \notin A\) となって矛盾する（対角線論法）。
\(X \stackrel{\#}< \wp X\) \(\blacktriangleleft\) \(\mathbb{W}.\) ，ax_s

2.2 証明②

全単射 \(g : \wp X \to X\) があると仮定し、 \(B = \{g(A) \mid A \subset X , g(A) \notin A\}\) とおくと \(B \in \wp X\)。
\(g(B) \in B\) なら \(g(B) = g(A)\)、\(g(A) \notin A\) となる \(A\) があり、単射だから \(A = B\) で \(g(B) \notin B\)。
\(g(B) \notin B\) なら \(A = B\) として \(g(B) \in B\)。どちらも矛盾する。
\(X \stackrel{\#}< \wp X\) \(\blacktriangleleft\) \(\mathbb{W}.\) ，ax_s