uniformidad en la eliminación del cuantificador

Question

Que $T_0$ ser una teoría coherente. Sea ${\cal T}$ el conjunto de todas las teorías completas que contienen $T_0$.

¿Es cierto que si cada $T\in{\cal T}$ elimina cuantificadores así $T_0$?

Tenga en cuenta. El punto es sobre uniformidad. Asumir cada fórmula $\varphi$ hay un fórmula cuantificador-libre $\psi_T$ tal que $T\vdash \varphi\leftrightarrow\psi_T$. ¿Es posible concluir que no depende que $\psi_T$ $T$?

Ed. Cuando $T_0$ no tiene ninguna modelos finitos, es particularmente interesante.

Answer 1

No, no lo es. Cada finalización de los vacíos de la teoría en el vacío tiene el lenguaje eliminación de cuantificadores, pero el vacío de la teoría en sí misma, no.

Por qué? Además, tenga en cuenta que los únicos datos que faltan en el vacío de la teoría es el tamaño del universo: una finalización de los vacíos de la teoría, ya sea generado por algunos frase de la forma "hay exactamente $n$ muchos elementos," o es generado por el conjunto de oraciones "hay, al menos, $n$ distintos elementos" para todos los $n$. De cualquier manera, en cualquier modelo de $T$ el tipo de una tupla se determina por completo la teoría atómica de la tupla (= que las coordenadas son iguales que los demás, en este caso) para cada extensión de $T$ eliminación de cuantificadores, sino $T$ sí no probar o refutar el cuantificador libre de sentencia $\eta=$"$\exists x\exists y(x\not=y)$", y sinec la única cuantificador libre de penas en el vacío del lenguaje son (equivalente a uno de) $\perp$$\top$, esto significa que el vacío de la teoría de no eliminar los cuantificadores de $\eta$.

---

Nota, sin embargo, que por Konig el lema para cualquier $T_0$ y cualquier fórmula $\psi(\overline{x})$, hay un conjunto finito de fórmulas de $\{\theta_1, ..., \theta_n\}$ tal que $T_0$ demuestra $$\bigvee_{1\le i\le n}\forall \overline{x}(\psi(\overline{x})\iff\theta_i(\overline{x})).$$ (This is a good exercise. HINT: consider the usual tree of consistent extensions of $T_0$, and look at the subtree of consistent extensions which do not yet eliminate quantifiers from $\psi$. Si que subárbol es finito está hecho; de lo contrario, pensar en lo que un camino a través del subárbol conlleva . . .)

---

EDIT: Esto puede ser fácilmente ajustado para evitar finito de modelos. Considerar el lenguaje consta de una sola unario relación símbolo $U$, y la teoría de la $T_0$ consta sólo de los axiomas de la afirmación de que el universo es infinito. La conclusión de $T_0$ se compone de los datos nos dice el tamaño de $U$ e de $\neg U$; es fácil comprobar que cada uno de estos cumple eliminación de cuantificadores, sino $T_0$ no eliminar cuantificadores, por ejemplo, de la frase "$\forall x(U(x))$."

Esto puede parecer barato, desde un modelo de $T_0$ consta básicamente de dos modelos de la teoría por encima de "lado a lado", al menos uno de los cuales es infinito. Sin embargo, se puede producir un montón de ejemplos más.

El fracaso de la eliminación de cuantificadores en $T_0$ está garantizada cuando los $T_0$ es completa para cuantificador libre de penas, pero no es completa (desde entonces $T_0$ no puede eliminar cuantificadores para cualquier frase no decidir), y esto tiene trivialmente si $T_0$ es en un lenguaje relacional (desde luego no tiene trivial cuantificador libre de las penas); más vagamente, el hecho de que la eliminación de cuantificadores mantiene en todas las terminaciones de $T_0$ está garantizado por el contenido de $T_0$ generados ( $T_0$ ) por un "simple" decisión, y de los modelos de la teoría "combinatoria simple." Con esto en mente, podemos construir muchos más ejemplos:

• La teoría de la densa lineal órdenes , posiblemente, con los extremos.

• La teoría de la $\overline{\mathbb{Q}}$-espacios vectoriales de las no especificadas de la dimensión. (Aquí para hacer que la independencia lineal de primer orden definibles, el espacio vectorial es interpretado como un dos clasificados de la estructura, con escalares y vectores; si reemplazamos $\overline{\mathbb{Q}}$ con un campo finito, no importa la forma en que lo presentó.)

Y así sucesivamente.

Otro enfoque es considerar la disyunción de dos teorías que eliminar los cuantificadores. Dada teorías $T_1$ $T_2$ en el mismo idioma, vamos $$T_{1\vee 2}=\{\varphi\vee\psi: \varphi\in T_1, \psi\in T_2\}.$$ Any model of $T_{1\vee 2}$ is either a model of $T_1$ or a model of $T_2$ (suppose not; let $\varphi$ and $\psi$ witness this, and think about $\varphi\v\psi$ . . .), hence $T_{1\vee 2}$ has exactly two completions, each of which eliminate quantifiers, but in general $T_{1\vee 2}$ sí no.

Por ejemplo, el trabajo en el idioma con un solo binario relación símbolo $R$, vamos a $T_1$ ser la teoría del azar gráfico, y $T_2$ ser la teoría de la densa orden lineal sin extremos. A continuación, $T_{1\vee 2}$ no se decide, y por lo tanto (ya que su única cuantificador libre de penas de hasta equivalencia semántica se $\top$$\perp$) no eliminar los cuantificadores de la frase,"$\exists x, y, z(xRy\wedge yRz\wedge \neg xRz)$".

Answer 2

Esta es una adición a @NoahSchweber a responder.

La respuesta es positiva, en algunos casos particulares (por ejemplo, para $T_0=$ACF y casos similares).

Supongamos que todas las terminaciones de $T_0$ son de la forma $T_0\cup S$ donde $S$ es un conjunto de cuantificador libre de penas. Entonces, si todos finalización de $T_0$ han eliminación de cuantificadores, así que no $T_0$.

Por compacidad (o Köning del lema), hay un número finito de cuantificador libre de condenas $\sigma_i$ y el cuantificador libre de fórmulas de $\psi_i(x)$ tal que

$\displaystyle\qquad\sigma_i\vdash\varphi(x)\leftrightarrow\psi_i(x)$, $\qquad\displaystyle T_0\vdash\bigvee^n_{i=1}\sigma_i$, $\qquad\sigma_i\vdash\neg\sigma_j$ para $i\neq j$.

entonces $\displaystyle\quad T_0\vdash\varphi(x)\leftrightarrow\bigvee^n_{i=1}\sigma_i\wedge\psi_i(x)$.