Tarski–Vaughtの判定法(Tarski–Vaught test)とは、$L$ 構造 $M$ の部分構造 $N$ が初等部分モデルであることと、$N$ の元をパラメータとする論理式について $M$ で存在が成り立つときはいつも証人を $N$ の中に取れることが同値であるという定理である。条件の真偽はすべて $M$ の中で判定するので、$N$ の中の真偽を知らなくても確かめられる。部分構造であることは仮定しなくてもよく、Skolem 関数で閉じた集合は初等部分モデルになる。下向き Löwenheim–Skolem の定理や集合論の初等部分モデルの構成の基礎である。
Tarski–Vaughtの判定法(Tarski–Vaught test)とは、構造 $M$ の部分構造 $N$ が初等部分モデルであるかどうかを、$M$ の中の真偽だけで判定する基準である。$N$ の元をパラメータとする論理式について、$M$ の中で存在が言えるなら、その証人を $N$ の中から取れる。これが必要十分である。
初等部分モデルの定義は「$N$ の中の真偽」と「$M$ の中の真偽」の一致を要求する。しかし、$N$ を下から組み立てている途中では、$N$ の中の真偽はまだ分からない。判定法の条件には $N$ の中の真偽が現れないので、$M$ だけを見て証人を $N$ に集めていけばよい。下向き Löwenheim–Skolem の定理も、集合論で初等部分モデルを作る議論も、この形で使われる。
この記事では、判定法を証明し、定義可能集合による言い換えと、部分構造であることを仮定しない形を述べる。続いて、証人を動かす例、条件が満たされない例、条件を弱めると成り立たなくなる例を見て、Skolem 関数と $\omega_1$ の中の初等部分モデルに応用する。
同じ 2 人の名前がつく定理や、名前の似た定理があるので、先に区別しておく。
| 名前 | 主張 |
|---|---|
| Tarski–Vaught の判定法(この記事) | 部分構造が初等部分モデルであることは、$M$ の中の証人が $N$ に取れることと同値である |
| Tarski–Vaught の初等鎖定理 | 初等部分モデルの鎖の和は、各項の初等拡大である(初等部分モデル の定理「初等鎖の和」) |
| Łoś–Vaughtの判定法 | 有限のモデルをもたず、ある基数 $\kappa\geq\lvert L\rvert+\aleph_0$ で範疇的な理論は完全である |
3 行目は構造どうしの関係ではなく、理論についての定理である。
$L$ を一階の言語、$M$ を $L$ 構造(台は空でない)とする。論理式は原子論理式から $\lnot,\land,\exists$ で作るものとする。ほかの記号はこれらの略記である。
$N$ が $M$ の部分構造であるとは、$N$ が $M$ の空でない部分集合で、定数の値を含み、関数で閉じていて、関数と関係を $M$ から制限した $L$ 構造であることをいう。$N$ が $M$ の初等部分モデル($N\preccurlyeq M$)であるとは、$N\subseteq M$ が部分構造であり、すべての論理式 $\psi(\bar x)$ と $N$ の元の組 $\bar a$ について
$$
N\models\psi(\bar a)\quad\Longleftrightarrow\quad M\models\psi(\bar a)
$$
が成り立つことをいう。$\psi$ が文のときは「$\bar a$ が空の組」の場合として含まれる。
$N$ を $M$ の部分構造とする。次の 2 つは同値である。
条件 2 の真偽は、どちらも $M$ の中で判定している。ここがこの定理の要点である。TV57(Theorem 1.10, p. 87)が原典である。
1 から 2 を示す。$M\models\exists y\,\varphi(y,\bar a)$ とする。$N\preccurlyeq M$ より $N\models\exists y\,\varphi(y,\bar a)$ なので、ある $b\in N$ で $N\models\varphi(b,\bar a)$ となる。再び $N\preccurlyeq M$ より $M\models\varphi(b,\bar a)$ である。
2 から 1 を示す。論理式 $\psi(\bar x)$ の構成についての帰納法で、$N$ のすべての元の組 $\bar a$ について $N\models\psi(\bar a)\Leftrightarrow M\models\psi(\bar a)$ となることを示す。
$\psi$ が原子論理式の場合。まず項 $t(\bar x)$ の構成についての帰納法で $t^N(\bar a)=t^M(\bar a)$ が分かる。変数と定数では明らかで、$F(t_1,\ldots,t_k)$ では $F^N$ が $F^M$ の制限であることから従う。$N$ の関係は $M$ の関係の制限なので、$t_1=t_2$ と $R(t_1,\ldots,t_k)$ の真偽は $N$ と $M$ で一致する。
$\psi$ が $\lnot\psi_1$ または $\psi_1\land\psi_2$ の場合は、帰納法の仮定からすぐに従う。
$\psi$ が $\exists y\,\varphi(y,\bar x)$ の場合。$N\models\psi(\bar a)$ なら、ある $b\in N$ で $N\models\varphi(b,\bar a)$ となり、帰納法の仮定より $M\models\varphi(b,\bar a)$ なので $M\models\psi(\bar a)$ である。逆に $M\models\psi(\bar a)$ なら、条件 2 より、ある $b\in N$ で $M\models\varphi(b,\bar a)$ となる。帰納法の仮定より $N\models\varphi(b,\bar a)$ なので $N\models\psi(\bar a)$ である。
帰納法はすべての $\bar a$ について同時に回している。$\varphi$ に $b$ を代入した組 $(b,\bar a)$ も $N$ の元の組なので、仮定を使うことができる。
逆向きの証明で条件 2 を使うのは、$\exists$ の場合の後半だけである。前半は部分構造なら無条件に成り立つ。つまり、部分構造では、$\varphi$ の真偽が $N$ と $M$ で一致していても、$\exists y\,\varphi$ の真偽は $N$ から $M$ へ上に伝わるだけで、下に戻る保証がない。この 1 か所を埋めるのが証人である。
条件 2 は、定義可能集合の言葉で書くと意味が見やすくなる。
$N$ を $M$ の部分構造とする。次の 3 つは同値である。
1 と 2 の同値は thm-tarski-vaught-test の言い換えである。$\{b\in M\mid M\models\varphi(b,\bar a)\}$ が空でないことが $M\models\exists y\,\varphi(y,\bar a)$ であり、それが $N$ と交わることが証人の存在だからである。
3 は 2 の対偶を $\lnot\varphi$ に当てたものである。すべての $b\in N$ で $M\models\varphi(b,\bar a)$ ということは、$\lnot\varphi(y,\bar a)$ の定義する集合が $N$ と交わらないということであり、2 より、その集合は空である。逆も同じである。
判定法は、部分構造であることを仮定しなくても使える。証人を集めるだけで、定数と関数の条件は自動的についてくる。
$X$ を $M$ の部分集合とする。すべての論理式 $\varphi(y,\bar x)$ と $X$ の元の組 $\bar a$ について、$M\models\exists y\,\varphi(y,\bar a)$ ならばある $b\in X$ で $M\models\varphi(b,\bar a)$ となるとする。このとき $X$ は $M$ の部分構造の台であり、$X\preccurlyeq M$ である。
$M$ は空でないので $M\models\exists y\,(y=y)$ である。パラメータなしで条件を使うと $X\neq\emptyset$ が分かる。定数記号 $c$ については $M\models\exists y\,(y=c)$ の証人が $X$ に取れるので、$c^M\in X$ である。関数記号 $F$ と $X$ の元の組 $\bar a$ については $M\models\exists y\,(y=F(\bar a))$ の証人が $X$ に取れるので、$F^M(\bar a)\in X$ である。関係を制限すれば $X$ は部分構造になり、thm-tarski-vaught-test が使える。
もう一つ、判定法からすぐに分かる形を挙げておく。
$N\preccurlyeq M$ とする。$M$ の元 $c$ が、$N$ の元をパラメータとする論理式を満たすただ一つの元なら、$c\in N$ である。
$\{c\}$ は $N$ の元をパラメータとして定義される空でない集合なので、prop-tarski-vaught-definable の 2 より $N$ と交わる。
たとえば $(\mathbb N,< )$ の元 $n$ は「ちょうど $n$ 個の元より大きい元」として定義されるので、$(\mathbb N,< )$ の初等部分モデルは自分自身だけである。$(\mathbb R,+,\cdot,0,1)$ では $x\leq y$ が $\exists z\,(x+z\cdot z=y)$ と書ける。実代数的数は、整数係数の多項式の $k$ 番目に小さい実根として定義されるので、$(\mathbb R,+,\cdot,0,1)$ の初等部分モデルは実代数的数をすべて含む。
ただし、定義可能な元を見るだけでは足りないこともある。$(\mathbb Z,+)$ の元 $1$ は、自己同型 $x\mapsto-x$ で動くのでパラメータなしでは定義できないが、初等部分モデル の例「整数の加法群は真の初等部分モデルをもたない」と同じ議論で、$(\mathbb Z,+)$ の初等部分モデルも自分自身だけである($0$ と符号の反転は $+$ で定義できる)。
判定法が役に立つのは、$M$ の証人が $N$ の外にあっても、パラメータを止める自己同型で $N$ の中へ動かせるときである。$\sigma$ が $M$ の自己同型で $\bar a$ を止めるなら、$M\models\varphi(b,\bar a)$ から $M\models\varphi(\sigma(b),\bar a)$ が従う。
$L$ を等号だけの言語とし、$M$ を無限集合、$N$ をその無限部分集合とする。このとき $N\preccurlyeq M$ である。
$M\models\varphi(b,\bar a)$($\bar a$ は $N$ の元)とする。$b\in N$ なら証人は取れている。$b\notin N$ のとき、$N$ は無限なので、$\bar a$ に現れない $c\in N$ が取れる。$b$ と $c$ を入れ替える互換は $M$ の自己同型で、$\bar a$ を止める。よって $M\models\varphi(c,\bar a)$ であり、$c\in N$ が証人である。
$N=\{a_1,\ldots,a_n\}$ が有限だと、この議論は止まる。実際、$M$ が無限なら $M\models\exists y\bigwedge_{i}y\neq a_i$ だが、$N$ に証人はない。
$K$ を体とする。言語 $L$ は $0,+,-$ と、各 $\lambda\in K$ のスカラー倍の 1 変数関数記号からなるものとする。$K$ 上のベクトル空間 $V$ の無限次元の部分空間 $W$ について $W\preccurlyeq V$ である。
$V\models\varphi(b,\bar a)$($\bar a$ は $W$ の元)とし、$U$ を $\bar a$ の張る有限次元の部分空間とする。$b\in U$ なら $b\in W$ である。$b\notin U$ とする。$W$ は無限次元なので $c\in W\setminus U$ が取れる。$U$ の基底に $b$ を加えて $V$ の基底に延ばすことで、$b$ を含む補空間 $C$ で $V=U\oplus C$ となるものが取れる。$c=u+c'$($u\in U$、$c'\in C$)と書くと $c'\neq0$ である。$C$ の 0 でない 2 つのベクトル $b,c'$ に対して $S(b)=c'$ となる線形同型 $S:C\to C$ がある。$U$ の上で恒等写像、$C$ の上で $S$ である写像は $V$ の自己同型で $\bar a$ を止めるので、$V\models\varphi(c',\bar a)$ である。$c'=c-u\in W$ が証人である。
$K$ が有限体のときは、有限次元の部分空間は有限集合なので、無限次元の $V$ の初等部分モデルにならない。「元が少なくとも $m$ 個ある」という文の真偽が食い違うからである。
$(\mathbb Q,< )\preccurlyeq(\mathbb R,< )$ も同じ型の議論で示される。証人を、$\bar a$ を止める区分線形な自己同型で有理数へ動かす。証明は 初等部分モデル の命題「有理数は実数の初等部分モデル(順序の言語)」にある。
判定法は、初等部分モデルでないことを確かめるときにも使える。証人のない論理式を 1 つ挙げればよい。
はじめの 2 つでは $N$ と $M$ は同型である。$x\mapsto 2x$ と $x\mapsto x-1$ が同型を与える。つまり、部分構造が全体と同型であっても初等部分モデルとは限らない。判定法が問題にするのは、$N$ だけを見て分かる性質ではなく、$N$ が $M$ の中にどう置かれているかである。
条件 2 は、すべての論理式について、$N$ のすべての元をパラメータとして要求している。どちらも省けない。
| 弱めた条件 | 反例 | 成り立たなくなる点 |
|---|---|---|
| 量化記号のない $\varphi$ だけで確かめる | $(\mathbb Q,< )\subseteq(\mathbb Q\cup\{\infty\},< )$($\infty$ は最大元) | 文 $\exists y\,\forall z\,\lnot(y < z)$ が $M$ でだけ真である |
| パラメータのない $\varphi(y)$ だけで確かめる | $(\mathbb N,< )\subseteq(\mathbb Z,< )$ | $M\models\exists y\,(y < 0)$ の証人が $N$ にない |
| 別の言語で確かめる | $\mathbb Q\subseteq\mathbb R$(順序の言語で確かめて環の言語で使う) | $y\cdot y=1+1$ の証人が $\mathbb Q$ にない |
| $N$ が $M$ と同型であることで代える | $(2\mathbb Z,+)\subseteq(\mathbb Z,+)$ | $y+y=2$ の証人が $2\mathbb Z$ にない |
1 行目。量化記号のない $\varphi(y,\bar a)$ の真偽は、$y$ と $a_1,\ldots,a_n$ の大小関係だけで決まる。$M$ の証人が $\infty$ なら、すべての $a_i$ より大きい有理数も同じ大小関係にあるので、証人になる。よって量化記号のない論理式については条件 2 が成り立つ。それでも $M$ には最大元があり、$N$ にはないので $N\not\preccurlyeq M$ である。
2 行目。平行移動 $x\mapsto x+k$ は $(\mathbb Z,< )$ の自己同型であり、どの元もどの元へも動かせる。したがって、パラメータなしの論理式の定義する部分集合は空集合か全体であり、空でなければ $\mathbb N$ と交わる。それでも $\mathbb N$ には最小元があり、$\mathbb Z$ にはないので、$N$ と $M$ は初等同値でさえない。
判定法の条件を、関数の形にまとめる。
$M$ の Skolem 関数の族とは、論理式 $\varphi(y,x_1,\ldots,x_n)$ ごとに定めた関数 $F_\varphi:M^n\to M$ であって、すべての $\bar a\in M^n$ について、$M\models\exists y\,\varphi(y,\bar a)$ ならば $M\models\varphi(F_\varphi(\bar a),\bar a)$ となるものをいう。$n=0$ のとき $F_\varphi$ は $M$ の 1 つの元である。
証人のある $\bar a$ では証人を 1 つ選び、証人のない $\bar a$ では値を任意に定めればよいので、Skolem 関数の族は選択公理のもとで存在する。$M$ が整列されていれば、最小の証人を取ることで選択公理なしに定義できる。
Skolem 関数の族のすべての関数で閉じた $M$ の部分集合 $X$ は、部分構造の台であり、$X\preccurlyeq M$ である。
$M\models\exists y\,\varphi(y,\bar a)$($\bar a$ は $X$ の元)なら、$F_\varphi(\bar a)\in X$ が証人である。prop-tarski-vaught-subset の仮定が成り立つ。
$M$ の部分集合 $A$ に、Skolem 関数の値を $\omega$ 回つけ足していくと、$A$ を含み Skolem 関数で閉じた集合ができる。関数の個数は $L$ の論理式の個数だけで、1 回のつけ足しは組の個数だけなので、その濃度は $\max(\lvert A\rvert,\lvert L\rvert,\aleph_0)$ 以下である。これが下向き Löwenheim–Skolem の定理の証明の骨格である(Kun80 Ch. V, Theorem 1.11, p. 156、Dow88 Theorem 1.1, p. 20)。定理の主張と細部は 初等部分モデル の定理「下向き Löwenheim–Skolem の定理」と Löwenheim–Skolemの定理 にある。
$M$ が順序数の上の構造なら、最小の証人が自然に取れる。すると判定法は、順序数 $\delta$ が初等部分モデルかどうかを「$\delta$ が関数で閉じているか」に変える。
$L$ を可算な言語とし、$M$ を台が $\omega_1$ である $L$ 構造とする。このとき
$$
C=\{\delta < \omega_1\mid\delta\neq0,\ \delta\preccurlyeq M\}
$$
は $\omega_1$ の閉非有界な部分集合である。
論理式 $\varphi(y,\bar x)$ と $\omega_1$ の元の組 $\bar a$ について、$M\models\exists y\,\varphi(y,\bar a)$ なら $w(\varphi,\bar a)$ を証人の最小元とし、そうでなければ $w(\varphi,\bar a)=0$ とする。
$\delta\neq0$ について、$\delta\in C$ であることは、すべての $\varphi$ と $\delta$ の元の組 $\bar a$ で $w(\varphi,\bar a) < \delta$ となることと同値である。実際、$\delta\preccurlyeq M$ なら thm-tarski-vaught-test より証人が $\delta$ の中に取れるので、最小の証人も $\delta$ の中にある。証人がなければ $w=0 < \delta$ である。逆は prop-tarski-vaught-subset から従う。
閉であること。$\delta < \omega_1$ が $C\cap\delta$ の上限で $\delta\neq0$ とする。$\delta$ の元の組 $\bar a$ は有限個なので、すべての成分が $\delta_0$ より小さい $\delta_0\in C\cap\delta$ がある。よって $w(\varphi,\bar a) < \delta_0 < \delta$ であり、$\delta\in C$ である。
非有界であること。$\gamma < \omega_1$ とする。$\gamma_0=\gamma+1$ とし、$\gamma_{n+1}$ を $\gamma_n+1$ とすべての $w(\varphi,\bar a)+1$($\bar a$ は $\gamma_n$ の元の組)の上限とする。$L$ が可算なので論理式は可算個であり、$\gamma_n$ も可算なので、これは可算個の可算順序数の上限であり、$\omega_1$ の元である(ここで選択公理を使う)。$\delta=\sup_n\gamma_n$ とすると、$\delta$ の元の組はある $\gamma_n$ に入るので、$w(\varphi,\bar a) < \gamma_{n+1}\leq\delta$ である。よって $\delta\in C$ であり、$\gamma < \delta$ である。
このように作った $\delta$ は $\gamma_n$ の狭義増加列の上限なので、極限順序数である。この命題は、$f:\omega_1\to\omega_1$ で閉じた順序数の全体が非有界であるという事実を含む(閉であることは定義からすぐに分かる)。$M=(\omega_1,< ,f)$ とすれば、$\delta\preccurlyeq M$ のとき $f$ の値を証人として $f(\alpha) < \delta$($\alpha < \delta$)となるからである。同様の議論は、Dow88(Corollary 1.4, p. 21)のように初等部分モデルの鎖で述べることもできる。
$M$ が集合の宇宙 $V$ のような真のクラスのときは、すべての論理式についての充足関係を集合論の中で定義できないので、判定法は有限個の論理式について述べる。部分論理式で閉じた有限の列について、$\exists$ の形のものの証人が小さいクラスに取れることと、列の論理式が 2 つのクラスの間で絶対的であることが同値である(Kun80 Ch. IV, Lemma 7.3, p. 136)。反映原理(集合論) は、この形を累積階層の段に当てて証明される。
$M$ が $H(\theta)$ のような集合なら、thm-tarski-vaught-test がそのまま使える。初等部分モデル の節「遺伝的に小さい集合の全体と初等部分モデル」が、その使い方を述べている。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する