連続論理
概要
連続論理（continuous logic）とは、一階述語論理の真理値 $\{0,1\}$ を閉区間 $[0,1]$ に替え、等号の代わりに完備な距離をもつ構造を扱う論理である。述語は記号ごとに定めた modulus に従う一様連続な関数、連結子は $[0,1]^n$ 上の連続関数、量化子は $\sup$ と $\inf$ で、値 $0$ を真と読む。距離構造の超積について、論理式の値が成分の値の超フィルター極限になるという Łoś の定理が成り立ち、そこから近似的に有限充足可能な条件の集合は充足可能であるというコンパクト性定理が従う。
前提知識: 一階述語論理, 距離空間, ウルトラフィルター, コンパクト性定理(一階論理)
連続論理（continuous logic、連続一階論理）は、一階述語論理の真理値の集合 $\{0,1\}$ を閉区間 $[0,1]$ に替えた論理である。等号の代わりに完備な距離 $d$ をもつ構造（距離構造）を扱い、述語は $[0,1]$ に値をとる一様連続な関数、連結子は $[0,1]^n\to[0,1]$ の連続関数、量化子は $\sup$ と $\inf$ である。真理値 $0$ を「真」と読む規約をとる。Banach 空間・Hilbert 空間・確率代数のように、等号ではなく距離で近さを測るのが自然な対象のモデル理論を、一階論理と同じ道具立てで行うための枠組みである。C. C. Chang と H. J. Keisler の連続値の論理の変種として I. Ben Yaacov と A. Usvyatsov が整え、Banach 空間の構造についての C. W. Henson の論理を含む枠組みになっている（BYU08 要旨・§4.1）。
この記事では、連結子・量化子・距離構造の定義を述べ、距離構造の超積を構成し、一階論理の Łoś の定理と コンパクト性定理(一階論理) が連続論理でもそのまま成り立つことを証明する。応用として、コンパクトな距離空間の全体は連続論理の条件の集合で特徴づけられないことを示す。
真理値・連結子・量化子
- 真理値は $[0,1]$ の元で、$0$ を真、$1$ を偽と読む。
- $n$ 変数の 連結子 は連続関数 $u\colon[0,1]^n\to[0,1]$ である。例えば $\lnot x:=1-x$、$x\mathbin{\dot-}y:=\max(x-y,0)$、$x/2$、$\max$、$\min$。
- 量化子 は $\sup_x$ と $\inf_x$ である。
$\sup_x\varphi$ の値が $0$ であることは、すべての $x$ で $\varphi$ の値が $0$ であることなので、$\sup$ は $\forall$ にあたる。同様に $\inf$ は $\exists$ にあたるが、$\inf_x\varphi=0$ は「値 $0$ をとる $x$ がある」ではなく「値がいくらでも $0$ に近い $x$ がある」ことを意味する。$x\mathbin{\dot-}y$ は含意 $y\to x$ にあたり、$y=0$ かつ $x\mathbin{\dot-}y=0$ なら $x=0$ である（連続版の前件肯定）。連結子 $\lnot$、$x/2$、$\mathbin{\dot-}$ を合成して得られる関数は、各 $n$ で $[0,1]^n$ 上の連続関数全体の中で一様収束の位相について稠密である（BYU08 Corollary 1.6、p. 6）。$\lnot,\min,\max$ だけでは、合成がすべて各変数について 1-Lipschitz になるので稠密にならない（同 Remark 1.7、p. 6）。
距離構造
一様連続性を測るため、連続性の modulus として関数 $\delta\colon(0,1]\to(0,1]$ を使う。距離空間の間の写像 $f$ が $\delta$ に 従う とは、すべての $\varepsilon$ と $x,y$ について $d(x,y)<\delta(\varepsilon)$ なら $d(f(x),f(y))\le\varepsilon$ となることをいう（$[0,1]$ には通常の距離を入れる）。
- 言語 $L$ は、関数記号と述語記号（それぞれ $0$ 以上の項数をもつ）、特別な 2 項述語記号 $d$、各記号 $s$ の各変数 $i$ ごとの modulus $\delta_{s,i}$ からなる。
- $L$ 構造 $M$ は、空でない集合 $M$ と、$[0,1]$ に値をとる完備な距離 $d^M$、関数記号 $f$ の解釈 $f^M\colon M^n\to M$、述語記号 $P$ の解釈 $P^M\colon M^n\to[0,1]$ からなり、各 $f^M,P^M$ は他の変数を固定した各変数 $i$ について $\delta_{f,i},\delta_{P,i}$ に従うものとする。
BYU08 Definition 2.1・2.3（p. 9）、2.4（p. 10）の定義である。modulus は記号ごとに固定され、構造によらないことが要点である。$d^M$ は三角不等式から各変数について 1-Lipschitz である。
項・論理式・値．項は一階論理と同じに作る。原子論理式は $P(t_1,\dots,t_n)$（$d(t_1,t_2)$ を含む）、論理式は原子論理式から連結子 $u(\varphi_1,\dots,\varphi_n)$ と $\sup_x\varphi$、$\inf_x\varphi$ で作る。構造 $M$ と元の組 $\bar a$ での値 $\varphi^M(\bar a)\in[0,1]$ は、原子論理式では解釈の値、$u(\varphi_1,\dots,\varphi_n)$ では $u(\varphi_1^M(\bar a),\dots,\varphi_n^M(\bar a))$、量化子では $M$ 全体での上限・下限と、帰納的に定める（同 Definition 2.6、p. 10）。
論理式 $\varphi$ について $\varphi=0$ を 条件 という。$\varphi^M(\bar a)=0$ のとき $M\models\varphi=0\,[\bar a]$ と書く。自由変数のない条件の集合 $\Gamma$ について、$\Gamma$ のすべての条件を満たす $L$ 構造があるとき $\Gamma$ は 充足可能 であるといい、各有限部分集合 $\{\varphi_1=0,\dots,\varphi_n=0\}$ と各 $\varepsilon>0$ について $\varphi_k^M\le\varepsilon$（$k\le n$）となる構造 $M$ があるとき 近似的に有限充足可能 であるという。
BYU08 Definition 1.8（p. 7）・2.8（pp. 10–11）にあたる。有限充足可能なら近似的に有限充足可能である。
- 一階論理の構造は、離散距離（$a\ne b$ なら $d(a,b)=1$）と、関係 $R$ を「成り立てば $0$、成り立たなければ $1$」とする述語で距離構造とみなせる。modulus は $\delta\equiv1$ でよい（$d(a,b)<1$ なら $a=b$）。論理式の $\land,\lor,\lnot,\to,\forall,\exists$ を $\max,\min,\lnot,\ (\psi\mathbin{\dot-}\varphi),\ \sup,\ \inf$ に置き換えると、値は $0$ か $1$ で、$0$ になることと元の論理式が成り立つことが同値である（組み立てに関する帰納法）。
- 記号が $d$ だけの言語（関数記号をもたない）の構造は、直径 $1$ 以下の完備距離空間である。文 $\sup_x\sup_yd(x,y)$ の値は直径であり、条件 $\sup_x\inf_y\bigl(\tfrac12\mathbin{\dot-}d(x,y)\bigr)=0$ は「各点 $x$ と各 $\varepsilon>0$ に対し $d(x,y)\ge\tfrac12-\varepsilon$ となる $y$ がある」ことを表す。
- 確率代数（測度環）は、測度 $\mu$ を述語、対称差の測度を距離とする距離構造であり、その公理は条件の集合で書ける（BYU08 Example 4.3、pp. 19–20）。Banach 空間の単位球も、凸結合の演算を関数記号とし、距離の値域を $[0,2]$ に広げた距離構造として扱える（同 Example 4.4・4.5、pp. 20–21）。この記事ではこれらの詳細に立ち入らない。
超積
$I$ を集合、$U$ を $I$ 上の超フィルターとする。$[0,1]$ の元の族 $(r_i)_{i\in I}$ に対し、すべての $\varepsilon>0$ で $\{i\mid|r_i-r|<\varepsilon\}\in U$ となる $r\in[0,1]$ がただ 1 つある。これを $\lim_Ur_i$ と書く（ウルトラフィルター の定理「超フィルター極限」。そこでは添字集合が自然数の場合を述べているが、証明は任意の $I$ で同じである）。
- 連続関数 $u\colon[0,1]^n\to[0,1]$ について $\lim_Uu(r^1_i,\dots,r^n_i)=u\bigl(\lim_Ur^1_i,\dots,\lim_Ur^n_i\bigr)$。
- $\{i\mid r_i\le s_i\}\in U$ ならば $\lim_Ur_i\le\lim_Us_i$。
証明を開く
1：$r^k:=\lim_Ur^k_i$ とおく。$u$ はコンパクト集合上の連続関数なので一様連続であり、$\varepsilon>0$ に対し $\eta>0$ を、各成分の差が $\eta$ 未満なら値の差が $\varepsilon$ 未満となるようにとれる。$\{i\mid|r^k_i-r^k|<\eta\}$（$k=1,\dots,n$）の共通部分は $U$ に属し、その上で $|u(r^1_i,\dots)-u(r^1,\dots)|<\varepsilon$ である。2：$r:=\lim_Ur_i> s:=\lim_Us_i$ なら、$\eta:=(r-s)/2$ について $\{i\mid r_i> r-\eta\}$、$\{i\mid s_i< s+\eta\}$、$\{i\mid r_i\le s_i\}$ の共通部分は $U$ に属し空でないが、その元では $s_i< s+\eta=r-\eta< r_i\le s_i$ となり矛盾する。$\square$
$L$ 構造の族 $(M_i)_{i\in I}$ について、直積 $\prod_iM_i$ の元 $a=(a_i)$、$b=(b_i)$ の間に $d(a,b):=\lim_Ud^{M_i}(a_i,b_i)$ とおき、$d(a,b)=0$ となる元を同一視した集合を $N:=\prod_iM_i/U$ と書く。$a$ の類を $[a_i]$ と書き、
$$
f^N([a^1_i],\dots,[a^n_i]):=[f^{M_i}(a^1_i,\dots,a^n_i)],\qquad P^N([a^1_i],\dots,[a^n_i]):=\lim_UP^{M_i}(a^1_i,\dots,a^n_i)
$$
と定める。これを $(M_i)$ の $U$ による 超積 という。
BYU08 Definition 2.14（pp. 12–13）の構成である（そこでは同一視の後に完備化をとっているが、次の補題により完備化は要らない）。
$d$ は $\prod_iM_i$ 上の擬距離であり、$f^N,P^N$ は代表元の選び方によらない。$N$ は $L$ 構造であり、とくに $d^N$ は完備な距離である。
証明を開く
擬距離と well-defined 性．三角不等式は lem-cl-ultralimit の 1（$u(x,y)=\min(x+y,1)$）と 2 から従う。$f$ の第 $k$ 変数だけを $d(a,a')=0$ となる $a'$ に替える。$\varepsilon>0$ について $\{i\mid d(a_i,a'_i)<\delta_{f,k}(\varepsilon)\}\in U$ であり、その上で 2 つの値の距離は $\varepsilon$ 以下なので、極限は $\varepsilon$ 以下、よって $0$ である。変数を 1 つずつ替えればよい。$P$ も同様で、値の差の極限が $\varepsilon$ 以下になる。
modulus．$d^N([a_i],[a'_i])<\delta(\varepsilon)$ なら $\{i\mid d(a_i,a'_i)<\delta(\varepsilon)\}\in U$ なので、上と同じく $f^N,P^N$ は $\delta_{f,k},\delta_{P,k}$ に従う。
完備性．Cauchy 列は部分列をとって $d^N(x^n,x^{n+1})< 2^{-n}$ としてよい。代表元 $x^n=[x^n_i]$ をとり、$A_0:=I$、$A_n:=\{i\mid d(x^k_i,x^{k+1}_i)< 2^{-k}\ (k< n)\}\in U$ とおく。$i\in\bigcap_nA_n$ なら $(x^n_i)_n$ は $M_i$ の Cauchy 列なのでその極限を $y_i$ とし、$i\in A_n\setminus A_{n+1}$ なら $y_i:=x^n_i$ とする。$i\in A_m$ なら $d(y_i,x^m_i)\le\sum_{k\ge m}2^{-k}=2^{1-m}$ なので、$d^N([y_i],x^m)\le2^{1-m}$ であり、$x^m\to[y_i]$ である。$\square$
$N=\prod_iM_i/U$ とする。任意の論理式 $\varphi(x_1,\dots,x_n)$ と $\prod_iM_i$ の元 $(a^1_i),\dots,(a^n_i)$ について
$$
\varphi^N([a^1_i],\dots,[a^n_i])=\lim_U\varphi^{M_i}(a^1_i,\dots,a^n_i)
$$
が成り立つ。
$\bar a_i:=(a^1_i,\dots,a^n_i)$、$[\bar a]:=([a^1_i],\dots,[a^n_i])$ と書く。項 $t$ について $t^N([\bar a])=[t^{M_i}(\bar a_i)]$ であることは、def-cl-ultraproduct の $f^N$ の定め方から項の組み立てに関する帰納法で分かる。以下、論理式の組み立てに関する帰納法による。
原子論理式．$\varphi=P(t_1,\dots,t_m)$ なら、項についての事実と $P^N$ の定義から $\varphi^N([\bar a])=P^N([t_1^{M_i}(\bar a_i)],\dots)=\lim_UP^{M_i}(t_1^{M_i}(\bar a_i),\dots)=\lim_U\varphi^{M_i}(\bar a_i)$。$P=d$ の場合も同じである。
連結子．$\varphi=u(\psi_1,\dots,\psi_m)$ なら、帰納法の仮定と lem-cl-ultralimit の 1 から従う。
量化子．$\varphi=\sup_y\psi(y,\bar x)$ とし、$s_i:=\sup_{b\in M_i}\psi^{M_i}(b,\bar a_i)$ とおく。任意の $[b_i]\in N$ について、帰納法の仮定と lem-cl-ultralimit の 2 から $\psi^N([b_i],[\bar a])=\lim_U\psi^{M_i}(b_i,\bar a_i)\le\lim_Us_i$ なので、$\varphi^N([\bar a])\le\lim_Us_i$ である。逆に $\varepsilon>0$ をとり、各 $i$ で $\psi^{M_i}(b_i,\bar a_i)\ge s_i-\varepsilon$ となる $b_i\in M_i$ を選ぶ。帰納法の仮定と lem-cl-ultralimit から
$$
\varphi^N([\bar a])\ge\psi^N([b_i],[\bar a])=\lim_U\psi^{M_i}(b_i,\bar a_i)\ge\lim_U\max(s_i-\varepsilon,0)=\max\Bigl(\lim_Us_i-\varepsilon,0\Bigr)
$$
である。$\varepsilon$ は任意なので $\varphi^N([\bar a])\ge\lim_Us_i$。$\inf_y$ も不等号の向きを替えて同じである。$\square$
BYU08 Theorem 2.15（p. 13）は「論理式の複雑さに関する帰納法による」として証明を述べていない。一階論理の場合（コンパクト性定理(一階論理) の定理「Łoś の定理」）と比べると、真偽の「多数決」が値の超フィルター極限に置き換わり、存在量化子の場合の「証人を選ぶ」議論が「上限に $\varepsilon$ まで近い証人を選ぶ」議論になっている。
コンパクト性定理
自由変数のない条件の集合 $\Gamma$ が近似的に有限充足可能ならば、$\Gamma$ は充足可能である。とくに、有限充足可能なら充足可能である。
$\Gamma$ の有限部分集合 $w$ と正の整数 $n$ の組の全体を $I$ とする。各 $(w,n)\in I$ について、$w$ の各条件 $\varphi=0$ が $\varphi^M\le1/n$ をみたす $L$ 構造 $M_{w,n}$ を選ぶ。$J_{w,n}:=\{(w',n')\in I\mid w\subset w',\ n\le n'\}$ とおくと、$J_{w,n}\cap J_{w',n'}\supset J_{w\cup w',\max(n,n')}\ne\emptyset$ なので、$\{J_{w,n}\}$ を含む固有のフィルターがあり、それを含む超フィルター $U$ がある（ウルトラフィルター の定理「超フィルターへの拡張」）。$N:=\prod_{(w,n)}M_{w,n}/U$ とおく。
$\varphi=0$ を $\Gamma$ の条件とし、$n\ge1$ とする。$(w',n')\in J_{\{\varphi=0\},n}$ なら $\varphi\in w'$ なので $\varphi^{M_{w',n'}}\le1/n'\le1/n$ である。$J_{\{\varphi=0\},n}\in U$ なので、thm-cl-los と lem-cl-ultralimit の 2 から $\varphi^N=\lim_U\varphi^{M_{w',n'}}\le1/n$ である。$n$ は任意なので $\varphi^N=0$。よって $N$ は $\Gamma$ を満たす。$\square$
BYU08 Corollary 2.16（p. 13）にあたる（そこでは自由変数を新しい定数記号に替えて同じ主張を自由変数つきの条件にも述べている）。
記号が $d$ だけの言語で、自由変数のない条件の集合 $T$ が直径 $1$ 以下のすべてのコンパクト距離空間で満たされるならば、$T$ はコンパクトでない完備距離空間でも満たされる。
定数記号 $c_1,c_2,\dots$ を加え、$\Gamma:=T\cup\{1\mathbin{\dot-}d(c_j,c_k)=0\mid j< k\}$ とおく。$\Gamma$ の有限部分集合に現れる定数が $c_1,\dots,c_m$ の中にあるとき、$m$ 点の離散距離空間（コンパクトで直径 $1$）で $c_1,\dots,c_m$ を相異なる点と解釈すればその部分集合を満たす。thm-cl-compactness により $\Gamma$ を満たす構造 $N$ がある。$T$ の条件の値は定数記号の解釈によらないので、$N$ の距離空間は $T$ を満たす。$d(c_j^N,c_k^N)=1$（$j\ne k$）なので点列 $(c_k^N)$ は収束する部分列をもたず、$N$ はコンパクトでない。$\square$
一階論理で「有限集合である」ことが一階の文の集合で特徴づけられないことの、連続論理での類似である。
反例と注意
表の各行は、1 つの条件を外すと超積と Łoś の定理が意味を失うことを示す。どの行でも $M_n:=\{p,q\}$（$n\ge1$）、$U$ は自然数の上の非主超フィルターとする。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 連結子の連続性 | $d(p,q)=1/n$、$\chi(0)=0$、$\chi(t)=1$（$t>0$）、文 $\sigma:=\sup_x\sup_y\chi(d(x,y))$ | Łoś の定理（thm-cl-los） |
| modulus が構造によらないこと | $d(p,q)=1/n$、述語 $P(p)=0$、$P(q)=1$ | $P^N$ が代表元によらないこと（lem-cl-ultraproduct） |
| 距離が $[0,1]$ に値をとること | $d(p,q)=n$ | $d^N$ が実数値の距離として定まること |
1 行目：各 $M_n$ で $\sigma^{M_n}=1$ だが、超積では任意の 2 元の距離が $\lim_U1/n=0$ なので $N$ は 1 点であり、$\sigma^N=0$ である。2 行目：各 $M_n$ の $P$ は modulus $\delta\equiv1/n$ に従うが、$n$ によらない modulus はない。超積では $[p]=[q]$ だが $\lim_UP(p)=0\ne1=\lim_UP(q)$ である。3 行目：$d(p,q)=n$ の極限は有限でない。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
