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 は一般化積について示した。
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$ 構造の族とする。
MVA25 Definition 1.2(p. 3)、Definition 2.2(p. 5)と同じ定義である(同論文は真理集合を $K_\psi(\bar a)$ と書く)。原子論理式では、直積での真偽は真理集合が $I$ 全体かどうかで決まる。
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$ についての和集合として述べる)。
$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$ から機械的に求められる。
組 $(\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$ なら全順序ではない。
$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アソシエイト)の紹介料で運営されています。 支援について / 寄付する