¿Admite toda teoría completa la eliminación de cuantificadores? Sé que, al menos en algunos casos sencillos, lo contrario es cierto; como algunas reducciones de la teoría de los números.Gracias
Respuestas
¿Demasiados anuncios?
toohool
Puntos
549
No, no toda teoría completa tiene eliminación de cuantificadores.
Tome $\mathcal{L} = \{U\}$ donde $U$ es un símbolo de función unitaria. Y toma la estructura $\mathbf{N} = (\mathbb{N}, S)$ donde $S$ es la función sucesora.
Entonces, por supuesto $\operatorname{Th}(\mathbf{N})$ está completo. Pero las únicas fórmulas atómicas en una variable son de la forma $S^n(x) = S^m(x)$ para algunos $n,m \in\mathbb{N}$ . Y porque $S$ es uno a uno esto es lo mismo que $S^k(x) = x$ para algunos $k \in\mathbb{N}$ .
Para $k = 0$ esto define $\mathbb{N}$ y para $k \geq 1$ esto define $\varnothing$ .
Así, toda fórmula libre de cuantificadores en una variable define $\mathbb{N}$ o $\varnothing$ .
Sin embargo, el conjunto $\{0\}$ es definible en una variable libre por $\forall y S(y) \neq x$ .
Así que $\operatorname{Th}(\mathbf{N})$ no puede tener la eliminación del cuantificador.
Camilo Arosemena
Puntos
4069
Dejemos que $G=(V,E)$ sea un grafo contable tal que existe un punto $a\in{V}$ tal que para todo $b\in{V}$ , $(a,b)\notin{E}$ y $E\neq{\emptyset}$ .
Dejemos que $L=\{R\}$ , donde $R$ es una relación binaria. Sea $\mathcal{M}$ sea el modelo de $G$ en la lengua $L$ . Poner $T=Th(\mathcal{M}),$ afirmamos que $T$ no tiene eliminación de cuantificadores.
Supongamos que no es así, entonces todos los mapas $f:N\rightarrow M$ tal que $N$ es un subconjunto finito de $M$ y, por tanto, una subestructura de $\mathcal M$ como $L$ es un lenguaje relacional, y $f:N\rightarrow Im(f)$ es un isomorfo, son incrustaciones elementales en $\mathcal M$ .
Pero como $E\neq\emptyset$ Hay $b,c\in V$ tal que $(b,c)\in E$ , entonces el mapa $f=\{(a,b)\}$ es un isomorfismo entre las subestructuras $\{a\}$ y $\{b\}$ Sin embargo $f:\{a\}\rightarrow M$ no es elemental.
En otro puesto He dado un ejemplo de cómo la teoría de campos reales cerrados en el lenguaje $(0,1,+,\cdot)$ no tiene q.e. (aunque sea un modelo completo).
En cuanto a la otra pregunta, utilizando la caracterización de q.e. por completitud subestructural (que, de nuevo, he explicado en ese post) se puede ver que si una teoría tiene q.e. Y tiene un símbolo constante Y decide todas las oraciones libres de cuantificadores (es decir, fórmulas sin variables), entonces es completa (lo que probablemente cubre tus reducciones de la teoría de números, ya que probablemente tendrían un símbolo para $0$ o $1$ ).
Sin constantes no tiene por qué ser cierto. Considere el lenguaje $\{P\}$ con un predicado unario, y la teoría que dice que el modelo es infinito y que todos sus elementos coinciden en $P$ . Está claro que no es completa, pero tiene q.e. (que es fácil de comprobar directamente, o por completitud subestructural).
