非標準モデル

$\sigma:=\varphi(\bar n_1,\ldots,\bar n_k)$ は文である。$\mathbb N$ では $\bar n^{\mathbb N}=n$ だから、$\mathbb N\models\varphi(n_1,\ldots,n_k)$ は $\sigma\in\mathrm{TA}$ と同値である。$\sigma\in\mathrm{TA}$ なら $M\models\sigma$。$\sigma\notin\mathrm{TA}$ なら $\lnot\sigma\in\mathrm{TA}$ だから $M\not\models\sigma$。よって $\mathbb N\models\varphi(n_1,\ldots,n_k)\iff M\models\sigma$ であり、右辺は $M\models\varphi(e(n_1),\ldots,e(n_k))$ にほかならない。単射性は $\varphi$ を $x_1\neq x_2$ とした場合、演算と順序の保存は $x_1+x_2=x_3$ などの原子式の場合である。$\square$

非標準元がなければ $e$ は全射で、prop-nonstandard-model-embedding により演算と順序を保つ全単射だから同型である。逆に同型 $g\colon\mathbb N\to M$ があれば、$g(0)=0^M$ と $g(n+1)=S^M(g(n))$ から帰納法で $g(n)=\bar n^M$ となる。$g$ は全射なので、すべての元が標準元である。$\square$

新しい定数記号 $c$ を加え、$T:=\mathrm{TA}\cup\{\bar n< c: n\in\mathbb N\}$ とおく。有限部分集合 $T_0\subseteq T$ に現れる $\bar n< c$ の $n$ の最大値を $N$ とし（なければ $N=0$）、$\mathbb N$ で $c$ を $N+1$ と解釈した構造を考える。これは TA を満たし、$T_0$ の $\bar n< c$ もすべて満たす。よって $T$ は有限充足可能であり、コンパクト性定理(一階論理)によりモデル $(M,c^M)$ をもつ。
$M$（$c$ を忘れた構造）は TA のモデルである。各 $n$ について $\bar n^M<^M c^M$ であり、TA の文 $\forall x\,\lnot(x< x)$ から $c^M\neq\bar n^M$ なので、$c^M$ は非標準元である。cor-nonstandard-model-criterion により $M$ は非標準モデルである。
可算なモデルを得るには、初等部分モデルの記事の「下向き Löwenheim–Skolem の定理」を使う。言語 $L_A$ は有限なので、$c^M$ を含む可算な初等部分モデル $N\preccurlyeq M$ がある。$N$ は $M$ と同じ文を満たすので TA のモデルであり、$c^M\in N$ は $N$ でも非標準元である。$\square$

各 $n$ について、文 $\forall x\,\bigl(x<\bar n\to(x=\bar 0\lor x=\bar 1\lor\cdots\lor x=\overline{n-1})\bigr)$（$n=0$ では $\forall x\,\lnot(x<\bar 0)$）は $\mathbb N$ で真なので $M$ でも真である。よって $\bar n^M$ より小さい元は標準元に限る。非標準元 $a$ は $a<\bar n^M$ を満たさず、$a\neq\bar n^M$ なので、線形性から $\bar n^M< a$ である。後半は前半の対偶である（$b=\bar m^M$ のとき $a< b$ なら $a$ は標準元、$a=b$ でも標準元）。$\square$

一致したと仮定する。$0^M=\bar 0^M$ は標準元なので $M\models\varphi(0,\bar b)$。$M\models\varphi(a,\bar b)$ なら $a=\bar n^M$ の形で、$S^M(a)=\overline{n+1}^M$ も標準元だから $M\models\varphi(S(a),\bar b)$。$\varphi$ についての帰納法の公理は $\mathbb N$ で真（通常の数学的帰納法）なので $M$ でも真であり、$M\models\forall x\,\varphi(x,\bar b)$ となる。すると $M$ のすべての元が標準元になり、$M$ が非標準であることに反する。$\square$

