Definición apropiada de eliminación de cuantificadores

Question

Yo estudio Marcador de libro "Modelo de la Teoría, Una Introducción". Definición 3.1.1 en la página 72 define la "teoría T tiene la eliminación de cuantificador".

Una teoría de la $T$ eliminación de cuantificadores si para cada fórmula $\phi$ no es un cuantificador fórmula libre de $\psi$ tal que $T \models \phi \leftrightarrow \psi$.

"$T \models \phi \leftrightarrow \psi$", tal y como yo lo veo, en realidad no se define en el Marcador en el libro, pero supongo que con esto él quiere decir $T \models \forall \vec v \; ( \phi \leftrightarrow \psi)$ donde $\vec v$ es la tupla de variables en $FV( \phi ) \cup FV ( \psi )$. ($FV(\phi) =$ conjunto de variables libres de $\phi$.)

Pregunta: Es mi interpretación correcta?

$\psi$ es permitido tener más variables libres parece, a partir de la definición de arriba. Algunos otros recursos (aquí por ejemplo) parecen tener la misma definición de la eliminación de cuantificadores.

Las definiciones anteriores no parecen requerir la siguiente: Cada una de las variables libres de $\psi$ es variable libre de $\phi$ (en particular, si $\phi$ es una frase, a continuación, $\psi$ es la frase también). Vi a otros recursos que requiere. Ahora esto me confundan. Alguien me puede decir una definición adecuada, o decir cual es la más común. Por ejemplo en este recurso en la página 30 de la definición requiere sólo para las fórmulas de $\psi (x_1 , \ldots, x_n )$"$n\geq 1$", pero no entiendo lo que exactamente significa (desde frases no tienen variables libres por lo que todavía están de esta forma por lo tanto podemos acaba de salir de la $n\geq 1$ requisito).

Answer 1

Algunos comentarios acerca de su crítica respecto a algunas de las "imperfecciones" en el Marcador del tratamiento.

Los básicos de la semántica de las definiciones de [página 11] :

Definición 1.1.6 Deje $\phi$ ser una fórmula con variables libres de $\overline v = (v_{i_1}, \ldots, v_{i_n})$, y deje $\overline a = (a_{i_1}, \ldots, a_{i_n}) \in M^m$ [donde $M$ es el universo (o dominio) de la $\mathcal L$estructura $\mathcal M$]. Nos inductivamente definir $\mathcal M \vDash \phi(\overline a)$ como sigue [...].

Entonces [página 14] :

Una $\mathcal L$-teoría de la $T$ es simplemente un conjunto de $\mathcal L$frases.

Y [página 18] :

Definición 1.2.12 Deje $T$ $\mathcal L$- la teoría y la $\phi$ $\mathcal L$a la sentencia. Decimos que $\phi$ es una consecuencia lógica de $T$ y escribir $T \vDash \phi$ si $\mathcal M \vDash \phi$ siempre $\mathcal M \vDash T$.

Por lo tanto, la definición en la página 72 :

Definición 3.1.1 decimos que una teoría de la $T$ eliminación de cuantificadores si para cada fórmula $\phi$ no es un cuantificador fórmula libre de $\psi$ tal que

$T \vDash \phi \leftrightarrow \psi$.

El "problema" - como se señaló - es que no hay una definición de consecuencia lógica para fórmulas en general.

Si tenemos en cuenta el Teorema 3.1.4 :

$T \vDash \forall \overline v(\phi(\overline v) \leftrightarrow \psi (\overline v))$

tenemos exactamente su interpretación.

---

Podemos compararla con Dirk van Dalen, la Lógica y la Estructura (5ª ed - 2013), donde hay un explícito "convención" en la Definición 3.4.4 [página 67] :

(i) $\mathfrak A \vDash \varphi$ fib $\mathfrak A \vDash Cl(\varphi)$, [donde $Cl(\varphi)$ es el universal el cierre de $\varphi$]

[...]

(iv) $\Gamma \vDash \varphi$ fib $(\mathfrak A \vDash \Gamma ⇒ \mathfrak A \vDash \varphi)$ donde $\Gamma \cup \{ \varphi \}$ se compone de frases.

Consulte la página 98 :

Definición 4.1.4 : Una teoría de la $T$ es una colección de frases con la propiedad $T \vdash \varphi ⇒ \varphi \in T$.

Por último, véase el breve tratamiento de eliminación de cuantificadores [página 121] :

Desde $T$ admite eliminación de cuantificadores, hay un cuantificador libre de $\psi(x_1,\ldots, x_n)$ tal que $T \vdash \varphi \leftrightarrow \psi$.

