Feferman–Vaughtの定理

同義語:Feferman-Vaughtの定理Feferman–Vaught theoremFeferman-Vaught theorem

概要

Feferman–Vaughtの定理(Feferman–Vaught theorem)とは、構造の族の直積 $\prod_{i\in I}A_i$ で一階の論理式 $\varphi(\bar a)$ が成り立つかどうかが、$\varphi$ だけから決まる論理式 $\psi_1,\dots,\psi_m$ の成り立つ添字の集合について、添字集合の冪集合の Boole 代数 $\mathcal P(I)$ の論理式 $\Phi$ が成り立つかどうかで決まる、という定理である。各因子での真偽がそのまま直積に移るわけではないが、因子ごとに初等同値な同じ添字集合の族の直積は初等同値になり、無限の添字集合による直冪の理論は添字集合の大きさによらない。Feferman と Vaught は一般化積について示した。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 一階述語論理, 初等同値, Boolean代数

Feferman–Vaught の定理(Feferman–Vaught theorem)は、構造の族の直積で一階の論理式が成り立つかどうかを、各因子での真偽から計算する方法を与える定理である。直積 $\prod_{i\in I}A_i$ で論理式 $\varphi(\bar a)$ が成り立つかは、「いくつかの論理式 $\psi_1,\dots,\psi_m$ が成り立つ添字の集合」を求め、それらの集合について添字集合 $I$ の冪集合の Boole 代数 $\mathcal P(I)$ のある論理式 $\Phi$ が成り立つかを見ればよい。しかも $\Phi$ と $\psi_j$ は $\varphi$ だけから決まり、族にはよらない。
各因子で成り立つ文が直積でも成り立つとは限らない。体の直積は(因子が 2 個以上なら)体でない。それでも直積の一階の性質は因子の一階の性質から決まり、とくに因子ごとに 初等同値 な族の直積は初等同値になる。この記事では直積の場合の定理を完全に証明し、帰結と例を述べる。一般化積についての Feferman と Vaught(1959 年)の元の形は主張だけを紹介する。同じ Vaught の名がつく Łoś–Vaughtの判定法 や Tarski–Vaughtの判定法 とは別の定理である。

設定

$L$ を一階言語(関数記号・定数記号を含んでよい)、$I$ を空でない集合、$(A_i)_{i\in I}$ を空でない $L$ 構造の族とする。

直積と真理集合
  1. 直積 $A=\prod_{i\in I}A_i$ は、台集合を 直積 の集合 $\prod_iA_i$ とし、記号を成分ごとに解釈した $L$ 構造である。定数 $c$ は $c^A(i)=c^{A_i}$、関数 $F$ は $F^A(\bar a)(i)=F^{A_i}(\bar a(i))$、関係 $R$ は「すべての $i$ で $A_i\models R(\bar a(i))$」のとき $A\models R(\bar a)$ と定める。ここで $\bar a=(a_1,\dots,a_n)$ について $\bar a(i):=(a_1(i),\dots,a_n(i))$ である。$A_i$ がすべて同じ構造 $B$ のとき $A=B^I$ と書き、直冪 という。
  2. $L$ の論理式 $\psi(\bar x)$ と $\bar a\in A^n$ について、$\psi$ が成り立つ添字の集合
    $$ \|\psi(\bar a)\|:=\{i\in I\mid A_i\models\psi(\bar a(i))\}\subseteq I $$
    を 真理集合 という。
  3. $\mathcal P(I)$ を、$0=\emptyset$、$1=I$、$\sqcap=\cap$、$\sqcup=\cup$、補元を $I\setminus{-}$ とする Boole 代数と見る。この言語 $L_{\mathrm{Bool}}=\{0,1,\sqcap,\sqcup,{}^c\}$ の論理式を Boole 論理式 という。

MVA25 Definition 1.2(p. 3)、Definition 2.2(p. 5)と同じ定義である(同論文は真理集合を $K_\psi(\bar a)$ と書く)。原子論理式では、直積での真偽は真理集合が $I$ 全体かどうかで決まる。

