Łoś–Vaughtの判定法

記号のない言語（等号だけ）で、$n\ge2$ について $\sigma_{\ge n}:=\exists x_1\cdots\exists x_n\bigwedge_{1\le i< j\le n}\lnot(x_i=x_j)$（相異なる元が $n$ 個以上ある）とおき、$I_\infty:=\{\sigma_{\ge n}\mid n\ge2\}$ とする。$I_\infty$ のモデルはちょうど無限集合であり、有限のモデルはない。この言語の構造の同型写像は全単射そのものなので、無限基数 $\kappa$ ごとに、濃度 $\kappa$ のモデル（濃度 $\kappa$ の集合）はどの 2 つも同型である。$\lvert L\rvert+\aleph_0=\aleph_0$ なので、thm-lv-main により $I_\infty$ は完全である。したがって、等号だけの言語では、無限集合はどれも同じ文を満たす。

言語 $\{<\}$ で、次の 6 つの文からなる理論を $\mathrm{DLO}$ とする：$\forall x\,\lnot\,x< x$、$\forall x\,\forall y\,\forall z\,(x< y\land y< z\to x< z)$、$\forall x\,\forall y\,(x< y\lor x=y\lor y< x)$、$\forall x\,\exists y\,x< y$、$\forall x\,\exists y\,y< x$、$\forall x\,\forall y\,(x< y\to\exists z\,(x< z\land z< y))$。そのモデルは端点のない稠密な全順序である。

• 有限のモデルをもたない：モデルは空でなく、どの元より大きい元があるので、$a_0< a_1< a_2< \cdots$ と相異なる元を限りなくとれる。
• $\aleph_0$-範疇的である：$(\mathbb Q,<)$ が可算なモデルであり、可算なモデルはすべて $(\mathbb Q,<)$ と同型である（往復論法 の記事の系「可算な稠密順序の一意性と均質性」）。
  言語は可算なので $\kappa=\aleph_0$ で thm-lv-main が使え、$\mathrm{DLO}$ は完全である。cor-lv-equivalent により、$(\mathbb Q,<)$、$(\mathbb R,<)$、$(\mathbb R\setminus\{0\},<)$ はどれも同じ文を満たす。一方、$(\mathbb R,<)$ と $(\mathbb R\setminus\{0\},<)$ は濃度 $2^{\aleph_0}$ のモデルだが同型でなく（カテゴリー性 の記事の例「連続体濃度では範疇的でない」）、$\mathrm{DLO}$ は $2^{\aleph_0}$-範疇的でない。判定法には、範疇性が 1 つの濃度で成り立てば足りる。

環の言語 $\{+,-,\cdot,0,1\}$ で、体の公理と、$n\ge1$ ごとの文 $\forall a_0\cdots\forall a_{n-1}\,\exists x\,(x^n+a_{n-1}x^{n-1}+\cdots+a_0=0)$（$x^k$ は $x$ を $k$ 個掛けた項の略記）を合わせた理論に、標数を定める文を加えたものを $\mathrm{ACF}_p$ とする。$p$ が素数なら文 $1+\cdots+1=0$（$1$ を $p$ 個足す）を、$p=0$ なら $m\ge1$ ごとの文 $\lnot(1+\cdots+1=0)$（$1$ を $m$ 個足す）を加える。そのモデルは標数 $p$ の代数閉体である。

