フェファーマン・ヴォートの定理

モデル理論におけるフェファーマン・ヴォート定理^{[ 1 ]}は、ソロモン・フェファーマンとロバート・ローソン・ヴォートによる定理であり、構造の積の1階理論を、その構造の要素の1階理論にアルゴリズム的に還元する方法を示している。

この定理は、モデル理論における標準的な結果の 1 つと考えられています。^{[ 2 ] [ 3 ] [ 4 ]}この定理は、理論の直積に関するAndrzej Mostowskiの以前の結果を拡張したものです。^{[ 5 ]}これは、普遍代数における等式 (恒等式) が代数構造の直積に引き継がれるという 性質(これはBirkhoff の定理の一方向の結果です) を (任意の量化子を持つ式に) 一般化しています。

一階述語論理のシグネチャLを考える。積構造の定義は、 L構造の族を取る。$\displaystyle \mathbf {A} _{i}}$のために${\displaystyle i\in I}$あるインデックス集合Iに対して、積構造を定義する。 ${\displaystyle \mathbf {A} =\prod _{i\in I}\mathbf {A} _{i}}$これもL構造であり、すべての関数と関係はポイントごとに定義されます。

この定義は、普遍代数における直積を、関数記号だけでなく関係記号も含む言語の構造に一般化するものである。

もし${\displaystyle r(a_{1},\ldots ,a_{p})}$は関係記号です${\displaystyle p}$Lの引数と${\displaystyle a_{1},\ldots ,a_{n}\in \Pi _{i\in I}\mathbf {A} _{i}}$はデカルト積の要素であり、 の解釈を定義します。${\displaystyle r}$で${\displaystyle \mathbf {A} }$による

$\displaystyle \mathbf {A} \models r(a_{1},\ldots ,a_{p})\iff \forall i\in I,\ \mathbf {A} _{i}\models r(a_{1}(i),\ldots ,a_{p}(i))}$

いつ${\displaystyle r}$これは関数関係であり、この定義は普遍代数における直積の定義に帰着する。

一次式の場合${\displaystyle \phi ({\bar {x}})}$自由変数を持つ署名Lの部分集合${\displaystyle {\bar {x}}}$解釈のために${\displaystyle {\bar {a}}}$変数の${\displaystyle {\bar {x}}}$インデックスの集合を定義します${\displaystyle i}$そのために${\displaystyle \phi ({\bar {a}})}$保持する$\displaystyle \mathbf {A} _{i}}$

${\displaystyle ||\phi ({\bar {a}})||=\{i\mid \mathbf {A} _{i}\models \phi ({\bar {a}}(i))\}}$

自由変数を含む一次式が与えられた場合${\displaystyle \phi ({\bar {x}})}$等価なゲーム正規形を計算するアルゴリズムがあり、それは有限の選言である。${\displaystyle \bigvee _{i=1}^{k}\theta _{i}({\bar {x}})}$互いに矛盾する公式の。

フェファーマン・ヴォートの定理は、一次式を入力とするアルゴリズムを与える。${\displaystyle \phi ({\bar {x}})}$そして式を構築する$\displaystyle \phi ^{*}}$それは、${\displaystyle \phi ({\bar {a}})}$製品には以下の条件が満たされている。$\displaystyle \phi ^{*}}$解釈において保持する${\displaystyle k+1}$インデックスのセット:

${\displaystyle I,||\theta _{i}({\bar {a}})||,\ldots ,||\theta _{k}({\bar {a}})||}$

式$\displaystyle \phi ^{*}}$したがって、は式である。${\displaystyle k+1}$例えば、集合体の第一階理論における自由集合変数。

直接積構造の部分構造を考察することは、しばしば興味深い。部分構造に属する積要素を定義する制約が、インデックス要素の集合に対する条件として表現できる場合、結果を一般化することができる。

一例として、有限個のインデックスを除くすべてのインデックスで定数である積要素の部分構造が挙げられる。言語Lには定数記号が含まれていると仮定する。${\displaystyle c}$そして、それらの製品要素のみを含む部分構造を検討する。${\displaystyle a}$セット

${\displaystyle \{i\mid {\textbf {A}}_{i}\models a(i)\neq c\}}$

は有限である。定理は、そのような部分構造における真理値を式に還元する。$\displaystyle \phi ^{*}}$集合の分野では、特定の集合は有限であるという制約がある。

一般化された積を定義する一つの方法は、集合が${\displaystyle ||\phi (a)||}$ある分野に属する${\displaystyle B}$セットの${\displaystyle X\subseteq I}$インデックスのサブセット（冪集合代数）${\displaystyle 2^{I}}$）、かつ製品のサブストラクチャが接着を許容する場合。^{[ 6 ]}ここで接着を許容するとは、次の閉鎖条件を指します。${\displaystyle a,b}$2 つの製品要素があり、${\displaystyle X\in B}$が集合体の要素であるならば、 も集合体の要素である。${\displaystyle c}$「接着」によって定義される${\displaystyle a}$そして${\displaystyle b}$によると${\displaystyle X}$:

${\displaystyle c(i)=\left\{{\begin{array}{rl}a(i),&{\mbox{ if }}i\in X\\b(i),&{\mbox{ if }}i\in (I\setminus X)\end{array}}\right.}$

フェファーマン・ヴォートの定理は、算術の基本定理を通して、乗法を伴う自然数の構造をプレスバーガー算術構造の一般化された積（冪乗）として捉えることで、スコレム算術の決定可能性を示唆する。

インデックスの集合上の超フィルタが与えられた場合${\displaystyle I}$積要素上に商構造を定義することができ、それによって超実数を構成するために使用できるイェジー・ウォシの定理が得られます。