Kripke–Platek集合論
概要
Kripke–Platek集合論（Kripke–Platek set theory）とは、外延性・基礎の図式・対・合併と、量化がすべて有界な論理式（$\Delta_0$ 論理式）による分出と収集からなる一階の集合論で、KP と略し、冪集合公理・無限公理・選択公理を含まない。KP の公理を満たす推移的な集合を許容集合といい、遺伝的有限集合の全体 $V_\omega$ が最小の許容集合である。KP では $\Sigma$ 論理式の真理がある集合の中で確かめられるという $\Sigma$ 反映原理が成り立ち、そこから $\Sigma$ 収集と $\Delta_1$ 分出が従う。許容集合は、自然数の上の計算可能性を集合や順序数の上へ広げる一般化された再帰理論の舞台である。
Kripke–Platek 集合論（Kripke–Platek set theory、KP）は、ZFC公理系から冪集合公理・無限公理・選択公理を除き、分出と収集を量化がすべて有界な論理式に限った、所属関係 $\in$ だけを基本記号とする一階の理論である。名前は、これを独立に考えた Kripke と Platek による（Bar75 Ch. I, 2.7, p. 11）。KP の公理を満たす推移的な集合を許容集合といい、自然数の上の計算可能性（計算可能性理論）を順序数や集合の上へ広げる「一般化された再帰理論」の舞台になる。
KP の公理は少ないが、有界な論理式の収集から「存在量化を含む論理式の真理は、ある集合の中で確かめられる」という $\Sigma$ 反映原理が出てくる。この原理から、$\Sigma$ 論理式による収集と、$\Sigma$ でも $\Pi$ でも書ける論理式による分出（$\Delta_1$ 分出）が従う。この記事ではこれらを証明し、遺伝的有限集合の全体が最小の許容集合であること、$V_{\omega+\omega}$ が許容集合でないことを確かめる。
定義
$\Delta_0$ 論理式（有界な論理式）は、$x\in y$、$x=y$ の形の論理式から、論理結合子と有界な量化 $\exists u\in v$、$\forall u\in v$ だけで作った論理式である（内部モデルの定義「有界な論理式」）。KP の公理を述べるにはこの言葉で足りる。
次の (i)〜(vi) を KP の公理とする（Bar75 Ch. I, Definition 2.3, 2.5, pp. 10–11 の、原子を含まない形）。(ii) は任意の論理式 $\varphi$ についての図式、(v)(vi) は $\Delta_0$ 論理式 $\varphi$ についての図式で、$\varphi$ はほかの自由変数（パラメータ）を含んでよい。
(i) 外延性：$\forall a\,\forall b\,\bigl(\forall x\,(x\in a\leftrightarrow x\in b)\to a=b\bigr)$。
(ii) 基礎の図式：$\exists x\,\varphi(x)\to\exists x\,\bigl(\varphi(x)\land\forall y\in x\ \lnot\varphi(y)\bigr)$。
(iii) 対：$\forall a\,\forall b\,\exists c\,(a\in c\land b\in c)$。
(iv) 合併：$\forall a\,\exists b\,\forall y\in a\,\forall x\in y\ (x\in b)$。
(v) $\Delta_0$ 分出：$\forall a\,\exists b\,\forall x\,\bigl(x\in b\leftrightarrow(x\in a\land\varphi(x))\bigr)$。
(vi) $\Delta_0$ 収集：$\forall a\,\Bigl(\forall x\in a\,\exists y\ \varphi(x,y)\to\exists b\,\forall x\in a\,\exists y\in b\ \varphi(x,y)\Bigr)$。
(iii)(iv) は「少なくともこれらを元にもつ集合」の存在だけを述べるが、(v) で余分な元を除けば、$\{a,b\}$ や $\bigcup a$ そのものが得られる。空集合は、任意の集合 $a$ から $\{x\in a\mid x\neq x\}$ として得られる。(ii) を $\varphi$ が $\lnot\psi$ の場合に当てると「$\forall y\in x\,\psi(y)$ から $\psi(x)$ が出るなら $\forall x\,\psi(x)$」という $\in$ についての帰納法と同値である。
KP は冪集合公理と無限公理を含まない。文献によっては無限公理を含めた体系を KP と呼ぶ（Rat06 pp. 58–59）。この記事では含めない形を KP と書き、含める形は「KP＋無限公理」と書く。
$A$ が推移的なら $o(A)=A\cap\mathrm{Ord}$ である。$\alpha$ が許容順序数であることは、$\alpha=o(A)$ となる許容集合 $A$ があることと同値である（Bar75 Ch. II, 1.7–1.8, p. 45 と 5.10, p. 60。この記事では証明しない）。
推移的な集合 $A$ では、外延性と基礎の図式はいつも成り立つ。
理由を開く
外延性は内部モデルの系「推移的なクラスで自動的に成り立つ公理」による。基礎の図式：論理式 $\varphi$ とパラメータ $\vec p\in A$ をとり、$(A,\in)\models\varphi(x,\vec p)$ を満たす $x\in A$ があるとする。そのような $x$ 全体 $X\subseteq A$ は ZFC の分出で集合になり、空でないので、正則性公理により $X$ の元 $x_0$ で $x_0\cap X=\emptyset$ となるものがある。$y\in x_0$ なら推移性から $y\in A$ で、$y\notin X$、すなわち $A$ の中で $\lnot\varphi(y,\vec p)$ である。$\forall y\in x_0$ の量化は $A$ の中でも外でも同じ範囲を動くので、$x_0$ は $A$ の中で (ii) の結論を満たす。
直感
ZFC で集合を作る操作のうち、冪集合は「すでにある集合の部分集合をすべて集める」という、作られる集合を外から一度に指定する操作である。KP はこれを捨て、すでにある集合の元を一つずつ調べて判定できる条件（$\Delta_0$ 論理式）による分出と、「各元に対して何かが見つかるなら、それらをまとめた集合がある」という収集だけを残す。そのため KP の定理は、集合を段階的に作る過程の途中で止めた宇宙（$L_\alpha$ のような小さい推移的集合）でも成り立つことが多い。
$\Sigma$ 論理式と $\Sigma$ 反映原理
$\Delta_0$ 論理式を含み、$\land$、$\lor$、有界な量化 $\exists u\in v$、$\forall u\in v$、有界でない存在量化 $\exists u$ で閉じた最小の論理式の集まりの元を $\Sigma$ 論理式という。$\exists u\,\psi$（$\psi$ は $\Delta_0$）の形のものを $\Sigma_1$ 論理式という。$\Sigma$ 論理式の否定と同値な論理式を $\Pi$ 論理式という（Bar75 Ch. I, Definition 4.1, p. 15）。
$\Sigma$ 論理式 $\varphi$ と、$\varphi$ に現れない変数 $a$ に対し、$\varphi$ の有界でない存在量化 $\exists u$ をすべて $\exists u\in a$ に替えた $\Delta_0$ 論理式を $\varphi^{(a)}$ と書く。
たとえば「$f$ は関数で、定義域は $\omega$、値はすべて $x$ の元」は $\Delta_0$ で、「$x$ は空でない可算集合である」すなわち「$\omega$ から $x$ への全射 $f$ がある」は $\exists f\,(\cdots)$ の形の $\Sigma_1$ 論理式である。
$\Sigma$ 論理式 $\varphi$ について、次は論理的に正しい（どんな構造でも成り立つ）。
(1) $\varphi^{(a)}\land a\subseteq b\to\varphi^{(b)}$。
(2) $\varphi^{(a)}\to\varphi$。
$\varphi$ の組み立てについての帰納法で示す（Bar75 Ch. I, Lemma 4.2, pp. 15–16 と同じ筋）。要になるのは、$\exists u$ の範囲を $a$ から $b$ へ広げても証拠 $u$ が残ることである。
証明を開く
$\varphi$ が $\Delta_0$ なら $\varphi^{(a)}=\varphi^{(b)}=\varphi$ で明らかである。$\land$、$\lor$、有界な量化の場合は、成分について (1)(2) が成り立てば全体についても成り立つ（有界な量化 $\forall u\in v$、$\exists u\in v$ は $a$ によらない）。$\varphi=\exists u\,\psi$ の場合：$\varphi^{(a)}=\exists u\in a\ \psi^{(a)}$ なので、$u\in a$ で $\psi^{(a)}(u)$ を満たすものがある。$a\subseteq b$ なら $u\in b$ であり、帰納法の仮定から $\psi^{(b)}(u)$ なので $\varphi^{(b)}$ が成り立つ。同じく帰納法の仮定から $\psi(u)$ なので $\varphi$ が成り立つ。$\square$
$\Sigma$ 論理式 $\varphi$ と、$\varphi$ に現れない変数 $a$ について、
$$
\mathsf{KP}\vdash\ \varphi\leftrightarrow\exists a\ \varphi^{(a)}.
$$
特に、すべての $\Sigma$ 論理式は KP のもとで $\Sigma_1$ 論理式と同値である。
右から左は lem-kp-persistence の (2) による。左から右を、$\varphi$ の組み立てについての帰納法で、KP の中で示す（Bar75 Ch. I, Theorem 4.3, pp. 16–17）。
- $\varphi$ が $\Delta_0$ の場合：$\varphi^{(a)}=\varphi$ なので、$a$ として任意の集合（たとえば空集合）をとればよい。
- $\varphi=\psi\lor\chi$ の場合：$\psi$ が成り立つなら帰納法の仮定から $\psi^{(a)}$ を満たす $a$ があり、$\varphi^{(a)}$ が成り立つ。$\chi$ の場合も同じ。
- $\varphi=\psi\land\chi$ の場合：帰納法の仮定から $\psi^{(a_1)}$、$\chi^{(a_2)}$ を満たす $a_1,a_2$ がある。対と合併（と $\Delta_0$ 分出）で $a:=a_1\cup a_2$ をとると、lem-kp-persistence の (1) により $\psi^{(a)}$ かつ $\chi^{(a)}$ である。
- $\varphi=\exists u\in v\ \psi(u)$ の場合：$u\in v$ で $\psi(u)$ を満たすものをとり、帰納法の仮定から $\psi^{(a)}(u)$ を満たす $a$ をとれば、$\varphi^{(a)}=\exists u\in v\ \psi^{(a)}(u)$ が成り立つ。
- $\varphi=\exists u\ \psi(u)$ の場合：$\psi(u)$ を満たす $u$ と、$\psi^{(b)}(u)$ を満たす $b$ をとる。$a:=b\cup\{u\}$ とおくと、$u\in a$ で、(1) により $\psi^{(a)}(u)$ なので、$\varphi^{(a)}=\exists u\in a\ \psi^{(a)}(u)$ が成り立つ。
- $\varphi=\forall u\in v\ \psi(u)$ の場合：これが $\Delta_0$ 収集を使う唯一の場合である。仮定から、各 $u\in v$ に対し、帰納法の仮定により $\psi^{(b)}(u)$ を満たす $b$ がある。$\psi^{(b)}(u)$ は $u,b$（とパラメータ）についての $\Delta_0$ 論理式なので、$\Delta_0$ 収集 (vi) により集合 $c$ で
$$ \forall u\in v\ \exists b\in c\ \psi^{(b)}(u) $$
を満たすものがある。$a:=\bigcup c$ とおく。$u\in v$ に対し $b\in c$ を上のようにとると $b\subseteq a$ なので、(1) により $\psi^{(a)}(u)$ である。よって $\varphi^{(a)}=\forall u\in v\ \psi^{(a)}(u)$ が成り立つ。
後半：$\varphi$ は $\exists a\,\varphi^{(a)}$ と同値で、$\varphi^{(a)}$ は $\Delta_0$ なので、これは $\Sigma_1$ 論理式である。$\square$
$\Sigma$ 論理式には有界でない全称量化 $\forall u$ がない。そのため、$\Sigma$ 論理式が成り立つことは、存在を主張された対象をすべて含む一つの集合 $a$ の中で確かめられる。Platek は許容集合の定義に $\Sigma$ 反映原理そのものを使った（Bar75 Ch. I, 2.7, p. 11）。
$\Sigma$ 収集と $\Delta_1$ 分出
$\Sigma$ 論理式 $\varphi(x,y)$ について、KP の中で次が成り立つ。$\forall x\in a\,\exists y\,\varphi(x,y)$ なら、集合 $b$ で
$$
\forall x\in a\ \exists y\in b\ \varphi(x,y)\quad\text{かつ}\quad\forall y\in b\ \exists x\in a\ \varphi(x,y)
$$
を満たすものがある（Bar75 Ch. I, Theorem 4.4, p. 17）。
$\forall x\in a\,\exists y\,\varphi(x,y)$ は $\Sigma$ 論理式なので、thm-kp-sigma-reflection により集合 $c$ で $\forall x\in a\,\exists y\in c\ \varphi^{(c)}(x,y)$ を満たすものがある。$\Delta_0$ 分出で
$$
b:=\{y\in c\mid\exists x\in a\ \varphi^{(c)}(x,y)\}
$$
とおく。$x\in a$ に対し $\varphi^{(c)}(x,y)$ を満たす $y\in c$ は $b$ に属し、lem-kp-persistence の (2) により $\varphi(x,y)$ を満たす。$y\in b$ なら $\varphi^{(c)}(x,y)$、したがって $\varphi(x,y)$ を満たす $x\in a$ がある。$\square$
$\varphi(x)$ を $\Sigma$ 論理式、$\psi(x)$ を $\Pi$ 論理式とする。KP の中で、$\forall x\in a\,\bigl(\varphi(x)\leftrightarrow\psi(x)\bigr)$ なら、集合 $\{x\in a\mid\varphi(x)\}$ が存在する（Bar75 Ch. I, Theorem 4.5, p. 17）。
$\lnot\psi$ と同値な $\Sigma$ 論理式 $\chi$ をとる。各 $x\in a$ について、$\psi(x)$ なら仮定から $\varphi(x)$、そうでなければ $\chi(x)$ なので、$\forall x\in a\,\bigl(\varphi(x)\lor\chi(x)\bigr)$ が成り立つ。これは $\Sigma$ 論理式なので、thm-kp-sigma-reflection により集合 $c$ で $\forall x\in a\,\bigl(\varphi^{(c)}(x)\lor\chi^{(c)}(x)\bigr)$ を満たすものがある。$\Delta_0$ 分出で $b:=\{x\in a\mid\varphi^{(c)}(x)\}$ とおく。
$x\in b$ なら、lem-kp-persistence の (2) により $\varphi(x)$ である。逆に $x\in a$ で $\varphi(x)$ なら、仮定から $\psi(x)$、したがって $\lnot\chi(x)$ であり、(2) の対偶から $\lnot\chi^{(c)}(x)$ となる。$c$ の選び方から $\varphi^{(c)}(x)$ なので $x\in b$ である。よって $b=\{x\in a\mid\varphi(x)\}$ である。$\square$
KP の分出は $\Delta_0$ 分出であり、上の系で広がるのは $\Delta_1$ 分出（$\Sigma$ でも $\Pi$ でも書ける条件による分出）までである。$\Sigma_1$ 論理式による分出（$\Sigma_1$ 分出）を公理として加えた体系も研究されるが、この記事では扱わない。
$\Sigma$ 反映原理からは、さらに次が従う（いずれもこの記事では証明しない）。$\Sigma$ 論理式 $\varphi(x,y)$ が $a$ 上で関数を定めるなら、その関数は集合である（$\Sigma$ 置換。Bar75 Ch. I, Theorem 4.6, pp. 17–18）。$\Sigma$ で定義された操作 $G$ から、$F(y)=G\bigl(y,\{\langle z,F(z)\rangle\mid z\in\mathrm{TC}(y)\}\bigr)$ を満たす $\Sigma$ の操作 $F$ を $\in$ についての再帰で定義できる（$\Sigma$ 再帰。Bar75 Ch. I, Theorem 6.4, p. 26。$\mathrm{TC}(y)$ は $y$ の推移閉包）。集合の階数、順序数の加法・乗法、構成可能階層 $\alpha\mapsto L_\alpha$ はこの形で定義される（同 p. 29 の表）。
許容集合の例
最小の許容集合
$V_\omega$ を、累積階層の段階 $V_0=\emptyset$、$V_{n+1}=\mathcal P(V_n)$ の和 $\bigcup_{n\in\omega}V_n$ とする（ZFC公理系の節「集合の中で公理を確かめる」）。その元を遺伝的有限集合という。$V_\omega$ の元はちょうど $V_\omega$ の有限部分集合である（ZFC公理系の定理「遺伝的有限集合の宇宙 $V_\omega$」の証明の (1)(2)）。
$V_\omega$ は許容集合で、$o(V_\omega)=\omega$ である。さらに、任意の許容集合 $A$ について $V_\omega\subseteq A$ である（Bar75 Ch. II, Theorem 2.1, Corollary 2.2, p. 47）。特に $\omega$ は許容順序数である。
$V_\omega$ が許容集合であること。 $V_\omega$ は推移的なので、(iii)〜(vi) を確かめればよい。各公理の結論に現れる集合が $V_\omega$ の有限部分集合であることを示せば、それは $V_\omega$ の元であり、公理の結論は $\Delta_0$ 論理式なので内部モデルの補題「有界な論理式の絶対性」により $V_\omega$ の中でも成り立つ。
- 対：$\{a,b\}$ は有限部分集合である。
- 合併：$a\in V_\omega$ の元は有限集合で、$\bigcup a$ は有限個の有限集合の和なので有限であり、推移性から $V_\omega$ の部分集合である。
- $\Delta_0$ 分出：$\{x\in a\mid\varphi(x)\}$ は有限集合 $a$ の部分集合である。ここで、$x,a$ とパラメータが $V_\omega$ の元なら $\varphi^{V_\omega}(x)$ と $\varphi(x)$ は同値なので、$V_\omega$ の中で分出した集合と外で分出した集合は一致する。
- $\Delta_0$ 収集：$a\in V_\omega$ と $\Delta_0$ 論理式 $\varphi$ について、各 $x\in a$ に対し $\varphi(x,y)$ を満たす $y\in V_\omega$ があるとする。$a$ は有限なので、元を $x_1,\dots,x_k$ と並べ、それぞれに $y_i\in V_\omega$ を一つずつ選ぶ（有限個の選択で、選択公理は要らない）。$b:=\{y_1,\dots,y_k\}$ は有限部分集合なので $V_\omega$ の元で、$\forall x\in a\,\exists y\in b\ \varphi(x,y)$ を満たす。
$V_\omega$ に属する順序数はちょうど自然数なので、$o(V_\omega)=\omega$ である。
最小性。 $A$ を許容集合とする。まず $\emptyset\in A$：$A$ の元 $a$ を一つとり、$\Delta_0$ 分出で $e:=\{x\in a\mid x\neq x\}\in A$ をとると、$A$ の中で $e$ は元をもたず、$A$ は推移的なので $e$ は実際に空集合である。次に、$x\in V_\omega$ についての $\in$ に関する帰納法で $x\in A$ を示す。$x$ の元がすべて $A$ に属するとする。$x$ は有限なので、元の個数 $k$ についての帰納法で示せばよい。$k=0$ なら $x=\emptyset\in A$。$x=x'\cup\{y\}$（$x'$ は $k-1$ 個の元をもち、$y\in A$）で $x'\in A$ とする。対の公理で $\{y,y\}$ を含む集合をとり、$\Delta_0$ 分出で $\{y\}\in A$ を得る。同様に $\{x',\{y\}\}\in A$、合併の公理と $\Delta_0$ 分出で $x'\cup\{y\}\in A$ を得る。「$z=\{y\}$」「$z=\{u,v\}$」「$z=u\cup v$」は $\Delta_0$ 論理式なので、$A$ の中で作った集合は実際にこれらの集合である。$\square$
$V_\omega$ の上では、$\Sigma_1$ 論理式で定義される自然数の集合は、ちょうど計算可能枚挙可能な集合である（Bar75 Ch. II, Theorem 2.3, p. 47。この記事では証明しない）。許容集合の理論は、この対応を大きな集合へ広げることから始まった。
許容集合でない例
$V_{\omega+\omega}$ は、KP の公理のうち $\Delta_0$ 収集 (vi) 以外をすべて満たし、$\Delta_0$ 収集のある例を満たさない。
$\lambda=\omega+\omega$ とおく。$V_\lambda$ は推移的なので外延性と基礎の図式を満たす。ZFC公理系の定理「$V_{\omega+\omega}$ は置換を満たさない」の前半により、$V_\lambda$ は対・合併と（任意の論理式による）分出の公理を満たすので、(iii)(iv)(v) も満たす。
$\Delta_0$ 収集が成り立たないこと。パラメータ $\omega\in V_\lambda$ をもつ論理式 $\varphi(n,g)$ を「$g$ は関数で定義域は $n\cup\{n\}$、$g(\emptyset)=\omega$、各 $k\in n$ について $g(k\cup\{k\})=g(k)\cup\{g(k)\}$」とする。これは $\Delta_0$ 論理式で書ける。$n\in\omega$ に対し $\varphi(n,g)$ を満たす $g$ はちょうど一つで、$k\leq n$ で $g(k)=\omega+k$ である（$k$ についての帰納法）。この $g$ は $V_\lambda$ の元どうしの有限個の順序対からなるので $V_\lambda$ に属する。
詳細
$\omega+k\in V_{\omega+k+1}$ なので、$g$ の順序対 $\langle k,\omega+k\rangle=\{\{k\},\{k,\omega+k\}\}$ は $V_{\omega+n+3}$ に属し、$g\subseteq V_{\omega+n+3}$ より $g\in V_{\omega+n+4}\subseteq V_\lambda$ である。
$\Delta_0$ 収集が $V_\lambda$ で成り立つと仮定すると、$b\in V_\lambda$ で、各 $n\in\omega$ に対し $\varphi(n,g)$ を満たす $g\in b$ をもつものがある。$b\in V_\lambda$ なので $b\in V_{\omega+m}$ となる $m\in\omega$ がある。$V_{\omega+m}$ は推移的なので、$n=m$ に対する $g\in b$ と、その順序対 $\langle m,\omega+m\rangle\in g$、その元 $\{m,\omega+m\}$、さらに $\omega+m$ がすべて $V_{\omega+m}$ に属する。ところが $V_{\omega+m}$ に属する順序数は $\omega+m$ より小さいものだけである（ZFC公理系の節「集合の中で公理を確かめる」）。これは矛盾である。$\square$
ここで集合 $\{\omega+n\mid n\in\omega\}$ を作れないことが、$V_{\omega+\omega}$ が置換図式を満たさないことの理由でもあった。KP は冪集合も無限公理も含まないが、収集を残しているので、この現象は起こらない。
そのほかの許容集合
次の例はこの記事では証明しない。
- 無限基数 $\kappa$ に対し、推移閉包の濃度が $\kappa$ 未満の集合全体 $H(\kappa)$ は許容集合である（選択公理を使う）。特に、無限基数はすべて許容順序数である（Bar75 Ch. II, Theorem 3.1, p. 52、Corollary 3.4, p. 53）。
- 純粋な推移的集合 $a$ に対し、$a$ を元にもつ許容集合すべての共通部分は許容集合で、ある許容順序数 $\alpha$ について、$a$ から始めた構成可能階層の段階 $L(a,\alpha)$ に等しい。さらに $a\in L_\alpha$ なら $L(a,\alpha)=L_\alpha$ である（Bar75 Ch. II, Theorem 5.11, Corollary 5.12, p. 60）。$a=\omega$ のとき、この $\alpha$ は $\omega$ より大きい最小の許容順序数で、$\omega\in L_\alpha$ なので共通部分は $L_\alpha$ である。計算可能な整列順序の順序型にならない最小の順序数を $\omega_1^{\mathrm{CK}}$（Church–Kleene の順序数）と書くと、この $\alpha$ は $\omega_1^{\mathrm{CK}}$ に等しい（この記事では証明しない）。Bar75 p. 60 は自然数の構造の上の最小の許容集合の順序数が $\omega_1^{\mathrm{CK}}$ であることを述べ、証明を後の章に回している。
$H(\omega_1)$（推移閉包が可算な集合全体）は $\omega$ を含む許容集合だが、冪集合公理を満たさない。したがって KP＋無限公理から冪集合公理は証明できない（ZFC が無矛盾なら）。理由を開く
$\omega$ の部分集合はすべて可算なので $H(\omega_1)$ に属する。$H(\omega_1)$ の中で冪集合公理が成り立つなら、$p\in H(\omega_1)$ で $\omega$ の部分集合をすべて元にもつものがあり、$p\supseteq\mathcal P(\omega)$ は非可算となって $p\in H(\omega_1)$ に反する。
反例の表
対・合併・$\Delta_0$ 収集のどれか一つを外すと、それを満たさない推移的な集合がある（外延性と基礎の図式は推移的な集合でいつも成り立つ）。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 対 (iii) | $V_1=\{\emptyset\}$ | $\{\emptyset,\emptyset\}$ を元にもつ集合があること |
| 合併 (iv) | 空集合から対をとる操作だけで作った集合の全体 $P$ | 元を 3 個以上もつ集合 $\bigcup a$ を含む集合があること |
| $\Delta_0$ 収集 (vi) | $V_{\omega+\omega}$（prop-kp-v-omega-omega） | 各 $n$ に対する $\omega+n$ をまとめて含む集合があること |
各行の反例は、外した公理以外の KP の公理をすべて満たす。
1 行目と 2 行目の確かめ
どちらの集合も推移的なので、外延性と基礎の図式は成り立つ。
1 行目：$V_1$ の元は $\emptyset$ だけなので、合併・$\Delta_0$ 分出・$\Delta_0$ 収集は $a=\emptyset$ について確かめればよく、どれも $b=\emptyset$ で満たされる。対は $a=b=\emptyset$ のとき、$\emptyset$ を元にもつ $c\in V_1$ が必要だが、$V_1$ の唯一の元 $\emptyset$ は元をもたない。
2 行目：$P_0=\{\emptyset\}$、$P_{n+1}=P_n\cup\bigl\{\{x,y\}\mid x,y\in P_n\bigr\}$、$P=\bigcup_nP_n$ とおく。$P$ は推移的で、$P$ の元は元を高々 2 個しかもたない。対は $x,y\in P_n$ なら $\{x,y\}\in P_{n+1}$ による。$\Delta_0$ 分出：$a\in P$ の部分集合は $\emptyset$、$\{x\}=\{x,x\}$、$\{x,y\}$（$x,y\in a\subseteq P$）のいずれかで $P$ に属する。$\Delta_0$ 収集：$a$ の元（高々 2 個）それぞれに $y\in P$ を一つずつ選び、それらの対（または $\emptyset$）を $b$ とすればよい。合併：$0=\emptyset$、$1=\{0\}$ とし、$a=\bigl\{\{0,1\},\{1,\{1\}\}\bigr\}\in P$ をとる。$\bigcup a=\{0,1,\{1\}\}$ は相異なる 3 個の元をもつので、これを含む $b\in P$ はない。
強さと位置づけ
- KP は ZFC の部分体系である：外延性・対・合併は ZFC の公理であり、$\Delta_0$ 分出は分出図式の例、基礎の図式は ZFC の中で正則性公理を推移閉包の分出した部分集合に当てて示せ、$\Delta_0$ 収集は ZFC で置換図式から示せる（Shu18 p. 6 は ZF のほかの公理から収集が証明できることを述べる）。
- KP＋無限公理の証明論的順序数は Bachmann–Howard 順序数とよばれる可算順序数である（Rat06 p. 61。この記事では証明しない）。
- 直観主義論理の上の集合論 CZF も、分出を $\Delta_0$ 論理式に限り、冪集合公理をもたない。収集は任意の論理式について強い形で認め、冪集合の代わりに弱い公理を置く（構成的集合論）。
注意
- 基礎の図式 (ii) は任意の論理式について立てる。KP の中では、一般の論理式の真理を集合の中で確かめることはできないが、$\in$ についての帰納法は任意の論理式について使える。
- 許容集合の定義では推移的であることを要求する。推移的でないモデルでは $\Delta_0$ 論理式の意味が外と食い違いうる。
- KP は無限公理を含まないので、$\omega$ が集合として存在することは KP の定理ではない（$V_\omega$ が許容集合であることによる）。
関連項目
- 前提: ZFC公理系, 内部モデル, 推移的集合
- 比較: Zermelo集合論, NBG集合論, 構成的集合論, New Foundations
- 発展: 計算可能性理論, 証明論, 順序数
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
