Teorema de Feferman-Vaught

El teorema de Feferman-Vaught ^{[ 1 ]} en teoría de modelos es un teorema de Solomon Feferman y Robert Lawson Vaught que muestra cómo reducir, de manera algorítmica, la teoría de primer orden de un producto de estructuras a la teoría de primer orden de elementos de la estructura.

El teorema se considera uno de los resultados estándar en la teoría de modelos. ^{[ 2 ] [ 3 ] [ 4 ]} El teorema extiende el resultado anterior de Andrzej Mostowski sobre productos directos de teorías . ^{[ 5 ]} Generaliza (a fórmulas con cuantificadores arbitrarios) la propiedad en álgebra universal de que las igualdades (identidades) se extienden a productos directos de estructuras algebraicas (lo cual es una consecuencia de una dirección del teorema de Birkhoff ).

Consideremos una signatura lógica de primer orden L. La definición de estructuras de producto toma una familia de L -estructuras.${\displaystyle \mathbf {A} _{i}}$para${\displaystyle i\in I}$para algún conjunto de índices I y define la estructura del producto ${\displaystyle \mathbf {A} =\prod _{i\in I}\mathbf {A} _{i}}$, que también es una estructura L , con todas las funciones y relaciones definidas punto por punto.

Esta definición generaliza el producto directo en álgebra universal a estructuras para lenguajes que contienen no solo símbolos de función, sino también símbolos de relación.

Si${\displaystyle r(a_{1},\ldots ,a_{p})}$es un símbolo de relación con${\displaystyle p}$argumentos en L y${\displaystyle a_{1},\ldots ,a_{n}\in \Pi _{i\in I}\mathbf {A} _{i}}$son elementos del producto cartesiano , definimos la interpretación de${\displaystyle r}$en${\displaystyle \mathbf {A} }$por

${\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))}$

Cuando${\displaystyle r}$es una relación funcional, esta definición se reduce a la definición de producto directo en álgebra universal .

Para una fórmula de primer orden${\displaystyle \phi ({\bar {x}})}$en signatura L con variables libres un subconjunto de${\displaystyle {\bar {x}}}$y para una interpretación${\displaystyle {\bar {a}}}$de las variables${\displaystyle {\bar {x}}}$, definimos el conjunto de índices${\displaystyle i}$para qué${\displaystyle \phi ({\bar {a}})}$se sostiene en${\displaystyle \mathbf {A} _{i}}$

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

Dada una fórmula de primer orden con variables libres${\displaystyle \phi ({\bar {x}})}$, existe un algoritmo para calcular su forma normal de juego equivalente, que es una disyunción finita.${\displaystyle \bigvee _{i=1}^{k}\theta _{i}({\bar {x}})}$de fórmulas mutuamente contradictorias.

El teorema de Feferman-Vaught proporciona un algoritmo que toma una fórmula de primer orden.${\displaystyle \phi ({\bar {x}})}$y construye una fórmula${\displaystyle \phi ^{*}}$que reduce la condición que${\displaystyle \phi ({\bar {a}})}$mantiene en el producto la condición de que${\displaystyle \phi ^{*}}$sostiene en la interpretación de${\displaystyle k+1}$conjuntos de índices:

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

La fórmula${\displaystyle \phi ^{*}}$es por lo tanto una fórmula con${\displaystyle k+1}$variables de conjunto libres, por ejemplo, en la teoría de primer orden de cuerpos de conjuntos .

A menudo resulta interesante considerar la subestructura de la estructura del producto directo. Si la restricción que define los elementos del producto que pertenecen a la subestructura se puede expresar como una condición sobre los conjuntos de elementos de índice, entonces los resultados se pueden generalizar.

Un ejemplo es la subestructura de elementos de producto que son constantes en todos los índices excepto en un número finito de ellos. Supongamos que el lenguaje L contiene un símbolo constante.${\displaystyle c}$y considere la subestructura que contiene solo esos elementos del producto.${\displaystyle a}$para el cual el conjunto

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

es finito. El teorema reduce entonces el valor de verdad en dicha subestructura a una fórmula.${\displaystyle \phi ^{*}}$en el campo de conjuntos, donde ciertos conjuntos están restringidos a ser finitos.

Una forma de definir productos generalizados es considerar aquellas subestructuras donde los conjuntos${\displaystyle ||\phi (a)||}$pertenecer a algún campo${\displaystyle B}$de conjuntos${\displaystyle X\subseteq I}$de índices (un subconjunto del álgebra de conjuntos potencia)${\displaystyle 2^{I}}$), y donde la subestructura del producto admite pegado. ^{[ 6 ]} Aquí, admitir pegado se refiere a la siguiente condición de cierre: si${\displaystyle a,b}$son dos elementos del producto y${\displaystyle X\in B}$es el elemento del campo de conjuntos, entonces también lo es el elemento${\displaystyle c}$definido por "pegamento"${\displaystyle a}$y${\displaystyle b}$de acuerdo a${\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.}$

El teorema de Feferman-Vaught implica la decidibilidad de la aritmética de Skolem al considerar, a través del teorema fundamental de la aritmética , la estructura de los números naturales con la multiplicación como un producto generalizado (potencia) de estructuras aritméticas de Presburger .

Dado un ultrafiltro en el conjunto de índices${\displaystyle I}$, podemos definir una estructura de cociente en elementos de producto, lo que lleva al teorema de Jerzy Łoś que puede usarse para construir números hiperreales .