• 有限のモデルをもたない：有限体 $F=\{c_1,\dots,c_q\}$ について、多項式 $f(x):=(x-c_1)\cdots(x-c_q)+1$ は次数 $q\ge1$ で、どの $c\in F$ でも $f(c)=1\ne0$ なので、$F$ に根をもたない。よって有限体は代数閉体でない。
• 非可算な基数 $\kappa$ について $\kappa$-範疇的である：標数が同じで、濃度が同じ非可算な代数閉体は同型である（この記事では証明しない。Mil22 Proposition 9.16 と Remark 9.17、p. 117。素体上の超越次数が同じ代数閉体は同型であり、非可算な代数閉体では超越次数が濃度に等しいことによる）。濃度 $\kappa$ の標数 $p$ の代数閉体があることは、素体（$\mathbb Q$ または $p$ 元体 $\mathbb F_p$）の代数閉包が無限の代数閉体であることに (LS) を当てれば分かる。
  言語は可算なので、非可算な $\kappa$ で thm-lv-main が使え、$\mathrm{ACF}_p$ は完全である。たとえば $\mathbb C$（代数学の基本定理により代数閉体）と、$\mathbb Q$ の代数閉包 $\overline{\mathbb Q}$ はどちらも $\mathrm{ACF}_0$ のモデルなので、環の言語の文で $\mathbb C$ で真なものは $\overline{\mathbb Q}$ でも、標数 $0$ のどの代数閉体でも真である。
  $\mathrm{ACF}_0$ は $\aleph_0$-範疇的ではない。$\overline{\mathbb Q}$ と、有理関数体 $\mathbb Q(t)$ の代数閉包 $K$ はどちらも可算である（可算な体の上の多項式は可算個で、それぞれの根は有限個なので、代数閉包は可算である）。もし体の同型 $h\colon K\to\overline{\mathbb Q}$ があれば、$h$ は $\mathbb Q$ の元を動かさないので、$h(t)$ を根にもつ $0$ でない有理係数の多項式 $P$ について $h(P(t))=P(h(t))=0$ となり、$P(t)=0$ である。これは $t$ が $\mathbb Q$ 上超越的であることに反する。

1 行目：$T_0$ のモデルは空でない集合そのもので、同型は全単射である。よって無限基数 $\kappa$ ごとに $T_0$ は $\kappa$-範疇的で、$\lvert L\rvert+\aleph_0=\aleph_0$ である。しかし文 $\forall x\,\forall y\,(x=y)$ は 1 元の集合で真、2 元の集合で偽なので、$T_0$ は完全でない。有限のモデルが判定法を破っている。
2 行目：言語を $L_1:=\{P\}\cup\{c_r\mid r\in\mathbb R\}$（$P$ は 1 項関係記号、$c_r$ は定数記号）とし、$\sigma:=\exists x\,P(x)$ とおく。$T_1$ を、ex-lv-sets の $I_\infty$ に次の文を加えたものとする。
$$ \sigma\to\lnot(c_r=c_s)\quad(r\ne s),\qquad\lnot\sigma\to c_r=c_0\quad(r\in\mathbb R). $$
$T_1$ のモデルは無限であり、$P$ が空でなければ定数の値は相異なる（濃度は $2^{\aleph_0}$ 以上）、$P$ が空ならすべての定数の値は 1 つの元に一致する。

• 可算なモデルでは $P$ は空でなければならず、すべての $c_r$ の値は 1 つの元 $e$ である。可算なモデル $(A,e)$、$(B,e')$ の間には、$e$ を $e'$ に送る全単射があり（$A\setminus\{e\}$ と $B\setminus\{e'\}$ はともに可算無限）、それは $P$（どちらも空）と定数を保つので同型である。$\mathbb N$ で $P$ を空、すべての $c_r$ を $0$ と解釈したものが可算なモデルなので、$T_1$ は $\aleph_0$-範疇的である。
• $T_1$ は有限のモデルをもたない。
• $\mathbb R$ で $P$ を $\mathbb R$ 全体、$c_r$ を $r$ と解釈したものは $T_1\cup\{\sigma\}$ のモデルで、上の可算なモデルは $T_1\cup\{\lnot\sigma\}$ のモデルである。よって $T_1$ は完全でない。
  $\lvert L_1\rvert=2^{\aleph_0}$ なので、$\kappa=\aleph_0$ は条件 $\kappa\ge\lvert L_1\rvert+\aleph_0$ だけを満たさない。prf-lv-main で言えば、$T_1\cup\{\sigma\}$ の無限モデルから (LS) で可算なモデルを得る段が成り立たない。
  3 行目：$I_\infty$ を言語 $\{P\}$ の文の集合とみる（$P$ についての公理はない）。モデルは無限集合 $A$ と部分集合 $P^A$ の組で、有限のモデルはない。文 $\exists x\,P(x)$ は $P^A=A$ のモデルで真、$P^A=\emptyset$ のモデルで偽なので、完全でない。どの無限基数 $\kappa$ でも、濃度 $\kappa$ の集合 $A$ について $(A,A)$ と $(A,\emptyset)$ は同型でないので、どの $\kappa$ でも範疇的でない。