非可算集合

1. $B$ が可算なら、可算集合 の記事の命題「部分集合の可算性と有限性」の 1 により、その部分集合 $A$ も可算となり、仮定に反する。
2. $A\setminus C$ が可算であると仮定する。$A\cap C$ は可算集合 $C$ の部分集合なので可算である（同じ命題）。$A=(A\setminus C)\cup(A\cap C)$ は 2 つの可算集合の和集合なので、可算集合 の記事の定理「可算個の可算集合の和集合」の後半（有限個の和。可算選択公理は要らない）により可算であり、仮定に反する。$\square$

閉区間の列 $I_n=[a_n,b_n]$（$a_n< b_n$）を再帰的に定める。$I_0:=[a,b]$ とする。$I_n$ が定まったとき、$\ell_n:=b_n-a_n>0$ とおき、
$$L_n:=\Bigl[a_n,\ a_n+\frac{\ell_n}{3}\Bigr],\qquad R_n:=\Bigl[b_n-\frac{\ell_n}{3},\ b_n\Bigr]$$
とする。$a_n+\ell_n/3< b_n-\ell_n/3$ なので $L_n$ と $R_n$ は交わらず、$h(n)$ はそのうち高々一方にしか属さない。$h(n)\notin L_n$ なら $I_{n+1}:=L_n$、$h(n)\in L_n$ なら $I_{n+1}:=R_n$ と定める。いずれの場合も $I_{n+1}\subset I_n$、$h(n)\notin I_{n+1}$ であり、$I_{n+1}$ の長さは $\ell_n/3>0$ である。各段の選び方は規則で一意に決まっているので、この再帰に選択公理は要らない。
$I_{n+1}\subset I_n$ より $(a_n)$ は単調非減少、$(b_n)$ は単調非増加である。任意の $n,m$ について $a_n\le b_m$ である。実際、$n\le m$ なら $a_n\le a_m< b_m$、$n>m$ なら $a_n< b_n\le b_m$ である。とくに $\{a_n\mid n\in\mathbb{N}\}$ は空でなく $b_0$ で上に有界なので、上限 $x:=\sup_n a_n$ が存在し、各 $m$ について $b_m$ は上界だから $a_m\le x\le b_m$、すなわち $x\in I_m$ である。
$x\in I_0=[a,b]$ である。任意の $n$ について $x\in I_{n+1}$ かつ $h(n)\notin I_{n+1}$ なので $x\neq h(n)$ である。よって $x$ は $h$ の像に属さない。
したがって $\mathbb{N}$ から $[a,b]$ への全射は存在せず、$[a,b]\neq\emptyset$ なので、rem-uncountable-set-maps により $[a,b]$ は非可算である。$\square$

1. 区間 $J$ が相異なる 2 点 $a< b$ を含めば、区間であることから $[a,b]\subset J$ である。thm-uncountable-set-interval と prop-uncountable-set-superset-difference の 1 により $J$ は非可算である。$\mathbb{R}$ 自身も区間である。
2. $\mathbb{Q}$ は可算なので（可算集合 の記事の例「有理数全体の可算性」）、1 と prop-uncountable-set-superset-difference の 2 により $J\setminus\mathbb{Q}$ は非可算である。
3. まず、実数の代数的数の全体 $K$ が可算であることを、選択公理を使わずに示す。有理数係数の多項式は係数の分母を払えば整数係数になるので、$K$ は $0$ でない整数係数の多項式の実根となる実数の全体である。$\zeta\colon\mathbb{Z}\to\mathbb{N}$ を 可算集合 の記事の例「整数と偶数の番号付け」の 3 の全単射 $\mathbb{N}\to\mathbb{Z}$ の逆写像とし、次数 $d$ の多項式 $p(t)=c_0+c_1t+\dots+c_dt^d$（$c_d\neq0$）に自然数の有限列 $(\zeta(c_0),\dots,\zeta(c_d))$ を対応させ、これを同記事の例「自然数の有限列の全体」の単射 $\Psi$ で $\mathbb{N}\times\mathbb{N}$ に送り、さらに同記事の命題「自然数の対の番号付け」の全単射 $\pi\colon\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ で $\mathbb{N}$ に送る（合成 $\pi\circ\Psi$ は単射である）。こうして $0$ でない整数係数の多項式の全体から $\mathbb{N}$ への単射 $\iota$ が一つの規則で定まる。$x\in K$ に対し、$x$ を根にもつ $0$ でない整数係数の多項式のうち $\iota$ の値が最小のもの $p_x$ をとる（$\mathbb{N}$ の空でない部分集合の最小元なので一意に定まる）。$p_x$ は $0$ でないので実根は有限個であり、それらを小さい順に並べたとき $x$ が $i_x$ 番目（$0$ から数える）であるとする。写像 $x\mapsto(\iota(p_x),i_x)$ は $K$ から $\mathbb{N}\times\mathbb{N}$ への単射である（$\iota(p_x)$ から $p_x$ が、さらに $i_x$ から $x$ が復元できる）。$\mathbb{N}\times\mathbb{N}$ は可算なので（同記事の系「有限個の直積の可算性」）、系「像と単射による可算性の伝播」の 2 により $K$ は可算である。どの段階も規則で一意に決まっているので、選択公理は要らない（同記事の補足では $K$ の可算性を可算個の可算集合の和集合から導いているが、その定理の証明は可算選択公理を使う）。超越数である実数の全体は $\mathbb{R}\setminus K$ なので、prop-uncountable-set-superset-difference の 2 により非可算である。$\square$

