絶対性チートシート

はじめに

公理的集合論であるモデルの性質を調べる際，様々な概念の絶対性を多用します．このプリントは，どのような条件下でどんな概念が絶対性を満たすのかをメモした個人的な覚書です．あくまで手軽に使うための覚え書きなので，そこまで踏み込んだ証明などは載せず，寧ろ一覧表のような体裁になる予定です．

基本的な定義と $\Delta_0$ -論理式

以下，特に断りのない限り言語は $\mathcal{L} = \left\{ \epsilon \right\}$ とする．

外延性公理，基礎の公理，内包公理，対の公理および和集合公理に加え，冪集合公理か置換公理のどちらか一方から成る公理系を集合論の基本公理系と呼び，記号 $\mathrm{BST}$ で表す．また，集合論の何らかの公理系 $\Gamma$ に対し， $\Gamma$ から基礎の公理を取り除いたものを $\Gamma^-$ で表す．

集合 $A$ に対し， $\epsilon_{{\mathfrak{A}}} = \left\{\: (a, b) \in A \times A \;\middle|\; a \in b \:\right\}$ により定まる $\mathcal{L}$ -構造を $\epsilon$ -モデルと呼ぶ．
$\epsilon$ -モデル $A$ が推移的モデル $\xLeftrightarrow{\mathrm{def}} A$ は推移的集合である（ $x \in y \in A \rightarrow x \in A$ ）

以下，特に推移的な $\epsilon$ -モデルの絶対性について議論することとする．

論理式 $\varphi \in \mathcal{L}$ ， $\mathfrak{A}, \mathfrak{B}$ を $\mathfrak{A} \subseteq \mathfrak{B}$ なる $\mathcal{L}$ -構造とする．この時，

$\mathfrak{A} \preccurlyeq_\varphi \mathfrak{B} \xLeftrightarrow{\mathrm{def}} A$ 上の任意の付値 $\sigma$ に対して $\mathfrak{A} \models \varphi[\sigma] \Leftrightarrow \mathfrak{B} \models \varphi[\sigma]$
論理式 $\varphi$ が $A$ および $B$ について絶対的 $\xLeftrightarrow{\mathrm{def}} A \preccurlyeq_\varphi B$
論理式 $\varphi$ が $A$ について絶対的 $\xLeftrightarrow{\mathrm{def}} A \preccurlyeq_\varphi V$

ある概念が絶対的であるとは，その概念が部分モデルと拡大モデルで一致するということを意味する．推移的モデルでの絶対性を考える上で基本的な道具として， $\Delta_0$ -論理式の概念は重要である：

次により帰納的に構成される論理式を $\Delta_0$ -論理式と呼ぶ：

任意の原子論理式は $\Delta_0$ 論理式である
$\varphi$ が $\Delta_0$ で $x, y$ を相異なる変数とすると $\forall x \in y\, \varphi$ および $\exists x \in y\, \varphi$ も $\Delta_0$ 論理式
$\Delta_0$ 論理式のブール結合も $\Delta_0$ 論理式である

即ち， $\Delta_0$ 論理式とは，それに現れる量化子が全て有界量化子であるような論理式の事である．

$A \subseteq B, A:$ 推移的， $\varphi: \Delta_0$ 論理式とすると， $A \preccurlyeq_\varphi B$

Proof. 構成による帰納法で明らか．

以下の概念は全て $\Delta_0$ 論理式と論理的に同値であり，従って任意の推移的モデルについて絶対的である：

$x$ は空集合 $\forall z \in x (z \neq z)$
$x \subseteq y$ （ $\Leftrightarrow \forall z \in x (z \in y)$ ）
$x$ は推移的（ $\forall y \in x \forall z \in y (z \in x)$ ）
$x$ は一点集合である（ $\exists y \in x \forall z \in x (y = x)$ ）
$z = \left\{ x, y \right\}$ （ $up(z,x,y) \equiv x \in z \wedge y \in z \wedge \forall w \in z (w = x \vee w = y)$ ）
$z = \left\langle x, y \right\rangle$ （ $op(z,x,y) \equiv \exists v \in z \exists w \in z [up(v,w,z) \wedge up(x,x,v) \wedge up(x,y,w)]$ ）
$z = x \cap y$ （ $z \subseteq x \wedge z \subseteq y \wedge \forall u \in z(u \in x \wedge u \in y)$ ）
$z = x \cup y$
$y = S(x) = x \cup \left\{ x \right\}$
$z = x \times y$ （ $\forall u \in x \forall v \in y \exists w \in z [w = \left\langle u,v \right\rangle] \wedge \forall w \in z \exists u \in x \exists v \in y [w = \left\langle u,v \right\rangle]$ ）
任意の遺伝的有限集合 $x$

