Cantorの定理

1. $D_f$ は $A$ の元のうち条件 $a\notin f(a)$ を満たすものを分出公理で取り出した集合なので、$D_f\subset A\subset X$、すなわち $D_f\in\mathcal{P}(X)$ である。ある $a_0\in A$ について $f(a_0)=D_f$ であったと仮定する。$a_0\in A$ なので、$D_f$ の定義から
   $$ a_0\in D_f\iff a_0\notin f(a_0)\iff a_0\notin D_f $$
   となる。$a_0\in D_f$ とすると右側の同値から $a_0\notin D_f$ となり矛盾する。したがって $a_0\notin D_f$ であるが、すると同じ同値から $a_0\in D_f$ となり、これも矛盾である。よって $D_f$ は $f$ の像に属さない。$D_f\in\mathcal{P}(X)$ なので $f$ は $\mathcal{P}(X)$ への全射でない。
2. 1 で $A=X$ とした場合である。
3. 単射 $g\colon\mathcal{P}(X)\to X$ があったとする。$A:=g[\mathcal{P}(X)]\subset X$ とおき、$f\colon A\to\mathcal{P}(X)$ を、$a\in A$ に対して $g(B)=a$ となるただ一つの $B\in\mathcal{P}(X)$ を対応させる写像とする（$g$ が単射なので $B$ はただ一つであり、$f$ は $g$ のグラフを裏返した集合として定まる）。任意の $B\in\mathcal{P}(X)$ について $f(g(B))=B$ なので $f$ は全射であり、1 に反する。
4. $x\mapsto\{x\}$ は $X$ から $\mathcal{P}(X)$ への単射である（$\{x\}=\{x'\}$ なら $x=x'$）。よって $|X|\le|\mathcal{P}(X)|$ である。全単射は全射なので、2 により $X$ から $\mathcal{P}(X)$ への全単射はない。したがって $|X|<|\mathcal{P}(X)|$ である。$\square$

Cantorの対角線論法の記事の定理「対角線論法の一般形」による。$Y$ の相異なる 2 元 $a\neq b$ をとり、$\sigma(a):=b$、$y\neq a$ では $\sigma(y):=a$ と定めると、$\sigma\colon Y\to Y$ は不動点をもたない。写像 $F\colon X\to Y^X$ に対して $d(x):=\sigma(F(x)(x))$ とおくと、$d$ はどの $F(x)$ とも点 $x$ で値が異なる。$Y=\{0,1\}$ と特性関数の対応をとれば、$d$ は thm-ct-main の $D_f$（$A=X$）の特性関数になる。$\square$

thm-ct-main の 4 を $X=\kappa$ に当てはめると $|\kappa|<|\mathcal{P}(\kappa)|$ である。基数の順序は単射の存在で定まる（基数の記事の命題「基数の一意性と濃度の順序」）ので、$\kappa<2^\kappa$ である。どの基数 $\kappa$ に対しても、より大きい基数 $2^\kappa$ があるので、最大の基数はない。$\square$

$A:=S\cap\mathcal{P}(S)$、すなわち $S$ の元のうち $S$ の部分集合でもあるもの全体とおく。$A\subset S$ であり、$a\in A$ に $a$ 自身を対応させる写像 $f\colon A\to\mathcal{P}(S)$（$a\subset S$ なので値は $\mathcal{P}(S)$ に入る）を考える。thm-ct-main の 1 を $X=S$ に当てはめると、
$$ D_f=\{a\in A\mid a\notin f(a)\}=\{a\in A\mid a\notin a\}=R_S $$
は $S$ の部分集合であり、$f$ の像 $A$ に属さない。$R_S\subset S$ なので、もし $R_S\in S$ なら $R_S\in S\cap\mathcal{P}(S)=A$ となって矛盾する。よって $R_S\notin S$ である。
すべての集合を元とする集合 $V$ があれば、$R_V$ は集合なので $R_V\in V$ となり、いま示したことに反する。$\square$

$T:=\{(p,q)\in\mathbb{Q}^2\mid p< q\}$ とおく。$\mathbb{R}$ の開集合 $U$ に対し $\Phi(U):=\{(p,q)\in T\mid (p,q)\subset U\}$ と定める。$U$ の各点 $x$ には $x\in(p,q)\subset U$ となる有理数 $p< q$ があるので $U=\bigcup_{(p,q)\in\Phi(U)}(p,q)$ であり、$U$ は $\Phi(U)$ から復元できる。よって開集合全体を $\mathcal{O}$ とすると、$\Psi\colon\mathcal{P}(T)\to\mathcal{O}$、$\Psi(E):=\bigcup_{(p,q)\in E}(p,q)$ は全射である（$\Psi(\Phi(U))=U$）。
$G_\delta$ 集合全体を $\mathcal{G}$ とする。開集合の列 $(U_n)_{n\in\mathbb{N}}$ に共通部分 $\bigcap_nU_n$ を対応させる写像 $\mathcal{O}^{\mathbb{N}}\to\mathcal{G}$ は全射であり、これに $\Psi$ を各成分に施す写像 $\mathcal{P}(T)^{\mathbb{N}}\to\mathcal{O}^{\mathbb{N}}$ を合成すると、全射 $\mathcal{P}(T)^{\mathbb{N}}\to\mathcal{G}$ が得られる。さらに、列 $(E_n)_n$ に $\{(t,n)\mid t\in E_n\}$ を対応させる写像は $\mathcal{P}(T)^{\mathbb{N}}$ と $\mathcal{P}(T\times\mathbb{N})$ の間の全単射である。
$T\times\mathbb{N}$ は $\mathbb{Q}^2\times\mathbb{N}$ の無限部分集合なので可算であり（可算集合の記事の命題「部分集合の可算性と有限性」）、$\mathbb{N}$ の無限部分集合に小さい順に番号を付けることで（選択公理なしに）$\mathbb{N}$ と対等である、$\mathcal{P}(T\times\mathbb{N})$ は $\mathcal{P}(\mathbb{N})$ と対等、$\mathcal{P}(\mathbb{N})$ は $\mathbb{R}$ と対等である（基数の記事の例「連続体の濃度」）。これらを合成すると、全射 $\mathbb{R}\to\mathcal{G}$ が得られる。もし $\mathbb{R}$ のすべての部分集合が $G_\delta$ なら $\mathcal{G}=\mathcal{P}(\mathbb{R})$ となり、$\mathbb{R}$ から $\mathcal{P}(\mathbb{R})$ への全射ができて thm-ct-main の 2 に反する。
使った対等はいずれも具体的な写像で与えられ、可算個の選択を含まない（$\Psi$ は $U$ を表す区間の族を一つ選ぶのではなく、全部の区間を使っている）。$\square$

$\Sigma^*$ は長さごとに有限個の語からなり、長さの順、同じ長さの中では辞書式の順に並べることで $\mathbb{N}$ との全単射 $e\colon\mathbb{N}\to\Sigma^*$ が得られる。$\Gamma^*$ についても同様に全射 $e'\colon\mathbb{N}\to\Gamma^*$ がある（$\Gamma=\emptyset$ なら $\Gamma^*$ は空列だけからなり、定値写像をとる）。$L$ がすべての言語を与えるなら、$L\circ e'\circ e^{-1}\colon\Sigma^*\to\mathcal{P}(\Sigma^*)$ は全射になり、thm-ct-main の 2 に反する。$\square$