Łośの定理

同義語：ウォシュの定理Łoś's theoremLos's theorem超積の基本定理fundamental theorem of ultraproducts

概要

前提知識: 超積, 一階述語論理, 超フィルター

Łoś の定理（Łoś's theorem）とは、一階言語の構造の族 $(\mathcal M_i)_{i\in I}$ と添字集合 $I$ 上の超フィルター $U$ について、超積 $\prod_{i\in I}\mathcal M_i/U$ で一階の論理式 $\varphi$ が元 $[f_1],\dots,[f_n]$ について成り立つことと、$\varphi$ が成分の元 $f_1(i),\dots,f_n(i)$ について成り立つ添字 $i$ の集合が $U$ に属することが同値である、という定理である。
超フィルターに属する集合を「ほとんどすべての添字」と読むと、この定理は「超積で成り立つ一階の性質は、ほとんどすべての成分で成り立つ性質にちょうど一致する」と言っている。超積は関数と関係（原子論理式）を成分の多数決で定めた構造であるが、Łoś の定理はこの多数決が否定・連言・量化記号を通しても崩れないことを保証する。そのため、ほとんどすべての成分で成り立つ一階の言葉で書ける事実は、どれも超積へそのまま移る。この定理から、超冪への対角写像が初等埋め込みであること、一階の理論のモデルの超積がまたモデルであること、コンパクト性定理(一階論理) などが従う。

結果	内容
thm-los-main	超積での真偽は、成分での真偽の多数決
cor-los-sentences	文の真偽と、理論のモデルの超積
cor-los-diagonal	超冪への対角写像は初等埋め込み
cor-los-finite	有限構造とほとんどすべて同型な成分の超積は、その構造と同型

設定と主張

$L$ を一階言語、$(\mathcal M_i)_{i\in I}$ を $L$ 構造の族、$M_i$ を $\mathcal M_i$ の台集合、$U$ を空でない集合 $I$ 上の超フィルターとする。選択公理を仮定する。超積 $\mathcal M:=\prod_{i\in I}\mathcal M_i/U$ の定義を思い出しておく（超積の記事の定義「超積と超冪」）。台集合 $M$ は、直積 $\prod_iM_i$ の元 $f,g$ を $\{f=g\}:=\{i\mid f(i)=g(i)\}\in U$ のとき同一視した同値類 $[f]$ の全体である。定数記号 $c$ は $[(c^{\mathcal M_i})_i]$、関数記号 $F$ は $F([\bar f])=[\,i\mapsto F^{\mathcal M_i}(\bar f(i))\,]$ と解釈し、関係記号 $R$ は $\{i\mid\bar f(i)\in R^{\mathcal M_i}\}\in U$ のときに $R([\bar f])$ が成り立つとする。これらが代表元によらないことは同記事の補題「超積の定義は代表元によらない」で示されている。
超フィルター $U$ については、次の 3 つの性質を使う（超フィルターの記事の定義と定理「超フィルターの特徴づけ」）。

(F1) $A\in U$ かつ $A\subset B\subset I$ なら $B\in U$。
(F2) $A,B\subset I$ について、$A\cap B\in U\iff$（$A\in U$ かつ $B\in U$）。
(F3) $A\subset I$ について、$A\notin U\iff I\setminus A\in U$。
(F2) の右から左はフィルターが共通部分で閉じていること、左から右は (F1) である。(F3) が超フィルターであることの言い換えで、フィルター一般では成り立たない。
論理式 $\varphi(x_1,\dots,x_n)$（自由変数が $x_1,\dots,x_n$ の中にあるもの）と $f_1,\dots,f_n\in\prod_iM_i$ について、$\bar f=(f_1,\dots,f_n)$、$[\bar f]=([f_1],\dots,[f_n])$、$\bar f(i)=(f_1(i),\dots,f_n(i))$ と書き、$\varphi$ が成分で成り立つ添字の集合を
$$ \|\varphi(\bar f)\|:=\{\,i\in I\mid\mathcal M_i\models\varphi(\bar f(i))\,\} $$
とおく。$\mathcal M_i\models\varphi(\bar f(i))$ は、$x_k$ に $f_k(i)$ を割り当てたときに $\varphi$ が $\mathcal M_i$ で充足されることを表す。