$\mathrm{BST}$ における絶対性

以上は任意の推移的モデルで云える．次に挙げる概念は幾らか公理を必要とし，特に $\mathrm{BST}$ の推移的モデルについて絶対的である．その証明には以下の補題が役に立つ：

$k < \omega, \varphi \in \Delta_0$ のとき，和集合公理の下で $\forall x \in \bigcup^k y\,\varphi$ および $\exists x \in \bigcup^k y\,\varphi$ も $\Delta_0$

$\mathrm{BST}$ の下で以下の概念は絶対的である：

$x$ は非順序対
$x$ は順序対
$x$ は関係
$x$ は関数
$x$ は順序数である
$x$ は後続順序数である
$x$ は極限順序数である
$x$ は自然数である
$x = \omega$
$x \subseteq \omega$
$z = \bigcup y$
$y = \mathrm{dom}(x)$
$y = \mathrm{rng}(x)$
$x$ は関数で $\mathrm{dom}(x)$ から $\mathrm{rng}(x)$ への全単射
$x$ は関数で， $y \in \mathrm{dom}(x)$ であり， $x(y) = z$
「 $x$ は有限である」を次で定義した場合：

$\mathrm{Fin}(x) \equiv \exists n, t, f [ n < \omega \wedge f: n \xrightarrow[onto]{1:1} t]$
「 $x$ は遺伝的有限である」を次で定義した場合：ある $n,t,f$ があって $x \subseteq t$ かつ $t$ は推移的集合， $n$ は自然数で $f : n \xrightarrow[\mathrm{1-1}]{\mathrm{onto}} t$

「 $z$ は順序対 $\left\langle x,y \right\rangle$ である」と「 $z$ は順序対である」は違う概念である．前で見た通り， $z = \left\langle x,y \right\rangle$ は集合論の公理を使わずに $\Delta_0$ -論理式で書くことが出来るが，「 $z$ は順序対である」を表す論理式 $\exists x, y \, [z = \left\langle x, y \right\rangle]$ はそのままで $\Delta_0$ -論理式で書けるという訳には行かない．後者は $\mathrm{BST}$ の下で $\exists x, y \in \bigcup^2 z [z = \left\langle x, y \right\rangle]$ という論理式で表されるが，これが $\Delta_0$ 論理式である為には和集合公理が必要である．

一般に $z = f(x,y)$ が絶対的であることと，関数 $f$ が絶対的でることは異なる．関数の絶対性は，個々の $x, y, z$ について偶然 $z = f(x,y)$ が絶対的であるだけではなく，関数 $f$ が定義出来る事も含む．よってある関数が絶対的である為には，それを定義するのに十分な公理が必要になる．

$n$ 項関係 $R$ が算術的 $\xLeftrightarrow{\mathrm{def}} R(x_1, \dots, x_n)$ が成り立つのは $x_1, \dots, x_n \in \mathrm{HF}$ に対してのみであり， $R$ の定義に現れる量化子が全て $\mathrm{HF}$ に相対化されている

次の関数・関係は $\mathrm{BST}$ の推移的モデルについて絶対的である：

二引数関数 $\cup$ および $\cap$
一引数関数 $\bigcap x$ および $\bigcup x$ ．但し $\bigcap \emptyset = \emptyset$ とする．
対関数 $x, y \mapsto \left\{ x,y \right\}$ および順序対関数 $x, y \mapsto \left\langle x, y \right\rangle$
二引数関数 $f, x \mapsto f(x)$ ．ここで $x$ が定義域にない場合は $f(x) = 0$ とする．
$x, y \mapsto x \times y$
任意の算術的関係．
$\varphi$ は $\mathcal{L}$ -論理式
$\mathfrak{A} \models \varphi[\sigma]$

