ZF 集合論上での基数についての基本的性質 (1)

記事の趣旨

ZFC 集合論と ZF 集合論のあいだのもっとも大きな相違点は、まさしく選択公理の存在にある。選択公理は ZF 集合論の視点に立てば、非常に強力な主張として観察される。実際的に我々がしばしば数学を行うにあたって、ZF 集合論上選択公理と同値な命題(Zorn's lemma, 整列可能定理などが有名である)を援用して議論を展開することが多々ある以上、ZFC 集合論に習熟してしまい、逆説的に、選択公理を排除した状況でどの程度までの主張が成立するのかということについて不明になってしまうこともある。そこで ZF 集合論上での基数の基本的性質を調べていきたいと思う。

本記事においては散発的に簡単な結果をいくつか紹介する。

注意

この記事においては、基本的に ZF 公理系を採用する。またこの記事は Loren J. Halbeisen "Combinatorial Set Theory - With a Gentle Introduction to Forcing" の 4 章を大きく参考にしている。

準備

定義 1 (順序数) 集合 $\alpha$ が順序数であるとは、次の性質をみたすことをいう。

$x \in y \in \alpha$ ならば $x \in \alpha$
$x, y \in \alpha$ ならば $x \in y$ または $x = y$ または $y \in x$

定義 2 ( $\mathbb{V}$ -階層) 順序数 $\alpha$ について、 $\mathbb{V}_\alpha$ とは次のように帰納的に定義される集合のことをいう。

$\mathbb{V}_0 = \emptyset$
$\mathbb{V}_{\alpha + 1} = \mathcal{P}(\mathbb{V}_\alpha)$
極限順序数 $\alpha$ について $\mathbb{V}_\alpha = \bigcup_{\beta \lt \alpha} \mathbb{V}_\beta$

定義 3 (基数) 集合 $X$ について $X$ の基数 $|X|$ とは、次で定義される集合のことである。

$Y \in \mathbb{V}_\alpha$ と $X$ との全単射が存在するような最小の $\alpha$ について $\{Y \in \mathbb{V}_\alpha | \exists \mathrm{bijection}\ f \colon X \to Y\}$

このような形で基数を定義することによって、整列不能な集合に関してもその基数を調べることができる。

定義 4 (有限集合) 集合 $X$ が有限集合であるとは、ある $n \in \omega$ について $n \to X$ なる全単射が存在することをいう。

定義 5 (D-有限集合) 集合 $X$ が D-有限であるとは、 $\omega \to X$ なる単射が存在しないことをいう。

有限集合は D-有限集合である。しかし選択公理のない状況では D-有限集合であるからといって有限集合であるとは限らない。

いくつかの基本的関係

以下散発的な主張を紹介する。

定理 6 (Cantor) 基数 $\kappa$ について、 $\kappa \lt 2^\kappa$ が成立する。

証明まず $\kappa \leq 2^\kappa$ を示す。このためには濃度 $\kappa$ の集合 $A$ について $A$ から $\mathcal{P}(A)$ への単射を作ればよい。これは、 $x \in A$ について $\{x\} \subset A$ を充てる対応を考えればよい。

次に $f \colon A \to \mathcal{P}(A)$ なる全射があったとして矛盾を導く。このとき次の集合 $\{x \in A: x \notin f(x)\}$ を $B$ とおく。 $f$ は全射であるため、 $f(a) = B$ なる $a \in A$ が存在する。従って $B$ の取り方より $a \in B$ ならば $a \notin B$ であり、逆に $a \notin B$ ならば $a \in B$ となってしまう。これは矛盾である。従って $\kappa \lt 2^\kappa$ が成り立つ。Q.E.D.

命題 7 $\aleph_0 \leq 2^\kappa$ ならば $2^{\aleph_0} \leq 2^\kappa$ .

証明濃度 $\kappa$ の集合 $A$ をとると、仮定より単射 $f \colon \omega \to \mathcal{P}(A)$ が取れる。このとき、 $A$ の可算無限個の非空な部分集合であって、互いに交わらないものを取れれば、それらを $\{B_i\}_{i \in \omega}$ とおくと $\mathcal{P}(\omega) \to \mathcal{P}(A)$ として $X$ に対して $\bigcup_{i \in X} B_i$ を充てる対応がとれ、これは単射となる。よって以下このような部分集合族を構成することを目標とする。

$v \colon A \to 2^{\aleph_0}$ を次のようにしてとる:

$i \in v(a) \Leftrightarrow a \in f(i)$ .

このとき $2^{\aleph_0}$ 上に次のような関係をいれる:

$g,h \in 2^{\aleph_0}$ について $g \lt h \Leftrightarrow \exists n \in \omega (g(n) \lt h(n) \land \forall k \lt n (g(k) = h(k)))$ .

また $P^0_n$ を $\{v(x)| v(x)(n) = 0\}$ なる集合とする。

ここで、すべての $n \in \omega$ について $P^0_n$ が上で作った関係のもとで整列順序付けられていたとき $P = \bigcup P^0_n$ は整列可能集合である。このとき $\bigcup P^0_n = \mathrm{Range}(v) \setminus \{\mathrm{const}_1\}$ であるため、 $P$ が有限ならば $v$ の像は有限となる。像が $n$ 点集合であったならば $f$ の像は高々 $2^n$ 点集合であるため矛盾する。よって $P$ は無限集合となる。 $P$ は整列可能な無限集合であるため $\{g_i\}_{i \in \omega} \subset P$ なる集合が取れる。このとき $B_i = \{a \in A| v(a) = g_i\}$ とおくと、これは非空な $A$ の部分集合であり、いずれも互いに交わらない。

また、いずれかの $n \in \omega$ について $P^0_n$ が整列順序付けられていないとする。このような $n$ で最小のものを固定しておく。このとき $S_n \subset P^0_n$ であって最小元を持たないものをとる。このとき、 $y := \mathrm{inf} S_n$ とすると $y(i) = 0$ となるような $i \in \omega$ は無限個存在する。ここで、 $v(i) = 1$ なる $n \lt i$ について $S_i = S_{i-1}$ , $v(i) = 0$ なる $n \lt i$ について $S_i = S_{i-1} \cap P^0_i$ とおくと $\{S_i\}_{n \leq i}$ は減少列となる。これは真に減少する無限列を部分列として含む。この部分列を $\{T_j\}_{j \in \omega}$ としてとると、 $B_j = \{a \in A|v(a) \in T_j \setminus T_{j-1}\}$ とすればこれは非空な集合族であり互いに交わらない。よって命題が証明された。Q.E.D.

命題 8 基数 $\kappa$ について $\kappa^2 \leq 2^{2^\kappa}$ が成り立つ。

証明濃度 $\kappa$ の集合 $A$ を任意に取る。このとき $\langle a , b \rangle \in A \times A$ について $\{a, \{a, b\}\} \in \mathcal{P}(\mathcal{P}(A))$ を充てる対応は単射である。Q.E.D.

定義 9 ( $\mathrm{fin}(-)$ ) 基数 $\kappa$ について、 $\mathrm{fin}(\kappa)$ とは濃度 $\kappa$ の集合 $A$ について $A$ の有限部分集合全体の集合 $\mathcal{P}_{\mathrm{fin}}(A)$ の濃度のことをいう。

命題 10 無限基数 $\kappa$ について $2^{\aleph_0} \leq 2^{\mathrm{fin}(\kappa)}$ が成り立つ。

証明 $A$ を濃度 $\kappa$ の集合とする。このとき $X_n = \{x \subset A| |x| = n\}$ とおくと、これらは $\mathcal{P}(\mathcal{P}_{\mathrm{fin}}(A))$ の相異なる元となるため、 $\aleph_0 \leq 2^{\mathrm{fin}(\kappa)}$ が言える。よって命題 7 より $2^{\aleph_0} \leq 2^{\mathrm{fin}(\kappa)}$ が成り立つ。Q.E.D.

系 11 無限基数 $\kappa$ について $2^{2^\kappa}$ は D-無限である。

証明命題 10 と同様の証明により $2^{2^\kappa}$ の相違なる可算無限個の元を取れるため。Q.E.D.

系 12 無限基数 $\kappa$ について $2^{2^{2^\kappa}} + 2^{2^{2^\kappa}} = 2^{2^{2^\kappa}}$ が成り立つ。

証明系 11 より $2^{2^{\kappa}} + 1 = 2^{2^{\kappa}}$ が成り立つ。従って $2^{2^{2^\kappa}} + 2^{2^{2^\kappa}} = 2^{2^{2^\kappa}+1} = 2^{2^{2^\kappa}}$ が成り立つ。Q.E.D.

参考文献

Loren J. Halbeisen, "Combinatorial Set Theory - With a Gentle Introduction to Forcing", 2012.
alg-d, "有限集合・無限集合の定義", http://alg-d.com/math/ac/def_of_finite.html .

空-Q-所為

在の実践

ZF 集合論上での基数についての基本的性質 (1)

記事の趣旨

注意

準備

いくつかの基本的関係

参考文献