Łoś の定理

任意の $L$ 論理式 $\varphi(x_1,\dots,x_n)$ と任意の $f_1,\dots,f_n\in\prod_{i\in I}M_i$ について
$$ \prod_{i\in I}\mathcal M_i/U\models\varphi([f_1],\dots,[f_n])\quad\Longleftrightarrow\quad\|\varphi(\bar f)\|\in U . $$

論理式の組み立てに関する帰納法

$\mathcal M:=\prod_i\mathcal M_i/U$ とおく。$\lor,\to,\forall$ は $\lnot,\land,\exists$ で論理的に同値に書き換えられ（$\varphi\lor\psi$ は $\lnot(\lnot\varphi\land\lnot\psi)$、$\varphi\to\psi$ は $\lnot(\varphi\land\lnot\psi)$、$\forall y\,\varphi$ は $\lnot\exists y\,\lnot\varphi$）、書き換えても両辺の真偽は変わらないので、論理式は原子論理式から $\lnot$、$\land$、$\exists$ で作られるとしてよい。
項。項 $t(x_1,\dots,x_n)$ について、$x_k$ に $[f_k]$ を割り当てたときの $\mathcal M$ での値を $t^{\mathcal M}([\bar f])$、$x_k$ に $f_k(i)$ を割り当てたときの $\mathcal M_i$ での値を $t^{\mathcal M_i}(\bar f(i))$ と書く。まず
$$ t^{\mathcal M}([\bar f])=[\,i\mapsto t^{\mathcal M_i}(\bar f(i))\,] $$
を項の組み立てに関する帰納法で示す（この等式を以下 (T) とよぶ）。$t=x_k$ なら両辺は $[f_k]$ である。$t$ が定数記号 $c$ なら、両辺は超積での $c$ の解釈 $[(c^{\mathcal M_i})_i]$ である。$t=F(t_1,\dots,t_m)$ なら、帰納法の仮定で $t_l^{\mathcal M}([\bar f])=[g_l]$、$g_l(i):=t_l^{\mathcal M_i}(\bar f(i))$ と書けるので、超積での $F$ の定義から $t^{\mathcal M}([\bar f])=F([g_1],\dots,[g_m])=[\,i\mapsto F^{\mathcal M_i}(g_1(i),\dots,g_m(i))\,]=[\,i\mapsto t^{\mathcal M_i}(\bar f(i))\,]$ である。
原子論理式。 $\varphi$ が $t_1=t_2$ のとき、$h_l(i):=t_l^{\mathcal M_i}(\bar f(i))$ とおくと、(T) により $\mathcal M\models\varphi([\bar f])\iff[h_1]=[h_2]\iff\{h_1=h_2\}\in U$ であり、$\{h_1=h_2\}=\|\varphi(\bar f)\|$ である。$\varphi$ が $R(t_1,\dots,t_m)$ のとき、$h_l$ を同様に定めると、(T) と超積での $R$ の定義から $\mathcal M\models\varphi([\bar f])\iff\{i\mid(h_1(i),\dots,h_m(i))\in R^{\mathcal M_i}\}\in U$ であり、この集合は $\|\varphi(\bar f)\|$ である。
否定。 $\|\lnot\varphi(\bar f)\|=I\setminus\|\varphi(\bar f)\|$ である。帰納法の仮定と (F3) により
$$ \mathcal M\models\lnot\varphi([\bar f])\iff\|\varphi(\bar f)\|\notin U\iff\|\lnot\varphi(\bar f)\|\in U . $$
連言。 $\|(\varphi\land\psi)(\bar f)\|=\|\varphi(\bar f)\|\cap\|\psi(\bar f)\|$ である。帰納法の仮定と (F2) により、$\mathcal M\models(\varphi\land\psi)([\bar f])$ は「$\|\varphi(\bar f)\|\in U$ かつ $\|\psi(\bar f)\|\in U$」と同値で、これは $\|(\varphi\land\psi)(\bar f)\|\in U$ と同値である。
存在量化。 $\varphi(\bar x)=\exists y\,\psi(\bar x,y)$ とし、$\psi$ については主張が成り立つとする。
$\Rightarrow$：$\mathcal M\models\varphi([\bar f])$ なら、ある $[g]\in M$ で $\mathcal M\models\psi([\bar f],[g])$ となる。帰納法の仮定により $\|\psi(\bar f,g)\|\in U$ である。$i\in\|\psi(\bar f,g)\|$ なら $g(i)$ が $\mathcal M_i$ での証人になるので $\|\psi(\bar f,g)\|\subset\|\varphi(\bar f)\|$ であり、(F1) により $\|\varphi(\bar f)\|\in U$ である。
$\Leftarrow$：$A:=\|\varphi(\bar f)\|\in U$ とする。各 $i\in A$ について $\mathcal M_i\models\psi(\bar f(i),b)$ となる $b\in M_i$ を 1 つ選んで $g(i)$ とし（選択公理）、$i\notin A$ では $g(i)\in M_i$ を任意に選ぶ（台集合は空でない）。すると $A\subset\|\psi(\bar f,g)\|$ なので、(F1) により $\|\psi(\bar f,g)\|\in U$ であり、帰納法の仮定から $\mathcal M\models\psi([\bar f],[g])$、したがって $\mathcal M\models\varphi([\bar f])$ である。$\square$

