可算集合

正の整数全体の集合を ${\mathbb{Z}}_{>0}$ とする。直積 ${\mathbb{Z}}_{>0}\times {\mathbb{Z}}_{>0}$ の元 $(m,n)$ を、次の規則で一列に並べる。

• $m+n$ の値が小さいものほど先に並べる。
• $m+n$ の値が等しいものどうしでは、$m$ が小さいものほど先に並べる。

この並べ方では、列は $(1,1),(1,2),(2,1),(1,3),(2,2),(3,1),(1,4),\dots$ となる。先頭から $1$ 番目、$2$ 番目、$\dots$ と番号を付けると、$(m,n)$ にその番号を対応させる写像 $\phi :{\mathbb{Z}}_{>0}\times {\mathbb{Z}}_{>0}\to {\mathbb{Z}}_{>0}$ は全単射になる。このことから ${\mathbb{Z}}_{>0}\times {\mathbb{Z}}_{>0}$ の濃度は ${\aleph }_0$ である。

このとき、$\phi (4,7)$ の値を求めよ。

${\mathbb{Z}}_{>0}$ を正の整数全体の集合とする。直積 ${\mathbb{Z}}_{>0}\times {\mathbb{Z}}_{>0}$ の濃度が ${\aleph }_0$ であることを示すために、その元 $(m,n)$ を次の規則で一列に並べる。

• $m+n$ の値が小さいものから順に並べる。
• $m+n$ の値が等しいものどうしは、$m$ の値が小さいものから順に並べる。

こうして得られる列は
$$(1,1),(1,2),(2,1),(1,3),(2,2),(3,1),(1,4),\dots$$
となる。この列の $k$ 番目の元を $\phi (k)$ とおくと、$\phi :{\mathbb{Z}}_{>0}\to {\mathbb{Z}}_{>0}\times {\mathbb{Z}}_{>0}$ は全単射になる。$\phi (k)=(3,5)$ となる正の整数 $k$ を求めよ。

${\mathbb{Z}}_{>0}$ を正の整数全体の集合とします。直積 ${\mathbb{Z}}_{>0}\times {\mathbb{Z}}_{>0}$ が可算であることを示すため、その元 $(m,n)$ を次の規則で一列に並べます。

• $m+n$ が小さいものほど前に置く。
• $m+n$ が等しいものどうしは、$m$ が小さいものほど前に置く。

この規則で並べると、列は
$$(1,1),(1,2),(2,1),(1,3),(2,2),(3,1),(1,4),\dots$$
となります。先頭から順に $1,2,3,\dots$ と番号をつけると、全単射 $\phi :{\mathbb{Z}}_{>0}\times {\mathbb{Z}}_{>0}\to {\mathbb{Z}}_{>0}$ が得られます。例えば $\phi (1,1)=1$、$\phi (2,1)=3$ です。

このとき、$\phi (4,7)$ を求めてください。

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$）全体の集合

ZFC のもとで考える。$\mathbb{R}$ は実数全体、$\mathbb{N}=\{0,1,2,\dots \}$ は $0$ 以上の整数全体とし、連続体の濃度を $\mathfrak{c}=2^{{\aleph }_0}$ と書く（連続体仮説は仮定しない）。次の集合のうち、濃度がちょうど $\mathfrak{c}$ であるものをすべて選べ。

ア. $\mathbb{R}$ から $\mathbb{R}$ への連続関数全体の集合

イ. $\mathbb{R}$ のルベーグ可測な部分集合全体の集合

ウ. $\mathbb{N}$ から $\mathbb{N}$ への写像全体の集合

エ. 代数的数（有理数係数の $0$ でない多項式の根となる複素数）全体の集合

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

カ. $\mathbb{R}$ から $\mathbb{R}$ への全単射全体の集合

実数全体の集合 $\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$）全体の集合

ZFC 集合論の中で考える。$\mathbb{N}=\{0,1,2,\dots \}$ とし、実数全体 $\mathbb{R}$ の濃度を $\mathfrak{c}=2^{{\aleph }_0}$ とする。次のア〜キの集合のうち、濃度が $2^{\mathfrak{c}}$ であるものをすべて選べ。

ア: $\mathbb{R}$ から $\mathbb{R}$ への連続関数全体の集合

イ: $\mathbb{R}$ から $\mathbb{R}$ への関数全体の集合

ウ: $\mathbb{R}$ の可算部分集合（有限集合を含む）全体の集合

エ: $\mathbb{R}$ のルベーグ可測集合全体の集合

オ: $\mathbb{R}$ のボレル集合全体の集合

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

キ: $\mathbb{N}$ 上の超フィルター全体の集合

ZFC（選択公理を含む）の中で考え、$\mathfrak{c}=2^{{\aleph }_0}$ とおく。実数全体を $\mathbb{R}$、有理数全体を $\mathbb{Q}$、$0$ 以上の整数全体を $\mathbb{N}$ とする。集合が可算であるとは、有限または $\mathbb{N}$ と全単射をもつことをいう。