各項は $0$ 以上で、$\sum_{k\ge n}2\cdot3^{-(k+1)}=3^{-n}$（等比級数）により部分和は上に有界なので、級数は収束する。
$\varphi(s)\in C$ であること：$n$ を固定し、$a:=(2s_0,\dots,2s_{n-1})\in\{0,2\}^n$ とおく。$\varphi(s)=t_a+r_n$、$r_n:=\sum_{k\ge n}2s_k3^{-(k+1)}$ と書け、$0\le r_n\le\sum_{k\ge n}2\cdot3^{-(k+1)}=3^{-n}$ なので $\varphi(s)\in[t_a,t_a+3^{-n}]\subset C_n$ である。$n$ は任意なので $\varphi(s)\in C$ である。
単射であること：$s\neq s'$ とし、$s_k\neq s'_k$ となる最小の $k$ をとる。$s_k=1$、$s'_k=0$ としてよい。$k$ より前の項は一致するので
$$\varphi(s)-\varphi(s')=2\cdot3^{-(k+1)}+\sum_{j>k}2(s_j-s'_j)3^{-(j+1)}\ge2\cdot3^{-(k+1)}-\sum_{j>k}2\cdot3^{-(j+1)}=2\cdot3^{-(k+1)}-3^{-(k+1)}>0$$
であり、$\varphi(s)\neq\varphi(s')$ である。
$C$ が可算なら、単射 $\varphi\colon\{0,1\}^{\mathbb{N}}\to C$ により $\{0,1\}^{\mathbb{N}}$ も可算となる（可算集合 の記事の系「像と単射による可算性の伝播」の 2）。これは $\{0,1\}^{\mathbb{N}}$ が非可算であること（同記事の系「自然数の冪集合の非可算性」）に反する。$\square$

すべての整数 $m$ について $A_m:=A\cap[m,m+1)$ が有限であると仮定する。$A_m$ の元を小さい順に $x_{m,0}< x_{m,1}<\dots< x_{m,k_m-1}$ と並べる（有限個の実数は大小順に一通りに並ぶ）。$x\in A$ に対し、$m:=\lfloor x\rfloor$（床関数）とすると $x\in A_m$ であり、$x=x_{m,i}$ となる $i$ がただ 1 つ定まる。写像 $x\mapsto(m,i)$ は $A$ から $\mathbb{Z}\times\mathbb{N}$ への単射である（$(m,i)$ から $x=x_{m,i}$ が復元できる）。$\mathbb{Z}\times\mathbb{N}$ は可算なので（可算集合 の記事の系「有限個の直積の可算性」）、同記事の系「像と単射による可算性の伝播」の 2 により $A$ は可算となり、仮定に反する。この議論は各 $A_m$ の並べ方を大小順で一斉に決めているので、選択公理を使わない。
よってある $m$ について $A_m$ は無限集合である。この $m$ を 1 つ固定し、2 等分を繰り返して集積点を作る。閉区間の列 $J_k=[u_k,v_k]$ を再帰的に定める。$J_0:=[m,m+1]$ とする。$J_k$ が定まり $A\cap J_k$ が無限集合であるとき、$c_k:=(u_k+v_k)/2$ とおき、$A\cap[u_k,c_k]$ が無限集合なら $J_{k+1}:=[u_k,c_k]$、そうでなければ $J_{k+1}:=[c_k,v_k]$ と定める。後者の場合、$A\cap J_k=(A\cap[u_k,c_k])\cup(A\cap[c_k,v_k])$ であり、有限集合 2 つの和集合は有限なので、$A\cap[c_k,v_k]$ は無限集合である。したがって、いずれの場合も $J_{k+1}\subset J_k$、$J_{k+1}$ の長さは $2^{-(k+1)}$ であり、$A\cap J_{k+1}$ は無限集合である（$A\cap J_0\supset A_m$ は無限集合）。各段の選び方は規則で一意に決まっているので、この再帰に選択公理は要らない。
thm-uncountable-set-interval の証明と同じく、$(u_k)$ は単調非減少、$(v_k)$ は単調非増加で、任意の $k,l$ について $u_k\le v_l$ であるから、$p:=\sup_k u_k$ が存在し、すべての $k$ について $p\in J_k$ である。$\varepsilon>0$ とし、$2^{-k}<\varepsilon$ となる $k$ をとる。$p\in J_k$ で $J_k$ の長さは $2^{-k}$ なので $J_k\subset(p-\varepsilon,p+\varepsilon)$ である。$A\cap J_k$ は無限集合なので $p$ 以外の元を含み、それは $(p-\varepsilon,p+\varepsilon)$ に属する $p$ と異なる $A$ の元である。よって $p$ は $A$ の集積点である。$\square$