$\mathrm{ZF}-P$ における絶対性

帰納的に定義された関数については，次の定理により $\mathrm{ZF}-P$ で絶対性を確立出来る．

$R, G:$ 定義済みの二項関係， $A:$ クラスとし，特に $R$ は $A$ 上でleft-narrowな整礎関係であるとする．関数 $F$ が次によって帰納的に定義されているとする： $\forall a \in A [F(a) = G(a, F \upharpoonright (a\mathord{\downarrow}))]$ また，簡単の為， $F$ は $A$ の外では $0$ を返すものとする（但し $a \mathord{\downarrow} = \left\{\: b \in A \;\middle|\; b \mathrel{R} a \:\right\}$ ）．

$M$ を $\mathrm{ZF}-P$ の推移的モデルとし，もし $R, A, G$ が共に $M$ で絶対的で $(R \text{は left-narrow})^M$ かつ任意の $a \in M$ に対して $a \mathord{\downarrow} \subseteq A$ が成立するとする．この時， $F^M(a)$ は任意の $a \in M$ で定義され， $F$ は $M$ について絶対的となる．

以上を踏まえて，次が $\mathrm{ZF}-P$ で絶対的となる：

以下は $ZF-P$ の推移的モデルについて絶対的である：

推移閉包を取る一変数関数 $x \mapsto \mathop{\mathrm{trcl}}(x)$
順序数演算 $\alpha + \beta$ および $\alpha \cdot \beta$
「 $R$ は $A$ を整列する」および「 $R$ は $A$ 上整礎」
集合 $\mathrm{HF}$
集合 $\omega$
一変数関数 $x \mapsto [x]^{<\omega}$ および $x \mapsto {}^{<\omega} x$
関数 $x \mapsto \mathop{\mathrm{rank}}\nolimits(x)$
順序数演算 $\alpha^\beta$
定義可能集合を取る関数 $\mathcal{D}(A, P)$ および $\mathcal{D}^+(A), \mathcal{D}^-(A)$
Gödelの構成可能階層を取る関数 $\delta \mapsto L(\delta)$

$\Delta_1$ -論理式と絶対性

$\Delta_0$ -論理式に較べるとそこまで出番はないが， $\Delta_1$ -論理式の概念も絶対性を判定する上で重要である：

以下， $\psi$ を $\Delta_0$ -論理式とする．

論理式 $\varphi$ が $\Pi_1$ -論理式 $\xLeftrightarrow{\mathrm{def}}$ ある変数 $x_1, \dots, x_n\,(0 \leq n < \omega)$ があって $\varphi = \forall x_1 \dots \forall x_n \psi$
論理式 $\varphi$ が $\Sigma_1$ -論理式 $\xLeftrightarrow{\mathrm{def}}$ ある変数 $x_1, \dots, x_n\,(0 \leq n < \omega)$ があって $\varphi = \exists x_0 \dots \exists x_n \psi$
論理式 $\varphi$ が理論 $T$ について $\Delta_1$ -論理式 $\xLeftrightarrow{\mathrm{def}} \Pi_1$ -論理式 $\psi_\Pi$ と $\Sigma_1$ -論理式 $\psi_\Sigma$ があって， $T \vdash \phi \leftrightarrow \psi_\Pi \leftrightarrow \psi_\Sigma$

$\varphi$ が $T$ について $\Delta_1$ -論理式であるとする．この時 $\varphi$ は $T$ に関して絶対的である．

記述集合論における絶対性

論理式の階層 $\boldsymbol{\Pi}^1_n, \boldsymbol{\Sigma}^1_n, \boldsymbol{\Delta}^1_n$ を次で定義する：

