Skolemのパラドックス

同義語:スコーレムのパラドックスSkolem's paradoxSkolem paradox

概要

Skolemのパラドックス(Skolem's paradox)とは、集合論 ZFC は自然数全体の冪集合が非可算であることを証明するのに、下向き Löwenheim–Skolem の定理により可算なモデルをもちうる、という一見した矛盾のことである。矛盾は生じない。モデルの中で「非可算」とは、自然数からの全射がモデルの元として存在しないことであり、外から見て元を数え上げる全射はあってもモデルに入っていないからである。可算な初等部分モデルを Mostowski 崩壊すると、ZFC の中だけで、冪集合や最小の非可算順序数が外から見て可算になる可算推移的集合が得られる。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: Löwenheim–Skolemの定理, 初等部分モデル, ZFC, 推移的集合

Skolem のパラドックス(Skolem's paradox)とは、次の 2 つの事実が一見矛盾するように見えることをいう。

  • 集合論の公理系 ZFC は「自然数全体の冪集合 $\mathcal P(\omega)$ は可算でない」ことを証明する。
  • ZFC は可算な言語で書かれているので、モデルをもつなら、下向きの Löwenheim–Skolemの定理 により可算なモデル $M$ ももつ。$M$ の中の「$\mathcal P(\omega)$」は、外から見ると可算個の元しかもたない。
    これは矛盾ではない。「$x$ は可算である」とは「自然数全体から $x$ の上への全射が存在する」ということで、$M$ の中で真であるとは、その全射が $M$ の元として 存在することである。外から見て可算個の元を数え上げる全射はあるが、それは $M$ に入っていない。「可算」は、どの宇宙の中で全射を探すかによって答えが変わる概念である。
    対象$M$ の中での判定外(集合の宇宙 $V$)での事実
    $M$ の中の $\mathcal P(\omega)$可算でない$\mathcal P(\omega)\cap M$ で、可算
    $M$ の中の $\omega_1$最小の非可算順序数可算順序数 $\delta$
    $\omega$ から $\mathcal P(\omega)\cap M$ の上への全射存在しない存在する($M$ の元ではない)
    この記事では、まずこの現象をモデルの仮定なしに ZFC の中で起こす(thm-skp-main)。次に、無矛盾性を仮定した古典的な形を述べ、内と外で何がずれているのかを分析する。「可算」の非絶対性そのものは 絶対性(集合論) の命題「可算性と基数は絶対的でない」でも扱われている。

ZFC の中で起きる Skolem のパラドックス

ZFC 全体の可算なモデルの存在は ZFC で証明できない(節「ZFC 全体のモデルについて」)。そこで、集合の宇宙の中の十分大きな推移的集合 $H(\theta)$ を ZFC の代わりに使う。
基数 $\theta$ について、推移閉包(元、元の元、… の全体)の濃度が $\theta$ 未満の集合全体を $H(\theta)$ と書く(Kun80 Chapter IV, Definition 6.1, p. 130)。$H(\theta)$ は推移的な集合である(初等部分モデル の節「遺伝的に小さい集合の全体と初等部分モデル」)。以下、$\theta>2^{\aleph_0}$ とする。すると $\omega$、$\omega_1$、$\mathcal P(\omega)$ と、$\omega$ のすべての部分集合が $H(\theta)$ に属する(推移閉包の濃度はそれぞれ $\aleph_0$、$\aleph_1$、$2^{\aleph_0}$ 以下で、$\aleph_1\le2^{\aleph_0}<\theta$)。
$\varphi(x)$ を $\in$ だけの論理式とする。$(H(\theta),\in)\models\varphi(a)$ を「$H(\theta)$ の中で $\varphi(a)$」と読む。次の 2 つの論理式を使う。

  • $\mathrm{Cnt}(x)$:「$x=\emptyset$ であるか、$\omega$ から $x$ の上への全射 $f$ が存在する」
  • $\mathrm{Pw}(x)$:「$x$ の元はすべて $\omega$ の部分集合で、$\omega$ の部分集合はすべて $x$ の元である」
    「$f$ は $\omega$ から $x$ の上への全射である」は有界な量化だけで書けるので、推移的集合の中で判定しても本当の意味と一致する(初等部分モデル の補題「有界論理式の絶対性」)。一方 $\mathrm{Cnt}(x)$ は「全射が存在する」という有界でない量化を含み、ここで内と外がずれる。
可算な推移的集合の中の非可算集合

$\theta>2^{\aleph_0}$ を基数とする。可算な推移的集合 $M$ と元 $a,\delta\in M$ で、次をみたすものがある。

  1. $(M,\in)$ と $(H(\theta),\in)$ は同じ文を満たす。とくに、$H(\theta)$ で真な文「$\omega$ の冪集合が存在し、それは可算でない」「最小の非可算順序数が存在する」は $M$ でも真である。
  2. $a=\mathcal P(\omega)\cap M$ であり、$M$ の中で $\mathrm{Pw}(a)$ かつ $\neg\mathrm{Cnt}(a)$ が成り立つ。しかし $a$ は($V$ で)可算な無限集合である。
  3. $\delta$ は可算順序数で、$M$ の中で「$\delta$ は $0$ でない順序数で $\neg\mathrm{Cnt}(\delta)$、$\delta$ の元 $\beta$ はすべて $\mathrm{Cnt}(\beta)$」が成り立つ。

$N\preccurlyeq(H(\theta),\in)$ を可算な初等部分モデルとし、$N$ を推移的集合 $M$ へ崩壊させて、崩壊写像を計算する。
(段 1:初等部分モデル)言語 $\{\in\}$ は可算で $H(\theta)$ は無限なので、初等部分モデル の定理「下向き Löwenheim–Skolem の定理」により可算な $N\preccurlyeq(H(\theta),\in)$ がある。$\theta>\aleph_1$ なので、同記事の命題「可算な初等部分モデルの基本性質」により、$\omega\subseteq N$、$\omega\in N$、$\omega_1\in N$ であり、$\delta:=N\cap\omega_1$ は可算順序数である。同記事の証明の冒頭にあるとおり、$H(\theta)$ の中で $N$ の元をパラメータとする論理式で一意に定まる元は $N$ に属する。$\omega$ の部分集合はすべて $H(\theta)$ に属するので $H(\theta)\models\mathrm{Pw}(\mathcal P(\omega))$ であり、外延性により $\mathrm{Pw}$ をみたす元は $\mathcal P(\omega)$ だけである。よって $\mathcal P(\omega)\in N$ である。同様に、$\omega$ の有限部分集合 $\{n_1,\dots,n_k\}$ は $n_1,\dots,n_k\in N$ をパラメータとして一意に定まるので $N$ に属する。
(段 2:崩壊)$x\ne y$ を $N$ の元とする。$H(\theta)$ は推移的なので $H(\theta)\models\exists z\,\neg(z\in x\leftrightarrow z\in y)$ であり、初等性から $N$ の中にもそのような $z$ がある。よって $N$ 上の $\in$ は外延的で、整礎でもある。Mostowskiの崩壊定理 の 2 により、推移的集合 $M$ と同型 $\pi\colon(N,\in)\to(M,\in)$ があり、$\pi(x)=\{\pi(y)\mid y\in x\cap N\}$ である。$N$ が可算なので $M$ も可算である。
(段 3:主張 1)$N\preccurlyeq H(\theta)$ なので $N$ と $H(\theta)$ は同じ文を満たし、同型は文の真偽を保つ(Kun80 Chapter IV, Lemma 7.9, p. 140)。よって 1 が成り立つ。
(段 4:$\pi$ の計算)$x\in N$ が $x\subseteq N$ をみたし、$x$ のすべての元 $y$ で $\pi(y)=y$ なら、$\pi(x)=\{\pi(y)\mid y\in x\}=x$ である。これと帰納法により、$n\in\omega$ について $\pi(n)=n$($n\subseteq\omega\subseteq N$)、したがって $\pi(\omega)=\omega$ である。$\beta< \delta$ なら $\beta\subseteq\delta\subseteq N$ なので、$\beta$ についての帰納法で $\pi(\beta)=\beta$ である。すると
$$ \pi(\omega_1)=\{\pi(\beta)\mid\beta\in\omega_1\cap N\}=\{\beta\mid\beta< \delta\}=\delta $$
である。$b\in N$ が $b\subseteq\omega$ なら $\pi(b)=\{\pi(n)\mid n\in b\}=b$ なので、
$$ a:=\pi(\mathcal P(\omega))=\{\pi(b)\mid b\in\mathcal P(\omega)\cap N\}=\mathcal P(\omega)\cap N $$
である。逆に $y\in M$ が $y\subseteq\omega$ なら、$y=\pi(b)$($b\in N$)と書け、$M$ は推移的なので $M\models y\subseteq\omega$、$\pi(\omega)=\omega$ と同型から $N\models b\subseteq\omega$、初等性と有界論理式の絶対性から $b\subseteq\omega$ で、$y=b\in N$ である。よって $a=\mathcal P(\omega)\cap M$ である。
(段 5:主張 2)$\omega$ から $\mathcal P(\omega)$ の上への全射は存在しない(Cantorの定理)ので、$H(\theta)$ の中にもなく、$H(\theta)\models\mathrm{Pw}(\mathcal P(\omega))\land\neg\mathrm{Cnt}(\mathcal P(\omega))$ である。初等性で $N$ に移し、$\pi$ で $M$ に移すと、$\pi(\omega)=\omega$ なので $M\models\mathrm{Pw}(a)\land\neg\mathrm{Cnt}(a)$ である。$a\subseteq N$ は可算で、段 1 により $\omega$ の有限部分集合をすべて含むので無限である。
(段 6:主張 3)初等部分モデル の命題「可算な初等部分モデルの基本性質」の証明により、$H(\theta)$ の中で $\omega_1$ は「$0$ でない順序数で $\neg\mathrm{Cnt}(\omega_1)$、その元 $\beta$ はすべて $\mathrm{Cnt}(\beta)$」をみたす($\beta=0$ は $\mathrm{Cnt}$ の定義の $x=\emptyset$ による)。これを $N$ に移し、$\pi(\omega_1)=\delta$ で $M$ に移せば 3 である。$\delta$ が可算であることは段 1 による。$\square$

thm-skp-main の $M$ は、$H(\theta)$ と区別できない小さな写しである。$M$ の住人は $a$ を「$\omega$ の冪集合」と呼び、それが可算でないことを証明できる。実際 $M$ の中には $\omega$ から $a$ の上への全射がない。全射であることは有界論理式で書けて $M$ の中と外で意味が一致するので、$M$ のどの元も本当に $\omega$ から $a$ の上への全射ではない。一方 $a$ は可算な無限集合なので、$V$ には全射 $\omega\to a$ がたくさんある。それらはどれも $M$ に入らない。$\delta$ についても同じで、$\beta< \delta$ ごとの全射 $\omega\to\beta$ は $M$ にあるが($M$ の中で $\mathrm{Cnt}(\beta)$ が成り立ち、有界論理式の絶対性により本当に全射である)、それらを束ねた全射 $\omega\to\delta$ は $M$ にない。

古典的な形:ZFC の可算なモデル

Skolem のパラドックスは、ふつう ZFC のモデルについて述べられる(Zac25 Example 12.34、p. 252)。$\in$ だけの言語の構造 $(M,E)$ と $x\in M$ について、$x$ の外延を $\operatorname{ext}(x):=\{y\in M\mid y\mathrel{E}x\}$ と書く。$E$ は本当の所属関係とは限らず、$\operatorname{ext}(x)$ は外から見た「$x$ の元」の集合である。

可算なモデルの中の冪集合

ZFC が無矛盾なら、ZFC の可算なモデル $(M,E)$ と $a\in M$ で、$M\models\mathrm{Pw}(a)\land\neg\mathrm{Cnt}(a)$ かつ $\operatorname{ext}(a)$ が可算なものがある。

Gödelの完全性定理 により ZFC はモデルをもつ。ZFC のモデルでは $\omega$ にあたる元の外延が $0,1,2,\dots$ にあたる相異なる元を含むので、モデルは無限である。言語は可算なので、Löwenheim–Skolemの定理 の定理「Löwenheim–Skolem の定理」の最後の主張により、ZFC は可算なモデル $(M,E)$ をもつ。ZFC は $\exists x\,\mathrm{Pw}(x)$ と、Cantor の定理 $\forall x\,(\mathrm{Pw}(x)\to\neg\mathrm{Cnt}(x))$ を証明するので、$M\models\mathrm{Pw}(a)\land\neg\mathrm{Cnt}(a)$ となる $a\in M$ がある。$\operatorname{ext}(a)\subseteq M$ は可算である。$\square$

ここで $M$ が「$a$ は可算でない」と判定することの意味を外延で書き直す。$M\models\mathrm{Cnt}(x)$ で $x$ が空でないとき、$M$ の元 $f$ で $M\models$「$f$ は $\omega$ から $x$ の上への全射」となるものがある。$M$ の $\omega$ にあたる元を $\omega^M$ と書き、$n\in\operatorname{ext}(\omega^M)$ に「$M\models(n,y)\in f$ となる $y$」を対応させる写像を $F$ とする。$M$ の中で $f$ は関数で値域が $x$ なので、$F$ は $\operatorname{ext}(\omega^M)$ から $\operatorname{ext}(x)$ の上への写像である。すなわち

  • $M\models\mathrm{Cnt}(x)$ なら、$\operatorname{ext}(\omega^M)$ から $\operatorname{ext}(x)$ の上への写像で、$M$ の元 $f$ が表すものがある。
    逆は成り立たない。外から作った全射が $M$ の元で表されるとは限らないからである。prop-skp-classical の $a$ では、$\operatorname{ext}(a)$ は可算なので外には全射があるが、$M$ の元で表されるものはない。パラドックスに見えたのは、「$M$ の中で可算」を「外で可算」と読み替えたためである。
    $M$ が推移的で $E=\in$ なら $\operatorname{ext}(x)=x$、$\omega^M=\omega$ なので、上の箇条は「$M\models\mathrm{Cnt}(x)$ なら $x$ は本当に可算」となる(絶対性(集合論) の命題「Σ₁ 論理式は上向きに絶対的」と同じ内容)。ずれは片側だけに起き、thm-skp-main はその片側を示している。

非標準な $\omega$:もう 1 つのずれ

$E$ が本当の所属関係でないモデルでは、もう 1 つのずれが起きる。「可算」は「$\omega^M$ から全射がある」という意味なので、$\omega^M$ の外延が本当の自然数全体と違えば、意味が変わる。

$\omega$ の外延が非可算なモデル

ZFC が無矛盾なら、ZFC のモデル $(M,E)$ で $\operatorname{ext}(\omega^M)$ が非可算なものがある。このモデルでは $M\models\mathrm{Cnt}(\omega^M)$ だが、$\operatorname{ext}(\omega^M)$ は可算でない。

言語に定数記号 $c_\alpha$($\alpha<\omega_1$)を加え、ZFC に「$c_\alpha$ は $\omega$ の元である」と「$c_\alpha\ne c_\beta$」($\alpha\ne\beta$)を加えた理論 $T$ を考える。$T$ の有限部分集合に現れる定数は有限個なので、ZFC のモデルでそれらを相異なる自然数として解釈すればモデルになる。コンパクト性定理(一階論理) により $T$ はモデルをもち、その $\in$ の部分を $(M,E)$ とすると、$\operatorname{ext}(\omega^M)$ は相異なる $c_\alpha$ の解釈を $\aleph_1$ 個含む。ZFC は「$\omega$ は可算」(恒等写像が全射)を証明するので $M\models\mathrm{Cnt}(\omega^M)$ である。$\square$

このモデルの「自然数」の大部分は本当の自然数ではない(超準モデル)。可算性は、どの全射が使えるかと、何を $\omega$ とみなすかの両方に依存する。

ZFC 全体のモデルについて

thm-skp-main で ZFC の代わりに $H(\theta)$ を使ったのには理由がある。ZFC が無矛盾なら、ZFC は「ZFC のモデルが存在する」を証明できない。証明できたとすると、モデルで成り立つ文から矛盾は導けないので、ZFC の中で ZFC の無矛盾性が証明でき、Gödelの不完全性定理 の第 2 定理に反するからである。そのため ZFC の中では、ZFC の任意の有限個の公理について可算な推移的モデルを作る形で議論する(Kun80 Chapter IV, Corollary 7.11, pp. 140–141)。すべての公理について一度に同じ議論をすることは ZFC の中では形式化できない(同 p. 141)。thm-skp-main の $M$ は ZFC 全体のモデルとは限らないが、$\mathcal P(\omega)$ と $\omega_1$ についての主張には $H(\theta)$ で足りる。

二階論理との対比

二階論理 の標準意味論では、二階の量化記号はつねに「すべての部分集合」の上を動く。そのため $\mathcal P(\omega)$ を小さく取り替えることができず、下向きの Löwenheim–Skolem の定理が成り立たない(同記事の定理「コンパクト性と Löwenheim–Skolem の定理が成り立たないこと」)。Skolem のパラドックスは、一階論理が「すべての部分集合」を言語の中で固定できないことの表れである。二階の量化の範囲を構造の一部として選ぶ Henkin 意味論では、一階論理と同じく完全性が回復し(同記事の定理「Henkin 意味論の完全性」)、範囲は「すべての部分集合」とは限らなくなる。

反例:条件を外すと成り立たないこと

thm-skp-main の証明は、(i) $N\preccurlyeq H(\theta)$、(ii) $N$ は可算、(iii) $\theta>2^{\aleph_0}$ の 3 つの条件を使った。1 つずつ外す。確かめは表の下にある。

外す条件反例成り立たなくなること
(i) 初等部分モデル$N=\omega\cup\{\omega_1\}$1($M$ と $H(\theta)$ が同じ文を満たす)
(ii) $N$ は可算$N=H(\theta)$2 と 3 の「$a$、$\delta$ は可算」
(iii) $\theta>2^{\aleph_0}$$\theta=\aleph_1$2($M\models\mathrm{Pw}(a)$ となる $a$ の存在)
反例の確かめ

1 行目:$N=\omega\cup\{\omega_1\}$ は可算で $\theta>2^{\aleph_0}$ だが、$H(\theta)$ の初等部分モデルではない。$\omega_1$ の $N$ の中の元は $\omega$ の元だけで、$\omega\notin N$ なので、$N$ 上の $\in$ は外延的である。崩壊は $\pi(n)=n$、$\pi(\omega_1)=\omega$ で、$M=\omega\cup\{\omega\}$ である。$M$ の中で $\omega$ の部分集合は $n\in\omega$ と $\omega$ 自身で、$\omega$ を元にもつ元は $M$ にないので、$M\models\neg\exists x\,\mathrm{Pw}(x)$ である。一方 $H(\theta)\models\mathrm{Pw}(\mathcal P(\omega))$ なので、1 が成り立たない。
2 行目:$N=H(\theta)$ は自分自身の初等部分モデルで、推移的なので崩壊は恒等写像であり、$M=H(\theta)$、$a=\mathcal P(\omega)$、$\delta=\omega_1$ である。どちらも可算でない。
3 行目:$H(\aleph_1)$ の元 $x$ は推移閉包が可算なので $x$ も可算で、全射 $f\colon\omega\to x$($x\ne\emptyset$)は推移閉包が可算なので $H(\aleph_1)$ に属する。$H(\aleph_1)\models\mathrm{Pw}(x)$ とすると、$\omega$ の部分集合はすべて $H(\aleph_1)$ に属するので $\mathcal P(\omega)\subseteq x$ となり、$x$ が可算であることに反する。よって $H(\aleph_1)\models\neg\exists x\,\mathrm{Pw}(x)$ で、$H(\aleph_1)$ と同じ文を満たす $M$ にも $\mathrm{Pw}(a)$ となる $a$ はない。条件 (i)、(ii) をみたす $N$ は下向き Löwenheim–Skolem の定理でとれる。

関連項目

参考文献

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する