数理論理学・集合論の問題

カントールの定理より ${\aleph }_0<\mathfrak{c}<2^{\mathfrak{c}}$ なので、3 つの濃度は互いに異なる（連続体仮説は不要）。また基数演算 ${\mathfrak{c}}^{{\aleph }_0}=(2^{{\aleph }_0}{)}^{{\aleph }_0}=2^{{\aleph }_0\cdot {\aleph }_0}=2^{{\aleph }_0}=\mathfrak{c}$、${\mathfrak{c}}^{\mathfrak{c}}=2^{{\aleph }_0\cdot \mathfrak{c}}=2^{\mathfrak{c}}$ を用いる。各集合はカントール–ベルンシュタインの定理により上下から評価する。

$(1)$ 次数 $n$ 以下の多項式全体は ${\mathbb{Q}}^{n+1}$ と全単射で対応し可算。可算個の可算集合の和集合なので高々可算で、無限集合だから ${\aleph }_0$。

$(2)$ $0$ でない各多項式 $f\in \mathbb{Q}[x]$ の実根は有限個。$(1)$ より可算個の有限集合の和集合で高々可算。$\mathbb{Q}$ を含むので無限、よって ${\aleph }_0$。

$(3)$ $\{0,1,\dots ,n\}$ の部分集合全体は有限で、$\mathbb{N}$ の有限部分集合はいずれかに含まれる。可算個の有限集合の和集合で、無限集合（$\{n\}$ たち）なので ${\aleph }_0$。

$(4)$ $\{0,1{\}}^{\mathbb{N}}\subseteq {\mathbb{N}}^{\mathbb{N}}$ より $\ge 2^{{\aleph }_0}$、${\mathbb{N}}^{\mathbb{N}}$ の濃度は ${\aleph }_0^{{\aleph }_0}\le {\mathfrak{c}}^{{\aleph }_0}=\mathfrak{c}$。よって $\mathfrak{c}$。

$(5)$ $(4)$ の部分集合なので $\le \mathfrak{c}$。$S\subseteq \mathbb{N}$ に対し、$n\in S$ のときだけ $2n$ と $2n+1$ を入れ替える全単射 ${\sigma }_S$ を対応させると $S\mapsto {\sigma }_S$ は単射なので $\ge \mathfrak{c}$。よって $\mathfrak{c}$。

$(6)$ 開集合 $U$ に $\{(p,q)\in {\mathbb{Q}}^2:p<q,(p,q)\subseteq U\}$ を対応させる。$U$ はこれらの区間の和集合なので単射であり、$\le 2^{{\aleph }_0}=\mathfrak{c}$。$a\mapsto (a,\infty )$ が単射なので $\ge \mathfrak{c}$。よって $\mathfrak{c}$。

$(7)$ 連続関数は $\mathbb{Q}$ 上の値で決まる（$\mathbb{Q}$ は稠密）ので $\le {\mathfrak{c}}^{{\aleph }_0}=\mathfrak{c}$。定数関数で $\ge \mathfrak{c}$。よって $\mathfrak{c}$。

$(8)$ 空でない高々可算集合は、ある写像 $\mathbb{N}\to \mathbb{R}$ の像なので（選択公理を用いて代表を選べば単射が得られ）$\le {\mathfrak{c}}^{{\aleph }_0}+1=\mathfrak{c}$。1 点集合全体で $\ge \mathfrak{c}$。よって $\mathfrak{c}$。

$(9)$ 濃度は ${\mathfrak{c}}^{\mathfrak{c}}=2^{\mathfrak{c}}$。

$(10)$ $\mathcal{P}(\mathbb{R})$ の部分集合なので $\le 2^{\mathfrak{c}}$。カントール集合 $C$ は測度 $0$ で濃度 $\mathfrak{c}$ なので、その部分集合はすべて（測度 $0$ の集合の部分集合として）可測。よって $\ge |\mathcal{P}(C)|=2^{\mathfrak{c}}$。したがって $2^{\mathfrak{c}}$。

