¿Dos formas del teorema de Beth?

Question

La versión de Beth del teorema estoy familiarizado con es que si $\phi$ es una frase en el idioma $\Sigma\sqcup \lbrace R\rbrace$ sólo depende de $\Sigma$ (es decir, $\mathcal{M}\upharpoonright\Sigma\cong\mathcal{N}\upharpoonright\Sigma\implies[\mathcal{M}\models\phi\iff\mathcal{N}\models\phi]$ $\mathcal{M},\mathcal{N}$ ($\Sigma\sqcup\lbrace R\rbrace$)-estructuras), entonces existe un $\Sigma$-sentencia de $\psi$ equivalente a $\phi$ (es decir, $\mathcal{M}\models\phi\iff\psi$ todos los $(\Sigma\sqcup\lbrace R\rbrace)$-estructuras de $\mathcal{M}$). Esta es la versión que actualmente se describe en detalle en la página de la wikipedia.

Por otro lado, hay implícito definability teorema (también llamada Beth del teorema?) el cual establece que si $\phi$ es una frase en $\Sigma\sqcup\lbrace R\rbrace$ tal que para cada a $\Sigma$estructura $\mathcal{M}$ no es exactamente una expansión $\mathcal{M}^\phi$ $\Sigma\sqcup R$tal que $\mathcal{M}^\phi\models\phi$, " $R$ ya está definida:" hay algo de $\Sigma$-fórmula $\psi$ tal que $R^{\mathcal{M}^\phi}=\psi^\mathcal{M}$. (Y una versión más fuerte donde "exactamente uno" se sustituye por "en la mayoría de uno.")

Mi pregunta es, ¿cuál es la relación entre estos dos teoremas? Yo vagamente recordar que se puede deducir de cada uno de los otros, pero me parece que no puede trabajar ahora (tal vez, soy de espesor); también, ¿cuáles son sus nombres correctos?

Answer 1

Lo que usted llame a Beth teorema en el primer párrafo es de hecho trivial: acaba de tomar para $\psi$ la frase $\phi$ donde todas las instancias de $R$ son reemplazados por $\bot$ (o cualquier fija $\Sigma$-fórmula, para el caso).

La forma correcta de formular Beth teorema a lo largo de estas líneas es la siguiente:

(B1) Deje $\Sigma\subseteq\Sigma^*$ dos idiomas, $T$ una teoría en la $\Sigma^*$, e $\phi$ $\Sigma^*$a la sentencia. Supongamos que para cada par de modelos de $M,N\models T$ tal que $M\let\res\restriction\res\Sigma\simeq N\res\Sigma$, $M\models\phi$ iff $N\models\phi$. Entonces existe un $\Sigma$-sentencia de $\psi$ tal que $M\models\phi\let\eq\leftrightarrow\eq\psi$ por cada modelo de $M\models T$.

Esto también es más o menos la versión dada en la Wikipedia, con la excepción de que el uso de $=$ en lugar de $\simeq$, y permitir que las fórmulas con variables libres (ambos de los cuales son irrelevantes las diferencias). La presencia de $T$ (y, específicamente, el hecho de que puede no ser $\Sigma$-teoría) es esencial, de lo contrario el resultado es trivial, como se mencionó anteriormente.

La segunda forma de Beth del teorema, en el "más uno" de la versión, puede enunciarse de la siguiente manera:

(B2) Deje $\Sigma\subseteq\Sigma^*$ dos idiomas, $T$ una teoría en la $\Sigma^*$, e $R\in\Sigma^*$. Suponga que $R^M=R^N$ para cada par de modelos de $M,N\models T$ tal que $M\res\Sigma=N\res\Sigma$. Entonces existe un $\Sigma$-fórmula $\psi$ tal que $R^M=\psi^M$ por cada modelo de $M\models T$.

Tenga en cuenta que en los dos (B1) y (B2), una simple aplicación de compacteness muestra que se podría suponer sin pérdida de generalidad que $T$ es finito, por lo tanto en (B2), $T$ desempeña el papel de su $\phi$. La única diferencia es que yo permito $\Sigma^*$ a ser más grande que la de $\Sigma\cup\{R\}$.

Ahora es fácil ver que (B1) y (B2) son equivalentes.

(B1)${}\Rightarrow{}$(B2): Si $\Sigma,\Sigma^*,T,R$ satisfacer los supuestos de (B2), elija nuevo constantes $\vec c$ correspondiente a las variables de $R$, y poner $\Sigma'=\Sigma\cup\{\vec c\}$, $\Sigma'^*=\Sigma^*\cup\{\vec c\}$, $\phi=R(\vec c)$. A continuación, los supuestos de (R1) son satisfechos por $\Sigma',\Sigma'^*,T,\phi$, por lo tanto, no existe un $\Sigma'$-sentencia de $\psi(\vec c)$ equivalente a $\phi$ en los modelos de $T$ (ampliado a $\Sigma'$), lo que significa que $R(\vec x)$ es equivalente a $\psi(\vec x)$ en los modelos de $T$, en el idioma original.

(B2)${}\Rightarrow{}$(B1): Dado $\Sigma,\Sigma^*,T,\phi$ la satisfacción de los supuestos de (B1), vamos a $\Sigma'=\Sigma^*\cup\{R\}$ donde $R$ es un nuevo nullary predicado, y $T'=T\cup\{\phi\eq R\}$. Entonces (B2) implica que hay un $\Sigma$-fórmula $\psi$ (que se puede suponer que tienen la misma libertad de variables como $R$, es decir, ninguno) equivalente a $R$ en los modelos de $T'$. Ya que cada modelo de $T$ puede ser ampliado a un modelo de $T'$, esto implica que $\psi$ es equivalente a $\phi$ en los modelos de $T$. (Si no te gusta nullary predicados, se puede hacer con unario de la misma.)

Las dos versiones de Beth del teorema también puede ser reformulado sintácticamente. Deje $\Sigma^*\smallsetminus\Sigma=\{R_i:i\in I\}$, y deje $R'_i$ ser nuevos predicados con la coincidencia de arity. Con el fin de no ser una carga para la notación demasiado, voy a escribir fórmulas o teorías en $\Sigma^*$ o $\Sigma\cup\{R'_i:i\in I\}$ en la forma $\phi(\vec R)$, como si estos fueron predicados de segundo orden, las variables libres. Entonces (B1) es equivalente a:

(B1') Si $T(\vec R),T(\vec R')\vdash\phi(\vec R)\eq\phi(\vec R')$, hay un $\Sigma$-sentencia de $\psi$ tal que $T(\vec R)\vdash\phi(\vec R)\eq\psi$,

y (B2) es equivalente a

(B2') Si $T(\vec R),T(\vec R')\vdash R_i(\vec x)\eq R'_i(\vec x)$, hay un $\Sigma$-fórmula $\psi$ tal que $T(\vec R)\vdash R_i(\vec x)\eq\psi(\vec x)$.