成り立たなければ、$\varphi(x,\bar b)$ を満たす元はちょうど標準元全体になり、prop-nonstandard-model-undefinable に反する。$\square$

(1) 反射律と対称律は定義から明らか。$\mathbb N$ で真な文 $\forall a\,\forall b\,\forall c\;\delta(a,c)\leq\delta(a,b)+\delta(b,c)$ と、標準元どうしの和 $\bar n^M+\bar m^M=\overline{n+m}^M$ が標準元であることから、$a\approx b$、$b\approx c$ なら $\delta(a,c)$ は標準元以下であり、prop-nonstandard-model-initial-segment の後半により標準元である。よって推移律が成り立つ。$a\leq x\leq b$ かつ $a\approx b$ なら $\delta(a,x)\leq\delta(a,b)$ から $x\approx a$ となるので、ブロックは区間である。$\delta(0,a)=a$ だから $0$ のブロックは標準元全体で、prop-nonstandard-model-initial-segment によりそれは最小のブロックである。
非標準元 $a$ について、$a\leq b$ かつ $b\approx a$ なら $b=a+\bar n^M$ の形である。$b\leq a$ かつ $b\approx a$ なら $a=b+\bar n^M$ で、$\bar n^M< a$ だから $b=a-\bar n^M$ である。$\mathbb N$ で真な文 $\forall x\,(x+\bar m< x+\bar n)$（$m< n$）により、$k\mapsto a+\bar k^M$（$k\geq0$）、$k\mapsto a-\overline{-k}^M$（$k<0$）は $\mathbb Z$ からブロックへの順序同型である。
(2) ブロックは互いに交わらない区間なので、$a< b$ となる $a\in B$、$b\in B'$ があるとき $B< B'$ と定めると線形順序になる。$a$ を非標準元とする。

• 最大のブロックはない：$\delta(a,a+a)=a$ は非標準元なので、$a+a$ は $a$ より大きい別のブロックにある。
• 非標準元の最小のブロックはない：$\mathbb N$ で真な文 $\forall x\,\exists y\,(y+y=x\lor S(y+y)=x)$ により、$b+b=a$ または $S(b+b)=a$ となる $b$ がある。$b=\bar n^M$ なら $a\leq\overline{2n+1}^M$ となって $a$ が標準元になるので、$b$ は非標準元である。$b\leq a$ で $a-b\geq b$ は非標準元だから、$b$ は $a$ より小さい別の非標準ブロックにある。
• 稠密：$a< b$ が別のブロックにあり、$d:=b-a$ は非標準元とする。$c+c=a+b$ または $S(c+c)=a+b$ となる $c$ をとる。$\mathbb N$ で真な文により $a\leq c\leq b$、$d\leq(c-a)+(c-a)+1$、$d\leq(b-c)+(b-c)$ が成り立つ。$c-a=\bar k^M$ なら $d\leq\overline{2k+1}^M$、$b-c=\bar k^M$ なら $d\leq\overline{2k}^M$ となり、どちらも $d$ が非標準であることに反する。よって $c$ は $a$ とも $b$ とも別のブロックにあり、両者の間にある。

(3) $M$ が可算なら非標準ブロック全体も可算で、(2) により最大元も最小元ももたない可算な稠密線形順序である（$M$ は非標準なので空でない）。Cantor の稠密順序の定理（そのような順序はすべて $(\mathbb Q,<)$ と同型、OLT26 Theorem 25.26）により順序同型 $\beta$ が非標準ブロック全体から $\mathbb Q$ へある。各非標準ブロック $B$ から代表 $a_B$ を選び、$a_B+\bar k^M\mapsto(\beta(B),k)$、$a_B-\bar k^M\mapsto(\beta(B),-k)$ と定め、標準元 $\bar n^M$ は $\mathbb N$ の $n$ へ送る。(1) により各ブロック内でこれは $\mathbb Z$ との順序同型であり、ブロックの間の順序は $\beta$ が保つので、全体として求める順序同型になる。$\square$