有限モデル理論

有限部分集合に現れる $\theta_n$ の $n$ の最大値を $N$ とすると、$N$ 元の構造がそのモデルである。全体のモデルは任意の $n$ について $n$ 元以上をもつので無限である。$\square$

段 1（有限充足可能性は半決定可能）． 文 $\sigma$ と $n\ge1$ について、$\sigma$ に現れる記号の、台集合 $\{1,\dots,n\}$ 上の解釈は有限個しかない。各解釈で $\sigma$ が真かどうかは、量化記号を有限集合の上の有限の連言・選言として読めば計算で判定できる。$n=1,2,\dots$ と順に調べ、モデルが見つかれば停止する手順により、有限充足可能な文の全体 $\mathrm{FS}$ は帰納的可算である（帰納的可算集合 の定理「帰納的可算集合の言い換え」の 4）。同型な構造は同じ文を満たすので、$n$ 元のモデルがあれば台集合を $\{1,\dots,n\}$ にとれる。
段 2． 文 $\sigma$ が有限充足可能でないことは、$\lnot\sigma$ が有限妥当であることと同値である。有限妥当な文の全体 $\mathrm{FV}$ が帰納的可算だとすると、$\mathrm{FS}$ の補集合（文の符号でない自然数と、$\lnot\sigma\in\mathrm{FV}$ となる文 $\sigma$ の符号）も帰納的可算になる（帰納的可算集合 の命題「帰納的可算集合の閉包性」）。$\mathrm{FS}$ とその補集合がどちらも帰納的可算なので、$\mathrm{FS}$ は決定可能である（帰納的可算集合 の系「補集合が帰納的可算でない集合」）。これは thm-fmt-trakhtenbrot に反する。
後半は、そのような証明体系があれば $\mathrm{FV}$ が証明できる文の全体に一致して帰納的可算になることから従う。$\square$

$G\in\mathcal G_n$ が $\chi_{k,l}$ を満たさないのは、相異なる頂点の組 $(a_1,\dots,a_k,b_1,\dots,b_l)$ で、条件を満たす $z$ がないものがあるときである。そのような組の候補は $n(n-1)\cdots(n-m+1)\le n^m$ 個ある。
組を 1 つ固定する。組に入らない頂点 $c$ は $n-m$ 個あり、$c$ が条件を満たす（$c$ がすべての $a_i$ と隣接し、どの $b_j$ とも隣接しない）事象を $A_c$ とする。$A_c$ は $m$ 個の 2 元集合 $\{a_i,c\},\{b_j,c\}$ が辺かどうかだけで決まり、確率は $2^{-m}$ である。$c\ne c'$ なら $A_c$ と $A_{c'}$ が関わる 2 元集合の集まりは交わらないので、事象 $A_c$ たちは独立である。よって条件を満たす $c$ が 1 つもない確率は $(1-2^{-m})^{n-m}$ である。すべての組について和をとれば、示すべき不等式を得る。
$q:=1-2^{-m}< 1$ とおくと、$n^mq^{n-m}=q^{-m}\cdot n^mq^n\to0$ である（多項式は指数関数より遅く増える）。$\square$

1：有限部分集合 $\Sigma\subset T_{\mathrm{rand}}$ に現れる拡大公理を $\chi^{(1)},\dots,\chi^{(r)}$ とする。lem-fmt-extension-prob により、十分大きい $n$ ですべての $i$ について $\mu_n(\lnot\chi^{(i)})< \frac1r$ となり、
$$ \mu_n\bigl(\lnot(\chi^{(1)}\land\cdots\land\chi^{(r)})\bigr)\le\sum_{i=1}^r\mu_n(\lnot\chi^{(i)})< 1 $$
なので、$\mathcal G_n$ のあるグラフが $\Sigma$ を満たす。コンパクト性定理(一階論理) により $T_{\mathrm{rand}}$ はモデルをもつ。$G$ が $n$ 個の頂点をもつ有限のモデルなら、$\chi_{n,0}$ で $x_1,\dots,x_n$ を全頂点とすると、それらと異なる $z$ がなく矛盾する。よってモデルは無限である。
2：$G,H$ を可算なモデルとする。$G$ の有限部分集合から $H$ への単射 $p$ で、定義域の $a,b$ について $E(a,b)\iff E(p(a),p(b))$ を満たすものを 部分同型 とよぶ。部分同型 $p$ と $a\in G$ について、$a$ を定義域に含む部分同型 $q\supset p$ があることを示す。$a$ が定義域にあれば $q=p$ とする。そうでなければ、$p$ の定義域のうち $a$ と隣接する頂点を $a_1,\dots,a_k$、隣接しない頂点を $b_1,\dots,b_l$ とする。$p$ の定義域が空なら $H$ の任意の頂点を $z$ とし、そうでなければ $H$ の拡大公理 $\chi_{k,l}$ を相異なる頂点 $p(a_1),\dots,p(a_k),p(b_1),\dots,p(b_l)$ に使って $z$ を得る。$q:=p\cup\{(a,z)\}$ は、$z$ が $p$ の値と異なり、$a$ と定義域の各頂点の隣接関係を $z$ と像の隣接関係が写すので、部分同型である。$G$ と $H$ を入れ替えれば、値域に指定の頂点を含むように広げることもできる。あとは カテゴリー性 の定理「Cantor の定理」の証明の段 3 と同じく、$G,H$ の元を交互に定義域・値域に入れて広げた部分同型の和をとれば、$G$ から $H$ への同型写像を得る。
3：言語 $L_E$ は有限で、1 により $T_{\mathrm{rand}}$ は無限モデルをもつので可算なモデルをもち（Löwenheim–Skolemの定理）、2 と合わせて $\aleph_0$-範疇的である。有限のモデルはないので、Löwenheim–Skolemの定理 の定理「Łoś–Vaught の判定法」により完全である。$\square$

lem-fmt-trand の 3 により、$T_{\mathrm{rand}}\models\sigma$ か $T_{\mathrm{rand}}\models\lnot\sigma$ のどちらかが成り立つ。
$T_{\mathrm{rand}}\models\sigma$ とする。コンパクト性定理(一階論理) の系「帰結の有限性」により、有限部分集合 $T_0\subset T_{\mathrm{rand}}$ で $T_0\models\sigma$ となるものがある。$T_0$ に現れる拡大公理を $\chi^{(1)},\dots,\chi^{(r)}$ とする。$\mathcal G_n$ のグラフはどれも $\Gamma_{\mathrm{gr}}$ を満たすので、$\sigma$ を満たさないグラフはある $\chi^{(i)}$ を満たさない。よって
$$ 1-\mu_n(\sigma)=\mu_n(\lnot\sigma)\le\sum_{i=1}^r\mu_n(\lnot\chi^{(i)})\to0 $$
であり（lem-fmt-extension-prob）、$\mu_n(\sigma)\to1$ である。
$T_{\mathrm{rand}}\models\lnot\sigma$ なら、同じ議論を $\lnot\sigma$ に使って $\mu_n(\lnot\sigma)\to1$、すなわち $\mu_n(\sigma)\to0$ である。2 つの場合は両立しないので、極限が $1$ であるのは前者のときちょうどである。$\square$

そのような $\sigma$ があれば、$\mathcal G_n$ のグラフはすべて頂点が $n$ 個なので、$\mu_n(\sigma)$ は $n$ が偶数なら $1$、奇数なら $0$ であり、極限をもたない。これは thm-fmt-zero-one に反する。等号だけの言語の文は $L_E$ の文でもあり、グラフで頂点の個数の偶奇を定義してしまうので、同じく存在しない。$\square$