証明の中で、$U$ が超フィルターであることを使ったのは否定の段の (F3) だけである。フィルター $\mathcal F$ による縮約積でも、原子論理式・連言・存在量化の段はそのまま通る。存在量化の後ろ向きの段では、成分ごとに証人を 1 つずつ選ぶために選択公理を使っている。この主張と証明は BS12 Chapter V, Theorem 2.9（pp. 210–211）にあり、同書は存在量化の段の証人の選び方を Lemma 2.6（p. 207）として切り出している。

帰結

文と理論

文の真偽と理論のモデル

文 $\sigma$ について、$\prod_{i\in I}\mathcal M_i/U\models\sigma\iff\{i\in I\mid\mathcal M_i\models\sigma\}\in U$ である。
文の集合 $T$ について、各 $\sigma\in T$ で $\{i\mid\mathcal M_i\models\sigma\}\in U$ ならば、超積は $T$ のモデルである。とくに、すべての $\mathcal M_i$ が $T$ のモデルなら、超積も $T$ のモデルである。

1 は thm-los-main の $n=0$ の場合である（文の真偽は割り当てによらない）。2 は 1 を各 $\sigma\in T$ に当てればよい。後半では $\{i\mid\mathcal M_i\models\sigma\}=I\in U$ である。$\square$

2 の後半は、ある文の集合のモデル全体として書けるクラスが超積で閉じていることを言っている。例えば群・環・体・順序体・代数閉体のクラスはどれも超積で閉じている。逆に、超積で閉じていないクラスは文の集合のモデル全体として書けない（ex-los-counterexamples の有限構造のクラス）。

対角写像

構造 $\mathcal A$ の超冪 $\mathcal A^I/U$ への対角写像 $d(a):=[c_a]$（$c_a$ は値 $a$ の定数関数）は、原子論理式の真偽を保つ埋め込みである（超積の記事の命題「対角写像は埋め込み」）。Łoś の定理により、さらに強いことが言える。

対角写像は初等埋め込み