---

Anexo

Tenga en cuenta que en el Marcador del libro introducción [página 4] hay una referencia a José Shoenfield, la Lógica Matemática (1968) como un "fondo en la lógica matemática".

En Shoenfield del libro [página 83] tenemos :

Decimos que [fórmula] $A$ es equivalente a $B$ en [teoría] $T$ si $\vdash_T A \leftrightarrow B$. Decimos que $T$ admite la eliminación de cuantificadores si cada fórmula en $T$ es equivalente en $T$ a abrir una fórmula.

---

2º Addendum

Con respecto a C. C. Chang & H. Jerome Keisler, Modelo de la Teoría (3ª ed, 1990), están en el "mainstream" de la tradición de los modelos de teoría, "restringir" los básicos de la semántica de la definición de la teoría y la consecuencia lógica de las oraciones.

Pero [consulte la página 50] que introducir el tema de la eliminación de cuantificadores de esta manera :

hemos introducido la noción de una sentencia de $\varphi$ ser una consecuencia de un conjunto de $\Sigma$ de las sentencias, en los símbolos $\Sigma \vDash \varphi$. Cuál es el significado que se le dé a $\Sigma \vDash \varphi$ si $\varphi$ es una fórmula? Decimos que una fórmula $\varphi (v_0 \ldots v_n)$ es una consecuencia de $\Sigma$, simbólicamente $\Sigma \vDash \varphi$, iff para cada modelo de $\mathfrak A$ $\Sigma$ y cada secuencia $a_0,\ldots, a_n \in A$, $a_0,\ldots, a_n$ satisface $\varphi$. De ello se deduce que la fórmula $\varphi(v_0 \ldots v_n)$ es una consecuencia de la $\Sigma$ si y sólo si la sentencia $(\forall v_0 \ldots v_n) \varphi(v_0 \ldots v_n)$ es una consecuencia de la $\Sigma$.

Decimos que dos fórmulas de $\varphi, \psi$ $\Sigma$-equivalente iff $\Sigma \vDash \varphi \leftrightarrow \psi$.

Por lo tanto, que demuestren [página 52] :

TEOREMA 1.5.3. Cada fórmula $\varphi$ $\Delta$- equivalente a una fórmula $\psi$ [donde $\Delta$ es la teoría de la densa simple orden sin extremos].

Answer 2

Sí, su interpretación es la correcta. De hecho, la escritura $T \models \varphi$ $\mathcal L$- teoría de la $T$ debe implicar que $\varphi$ $\mathcal L$a la sentencia. Pero los modelos teóricos son muy libres (sin juego de palabras) con las variables de$^{[1]}$ : si $\varphi(\bar x)$ $\mathcal L$- fórmula, sin duda, es una $(\mathcal L \cup \bar x)$-frase (donde cada $x_i$ ahora es una nueva constante de símbolos). Así que la escritura $T \models \varphi(\bar x)$ $\mathcal L$- teoría de la $T$ es un abuso para $\tilde T \models \varphi(\bar x)$ donde $\tilde T$ es la teoría de la $T$ visto como un $(\mathcal L \cup \bar x)$-teoría.

Ahora un $(\mathcal L \cup \bar x)$-la estructura es sólo una $\mathcal L$-con una estructura de asignación de las variables $x_i$. A continuación, $\tilde T \models \varphi(\bar x)$ si y sólo si, para cualquier $\mathcal L$-estructuras de $\mathfrak M$ que modelos de $T$ y para cualquier asignación $\sigma$ de la $x_i$'s, uno ha $(\mathfrak M,\sigma) \models \varphi(\bar x)$. Que es precisamente la definición de $T \models \forall \bar x \varphi(\bar x)$.

Acerca de la "$n\geq 1$", es una cuestión técnica. Si permites $n=0$ en un lenguaje sin constante, no como ningún cuantificador libre de la frase : no se puede encontrar un cuantificador libre de frase equivalente a $\exists x (x =x)$ por ejemplo. Que requieren $n\geq 1$ obliga a considerar sentencias como la fórmula de la forma $\phi(y)$ : a continuación, un cuantificador fórmula libre como $y=y$ es el adecuado para el anterior problema.

---

[1] escribo $\bar x$ para una tupla $(x_1,\dots,x_n)$ cuando no me importa acerca de la longitud de la $n$. Yo la escriba $\varphi(\bar x)$ cuando las variables libres de $\varphi$ están entre los $x_i$'s.