¿Qué teorías se conservan bajo el producto?

La definición de producto que sugiere es, de hecho, la estándar. Puede extenderse naturalmente para definir el producto.$\prod_{i\in I} M_i$de cualquier familia de estructuras$(M_i)_{i\in I}$. Aquí incluiré el caso.$I = \emptyset$. Entonces el producto es la estructura singleton$\{*\}$con$f(*,\dots,*) = *$para cualquier símbolo de función$f$y$R(*,\dots,*)$para cualquier símbolo de relación$R$. A continuación, cuando hablo de fórmulas que se conservan en productos, me refiero a productos de familias arbitrarias de estructuras (incluida la familia vacía, pero comentaré más sobre eso a continuación).

Una respuesta simple (pero no óptima, ver más abajo) a su pregunta es que las fórmulas estrictas de Horn se conservan bajo los productos.

Una fórmula básica estricta de Horn tiene la forma$\left(\bigwedge_{i=1}^n \varphi_i(x)\right)\rightarrow \psi(x)$, donde cada uno de los$\varphi_i(x)$y$\psi(x)$son fórmulas atómicas. Permitimos el caso$n = 0$, por lo que cualquier fórmula atómica es una fórmula básica de Horn. Una fórmula estricta de Horn se construye a partir de fórmulas básicas de Horn por$\land$,$\forall$, y$\exists$(pero no$\lor$o$\lnot$).

Puede verificar que las fórmulas básicas estrictas de Horn se conservan en los productos y luego probar por inducción que todas las fórmulas estrictas de Horn se conservan en los productos. De esto se sigue que si$T$es cualquier teoría y$S$es el conjunto de todas las oraciones de Horn estrictas que están implicadas por$T$, entonces cualquier producto de modelos de$T$es un modelo de$S$.

¿Qué hace allí la palabra "estricto"? Bueno, podemos definir la fórmula básica de Horn y la fórmula de Horn exactamente de la misma manera, excepto que también permitimos$\psi(x)$ser la fórmula contradictoria$\bot$. Una definición más común (y equivalente) es que una fórmula básica de Horn es una de la forma$\bigvee_{i=1}^n \varphi_i(x)$, donde a lo sumo uno de los$\varphi_i$es una fórmula atómica, y el resto son fórmulas atómicas negadas. El punto es que las fórmulas estrictas de Horn se conservan bajo productos arbitrarios, mientras que las fórmulas de Horn solo se conservan bajo productos de familias de estructuras no vacías .

Tenga en cuenta que el axioma de los dominios integrales$\forall x\forall y\,(xy = 0\rightarrow (x = 0\lor y = 0))$no es una oración de Horn (estricta), y el hecho de que este axioma no se conserve bajo los productos prueba que no es equivalente a una oración de Horn (estricta). Del mismo modo la oración$\forall x\exists y\, (xy = 1)$de la teoría de grupos es una oración de Horn (estricta), y se conserva bajo productos, pero la oración$\forall x \exists y\, (x\neq 0\rightarrow xy = 1)$de la teoría de campos no es una oración (estricta) de Horn (ya que$x\neq 0$no es atómico), y no se conserva bajo los productos.

Todo esto está muy bien, pero plantea la pregunta natural: ¿Se conserva una oración de primer orden bajo productos si y solo si es equivalente a una oración de Horn estricta?

La respuesta es no: las oraciones estrictas de Horn se conservan no solo bajo los productos, sino también bajo la construcción más general de productos reducidos . Y como señala bof en los comentarios, Keisler demostró que una oración de primer orden es equivalente a una oración estricta de Horn si y solo si se conserva bajo productos reducidos. Este es el Teorema 6.2.5 de la Teoría de modelos de Chang y Keisler (al que me referiré como C&K a continuación). Lo que en realidad está probado allí es que una oración es equivalente a una oración de Horn si y solo si se conserva bajo productos reducidos mediante procedimientos adecuados .filtros Tomar un producto reducido por el filtro inadecuado da una estructura singleton, al igual que el producto vacío. Consulte el ejercicio 6.2.8 de C&K para ver la versión sobre oraciones de Horn estrictas y productos reducidos arbitrarios.