$\mathcal A$ を $L$ 構造、$U$ を $I$ 上の超フィルターとする。任意の論理式 $\varphi(x_1,\dots,x_n)$ と $a_1,\dots,a_n\in A$ について
$$ \mathcal A\models\varphi(a_1,\dots,a_n)\iff\mathcal A^I/U\models\varphi(d(a_1),\dots,d(a_n)) $$
である。すなわち $d$ は初等埋め込みであり、とくに $\mathcal A$ と $\mathcal A^I/U$ は同じ文を真にする（初等同値である）。

$f_k:=c_{a_k}$ とすると、$\|\varphi(\bar f)\|$ は $i$ によらない条件で決まり、$\mathcal A\models\varphi(\bar a)$ なら $I$、そうでなければ $\emptyset$ である。$I\in U$、$\emptyset\notin U$ なので、thm-los-main から主張が従う。$\square$

これは BS12 Theorem 2.11（p. 211）である。$U$ が非主なら、超冪は元の構造と同じ文を真にしながら、新しい元をもつ大きな構造になる。

有限構造の超積

$L$ を有限個の記号からなる言語、$\mathcal N$ を有限な $L$ 構造とする。$\{i\in I\mid\mathcal M_i\cong\mathcal N\}\in U$ ならば、$\prod_{i\in I}\mathcal M_i/U\cong\mathcal N$ である。

$\mathcal N$ を同型を除いて定める文を作る

$\mathcal N$ の台集合を $\{a_1,\dots,a_k\}$（相異なる元）とする。変数 $x_1,\dots,x_k$ について、次の論理式の連言を $\delta(x_1,\dots,x_k)$ とおく。

$j< l$ について $x_j\ne x_l$。
$\forall y\,(y=x_1\lor\cdots\lor y=x_k)$。
定数記号 $c$ について、$c^{\mathcal N}=a_j$ となる $j$ に対する $c=x_j$。
$m$ 項関数記号 $F$ と添字の組 $(j_1,\dots,j_m)$ について、$F^{\mathcal N}(a_{j_1},\dots,a_{j_m})=a_j$ となる $j$ に対する $F(x_{j_1},\dots,x_{j_m})=x_j$。
$m$ 項関係記号 $R$ と添字の組 $(j_1,\dots,j_m)$ について、$(a_{j_1},\dots,a_{j_m})\in R^{\mathcal N}$ なら $R(x_{j_1},\dots,x_{j_m})$、そうでなければ $\lnot R(x_{j_1},\dots,x_{j_m})$。
$L$ も $k$ も有限なので、これは有限個の論理式の連言であり、$\sigma_{\mathcal N}:=\exists x_1\cdots\exists x_k\,\delta$ は文である。$x_j$ に $a_j$ を割り当てれば $\delta$ が $\mathcal N$ で充足されるので $\mathcal N\models\sigma_{\mathcal N}$ であり、同型は文の真偽を保つので、$\mathcal N$ と同型な構造も $\sigma_{\mathcal N}$ を満たす。
逆に、$L$ 構造 $\mathcal B$ が $\sigma_{\mathcal N}$ を満たすとし、証人を $b_1,\dots,b_k$ とする。最初の 2 種類の論理式から、$b_1,\dots,b_k$ は相異なり、$\mathcal B$ の台集合はちょうど $\{b_1,\dots,b_k\}$ である。よって $h(a_j):=b_j$ は全単射である。残りの 3 種類の論理式から、$h$ は定数記号の解釈と関数記号の値を保ち、関係記号については成り立つ組も成り立たない組も保つ。よって $h$ は同型である。
仮定から $\{i\mid\mathcal M_i\models\sigma_{\mathcal N}\}\supset\{i\mid\mathcal M_i\cong\mathcal N\}\in U$ なので、cor-los-sentences により超積は $\sigma_{\mathcal N}$ を満たし、上で示したことから $\mathcal N$ と同型である。$\square$