関数 $f:\mathbb{R}\to \mathbb{R}$ が単調非減少であるとは、すべての実数 $x,y$ について $x<y\Rightarrow f(x)\le f(y)$ が成り立つことをいう。単調非減少な関数 $f:\mathbb{R}\to \mathbb{R}$ 全体の集合を $\mathcal{M}$ とする。$\mathcal{M}$ の濃度が $\mathfrak{c}$ であることを証明せよ。

ただし、次の事実は証明なしに用いてよい。
- $|\mathbb{R}|=|{\mathbb{R}}^2|=\mathfrak{c}$、$|\mathbb{Q}|={\aleph }_0$ であり、$\mathbb{Q}$ は $\mathbb{R}$ で稠密である。
- 基数の演算法則 $({\kappa }^{\lambda }{)}^{\mu }={\kappa }^{\lambda \cdot \mu }$ と ${\aleph }_0\cdot {\aleph }_0={\aleph }_0$。
- ベルンシュタインの定理（$|X|\le |Y|$ かつ $|Y|\le |X|$ なら $|X|=|Y|$）。
- 実数の連続性（上に有界な空でない部分集合は上限をもち、下に有界な空でない部分集合は下限をもつ）。

$\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}}$ であるものの個数を求めよ。

実数全体の集合 $\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$ が有限個であるもの全体の集合

選択公理を含む ZFC で考える。$\mathfrak{c}=2^{{\aleph }_0}$ を連続体の濃度とし、$\mathbb{N}=\{0,1,2,\dots \}$ とする。次の集合のうち、濃度が $2^{\mathfrak{c}}$ に等しいものをすべて選べ。

ア．$\mathbb{R}$ から $\mathbb{R}$ への連続関数全体の集合

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

ウ．$\mathbb{R}$ の部分集合のうち、ルベーグ可測なもの全体の集合

エ．$\mathbb{R}$ のボレル集合全体の集合

オ．$\mathbb{N}$ 上の超フィルター（ultrafilter）全体の集合

カ．複素数体 $\mathbb{C}$ の体としての自己同型全体の集合

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

ク．$\mathbb{N}$ から $\mathbb{N}$ への全単射全体の集合

ケ．$\mathbb{R}$ の可算無限部分集合全体の集合

選択公理を含む集合論 ZFC の中で考える。$\mathbb{R}$ を実数全体の集合、$\mathbb{N}=\{0,1,2,\dots \}$（$0$ を含む）とし、$\mathfrak{c}=2^{{\aleph }_0}$ を連続体の濃度とする。次のア〜クの集合のうち、濃度が $2^{\mathfrak{c}}$ であるものをすべて選べ。

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

イ　ルベーグ可測な $\mathbb{R}$ の部分集合全体の集合

ウ　単調非減少な関数 $f:\mathbb{R}\to \mathbb{R}$（$x\leqq y\Rightarrow f(x)\leqq f(y)$）全体の集合

エ　すべての $x,y\in \mathbb{R}$ に対して $f(x+y)=f(x)+f(y)$ を満たす関数 $f:\mathbb{R}\to \mathbb{R}$ 全体の集合

オ　$\mathbb{R}$ の可算な部分集合（有限集合を含む）全体の集合

カ　全単射 $\sigma :\mathbb{N}\to \mathbb{N}$ 全体の集合

キ　濃度がちょうど $\mathfrak{c}$ である $\mathbb{R}$ の部分集合全体の集合

ク　$\mathbb{R}$ の（通常の位相に関する）閉集合全体の集合

ZFC（選択公理を含む集合論）で考える。$\mathbb{R}$ を実数全体、$\mathbb{N}=\{0,1,2,\dots \}$ とし、$\mathfrak{c}=2^{{\aleph }_0}$ を $\mathbb{R}$ の濃度とする。次の集合ア〜コのうち、濃度がちょうど $\mathfrak{c}$ であることが ZFC で証明できるものをすべて選べ（連続体仮説などの追加の仮定は用いない）。

ア．連続関数 $f:\mathbb{R}\to \mathbb{R}$ 全体の集合

イ．$\mathbb{R}$ のルベーグ可測な部分集合全体の集合

ウ．$\mathbb{R}$ のボレル集合全体の集合

エ．$\mathbb{N}$ 上の超フィルター（単項のものも含む）全体の集合

オ．加法的な関数、すなわちすべての $x,y\in \mathbb{R}$ で $f(x+y)=f(x)+f(y)$ を満たす関数 $f:\mathbb{R}\to \mathbb{R}$ 全体の集合

カ．単調非減少な関数 $f:\mathbb{R}\to \mathbb{R}$ 全体の集合

キ．実数列 $(a_n{)}_{n\in \mathbb{N}}$ 全体の集合 ${\mathbb{R}}^{\mathbb{N}}$

ク．体 $\mathbb{R}$ の自己同型写像全体の集合

ケ．$\mathbb{R}$ の可算無限部分集合全体の集合

コ．代数的数（有理数係数の $0$ でない多項式の根となる複素数）全体の集合