算術的論理式 $\varphi(x_1, \dots, x_n, y)$ と $z \in {}^{\omega} {\omega}$ に対し， $\exists a_1 \in {}^{\omega} {\omega}\: \dots \exists a_n\: \varphi(a_1, \dots, a_n, z)$ の形の論理式を $\Sigma^1_1(z)$ -論理式と呼ぶ．
算術的論理式 $\varphi(x_1, \dots, x_n, y)$ と $z \in {}^{\omega} {\omega}$ に対し， $\forall a_1 \in {}^{\omega} {\omega}\: \dots \forall a_n\: \varphi(a_1, \dots, a_n, z)$ の形の論理式を $\Pi^1_1(z)$ -論理式と呼ぶ．
$\Pi^1_n(z)$ -論理式 $\varphi(x_1, \dots, x_n)$ に対し， $\exists a_1 \in {}^{\omega} {\omega}\:\dots \exists a_n \in {}^{\omega} {\omega}\: \varphi(a_1, \dots, a_n)$ の形の論理式を $\Sigma^1_{n+1}(z)$ -論理式と呼ぶ．
$\Sigma^1_n(z)$ -論理式 $\varphi(x_1, \dots, x_n)$ に対し， $\forall a_1 \in {}^{\omega} {\omega}\:\dots \forall a_n \in {}^{\omega} {\omega}\: \varphi(a_1, \dots, a_n)$ の形の論理式を $\Pi^1_{n+1}(z)$ -論理式と呼ぶ．
論理式 $\varphi$ に対し， $\Sigma^1_n(z)$ -論理式 $\varphi_\Sigma$ と $\Pi^1_n(z)$ -論理式 $\varphi_\Delta$ があり， $V_{\omega_1} \models \text{“}\varphi \iff \varphi_\Sigma \iff \varphi_\Delta\text{”}$ を満たす時， $\varphi$ は $\Delta^1_n(z)$ -論理式と呼ばれる．
$\begin{gathered} \Sigma^1_n \mathrel{:=} \Sigma^1_n(\emptyset), \Pi^1_n \mathrel{:=} \Pi^1_n(\emptyset), \Delta^1_n \mathrel{:=} \Delta^1_n(\emptyset)\end{gathered}$
$\begin{gathered}\boldsymbol{\Sigma}^1_n \mathrel{:=} \bigcup_{a \in {}^{\omega} {\omega}} \Sigma^1_n(a), \qquad \boldsymbol{\Pi}^1_n \mathrel{:=} \bigcup_{a \in {}^{\omega} {\omega}} \Pi^1_n(a), \qquad \boldsymbol{\Delta}^1_n \mathrel{:=} \boldsymbol{\Pi}^1_n \cap \boldsymbol{\Sigma}^1_n.\end{gathered}$

以下の議論には，次の概念が役に立つ：

$T$ が $\alpha_1 \times \dots \times \alpha_n$ 上の木 $\xLeftrightarrow{\mathrm{def}} T \subseteq \bigcup_n ({}^{n} {\alpha}_1 \times \dots \times {}^{n} {\alpha_n})$ かつ $(s_1, \dots, s_n) \in T \implies (s_1 \upharpoonright k, \dots, s_n \upharpoonright k) \in T$ .
$T$ が $\alpha_1 \times \dots \times \alpha_n$ 上の木の時， $\begin{align*} \phantom{} [T] &\mathrel{:=} \left\{\: (x_1, \dots, x_n) \in {}^{\omega} {\alpha_1} \times \dots \times {}^{\omega} {\alpha_n} \;\middle|\; \forall k < \omega \: (x_1 \upharpoonright k, \dots, x_n \upharpoonright k) \in T \:\right\},\\[0em] p_\ell[T] &\mathrel{:=} \left\{\: (x_1, \dots, x_\ell) \;\middle|\; \exists x_{\ell+1}\dots \exists x_{n}\: (x_1, \dots, x_{\ell}, x_{\ell+1}, \dots, x_n) \in [T] \:\right\}. \end{align*}$

次は同値：

$A$ : $\Sigma^1_1(z)$
$A = p[T]$ を満たす $\omega\times\omega$ 上の木 $T \in L[z]$ が存在する．

$\boldsymbol{\Sigma}^1_1$ -概念は任意の推移的モデルについて絶対．従って $\boldsymbol{\Delta}^1_1$ と $\boldsymbol{\Pi}^1_1$ もそう．