各成分が、互いに同型でない有限個の有限構造 $\mathcal N_1,\dots,\mathcal N_m$ のどれかと同型なら、$I$ を $m$ 個の集合 $\{i\mid\mathcal M_i\cong\mathcal N_j\}$ に分けたうちのちょうど 1 つが $U$ に属するので、超積はその $\mathcal N_j$ と同型になる。代数系についてのこの主張は BS12 Chapter IV, Lemma 6.5（p. 146）で直接示されている。例えば $n$ が偶数なら $\mathbb Z/2\mathbb Z$、奇数なら $\mathbb Z/3\mathbb Z$ を成分とする $\mathbb N$ 上の超積は、偶数の集合が $U$ に属すれば $\mathbb Z/2\mathbb Z$ と、そうでなければ $\mathbb Z/3\mathbb Z$ と同型であり、どちらになるかは $U$ による。

例

有限体の超積は代数閉体でない

$P$ を素数の全体、$U$ を $P$ 上の非主超フィルターとし、$K:=\prod_{p\in P}\mathbb F_p/U$ とおく。$K$ は標数 $0$ の無限体である（超積の記事の例「有限体の超積」）。
奇素数 $p$ について、$\mathbb F_p$ の $0$ でない元の平方はちょうど $(p-1)/2$ 個で（平方剰余の記事の命題「平方剰余はちょうど半分」）、平方でない元がある。よって文 $\exists x\,\forall y\,\lnot(y\cdot y=x)$ は奇素数 $p$ のすべてで $\mathbb F_p$ で真であり、奇素数の集合は補集合 $\{2\}$ が有限なので $U$ に属する。cor-los-sentences により $K$ でも真であり、$K$ には平方根をもたない元 $a$ がある。多項式 $X^2-a$ は $K$ に根をもたないので、$K$ は代数閉体でない。
さらに、文 $\exists c\,\forall x\,\exists y\,(y\cdot y=x\lor y\cdot y=c\cdot x)$ はすべての素数 $p$ で $\mathbb F_p$ で真である（$p=2$ ではすべての元が平方。奇素数では $c$ を平方でない元にとると、平方でない元 $x\ne0$ について $cx$ は平方でない元どうしの積なので平方になる。平方剰余の記事の命題「平方剰余と平方非剰余の積」）。したがって $K$ でも真であり、$K$ の $0$ でない元は、平方であるか、固定した 1 つの元 $c$ と平方の積である。

複素数体の超冪

$U$ を $\mathbb N$ 上の非主超フィルターとし、$K:=\mathbb C^{\mathbb N}/U$ とおく（言語は $\{+,-,\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) $$
は $\mathbb C$ で真であり（$x^k$ は $x$ を $k$ 個掛けた項の略記）、文 $\lnot(1+\cdots+1=0)$（$1$ を $m$ 個足す。$m\ge1$）も真である。cor-los-diagonal により $K$ もこれらを満たすので、$K$ は標数 $0$ の代数閉体である。超積の記事の命題「可算添字の非主超冪の濃度」により $K$ の濃度は連続体濃度である。
対角写像 $d$ で $\mathbb C$ を $K$ の部分体とみる。$\alpha(n):=n$ の類 $[\alpha]$ は $d(\mathbb C)$ 上で超越的である。実際、$P$ を $0$ でない複素係数の多項式とすると、$P([\alpha])=[\,n\mapsto P(n)\,]$ であり、$\{n\mid P(n)=0\}$ は有限集合なので $U$ に属さず、$P([\alpha])\ne0$ である。したがって $K$ は $\mathbb C$ の真の拡大体で、$\mathbb C$ と同じ一階の文を満たす。

算術の超準モデル

$\mathcal N=(\mathbb N,0,S,+,\cdot,<)$ と $\mathbb N$ 上の非主超フィルター $U$ について、cor-los-diagonal により超冪 $\mathcal N^{\mathbb N}/U$ は $\mathcal N$ と同じ文を真にする。一方 $\omega:=[\,n\mapsto n\,]$ は、各 $m$ について $\{n\mid m< n\}\in U$ なので $d(m)< \omega$ を満たし、どの標準的な自然数よりも大きい。よって $\mathcal N^{\mathbb N}/U$ は、自然数で真な文をすべて満たしながら無限大の元をもつ超準モデルである。