原子論理式と論理結合子
  1. 項 $t(\bar x)$ について $t^A(\bar a)(i)=t^{A_i}(\bar a(i))$ である。原子論理式 $\varphi(\bar x)$ について $A\models\varphi(\bar a)\iff\|\varphi(\bar a)\|=I$ である。
  2. $\|\lnot\psi(\bar a)\|=I\setminus\|\psi(\bar a)\|$、$\|(\psi\land\chi)(\bar a)\|=\|\psi(\bar a)\|\cap\|\chi(\bar a)\|$ である。
  3. $\psi(y,\bar x)$ について、どの $c\in A$ でも $\|\psi(c,\bar a)\|\subseteq\|\exists y\,\psi(y,\bar a)\|$ であり、等号となる $c\in A$ がある。
証明を開く

1:項の式は項の構成についての帰納法で、直積の定義そのものから従う。$R(t_1,\dots,t_k)$ の形は関係の解釈の定義から、$t_1=t_2$ の形は「2 つの関数 $I\to\bigcup_iA_i$ が等しいのは全成分が等しいとき」から従う。2:定義から明らか。3:包含は、$A_i\models\psi(c(i),\bar a(i))$ なら $A_i\models\exists y\,\psi(y,\bar a(i))$ だからである。等号となる $c$ は、選択公理 により、$i\in\|\exists y\,\psi(y,\bar a)\|$ では $A_i\models\psi(c(i),\bar a(i))$ となる $c(i)$ を、それ以外の $i$ では $A_i$ の任意の元を選べば得られる($A_i$ は空でない)。$\square$

2 と、3 の包含は MVA25 Lemma 2.8(p. 6)にある(同論文は $\exists$ の真理集合を $c$ についての和集合として述べる)。

主定理

Feferman–Vaught の定理(直積)

$L$ の各論理式 $\varphi(x_1,\dots,x_n)$ に対し、自由変数が $x_1,\dots,x_n$ の中にある $L$ の論理式 $\psi_1,\dots,\psi_m$ と、Boole 論理式 $\Phi(y_1,\dots,y_m)$ があって、次が成り立つ。空でない集合 $I$、空でない $L$ 構造の族 $(A_i)_{i\in I}$、$\bar a\in(\prod_iA_i)^n$ がどれであっても
$$ \prod_{i\in I}A_i\models\varphi(\bar a)\iff\mathcal P(I)\models\Phi\bigl(\|\psi_1(\bar a)\|,\dots,\|\psi_m(\bar a)\|\bigr). $$
$\Phi$ と $\psi_j$ は $\varphi$ から機械的に求められる。

出典

MVA25 Proposition 2.6(p. 6)の形であり、同論文はこれを Feferman と Vaught の一般化積についての基本定理(MVA25 Fact 2.5、p. 5。原論文の Theorem 3.1 とされる)から導いている。以下では一般化積を経ずに、論理式の構成についての帰納法で直接に証明する。

組 $(\Phi;\psi_1,\dots,\psi_m)$ が $\varphi$ について上の同値を満たすとき、これを $\varphi$ の 表示 と呼ぶ。論理式は原子論理式から $\lnot$、$\land$、$\exists$ で作られるとしてよい($\lor,\to,\forall$ はこれらで書ける)。

論理式の構成についての帰納法