Proof. $M$ をc.t.m.とし， $A \in M$ を $\boldsymbol{\Sigma}^1_1$ -概念とする．すると，上の定理から $A = p[T]$ となるような $\omega \times \omega$ 上の木 $T$ がとれるので，各 $x \in {}^{\omega} {\omega}$ に対し $T_x \mathrel{:=} \left\{\: s \in {}^{<\omega} {\omega} \;\middle|\; (x \upharpoonright \mathop{\mathrm{lh}}(s), s) \in T \:\right\}$ とおく．この時，明らかに $(T_x, \supsetneq): \text{ill-founded} \iff x \in p[T] = A$ .

よって， $x \in M$ , $N \supseteq M$ とすると， $\begin{align*} (x \in A)^{M} &\iff (T_x: \text{ill-founded})^M\\[0em] &\iff (T_x: \text{ill-founded})^N &\quad& (\because \text{定理}6)\\[0em] &\iff (x \in A)^N. \end{align*}$

特に， $\boldsymbol{\Sigma}^1_2$ -性の証拠となる木は可算であるから，上の補題は次のように推移的モデル以外にも一般化出来る．

$A$ を $\boldsymbol{\Sigma}^1_1$ -集合， $T$ を $p[T] = A$ を満たす $\omega \times \omega$ 上の木とする． $H(\omega) \subseteq M$ を満たす可算 $\mathord{\in}$ -モデル $M$ について， $A, T \in M$ なら論理式「 $z \in A$ 」は $M$ に対し絶対．従って $\boldsymbol{\Pi}^1_1$ -概念や $\boldsymbol{\Delta}^1_1$ -概念も絶対．

この系は，特に $M$ が $H(\theta)$ の可算初等部分モデル（やその生成拡大）の時に有用である．

Proof. $\mathop{\mathrm{mos}} = \mathop{\mathrm{mos}}_{(M, \mathord{\in})}$ を $(M, \mathord{\in})$ の決定するMostwski崩壊としよう． $\bar{M} \mathrel{:=} \mathop{\mathrm{mos}}[M]$ とおき，実数 $z \in M$ を取る．この時， $z, T, T_z \subseteq H(\theta) \subseteq M$ なので，Mostwski崩壊の性質から $\mathop{\mathrm{mos}}(z) = z, \mathop{\mathrm{mos}}(T) = T, \mathop{\mathrm{mos}}(T_z) = T_z$ が成り立つ事に注意すれば， $\begin{align*} M \models z \in A & \iff M \models (T_z, \supset) : \text{ill-founded}\\[0em] &\iff \bar{M} \models (\mathop{\mathrm{mos}}(T_z), \supset): \text{ill-founded}\\[0em] &\iff \bar{M} \models (T_z, \supset): \text{ill-founded} & \quad& (\mathop{\mathrm{mos}}(T_z) = T_z)\\[0em] &\iff (T_z, \supset): \text{ill-founded} & & (\text{Mostwski絶対性})\\[0em] &\iff z \in A. \end{align*}$ よって示せた．

射影階層における絶対性の結果は，適切な仮定の下でもう一段だけ登ることが出来る．それには再び木を用いた議論を行う．

$A \in \boldsymbol{\Pi}^1_1$ なら， $A = p[T]$ を満たす $\omega \times \omega_1$ 上の木 $T$ が取れる．

Proof. $A = {}^{\omega} {\omega} \setminus p[S]$ を満たす $\omega \times \omega$ 上の木 $S$ を取る．この時， $x \in A \iff (S_x, \supsetneq): \text{well-founded}$ となる事に注意する．特に $|S_x| \leq \aleph_0$ なので， $S_x$ が整礎木の時，その対応するランク関数の値域は $\omega_1$ で十分である．なので， $(x, h) \in [T]$ なら $h$ が $S_x$ 上の（広い意味での）ランク関数となるように $\omega \times \omega_1$ 上の木 $T$ を定めたい．