Un poco de historia: la demostración original de Keisler del Teorema 6.2.5 (de 1965) asumió la hipótesis del continuo (CH). Esta es la prueba en la Sección 6.2 de C&K. El mismo año, Galvin eliminó la dependencia de CH, y la Sección 6.3 de C&K está dedicada en gran parte a una exposición de la prueba de Galvin. En 1971, Shelah demostró lo que ahora se conoce como el teorema del isomorfismo de Keisler-Shelah , eliminando la dependencia de CH del resultado anterior de Keisler de que dos estructuras son elementalmente equivalentes si y solo si tienen ultrapoderes isomórficos. En este artículo, Shelah afirmó que se podría usar la misma técnica para dar una prueba más clara del teorema 6.2.5 sin CH. El ejercicio 6.2.4 en C&K le pide al lector que resuelva los detalles, y el ejercicio fue resuelto en forma de artículo publicado por George C.Teoremas de conservación sin hipótesis del continuo ).

Para completar la historia, aquí hay información adicional de Chang y Keisler:

• Hay un ejemplo (Ejemplo 6.2.3 en C&K) de una oración que se conserva bajo productos (no vacíos) pero que no se conserva bajo productos reducidos arbitrariamente mediante filtros adecuados (y por lo tanto no es equivalente a una oración Horn). El ejemplo dado es la conjunción de un número finito de axiomas para álgebras booleanas, junto con la oración que afirma que existe un átomo. Este ejemplo se puede modificar fácilmente a uno que se conserva en todos los productos pero que no es equivalente a una oración estricta de Horn reemplazando "existe un átomo" con "$0=1$o existe un átomo".
• Aparentemente, hay una verdadera caracterización de esas oraciones de primer orden preservadas bajo productos. C&K escriben: "Weinstein (1965) dio una caracterización sintáctica de oraciones de producto directo. Dado que su caracterización es muy complicada, no la daremos aquí". De hecho, debe ser muy complicado, porque C&K no evita incluir material extremadamente técnico en otras partes de su libro. La referencia es a la tesis doctoral de Weinstein "Propiedades de primer orden conservadas por producto directo". Parece difícil rastrear esta tesis en línea. ¿Quizás esté en la biblioteca de la Universidad de Wisconsin? Si alguien que lea esto tiene una copia o conoce la caracterización, ¡me gustaría saber de qué se trata!
• Finalmente, C&K muestran (Proposiciones 6.2.8 y 6.2.9) que si una oración universal (existencial, respectivamente) se conserva bajo productos (no vacíos), entonces es equivalente a una oración Horn universal (existencial, respectivamente). Y dan una referencia, nuevamente a la tesis de Weinstein, para el mismo resultado para$\forall\exists$-oraciones. Este es el mejor resultado posible, ya que el contraejemplo sobre los átomos en álgebras booleanas es un$\exists\forall$-oración.

Pude localizar una copia de la tesis de Weinstein (en microfilm, nada menos) y puedo reproducir aquí su caracterización de oraciones de producto directo. Es bastante técnico y algo insatisfactorio porque en lugar de ser una clase de fórmulas definida inductivamente (como las oraciones de Horn y las oraciones estrictas de Horn), es una clase definida en términos de un procedimiento de decisión recursivo.

Hay un argumento en Chang y Keisler de que las oraciones preservadas bajo productos directos finitos se preservan bajo productos directos arbitrarios, así que realmente todo lo que necesitamos hacer es caracterizar las oraciones que se preservan bajo productos directos finitos.

Primero algo de notación. fórmulas dadas$\varphi_0$,$\varphi_1$, y$\varphi$, nosotros escribimos$\varphi_0 \times \varphi_1 \Rightarrow \varphi$para significar que cada vez que$M \models \varphi_0(a_1,\dots,a_n)$y$N \models \varphi_1(b_1,\dots,b_n)$, entonces$M \times N \models \varphi((a_1,b_1),\dots,(a_n,b_n))$. Para cualquier conjunto de fórmulas$S$, nosotros escribimos