原子論理式. lem-fv-basic の 1 により、$(y_1=1;\ \varphi)$ が表示である。
否定と連言. $(\Phi;\bar\psi)$ が $\varphi$ の表示なら $(\lnot\Phi;\bar\psi)$ は $\lnot\varphi$ の表示である。$(\Phi;\psi_1,\dots,\psi_m)$ が $\varphi$ の、$(\Phi';\psi'_1,\dots,\psi'_k)$ が $\varphi'$ の表示なら、
$$ \bigl(\Phi(y_1,\dots,y_m)\land\Phi'(y_{m+1},\dots,y_{m+k});\ \psi_1,\dots,\psi_m,\psi'_1,\dots,\psi'_k\bigr) $$
は $\varphi\land\varphi'$ の表示である。自由変数の条件も保たれる。
存在量化. $(\Phi;\psi_1,\dots,\psi_m)$ を $\varphi(y,\bar x)$ の表示とし、$\exists y\,\varphi$ の表示を作る。$[m]:=\{1,\dots,m\}$ の部分集合 $s$ ごとに
$$ \theta_s:=\bigwedge_{j\in s}\psi_j\land\bigwedge_{j\notin s}\lnot\psi_j $$
とおく。どの $c\in A$、$\bar a$ についても、lem-fv-basic の 2 により、真理集合 $Z_s:=\|\theta_s(c,\bar a)\|$($s\subseteq[m]$)は $I$ を互いに交わらない集合に分け(空の部分があってよい)、$\|\psi_j(c,\bar a)\|=\bigcup_{s\ni j}Z_s$ である。そこで変数 $z_s$($s\subseteq[m]$)の Boole 論理式
$$ \Phi^*(\bar z):=\Phi\Bigl(\bigsqcup_{s\ni1}z_s,\dots,\bigsqcup_{s\ni m}z_s\Bigr) $$
をとると(空の結びは $0$)、$A\models\varphi(c,\bar a)\iff\mathcal P(I)\models\Phi^*(\|\theta_s(c,\bar a)\|)_s$ である。さらに
$$ \Phi'(\bar w):=\exists\bar z\,\Bigl(\bigsqcup_sz_s=1\land\bigwedge_{s\ne t}z_s\sqcap z_t=0\land\bigwedge_sz_s\sqcap w_s=z_s\land\Phi^*(\bar z)\Bigr),\qquad\psi'_s:=\exists y\,\theta_s $$
とおく。$\Phi'(\bar w)$ は「$I$ の分割 $(z_s)_s$ で、各 $z_s\subseteq w_s$ かつ $\Phi^*(\bar z)$ を満たすものがある」という意味である。$(\Phi';(\psi'_s)_s)$ が $\exists y\,\varphi$ の表示であることを示す。$\psi'_s$ の自由変数は $\bar x$ の中にある。
($\Rightarrow$) $A\models\varphi(c,\bar a)$ となる $c$ をとり、$Z_s:=\|\theta_s(c,\bar a)\|$ とする。これは $I$ の分割で、$\Phi^*(\bar Z)$ が成り立ち、lem-fv-basic の 3 により $Z_s\subseteq\|\psi'_s(\bar a)\|$ である。
($\Leftarrow$) $I$ の分割 $(Z_s)_s$ が $Z_s\subseteq\|\psi'_s(\bar a)\|$ と $\Phi^*(\bar Z)$ を満たすとする。各 $i\in I$ はただ一つの $Z_s$ に属し、$i\in\|\exists y\,\theta_s(y,\bar a)\|$ なので、選択公理により $A_i\models\theta_s(c(i),\bar a(i))$ となる $c(i)\in A_i$ を選べる。こうして得た $c\in A$ について、各 $s$ で $Z_s\subseteq\|\theta_s(c,\bar a)\|$ である。左右とも $I$ の分割なので等号が成り立つ($i\in\|\theta_s(c,\bar a)\|$ が $Z_t$ に属せば $i\in\|\theta_t(c,\bar a)\|$ で、交わらないので $t=s$)。よって $\Phi^*(\|\theta_s(c,\bar a)\|)_s$ が成り立ち、$A\models\varphi(c,\bar a)$、すなわち $A\models\exists y\,\varphi(\bar a)$ である。
各段の構成は $\varphi$ の形だけで決まり、族にも $I$ にもよらないので、帰納法により定理が成り立つ。$\square$

存在量化の段で真理集合を分割に直したのは、成分ごとに証人を選ぶとき、各添字で「どの $\psi_j$ を成り立たせるか」を一つに決めておく必要があるからである。分割にしないと、$\|\exists y\,\psi_1\|$ と $\|\exists y\,\psi_2\|$ がそれぞれ大きくても、同じ証人で両方を満たせるとは限らない。

帰結

文 $\sigma$(自由変数のない論理式)の表示 $(\Phi;\psi_1,\dots,\psi_m)$ では $\psi_j$ も文で、$\|\psi_j\|=\{i\mid A_i\models\psi_j\}$ は各因子の理論だけで決まる。

初等同値は直積で保たれる

$(A_i)_{i\in I}$、$(B_i)_{i\in I}$ を同じ添字集合の空でない $L$ 構造の族とし、すべての $i$ で $A_i\equiv B_i$ とする。このとき $\prod_iA_i\equiv\prod_iB_i$ である。より詳しく、$\prod_iA_i$ の理論は、写像 $i\mapsto\operatorname{Th}(A_i)$ だけで決まる。

文 $\sigma$ の表示を $(\Phi;\psi_1,\dots,\psi_m)$ とする。$A_i\equiv B_i$ なので $\{i\mid A_i\models\psi_j\}=\{i\mid B_i\models\psi_j\}$ が各 $j$ で成り立ち、thm-fv-main の右辺は両方の族で同じ Boole 代数 $\mathcal P(I)$ の同じ元についての同じ主張になる。よって $\prod_iA_i\models\sigma\iff\prod_iB_i\models\sigma$ である。後半も同じ理由による。$\square$

直冪

空でない $L$ 構造 $B$ と文 $\sigma$ の表示 $(\Phi;\psi_1,\dots,\psi_m)$ について、$e_j:=1$($B\models\psi_j$)、$e_j:=0$($B\not\models\psi_j$)とおくと
$$ B^I\models\sigma\iff\mathcal P(I)\models\Phi(e_1,\dots,e_m) $$
である。とくに、$B\equiv B'$ なら $B^I\equiv B'^I$、$\mathcal P(I)\equiv\mathcal P(J)$ なら $B^I\equiv B^J$ である。

直冪では $\|\psi_j\|$ は $I$ か $\emptyset$ で、$B\models\psi_j$ かどうかで決まる。thm-fv-main に代入すればよい。後半の 2 つ目は、$\Phi(e_1,\dots,e_m)$ が $0,1$ だけを含む Boole 論理の文なので、$\mathcal P(I)$ と $\mathcal P(J)$ で真偽が同じことによる。$\square$

MVA25 Fact 2.9(p. 7)は、無限の原子的 Boole 代数の理論が、「少なくとも $k$ 個の原子の上にある」を表す述語 $A_k$ を足した言語で量化記号を消去できることを、Poizat の教科書を引いて述べている(量化記号消去)。$I$ が無限なら $\mathcal P(I)$ は無限の原子的 Boole 代数で、量化記号のない文は $0,1$ と $A_k$ だけの原子文の組み合わせであり、どの無限の原子的 Boole 代数でも真偽が同じ($A_k(1)$ は真、$A_k(0)$ は偽、$0\ne1$)である。したがって $I,J$ が無限なら $\mathcal P(I)\equiv\mathcal P(J)$ で、cor-fv-power により $B^I\equiv B^J$ となる。直冪の理論は、添字集合が無限である限り、その大きさによらない。

例

体の直積は体でない

$I$ を 2 個以上の元をもつ集合、$A_i$ を体とする。体の公理のうち $\sigma:=\forall x\,(x\ne0\to\exists y\,(xy=1))$ はすべての $A_i$ で成り立つが、$\prod_iA_i$ では成り立たない。$i_0\in I$ を一つとり、$a(i_0)=1$、それ以外の成分を $0$ とすると $a\ne0$ である。$ab=1$ なら $i\ne i_0$ の成分で $0\cdot b(i)=1$ となり矛盾する。thm-fv-main の言葉では、$\| x=0\|$ が $I$ でも $\emptyset$ でもない元があるので、$\sigma$ の表示の $\Phi$ は「真理集合が $I$ に等しい」という形にはならない。$\lvert I\rvert=1$ なら直積は $A_{i_0}$ と同型で $\sigma$ が成り立つので、$\sigma$ の真偽は添字集合の大きさにもよる。

初等同値な体の直冪

複素数体 $\mathbb C$ と有理数体の代数閉包 $\overline{\mathbb Q}$ は、どちらも標数 $0$ の代数閉体で初等同値である(Łoś–Vaughtの判定法 の例「代数閉体の理論」)。cor-fv-equivalence により、どの集合 $I$ についても環として $\mathbb C^I\equiv\overline{\mathbb Q}^I$ である。$I=\mathbb N$ なら左辺は濃度 $2^{\aleph_0}$、右辺も濃度 $2^{\aleph_0}$ だが、$I$ が有限なら $\overline{\mathbb Q}^I$ は可算で $\mathbb C^I$ は非可算であり、同型ではない。同じように、順序の言語で $(\mathbb Q,<)\equiv(\mathbb R,<)$ から $(\mathbb Q,<)^I\equiv(\mathbb R,<)^I$ が従う。直積の順序は成分ごとの順序で、$\lvert I\rvert\ge2$ なら全順序ではない。

長さ 2 の直積での計算

$I=\{1,2\}$ では $\mathcal P(I)$ は 4 元の Boole 代数で、thm-fv-main は直積 $A_1\times A_2$ での真偽を、$\psi_j$ が「両方で真」「$A_1$ だけで真」「$A_2$ だけで真」「どちらでも偽」のどれかという有限の情報から求める。例えば環 $R_1\times R_2$ の元 $(a_1,a_2)$ が単元であることは $\|\exists y\,(xy=1)\|=I$、零因子か $0$ であること($\exists y\,(y\ne0\land xy=0)$)は $\|\exists y\,(y\ne0\land xy=0)\|\ne\emptyset$ と同値である。実際、$y\ne0$ ならある成分 $y_i\ne0$ で $a_iy_i=0$ となり、逆に $a_iy_i=0$、$y_i\ne0$ となる成分 $i$ があれば、その成分に $y_i$ を置き残りを $0$ にした元が証人になる。単元の条件は「全成分で」、零因子の条件は「ある成分で」という形の $\Phi$ になる。

一般化積と精密化

Feferman と Vaught の元の定理は、直積より広い 一般化積 についてのものである。MVA25 Definition 2.3・2.4(p. 5)は、表示 $(\Phi;\psi_1,\dots,\psi_m)$ ごとに「$\mathcal P(I)\models\Phi(\|\psi_1(\bar a)\|,\dots)$ となる組 $\bar a$ の全体」を関係とする構造を 完全一般化積 と呼び、Fact 2.5(p. 5)として、この構造のどの論理式もある表示の関係と同値であること(量化記号の消去の形)を述べている。thm-fv-main は、直積の原子論理式が完全一般化積の関係で書けることから、その特別な場合として得られる(同 Proposition 2.6 の証明)。$L_{\mathrm{Bool}}$ に「有限集合である」などの述語を足せば、有限個を除いて条件を課す積なども同じ枠組みで扱える(同 p. 5)。
超フィルター $\mathcal U$ による商である超積では、Łośの定理 により $\varphi(\bar a)$ の真偽は $\|\varphi(\bar a)\|\in\mathcal U$ かどうかで決まる。直積の場合は、真理集合についての判定が Boole 論理式 $\Phi$ で与えられる点で、Łoś の定理と同じ形をしている。
$I$ が無限のとき、MVA25 Lemma 2.10・Corollary 2.11(pp. 7–8)は Fact 2.9 を使って $\Phi$ を量化記号のない形にとれることを示し、直積で定義可能な集合は「$\psi(\bar x,\bar b)$ が少なくとも $k$ 個の添字で成り立つ」という形の集合の有限個の Boole 結合であることを導いている。同論文はこれを使って、素数 $p$ についての有限体 $\mathbb F_p$ の直積の中で、整数の写し $\{n\cdot(1,1,\dots)\mid n\in\mathbb Z\}$ が定義可能でないことを示している(p. 6 の Theorem 2.7 とその後の説明)。

反例:仮定を外すと成り立たないこと

外した仮定例成り立たなくなる結論
$\varphi$ が原子論理式(lem-fv-basic の 1 の「全成分で真なら直積で真」)ex-fv-fields の文 $\sigma$ と 2 個以上の体の族$\sigma$ は全成分で真だが直積で偽
添字集合が同じ(cor-fv-equivalence)$A_1=B_1=B_2=\mathbb Z/2\mathbb Z$(群)、$I=\{1\}$、$J=\{1,2\}$$\prod_{i\in I}A_i$ は 2 元、$\prod_{j\in J}B_j$ は 4 元で、「ちょうど 2 元」という文で区別され初等同値でない
$I,J$ が無限(cor-fv-power の後の注意)$B=\mathbb Z/2\mathbb Z$、$I=\{1\}$、$J=\{1,2\}$$B^I\equiv B^J$ が成り立たない(元の個数が違う)

cor-fv-equivalence の逆も成り立たない。$A=\mathbb Z/2\mathbb Z$、$B=(\mathbb Z/2\mathbb Z)^2$ とすると、$\mathbb N$ と $\mathbb N\times\{1,2\}$ の全単射から $A^{\mathbb N}\cong B^{\mathbb N}$ なので直冪は初等同値だが、$A$ は 2 元、$B$ は 4 元で $A\not\equiv B$ である。

関連項目

参考文献

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する