構成可能宇宙(constructible universe)とは、空集合から始め、各段階ですでにある集合の上で論理式により定義できる部分集合だけを加えることを超限回くり返して得られるクラス $L=\bigcup_\alpha L_\alpha$ である。Gödel が導入した。$L$ は ZF の最小の内部モデルで、その中では「すべての集合は構成可能」という公理 $V=L$ が成り立つ。$V=L$ からは $L$ 全体の定義可能な整列順序と、凝縮の議論による一般連続体仮説が従うので、ZF が無矛盾なら ZFC と一般連続体仮説も無矛盾である。
構成可能宇宙(constructible universe)とは、空集合から始めて、各段階で「すでにある集合の上で論理式によって定義できる部分集合」だけを加えることを超限回くり返して得られるクラス $L=\bigcup_{\alpha}L_\alpha$ である。Gödel が導入した。累積階層 $V_\alpha$ が各段階で部分集合をすべて加えるのに対し、$L_\alpha$ は定義できるものだけを加える。
$L$ は ZF の 内部モデル であり、しかも最小のものである。さらに $L$ の中では「すべての集合は構成可能である」という文 $V=L$ が成り立ち、$V=L$ からは選択公理と一般連続体仮説($2^\kappa=\kappa^+$)が導かれる。ここから、ZF が無矛盾なら ZFC に一般連続体仮説を加えた体系も無矛盾であることが分かる。
内部モデルの一般の定義と、$L$ の各段階が推移的で $L_\alpha\cap\mathrm{Ord}=\alpha$ を満たすことは 内部モデル で扱った。この記事は $L$ そのものの性質、すなわち $L$ が ZF を満たすこと、$V=L$ が $L$ で成り立つこと、$L$ での選択公理と一般連続体仮説の証明を扱う。
集合 $X$ と、集合論の論理式 $\varphi(x,y_1,\dots,y_n)$、$X$ の元 $a_1,\dots,a_n$ について、$\{x\in X\mid(X,\in)\models\varphi(x,a_1,\dots,a_n)\}$ を、$X$ の上で母数 $a_1,\dots,a_n$ から定義できる部分集合という。
集合 $X$ に対し、$X$ の上で(有限個の母数から)定義できる部分集合の全体を $\operatorname{Def}(X)$ と書く。順序数についての超限再帰で
$$
L_0:=\emptyset,\qquad L_{\alpha+1}:=\operatorname{Def}(L_\alpha),\qquad L_\lambda:=\bigcup_{\alpha<\lambda}L_\alpha\quad(\lambda\text{ は極限順序数})
$$
と定め、$L:=\bigcup_{\alpha\in\mathrm{Ord}}L_\alpha$ を構成可能宇宙、その元を構成可能集合という。列 $(L_\alpha)$ を構成可能階層という。$x\in L$ について、$x\in L_{\beta+1}$ となる最小の $\beta$ を $x$ の $L$ 階数といい $\rho(x)$ と書く。「すべての集合は構成可能である」、すなわち $\forall x\,\exists\alpha\,(x\in L_\alpha)$ を構成可能性公理といい、$V=L$ と書く。
論理式を自然数で符号化し、集合 $X$ 上の充足関係を再帰で定めれば、$\operatorname{Def}(X)$ は ZF の中で $X$ の関数として定義できる(Kun80 Ch. V §1、Ch. VI Definition 1.1 と Lemma 1.2, p. 165)。$L_\alpha$ を $L(\alpha)$ と書く本もある。
$L_\alpha$ が推移的で $\alpha\leq\beta$ なら $L_\alpha\subseteq L_\beta$ となること、$L_\alpha\cap\mathrm{Ord}=\alpha$ であること、$L_n=V_n$($n\leq\omega$)、$L_{\omega+1}\neq V_{\omega+1}$ であることは 内部モデル で証明した(Kun80 Lemmas VI.1.6, 1.9, 1.13, pp. 167–168)。とくに $L$ は推移的なクラスで、すべての順序数を含む。$\rho(x)=\beta$ なら $x\subseteq L_\beta$ かつ $x\notin L_\beta$ である。
集合 $X$ について次が成り立つ。
(a) $\operatorname{Def}(X)\subseteq\mathcal P(X)$。$X$ が推移的なら $X\subseteq\operatorname{Def}(X)$ であり、$X\in\operatorname{Def}(X)$ である。
(b) $X$ の有限部分集合はすべて $\operatorname{Def}(X)$ に属する。
(c) $X$ が無限で整列可能なら $\lvert\operatorname{Def}(X)\rvert=\lvert X\rvert$。
(a) 前半は定義から明らかである。$a\in X$ なら推移性より $a\subseteq X$ なので、$a=\{x\in X\mid(X,\in)\models x\in y_1\}$($y_1:=a$)と書ける。$X$ 自身は論理式 $x=x$ で定義できる。
(b) $S=\{s_1,\dots,s_k\}\subseteq X$ は、母数 $s_1,\dots,s_k$ と論理式 $x=y_1\lor\cdots\lor x=y_k$ で定義できる($S=\emptyset$ なら $x\neq x$)。
(c) $\operatorname{Def}(X)$ の各元は、論理式の符号 $m\in\omega$ と母数の有限列 $s\in X^{<\omega}$ の組で定まるので、$\omega\times X^{<\omega}$ から $\operatorname{Def}(X)$ への全射がある。$X$ が無限で整列可能なら $\lvert\omega\times X^{<\omega}\rvert=\lvert X\rvert$ であり、整列可能な集合からの全射の像の濃度は元の濃度以下なので $\lvert\operatorname{Def}(X)\rvert\leq\lvert X\rvert$。逆向きは $x\mapsto\{x\}\in\operatorname{Def}(X)$((b))が単射であることから従う。$\square$
選択公理を仮定する。無限の順序数 $\alpha$ について $\lvert L_\alpha\rvert=\lvert\alpha\rvert$ である。
$\alpha\subseteq L_\alpha$ なので $\lvert\alpha\rvert\leq\lvert L_\alpha\rvert$ である。逆を $\alpha\geq\omega$ についての超限帰納法で示す。$L_\omega=V_\omega$ は可算なので $\alpha=\omega$ では成り立つ。$\alpha=\beta+1$($\beta\geq\omega$)なら、lem-cu-def の (c) と帰納法の仮定から $\lvert L_\alpha\rvert=\lvert L_\beta\rvert=\lvert\beta\rvert=\lvert\alpha\rvert$。$\alpha$ が極限順序数なら、$L_\alpha$ は濃度 $\leq\lvert\alpha\rvert$ の集合(有限の $n$ では $L_n$ は有限)の $\lvert\alpha\rvert$ 個の和なので、選択公理により濃度は $\lvert\alpha\rvert\cdot\lvert\alpha\rvert=\lvert\alpha\rvert$ 以下である。$\square$
これは Kun80 Lemma VI.1.14(p. 168)である。
ZF のもとで、ZF の各公理 $\sigma$ について $\sigma^L$ が成り立つ。したがって $L$ は ZF の内部モデルである。
$L$ は推移的なので、外延性と正則性の相対化は成り立つ(内部モデル の系「推移的なクラスで自動的に成り立つ公理」)。$\omega\in L_{\omega+1}$ なので無限公理も成り立つ。推移的なクラスで残りの公理を確かめるには、分出図式を示したうえで、対・和集合・冪集合・置換については「求める集合を部分集合として含む $L$ の元がある」ことを示せば足りる(分出で正確な集合を切り出せるから。Kun80 Ch. IV §2)。
分出。 論理式 $\psi(x,z,\vec v)$ と $z,\vec v\in L$ を固定し、$\{x\in z\mid\psi^L(x,z,\vec v)\}\in L$ を示す。$z,\vec v\in L_\alpha$ となる $\alpha$ をとる。反映原理(集合論) の定理を $Z=L$、$Z(\beta)=L_\beta$ に使う($L_\beta$ は単調で極限で和をとり、和が $L$ なので仮定を満たす)と、$\beta>\alpha$ で $\psi$ が $L_\beta$ と $L$ の間で絶対的になるものがある。このとき
$$
\{x\in z\mid\psi^L(x,z,\vec v)\}=\{x\in L_\beta\mid(L_\beta,\in)\models x\in z\land\psi(x,z,\vec v)\}
$$
($z\subseteq L_\beta$ を推移性で使う)であり、右辺は $\operatorname{Def}(L_\beta)=L_{\beta+1}$ に属する。
大きな集合の存在。 $x,y\in L$ なら $x,y\in L_\alpha$ となる $\alpha$ があり、$L_\alpha\in L_{\alpha+1}$(lem-cu-def の (a))は $\{x,y\}$ と $\bigcup x$ を部分集合として含む(推移性)。冪集合では、$x\in L$ の部分集合で $L$ に属するものの $L$ 階数に $1$ を足したものの上限 $\alpha$ をとれば(置換公理)、$\mathcal P(x)\cap L\subseteq L_\alpha\in L$ である。置換では、$a\in L$ の各元 $u$ に $L$ の中で一意に対応する $w_u\in L$ の $L$ 階数に $1$ を足したものの上限 $\alpha$ をとれば、$\{w_u\mid u\in a\}\subseteq L_\alpha\in L$ である。$\square$
これは Kun80 Theorem VI.2.1(p. 169)の証明である。
$(V=L)^L$ は「$L$ の各元は、$L$ の中で計算した $L_\alpha$ に属する」という主張である。$L$ の各元がある $L_\alpha$ に属することは定義から分かるが、$L$ の中で作った $L_\alpha$ が本物の $L_\alpha$ と同じであることは別に示す必要がある。
冪集合の公理を除いた ZF の有限個の公理の合接 $\psi$ で、次を満たすものがある:$\psi$ を満たす推移的なクラスまたは集合 $M$ と $\alpha\in M$ について、「$\alpha$ は順序数」「$y=L_\alpha$」は $M$ の中で判定しても外で判定しても同じ意味であり、$L_\alpha\in M$、$(L_\alpha)^M=L_\alpha$ である。
ZF のもとで $(V=L)^L$ が成り立つ。したがって $L$ は ZF $+$ $V=L$ の内部モデルであり、ZF が無矛盾なら ZF $+$ $V=L$ も無矛盾である。
$x\in L$ をとり、$x\in L_\alpha$ となる $\alpha$ をとる。$L$ はすべての順序数を含むので $\alpha\in L$ であり、thm-cu-zf により $L$ は ZF を満たすから lem-cu-absolute が使えて $(L_\alpha)^L=L_\alpha$ である。よって $(x\in L_\alpha)^L$、すなわち $(\exists\alpha\,(x\in L_\alpha))^L$ が成り立つ。$x$ は任意なので $(\forall x\,\exists\alpha\,(x\in L_\alpha))^L$ である。
後半:ZF $+$ $V=L$ から矛盾が証明できたとすると、その証明は有限個の公理 $\sigma_1,\dots,\sigma_n$ しか使わない。相対化により ZF から $\sigma_1^L\land\cdots\land\sigma_n^L\to\bot$ が証明でき、前半と thm-cu-zf により ZF から矛盾が出る。$\square$
同じ議論で、ZF $+$ $V=L$ から証明できる文 $\theta$ はすべて $L$ で成り立つ:ZF $\vdash\theta^L$。$V=L$ のもとでの証明がそのまま $L$ についての定理になる。これが $V=L$ を仮定して議論する理由である(Kun80 p. 171)。
(a) $M$ がすべての順序数を含む推移的なクラスで、lem-cu-absolute の $\psi$ を満たすなら、$L^M=L$ であり、とくに $L\subseteq M$。
(b) ZF の有限個の公理と $V=L$ の合接 $\chi$ で、$\chi$ を満たす推移的な集合 $M$ はどれも $M=L_{o(M)}$($o(M):=M\cap\mathrm{Ord}$)となるものがある。
(a) lem-cu-absolute により、$M$ の中で計算した構成可能集合の全体は $\{x\in M\mid\exists\alpha\in M\,(x\in L_\alpha)\}=\bigcup_{\alpha\in\mathrm{Ord}}L_\alpha=L$ である($L_\alpha\in M$ と推移性から $L_\alpha\subseteq M$)。
(b) $\chi$ を、$\psi$、「最大の順序数はない」、$V=L$ の合接とする($\psi$ は ZF の公理の合接で、最大の順序数がないことは ZF の有限個の公理から証明できるので、その公理も $\chi$ に加える)。推移的な集合 $M$ が $\chi$ を満たすとする。$o(M)$ は推移的な順序数の集合なので順序数で、$M$ に最大の順序数がないから極限順序数である。(a) と同じ計算で $L^M=\bigcup_{\alpha< o(M)}L_\alpha=L_{o(M)}$、$(V=L)^M$ から $M=L^M$ である。$\square$
(a) は 内部モデル の定理「構成可能宇宙の基本定理」の (d)(最小性)の証明でもある。(b) は Kun80 Theorems VI.3.5, 3.8, 3.9(pp. 171–172)の形で、一般連続体仮説の証明の鍵になる。
$L$ の元は「どの論理式と、どの母数で定義されたか」という名前をもつ。名前を比べれば $L$ 全体を整列できる。
順序数 $\alpha$ についての再帰で、$L_\alpha$ の整列順序 $\lhd_\alpha$ を定める。$\lhd_0:=\emptyset$ とする。
後続の段階。 $\lhd_\alpha$ が $L_\alpha$ の整列順序だとする。$X\in L_{\alpha+1}$ の表示とは、組 $(n,s,m)$ で、$n\in\omega$、$s\in(L_\alpha)^n$、$m$ は自由変数が $x,y_1,\dots,y_n$ の論理式 $\varphi_m$ の符号で、$X=\{x\in L_\alpha\mid(L_\alpha,\in)\models\varphi_m(x,s(0),\dots,s(n-1))\}$ となるものをいう。表示どうしを、まず $n$ の大小、次に $(L_\alpha)^n$ 上の $\lhd_\alpha$ から決まる辞書式順序、最後に $m$ の大小で比べる。この順序は整列順序なので、各 $X\in L_{\alpha+1}$ には最小の表示 $r(X)$ がある。$X,Y\in L_{\alpha+1}$ について $X\lhd_{\alpha+1}Y$ を次で定める:$X,Y\in L_\alpha$ かつ $X\lhd_\alpha Y$、または $X\in L_\alpha$ かつ $Y\notin L_\alpha$、または $X,Y\notin L_\alpha$ かつ $r(X)$ が $r(Y)$ より小さい。
極限の段階。 $\lambda$ が極限順序数のとき、$x\lhd_\lambda y$ を「$\rho(x)<\rho(y)$、または $\rho(x)=\rho(y)=\beta$ かつ $x\lhd_{\beta+1}y$」で定める。
$L$ 上の関係 $<_L$ も同じ式で定める:$x<_Ly$ $:\Leftrightarrow$ $\rho(x)<\rho(y)$、または $\rho(x)=\rho(y)=\beta$ かつ $x\lhd_{\beta+1}y$。
ZF のもとで次が成り立つ。
(a) 各 $\lhd_\alpha$ は $L_\alpha$ の整列順序で、$\beta<\alpha$ なら $L_\beta$ は $(L_\alpha,\lhd_\alpha)$ の始切片であり、$\lhd_\alpha$ の $L_\beta$ への制限は $\lhd_\beta$ である。$<_L$ は $L$ 上の整列順序で、どの真の始切片も集合である。
(b) $V=L$ なら選択公理が成り立つ。したがって $L$ では選択公理が成り立ち、ZF が無矛盾なら ZFC も無矛盾である。
(a) $\alpha$ についての超限帰納法で示す。後続の段階:表示の順序は、3 つの整列順序 $\omega$、$((L_\alpha)^n,\text{辞書式})$、$\omega$ の辞書式の積を $n$ ごとに並べたものなので整列順序である(有限個の成分の辞書式順序は整列順序で、整列順序の順序和も整列順序)。$X\mapsto r(X)$ は単射なので、$L_{\alpha+1}\setminus L_\alpha$ は $r$ の値で整列され、$\lhd_{\alpha+1}$ はその前に $(L_\alpha,\lhd_\alpha)$ を置いたものだから整列順序で、$L_\alpha$ は始切片である。極限の段階:$x\in L_\lambda$ の $L$ 階数は $\lambda$ 未満で、$\lhd_\lambda$ は $L$ 階数 $\beta<\lambda$ の層 $L_{\beta+1}\setminus L_\beta$ を $\beta$ の順に並べ、各層の中を $\lhd_{\beta+1}$ で並べたものである。帰納法の仮定から各層は整列されているので $\lhd_\lambda$ は整列順序で、$L_\beta$($\beta<\lambda$)は $L$ 階数 $<\beta$ の元の全体だから始切片である。制限についての主張も同じ記述から従う。$<_L$ も同じく層ごとに並べた順序であり、$x$ より小さい元は $L_{\rho(x)+1}$ に含まれるので集合である。
(b) $V=L$ とし、集合 $x$ をとる。$x\in L_\alpha$ となる $\alpha$ をとると、推移性から $x\subseteq L_\alpha$ であり、$\lhd_\alpha$ の制限が $x$ を整列する。すべての集合が整列可能なので選択公理が成り立つ(整列定理)。この証明は ZF $+$ $V=L$ で行えるので、thm-cu-vl の後の注意により $L$ で選択公理が成り立つ。無矛盾性は thm-cu-vl の後半と同じ議論で従う。$\square$
これは Kun80 Definitions VI.4.1, 4.3 と Lemmas VI.4.2, 4.4(pp. 173–174)を、表示の比べ方を少し変えて書いたものである。$V=L$ のもとでは、$L$ 全体の整列順序 $<_L$ が論理式で定義できる。選択公理だけでなく、整列順序を具体的に指定できることが、$V=L$ のもとでの多くの構成(ダイヤモンド原理 の列や Suslin木 など)で使われる。
鍵は「$\omega$ の部分集合はすべて可算な段階までに構成される」という性質である。証明では、部分集合 $A$ を含む小さな初等部分構造をとり、それを推移的な集合に潰すと、ある $L_\gamma$ になる。
$V=L$ を仮定する。無限の順序数 $\alpha$ について $\mathcal P(L_\alpha)\subseteq L_{\lvert\alpha\rvert^+}$ である。とくに無限の基数 $\kappa$ について $\mathcal P(\kappa)\subseteq L_{\kappa^+}$。
thm-cu-ac により選択公理が使える。thm-cu-minimal の (b) の $\chi$ をとる。$\chi$ は ZF の公理と $V=L$ の合接なので、仮定のもとで $V$ で真である。$A\subseteq L_\alpha$ をとり、$X:=L_\alpha\cup\{A\}$ とおく。$L_\alpha$ は推移的で $A\subseteq L_\alpha$ なので $X$ は推移的であり、lem-cu-card より $\lvert X\rvert=\lvert\alpha\rvert$ である。
Löwenheim–Skolemの定理 の論法($\chi$ の部分論理式について Skolem 関数で閉じた部分集合をとる)と Mostowskiの崩壊補題 を組み合わせると、推移的な集合 $M$ で、$X\subseteq M$、$\lvert M\rvert\leq\lvert X\rvert$、かつ $\chi^M\leftrightarrow\chi$ を満たすものがとれる(Kun80 Theorem IV.7.8 と Corollary IV.7.10, pp. 139–140。崩壊は $X$ の元を動かさないので $X\subseteq M$ が保たれる)。$\chi$ は真なので $\chi^M$ が成り立ち、thm-cu-minimal の (b) により $M=L_{o(M)}$ である。$o(M)\subseteq M$ なので $\lvert o(M)\rvert\leq\lvert M\rvert\leq\lvert\alpha\rvert$、したがって $o(M)<\lvert\alpha\rvert^+$ である。よって $A\in M=L_{o(M)}\subseteq L_{\lvert\alpha\rvert^+}$。
後半:$L_\kappa\cap\mathrm{Ord}=\kappa$ なので $\kappa\subseteq L_\kappa$ であり、$\mathcal P(\kappa)\subseteq\mathcal P(L_\kappa)\subseteq L_{\kappa^+}$。$\square$
これは Kun80 Theorem VI.4.6(p. 175)である。初等部分構造を潰したものが再び構成可能階層の段階になる、というこの種の性質を凝縮(condensation)という。
ZF のもとで、$V=L$ から選択公理と一般連続体仮説(無限の基数 $\kappa$ について $2^\kappa=\kappa^+$)が従う。したがって $L$ は ZFC と一般連続体仮説を満たし、ZF が無矛盾なら ZFC $+$ 一般連続体仮説も無矛盾である。
選択公理は thm-cu-ac の (b) である。thm-cu-condensation と lem-cu-card から $2^\kappa=\lvert\mathcal P(\kappa)\rvert\leq\lvert L_{\kappa^+}\rvert=\kappa^+$、Cantor の定理から $2^\kappa\geq\kappa^+$ である。この証明は ZF $+$ $V=L$ の中で行えるので、thm-cu-vl の後の注意により $L$ で成り立ち、無矛盾性も thm-cu-vl の後半と同じ議論で従う。$\square$
Kun80 Corollaries VI.4.7–4.9(p. 175)にあたる。この結果は $V$ で連続体仮説が成り立つことを示すものではない。$V\neq L$ も ZF と無矛盾であり、連続体仮説の否定の無矛盾性には 強制法 が要る(連続体仮説の独立性)。
選択公理を仮定し、$\alpha$ を無限の順序数とする。$\mathcal P(L_\alpha)\not\subseteq L_{\alpha+1}$ である。実際 lem-cu-card より $\lvert L_{\alpha+1}\rvert=\lvert\alpha\rvert$、一方 Cantor の定理より $\lvert\mathcal P(L_\alpha)\rvert=2^{\lvert\alpha\rvert}>\lvert\alpha\rvert$ である。したがって thm-cu-condensation の上限 $L_{\lvert\alpha\rvert^+}$ を、すぐ次の段階 $L_{\alpha+1}$ に縮めることはできない。
$V=L$ のもとでは、$\omega$ の部分集合はすべて $L_{\omega_1}$ に入る(thm-cu-condensation)が、可算な $\alpha$ で $\mathcal P(\omega)\subseteq L_\alpha$ となるものはない。$L_\alpha$ は可算で $\mathcal P(\omega)$ は非可算だからである。
$\omega_1\in N$ となる可算な部分集合 $N\subseteq L_{\omega_2}$ は推移的でない。$\omega_1$ は非可算なので $\omega_1\not\subseteq N$ であり、ある $\xi\in\omega_1$ が $N$ に属さないからである。Löwenheim–Skolemの定理 で得られる可算な初等部分構造は、$\omega_1$ を含めて選べばこの形になる。
したがって prf-cu-condensation で thm-cu-minimal の (b) を使うには、推移性を仮定した (b) を直接当てはめることはできず、Mostowskiの崩壊補題 で推移的な集合に潰す段階が欠かせない。潰した後では $\omega_1$ は可算な順序数に写る。
$V=L$ からは一般連続体仮説のほかにも多くの組合せ原理が従う。たとえば $V=L$ なら ダイヤモンド原理 が成り立ち(Kun80 Theorem VI.5.2, p. 178)、ダイヤモンド原理からは $\omega_1$ 上の Suslin木 の存在が従う(Kun80 Theorem II.7.8, p. 82)。
一方、$L$ に属する実数の全体 $\mathbb R\cap L$ は実数全体の一部にすぎないことがある。$V$ の実数をすべて含む最小の内部モデル $L(\mathbb R)$ は 内部モデル で扱った。また二階算術の部分体系 $\Pi^1_k\text{-}\mathsf{CA}_0$ の最小の $\beta$ モデルは $L_\alpha\cap\mathcal P(\omega)$ の形をしている(二階算術 の注意「β モデルと部分体系の強さ」)。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する