反例：条件を外すと成り立たない

外す条件	反例	成り立たなくなること
超フィルター（補有限フィルターにする）	縮約積 $\mathbb R^{\mathbb N}/\mathcal F_0$ と文 $\forall x\,(x\ne0\to\exists y\,(x\cdot y=1))$	各成分で真なら超積でも真
一階の論理式（可算無限の選言を許す）	$\mathcal N^{\mathbb N}/U$ と $\forall x\,\bigvee_{n\in\mathbb N}x=S^n(0)$	各成分で真なら超冪でも真
一階の論理式（部分集合を量化する）	$(\mathbb N,<)^{\mathbb N}/U$ と「空でない部分集合は最小元をもつ」	各成分で真なら超冪でも真
一階の文の集合で書ける性質	有限体の超積 $\prod_p\mathbb F_p/U$	成分が有限なら超積も有限

反例の確認

$\mathcal F_0$ は $\mathbb N$ の補有限集合の全体、$U$ は $\mathbb N$（4 行目では素数の全体）上の非主超フィルターとする。
1 行目：$e:=(1,0,1,0,\dots)$ は $\{e=0\}$（奇数の集合）が $\mathcal F_0$ に属さないので $[e]\ne0$ である。$[e][g]=1$ なら $\{eg=1\}\in\mathcal F_0$ のはずだが、$\{eg=1\}$ は偶数の集合に含まれ、補集合が有限でない。よって $[e]$ は逆元をもたず、各成分 $\mathbb R$ で真な文が縮約積で偽になる。thm-los-main の証明では否定の段の (F3) が破れている：$\|e\ne0\|$ は偶数の集合で $\mathcal F_0$ に属さないのに、$[e]\ne0$ である。
2 行目：各成分 $\mathcal N$ ではどの元も $S^n(0)$ の値である。超冪の $\omega=[\,n\mapsto n\,]$ は、各 $n$ について $\{m\mid m=n\}=\{n\}\notin U$ なので $\omega\ne d(n)$ であり、無限の選言は超冪で偽である。添字の集合では、$\mathbb N=\bigcup_n\{n\}\in U$ なのにどの $\{n\}$ も $U$ に属さず、(F2) の有限個の共通部分の議論が無限個には延びない。
3 行目：$f_k(m):=\max(m-k,0)$ とおくと、$\{m\mid f_{k+1}(m)< f_k(m)\}=\{m\mid m\ge k+1\}\in U$ なので $[f_0]>[f_1]>[f_2]>\cdots$ であり、集合 $\{[f_k]\mid k\in\mathbb N\}$ は最小元をもたない。整列性は部分集合を量化する性質であり、一階の論理式ではない。
4 行目：各 $\mathbb F_p$ は有限だが、超積は無限体である（超積の記事の例「有限体の超積」）。もし有限な体の全体がある文の集合 $T$ のモデル全体なら、cor-los-sentences により超積も $T$ のモデルで有限になるはずなので、そのような $T$ はない。

補足

コンパクト性定理への応用。 文の集合 $T$ のどの有限部分にもモデルがあれば、有限部分ごとのモデルを、「有限部分が大きくなる方向」を表す超フィルターで超積にしたものが $T$ のモデルになる。この証明はコンパクト性定理(一階論理) の記事にあり、超積の中で各文が真であることを確かめる段で Łoś の定理を使う。
名前と出典。 Łoś はポーランドの数学者で、名前は英語の wash に近く発音される（BS12 Chapter IV §6, p. 145）。超積と、この定理は Łoś の 1955 年の論文による（Kei22 の References、p. 199）。Kei22 §15D（Theorem 15.30, p. 193）は、実数の上の超構造 $V(\mathbb R)$ の有界な超冪と有界な論理式について、同じ形の定理を述べている。