それには，全単射 $e: \omega \stackrel{\sim}{\to} {}^{<\omega} {\omega}$ で $n < \mathop{\mathrm{lh}}(s) \rightarrow e^{-1}(s \upharpoonright n) < e^{-1}(s)$ を満たすものを一つ固定して，次のように $T$ を定めれば良い： $(s, h) \in T \xLeftrightarrow{\mathrm{def}} \begin{cases} h: \mathop{\mathrm{lh}}(s) \to \kappa\\[0em] \forall k, \ell < \mathop{\mathrm{lh}}(s)\:[e(k), e(\ell) \in T_s\wedge e(k) \supsetneq e(\ell) \longrightarrow h(k) < h(\ell)]. \end{cases}$

$A \in \boldsymbol{\Sigma}^1_2$ なら， $A = p[T]$ を満たす $\omega \times \omega_1$ 上の木 $T$ が取れる．

Proof. $A = \mathbf{\exists}^{{}^{\omega} {\omega}} p[S]$ を満たすような $\omega \times \omega \times \omega_1$ 上の木 $S$ を前の補題2により取る．この時，次により $T$ を定めれば，これが明らかに求めるものになっている： $T \mathrel{:=} \left\{\: (s, t) \;\middle|\; (s \upharpoonright \lfloor \mathop{\mathrm{lh}}(t)/2 \rfloor, (t)_0, (t)_1) \in S \:\right\}.$ 但し， $s \in {}^{<\omega} {\omega}$ に対して $(s)_0 \mathrel{:=} \left\langle\: s(2i) \; \middle|\; i < \lfloor \mathop{\mathrm{lh}}(s)/2 \rfloor \:\right\rangle,\quad (s)_1 \mathrel{:=} \left\langle\: s(2i+1) \; \middle|\; i < \lfloor \mathop{\mathrm{lh}}(s)/2 \rfloor \:\right\rangle.$

$\omega_1 \in M$ を満たす $\mathrm{ZF}$ の推移的モデルについて， $\boldsymbol{\Sigma}^1_2$ -概念（よって $\boldsymbol{\Delta}^1_2$ および $\boldsymbol{\Pi}^1_2$ 概念も）は絶対．特に，内部モデルに対し $\boldsymbol{\Pi}^1_2$ , $\boldsymbol{\Sigma}^1_2$ , $\boldsymbol{\Delta}^1_2$ -概念は絶対．

Proof. $A$ を $\boldsymbol{\Sigma}^1_2$ -集合とすると，上の補題3から $A = p[T]$ を満たす $\omega \times \omega_1$ 上の木 $T$ が取れる．上と同様の議論によって， $x \in A \iff T_x: \text{ill-founded}$ となる．ここで， $\omega_1 \in M$ は $T$ や $T_x$ の絶対性を保証するのに必要である．

$\omega_1$ は絶対的な概念ではないので，上のShoenfield絶対性は可算推移的モデルに使うことは出来ない． $\in$ -モデルに対する絶対性は、 $H(\omega)$ の $\omega$ を大きく取れば同様に証明出来るが、可算初等部分モデルに対して用いることは出来ない。

参考文献

[1]

新井敏康, 数学基礎論. 岩波書店, 2011.

[2]

K. Kunen, Set theory, vol. 34. College Publications, 2011.

[3]

T. Jech, Set theory: The third millennium edition, revised and expanded, 3rd ed. Springer-Verlag Berlin Heidelberg New York, 2002.

[4]

K. Kunen, The foundations of mathematics, vol. 19. Kings College Publications, 2009.

絶対性チートシート konn-san.com

はじめに

基本的な定義と $\Delta_0$ -論理式

$\mathrm{BST}$ における絶対性

$\mathrm{ZF}-P$ における絶対性

$\Delta_1$ -論理式と絶対性

記述集合論における絶対性

参考文献

Comments

絶対性チートシート konn-san.com

はじめに

基本的な定義とΔ0\Delta_0Δ0​-論理式

BST\mathrm{BST}BST における絶対性

ZF−P\mathrm{ZF}-PZF−P における絶対性

Δ1\Delta_1Δ1​-論理式と絶対性

記述集合論における絶対性

参考文献

Comments

基本的な定義と $\Delta_0$ -論理式

$\mathrm{BST}$ における絶対性

$\mathrm{ZF}-P$ における絶対性

$\Delta_1$ -論理式と絶対性