$(11)$ 同値関係は $\mathbb{R}\times \mathbb{R}$ の部分集合なので $\le 2^{|\mathbb{R}\times \mathbb{R}|}=2^{\mathfrak{c}}$。$S\subseteq \mathbb{R}\setminus \{0\}$ に対し、類 $S\cup \{0\}$ と残りの各 1 点集合からなる分割に対応する同値関係を考えると、$0$ の同値類から $S$ が復元できるので単射。$|\mathcal{P}(\mathbb{R}\setminus \{0\})|=2^{\mathfrak{c}}$ より $\ge 2^{\mathfrak{c}}$。よって $2^{\mathfrak{c}}$。

以上より、${\aleph }_0$ は $(1),(2),(3)$ の 3 個、$\mathfrak{c}$ は $(4)$〜$(8)$ の 5 個、$2^{\mathfrak{c}}$ は $(9),(10),(11)$ の 3 個。答えは $(3,5,3)$。

各集合の濃度を求める。
(1) $\mathbb{Q}[x]$ は、次数ごとに ${\mathbb{Q}}^{n+1}$ が可算で、それらの可算和なので可算。濃度は ${\aleph }_0$。
(2) 実代数的数は、$\mathbb{Q}[x]$ の各多項式の実根が有限個で、それらの可算和なので可算。しかも $\mathbb{Q}$ を含むので無限。濃度は ${\aleph }_0$。
(3) $\mathbb{N}$ の有限部分集合全体は、要素数 $n$ ごとに ${\mathbb{N}}^n$ が可算で、その可算和なので可算。しかも無限。濃度は ${\aleph }_0$。
(4) ${\mathbb{N}}^{\mathbb{N}}$ の濃度は ${\aleph }_0^{{\aleph }_0}=\mathfrak{c}$。
(5) 全単射全体は ${\mathbb{N}}^{\mathbb{N}}$ の部分集合なので $\le \mathfrak{c}$。一方、$\{2k,2k+1\}$ の各組について入れ替えるか否かを選ぶと $2^{{\aleph }_0}$ 個の相異なる全単射が得られるので $\ge \mathfrak{c}$。濃度は $\mathfrak{c}$。
(6) 開集合は有理端点の開区間の可算和で決まるので、高々 $2^{{\aleph }_0}=\mathfrak{c}$ 個。開区間 $(a,\infty )$ だけでも $\mathfrak{c}$ 個ある。濃度は $\mathfrak{c}$。
(7) 連続関数は $\mathbb{Q}$ 上の値で決まるので高々 ${\mathfrak{c}}^{{\aleph }_0}=\mathfrak{c}$ 個。定数関数だけで $\mathfrak{c}$ 個ある。濃度は $\mathfrak{c}$。
(8) 高々可算な部分集合は ${\mathbb{R}}^{\mathbb{N}}$ の像として表せるので高々 ${\mathfrak{c}}^{{\aleph }_0}=\mathfrak{c}$ 個。一点集合だけで $\mathfrak{c}$ 個ある。濃度は $\mathfrak{c}$。
(9) ${\mathbb{R}}^{\mathbb{R}}$ の濃度は ${\mathfrak{c}}^{\mathfrak{c}}=2^{\mathfrak{c}}$。
(10) ルベーグ可測集合全体は、カントール集合（測度 0）のすべての部分集合 $2^{\mathfrak{c}}$ 個を含み、$\mathcal{P}(\mathbb{R})$ の部分集合なので高々 $2^{\mathfrak{c}}$。濃度は $2^{\mathfrak{c}}$。
(11) 同値関係は $\mathbb{R}\times \mathbb{R}$ の部分集合なので高々 $2^{\mathfrak{c}}$。$A\subseteq \mathbb{R}\setminus \{0\}$ に対し、$\{0\}\cup A$ を 1 つの類、残りを一点類とする同値関係を作ると、相異なる $A$ から相異なる同値関係が得られるので $\ge 2^{\mathfrak{c}}$。濃度は $2^{\mathfrak{c}}$。

集計すると、${\aleph }_0$ は (1)(2)(3) の 3 個、$\mathfrak{c}$ は (4)〜(8) の 5 個、$2^{\mathfrak{c}}$ は (9)(10)(11) の 3 個。合計 11 個で、すべての集合がちょうど 1 つの類に入る。