• $\neg S$para el conjunto de las negaciones de los elementos de$S$,
• $\exists x S$para el conjunto de fórmulas de la forma$\exists x \varphi$para$\varphi \in S$(para la variable particular$x$),
• $\forall x S$para el conjunto de fórmulas de la forma$\forall x \varphi$para$\varphi \in S$,
• $\bigvee S$para el conjunto de disyunciones finitas de elementos de$S$(incluida la disyunción vacía$\top$),
• $\bigwedge S$para el conjunto de conjunciones finitas de elementos de$S$(incluida la conjunción vacía$\bot$), y
• $\bigwedge^\ast S$para el conjunto de todas las conjunciones consistentes máximas de elementos de$S$.

En el caso de$\bigvee S$y$\bigwedge S$, suponga que tenemos alguna convención razonable fija para enumerar estas fórmulas para evitar la redundancia. (Por ejemplo, podríamos requerir que los disyuntivos/conjuntos se enumeren en algún orden lexicográfico fijo sin repeticiones). En particular, cuando$S$es finito, queremos$\bigvee S$y$\bigwedge S$sea ​​finito, y queremos que los mapas$S \mapsto \bigvee S$y$S \mapsto \bigwedge S$ser computable.

Además, supongamos que elegimos$\bigwedge^\ast S$de modo que$\bigwedge^\ast S \subseteq \bigwedge S$. Una cosa a tener en cuenta es que no hay una forma computable de determinar$\bigwedge^\ast S$como un subconjunto de$\bigwedge S$.

Dejar$(v_n)_{n< \omega}$sea ​​una enumeración de nuestras variables. Dado un conjunto finito de fórmulas atómicas$S$, definimos los siguientes conjuntos finitos de fórmulas atómicas:

• $S_0 = \bigvee \bigwedge (S \cup \neg S)$.
• $S_{n+1} = \bigvee \bigwedge \exists v_n S_n$, cuando$n$incluso.
• $S_{n+1} = \bigvee \bigwedge \forall v_n S_n$, cuando$n$es impar.
• $S^\ast_0 = \bigvee \bigwedge^\ast (S \cup \neg S)$.
• $S^\ast_{n+1} = \bigvee \bigwedge^\ast \exists v_n S^\ast_n$, cuando$n$incluso.
• $S^\ast_{n+1} = \bigvee \bigwedge^\ast \forall v_n S^\ast_n$, cuando$n$es impar.

Algunas cosas a tener en cuenta:

• La secuencia$S_n$es uniformemente computable como una función de$S$, pero la secuencia$S^\ast_n$normalmente no lo será.
• siempre tendremos$S^\ast_n \subseteq S_n$para cada$n<\omega$.
• Cada fórmula es equivalente a una fórmula en$S^\ast_n$para algunos$S$y algo$n$. A fortiori, esto implica que toda fórmula es equivalente a una fórmula en$S_n$para algunos$S$y algo$n$.

Weinstein demostró el siguiente lema:

Lema. Dejar$F$sea ​​un conjunto autónomo finito de fórmulas cerradas bajo$\wedge$y$\vee$hasta la equivalencia. Dejar$u$Sea cualquier variable y sea$\varphi_0$,$\varphi_1$, y$\varphi$ser fórmulas en$\bigvee\bigwedge\exists u F$. la siguiente condición$(\ast)$es suficiente para asegurar que$\varphi_0 \times \varphi_1 \Rightarrow \varphi$.

$(\ast)$Por cada disyunción$\psi_0$de$\varphi_0$y toda disyunción$\psi_1$de$\varphi_1$, hay una disyunción$\psi$de$\varphi$tal que para todo conjunto$\exists u \chi$de$\psi$, hay conjunciones$\exists u \chi_0$de$\psi_0$y$\exists u \chi_1$de$\psi_1$tal que$\chi_0 \times \chi_1 \Rightarrow \chi$.

