対角線論法と連続体の濃度

各正の整数 $n$ に対して、$0$ と $1$ からなる無限列 $s_n=(s_n(1),s_n(2),s_n(3),\dots )\in \{0,1{\}}^{{\mathbb{Z}}_{>0}}$ を
$$s_n(k)=\{\begin{array}{ll}1& (n+k\text{が}3\text{の倍数のとき})\\ 0& (\text{それ以外のとき})\end{array}(k\text{は正の整数})$$
で定める。カントールの対角線論法にならい、列 $d=(d(1),d(2),d(3),\dots )$ を
$$d(n)=1-s_n(n)(n\text{は正の整数})$$
で定める。このとき $d\in \{0,1{\}}^{{\mathbb{Z}}_{>0}}$ であり、各 $n$ について $d$ は $n$ 番目の項で $s_n$ と異なるので、$d$ はどの $s_n$ とも一致しない。

和 $d(1)+d(2)+\cdots +d(30)$ の値を求めよ。

${\mathbb{Z}}_{>0}$ を正の整数全体の集合、$\mathcal{P}({\mathbb{Z}}_{>0})$ をそのべき集合とする。写像 $f:{\mathbb{Z}}_{>0}\to \mathcal{P}({\mathbb{Z}}_{>0})$ を
$$f(n)=\{k\in {\mathbb{Z}}_{>0}\mid (n-6)k+8>0\}$$
で定める。カントールの対角線論法にならって、集合
$$D=\{n\in {\mathbb{Z}}_{>0}\mid n\notin f(n)\}$$
を考える。この $D$ はどの正の整数 $m$ に対しても $f(m)$ と一致しないので、$f$ は全射ではない。集合 $D$ を求めよ。

${\mathbb{Z}}_{>0}$ を正の整数全体の集合、$\mathcal{P}({\mathbb{Z}}_{>0})$ をそのべき集合とする。写像 $f:{\mathbb{Z}}_{>0}\to \mathcal{P}({\mathbb{Z}}_{>0})$ を
$$f(n)=\{k\in {\mathbb{Z}}_{>0}\mid k\le (n-3{)}^2\}$$
で定める（たとえば $f(3)=\varnothing$ である）。カントールの対角線論法で用いる集合
$$D=\{n\in {\mathbb{Z}}_{>0}\mid n\notin f(n)\}$$
を求めよ。

ZFC のもとで考える。$\mathbb{N}=\{0,1,2,\dots \}$（$0$ を含む）、$\mathbb{Q}$ は有理数全体、$\mathbb{R}$ は実数全体とし、$\mathfrak{c}=2^{{\aleph }_0}$ とおく（連続体仮説は仮定しない）。次の 11 個の集合を考える。

$(1)$ 有理数係数の 1 変数多項式全体 $\mathbb{Q}[x]$

$(2)$ 実数である代数的数全体

$(3)$ $\mathbb{N}$ の有限部分集合全体

$(4)$ 写像 $\mathbb{N}\to \mathbb{N}$ 全体 ${\mathbb{N}}^{\mathbb{N}}$

$(5)$ 全単射 $\mathbb{N}\to \mathbb{N}$ 全体

$(6)$ $\mathbb{R}$ の（通常の位相に関する）開集合全体

$(7)$ 連続関数 $\mathbb{R}\to \mathbb{R}$ 全体

$(8)$ $\mathbb{R}$ の高々可算な部分集合（有限集合・空集合を含む）全体

$(9)$ 関数 $\mathbb{R}\to \mathbb{R}$ 全体

$(10)$ $\mathbb{R}$ のルベーグ可測集合全体

$(11)$ $\mathbb{R}$ 上の同値関係全体

これらのうち、濃度が ${\aleph }_0$ であるものの個数、$\mathfrak{c}$ であるものの個数、$2^{\mathfrak{c}}$ であるものの個数を、この順に組で答えよ。

${\mathbb{Z}}_{>0}$ を正の整数全体の集合、$\mathbb{Q}$ を有理数全体の集合、$\mathbb{R}$ を実数全体の集合とする。次の $(1)$〜$(8)$ の集合のうち、濃度が $2^{{\aleph }_0}$（連続体の濃度）であるものの番号をすべて求め、番号の集合として答えよ。

$(1)$ 写像 $f:{\mathbb{Z}}_{>0}\to \{0,1\}$ 全体の集合

$(2)$ 直積集合 $\mathbb{Q}\times \mathbb{Q}$

$(3)$ ${\mathbb{Z}}_{>0}$ の有限部分集合（空集合を含む）全体の集合

$(4)$ 実数係数の 1 変数多項式全体の集合 $\mathbb{R}[x]$

$(5)$ 連続関数 $f:\mathbb{R}\to \mathbb{R}$ 全体の集合

$(6)$ 写像 $f:\mathbb{R}\to \mathbb{R}$ 全体の集合（連続とは限らない）

$(7)$ 実数である代数的数（整数係数の $0$ でない多項式の根になる実数）全体の集合

$(8)$ 正の整数からなる狭義単調増加の無限数列 $(a_1,a_2,a_3,\dots )$（$a_1<a_2<a_3<\cdots$）全体の集合

実数全体の集合 $\mathbb{R}$ の濃度を $2^{{\aleph }_0}$ と書く。次の $8$ つの集合 $S_1,\dots ,S_8$ のうち、濃度がちょうど $2^{{\aleph }_0}$ であるものの個数を求めよ。

• $S_1$: 有理数を係数とする $1$ 変数多項式全体の集合 $\mathbb{Q}[x]$
• $S_2$: 実数列 $(a_n{)}_{n=1}^{\infty }$（$a_n\in \mathbb{R}$）全体の集合
• $S_3$: 正の整数全体の集合から $\{0,1\}$ への写像全体の集合
• $S_4$: 正の整数全体の集合の有限部分集合全体の集合
• $S_5$: $\mathbb{R}$ から $\mathbb{R}$ への連続写像全体の集合
• $S_6$: $\mathbb{R}$ から $\mathbb{R}$ への写像全体の集合
• $S_7$: 代数的数（有理数係数の $0$ でない多項式の根となる複素数）全体の集合
• $S_8$: 平面 ${\mathbb{R}}^2$ 内の開円板 $\{(x,y)\mid (x-a{)}^2+(y-b{)}^2<r^2\}$（$a,b\in \mathbb{R}$, $r>0$）全体の集合

$\mathfrak{c}=2^{{\aleph }_0}$ を実数全体の集合 $\mathbb{R}$ の濃度とする。次の $5$ つの集合を考える。

• $X_1=\{0,1,2\}$
• $X_2$：実数である代数的数全体の集合（整数係数の $1$ 次以上の多項式の実数解となる実数全体）
• $X_3$：通常の位相に関する $\mathbb{R}$ の開集合全体の集合
• $X_4$：$\mathbb{R}$ から $\mathbb{R}$ への連続関数全体の集合
• $X_5$：$\mathbb{R}$ から $\mathbb{R}$ への全単射全体の集合

$i,j\in \{1,2,3,4,5\}$ に対し、$X_i$ から $X_j$ への写像全体の集合を $\mathrm{Map}(X_i,X_j)$ とする。順序対 $(i,j)$ 全 $25$ 個のうち、$\mathrm{Map}(X_i,X_j)$ の濃度がちょうど $2^{\mathfrak{c}}$ であるものの個数を求めよ。

集合 $X,Y$ に対して、$Y$ から $X$ への写像全体の集合を $X^Y$ で表す。ただし、$X^{\varnothing }$ は空写像 $1$ 個だけからなる集合とし、$Y\ne \varnothing$ のとき ${\varnothing }^Y=\varnothing$ とする。${\mathbb{Z}}_{>0}$ を正の整数全体の集合、$\mathbb{R}$ を実数全体の集合、$\mathcal{P}(\mathbb{R})$ を $\mathbb{R}$ のべき集合とする。次の $7$ 個の集合からなる族を考える。
$$\mathcal{F}=\{\varnothing ,\{1\},\{1,2\},\{1,2,3\},{\mathbb{Z}}_{>0},\mathbb{R},\mathcal{P}(\mathbb{R})\}$$
$X,Y$ がそれぞれ $\mathcal{F}$ の元全体を動くとき（$X=Y$ の場合も含む）、$49$ 個の集合 $X^Y$ が得られる。これら $49$ 個の集合の濃度として現れる値は、全部で何種類あるか求めよ。ただし、$2$ つの集合の濃度が等しいとは、それらの間に全単射が存在することである。

実数全体の集合 $\mathbb{R}$ の濃度を $\mathfrak{c}=2^{{\aleph }_0}$ とする。次の $8$ 個の集合のうち、濃度がちょうど $\mathfrak{c}$ であるものの個数を求めよ。

$(1)$ $\mathbb{R}$ から $\mathbb{R}$ への連続関数全体の集合

$(2)$ 有理数全体の集合 $\mathbb{Q}$ の有限部分集合全体の集合

$(3)$ $\mathbb{R}$ から $\mathbb{R}$ への単調増加関数（$x<y\Rightarrow f(x)\le f(y)$ を満たす関数）全体の集合

$(4)$ 閉区間 $[0,1]$ 上で定義された実数値関数のうち、$[0,1]$ でリーマン積分可能なもの全体の集合

$(5)$ 正の整数全体の集合上の同値関係全体の集合

$(6)$ 実代数的数（整数係数の $0$ でない多項式の根となる実数）全体の集合

$(7)$ $\mathbb{R}$（通常の位相）の開集合全体の集合

$(8)$ 関数 $f:\mathbb{R}\to \{0,1\}$ のうち、$f(x)=1$ となる $x$ が有限個であるもの全体の集合