Además, si$\varphi_0$y$\varphi_1$son elementos de$\bigvee \bigwedge^\ast \exists u F$, entonces$(\ast)$es necesario y suficiente para$\varphi_0 \times \varphi_1 \Rightarrow \varphi$sostener.

Finalmente, las afirmaciones anteriores son válidas para todos los casos de$\exists$reemplazadas con$\forall$.

La definición de conjuntos autónomos se da en Chang y Keisler. Todo lo que es relevante aquí es que nuestros conjuntos$S_n$son todos autónomos.

Este lema motiva la definición del siguiente predicado recursivo primitivo:$R(\varphi_0,\varphi_1,\varphi)$se cumple si y solo si$\varphi_0$,$\varphi_1$, y$\varphi$pertenecen a algunos comunes$S_n$y

• si$n$es$0$, entonces$\varphi_0 \times \varphi_1 \Rightarrow \varphi$;
• si$n$es raro entonces$(\ast\ast)$por cada disyunción$\psi_0$de$\varphi_0$y toda disyunción$\psi_1$de$\varphi_1$, hay una disyunción$\psi$de$\varphi$tal que para todo conjunto$\exists v_{n-1} \chi$de$\psi$hay conjuntos$\exists v_{n-1} \chi_0$de$\psi_0$y$\exists v_{n-1} \chi_1$de$\psi_1$tal que$R(\chi_0,\chi_1,\chi)$sostiene;
• si$n$es par y positivo, entonces$(\ast\ast)$sostiene con$\forall$en lugar de$\exists$.

Este es un predicado computable porque podemos tomar$S$para ser el conjunto de fórmulas atómicas que ocurren en nuestras fórmulas y solo necesitamos verificar$n$eso es aproximadamente tan grande como los rangos cuantificadores de nuestras fórmulas.

El lema enails que$R(x,y,z)$satisface lo siguiente:

• Para cualquier$\varphi_0$,$\varphi_1$, y$\varphi$en algunos$S_n$, si$R(\varphi_0,\varphi_1,\varphi)$sostiene, entonces$\varphi_0 \times \varphi_1 \Rightarrow \varphi$.
• Para cualquier$\psi_0$,$\psi_1$, y$\psi$en algunos$S^\ast_n$, si$\psi_0 \times \psi_1 \Rightarrow \psi$, entonces$R(\psi_0,\psi_1,\psi)$sostiene

En particular, esto significa que una oración$\chi$se conserva bajo productos directos binarios (y por lo tanto productos directos finitos y también productos directos arbitrarios) si y solo si es lógicamente equivalente a una oración$\varphi$en algunos$S_n$tal que$R(\varphi,\varphi,\varphi)$sostiene

Una fórmula (de primer orden) se conserva por factores directos si, siempre que se mantenga en un producto directo$A\times B$, también se cumple en los factores$A$y$B$. Keisler dio algún tipo de caracterización sintáctica complicada de fórmulas conservadas por factores directos: Keisler, HJ, Propiedades conservadas bajo factores directos. Avisos de la Sociedad Matemática Estadounidense, vol. 10 (1963), pág. 302. Resumen 63T–169.

Ahora considere fórmulas de la forma

$$Q[(\varphi_1\to\alpha_1)\land(\varphi_2\to\alpha_2)\land\cdots\land(\varphi_n\to\alpha_n)]\tag1$$ donde cada uno$\alpha_i$es una fórmula atómica, cada$\varphi_i$es una fórmula preservada por factores directos, y$Q$es un prefijo cuantificador. fórmulas de la forma$(1)$son más generales que las fórmulas de Horn y aún se conservan mediante productos directos. Creo que alguien ha conjeturado (¿Weinstein? ¿Keisler?) que toda fórmula que se conserva mediante productos directos es equivalente a una fórmula de la forma$(1)$. Si esto es cierto, combinado con la caracterización de Keisler de fórmulas preservadas por factores, daría una caracterización sintáctica de oraciones preservadas por productos.