¿Cómo es el Gödel ' s Teorema de completitud no una tautología?

Question

Como físico, tratando de entender los fundamentos de la matemática moderna (en particular el Modelo de la Teoría de la) $-$ I tienen dificultades para hacer frente con la frontera entre la sintaxis y la semántica. Creo que mucho sería más claro para mí, si he dicho lo que pienso de la Gödel Integridad del Teorema es de aproximadamente (después de estudiar varios materiales incluyendo Wikipedia parece redundante para mí) y alguien que conozca del tema para aclarar mis ideas. Así que aquí va:

Como yo lo entiendo, si tenemos un conjunto $U$, con una estructura particular (funciones, relaciones, etc.) podemos interpretar (a través de una firma en particular, por ejemplo, firma de grupo $\{ e,\cdot \}$ ), como un modelo de $\mathfrak{A}$ para una cierta teoría matemática $\mathcal{T}$ (una teoría es un conjunto de axiomas y sus consecuencias). La teoría es satisfecho por $\mathfrak{A}$ si $U$'s de la estructura satisface los axiomas.

Introduzca el teorema de Gödel: Para todos los de primer orden de la teoría de la $\mathcal{T}$ :

$$\left( \exists \textrm{modelo } \mathfrak{A}: \mathfrak{A} \modelos \mathcal{T} \right) \ffi \mathcal{T} \textrm{ es consistente}$$ Así que estoy confundido. No $\mathcal{T}$ ser consistente en un requisito natural que implica que un conjunto $U$, con una estructura correspondiente siempre existe (porque de la ZFC del conjunto de la teoría de la libertad en la construcción de conjuntos como nos plazca sin ningún tipo de preocupaciones con respecto a lo que constituye el conjunto)? Y que a su vez siempre nos permite crear un modelo de $\mathfrak{A}$ con una interpretación de la firma de la teoría de la $\mathcal{T}$ en términos de $U$'s de la estructura?

Donde estoy cometiendo errores? ¿Qué conceptos necesito para entender mejor, para ser capaz de comprender apropiadamente este teorema y cuál es el modelo de la teoría de que es y no es? Por favor, ayuda!

Answer 1

Esto puede ayudar a ver las cosas desde una perspectiva más general. Las presentaciones que se centra sólo en la lógica de primer orden puede ocultar el hecho de que las opciones que están implícitos en las definiciones de la lógica de primer orden; la perspectiva general se destacan estas opciones. Quiero escribir esto en detalle, como una referencia.

General "lógicas"

Podemos definir un tipo particular de general "lógica" con la negación. Esta definición es la intención de ser muy general. En particular, se adapta mucho más amplia de tipos de "sintaxis" y "semántica" de la lógica de primer orden.

Un general de la "lógica" que consistirá en:

• Un conjunto de "oraciones" $L$. Estos no tienen que ser frases en el sentido de la lógica de primer orden, que puede ser cualquier conjunto de objetos.

• Una función de $N: L \to L$ que asigna a cada una de las $x \in L$ "negación" o "negación" $N(x)$.

• Un conjunto de "reglas deductivas", que se dan como cierre de la operación en el powerset de $L$. Así que tenemos una función de $c: 2^L \to 2^L$ tal que

  1. $S \subseteq c(S)$ por cada $S \subseteq L$

  2. $c(c(S)) = c(S)$ por cada $S \subseteq L$

  3. Si $S \subseteq S'$$c(S) \subseteq c(S')$.

• Un conjunto de "modelos" $M$. Estos no tienen que ser las estructuras en el sentido de la lógica de primer orden. La única suposición es que cada una de las $m \in M$ viene con un conjunto $v_m \subseteq L$ de las sentencias que están "satisfechos" (en algún sentido) por $M$:

  1. Si $S \subseteq L$ $x \in v_m$ por cada $x \in S$ $y \in v_m $ por cada $y \in c(S)$

  2. No es $m \in M$ $x \in L$ $x \in v_m$ $N(x) \in v_m$

La naturaleza exacta de las "sentencias", "reglas deductivas", y de "modelos", y la definición de un modelo de "satisfacer" una oración es irrelevante, siempre y cuando satisfagan los axiomas mencionados anteriormente. Estos axiomas son compatibles con los clásicos y de intuitionistic lógica. También son compatibles con infinitary lógicas tales como $L_{\omega_1, \omega}$, con modal, la lógica, y otros sistemas lógicos.

La principal restricción en general "lógica" es que hemos incluido una noción de negación o el rechazo de la definición general de una "lógica" de modo que podemos hablar acerca de la consistencia.

• Decimos que un conjunto a $S \subseteq L$ es sintácticamente consistente si no es $x \in L$ tal que $x$ $N(x)$ están en $c(S)$.

• Podemos decir $S$ es semánticamente consistente si hay un $m \in M$ tal que $x \in v_m$ todos los $x \in S$.

La definición general de una "lógica" está diseñado para que implican que cada semánticamente coherente de la teoría de la sintaxis coherente.

La lógica de primer orden como una lógica general

Para ver cómo la definición general de una "lógica" que funciona, aquí es cómo ver la lógica de primer orden en cualquier fija de la firma como un general "lógica". Fijar una firma de $\sigma$.

• $L$ será el conjunto de todos los $\sigma$frases.

• $N$ va a tomar una frase $x$ y regresar $\lnot x$, canónica de la negación de la $x$.

• $c$ tomará $S \subseteq L$ y devolver el conjunto de todos los $\sigma$frases comprobable de $S$.

• $M$ será el conjunto de todos los $\sigma$-estructuras. Para cada $m \in M$, $v_m$ está dada por la costumbre Tarski definición de la verdad.

Con estas definiciones, la consistencia sintáctica y coherencia semántica en el sentido general coinciden con la consistencia sintáctica y coherencia semántica como usualmente definida por la lógica de primer orden.

El teorema de completitud

Gödel integridad del teorema dice simplemente que, si tratamos a la lógica de primer orden en una parte fija de la firma como un general "lógica" (como el anterior), entonces sintáctica consistencia es equivalente a la coherencia semántica.

El beneficio de la perspectiva general es que podemos ver cómo las cosas podrían ir mal si vamos a cambiar sólo una parte de la interpretación de la lógica de primer orden con la firma de $\sigma$ como un general "lógica":

1. Si vamos a reemplazar$c$, con una débil operador, sintáctico consistencia no puede implicar la coherencia semántica. Por ejemplo, podríamos tomar a $c(S) = S$ todos los $S$. Entonces no sería sintácticamente coherente de teorías que no tienen ningún modelo. En términos prácticos, lo $c$ más débil significa la eliminación de la deducción de reglas.

2. Si vamos a reemplazar $M$ con una pequeña clase de modelos, sintáctico consistencia no puede implicar la coherencia semántica. Por ejemplo, si nos tomamos $M$ a ser el conjunto de finito $\sigma$-estructuras, no son sintácticamente coherente de teorías que no tienen ningún modelo. En términos prácticos, lo $M$ más pequeño significa la exclusión de algunos de estructuras de consideración.

3. Si vamos a reemplazar $c$ con un fuerte cierre de operador, la coherencia semántica no puede implicar sintáctica consistencia. Por ejemplo, podríamos tomar a $c(S) = L$ todos los $S$. Entonces no sería semánticamente coherente de teorías que son sintácticamente inconsistente. En términos prácticos, lo $c$ más fuerte significa la adición de nuevas reglas de deducción.

Por otro lado, algunos cambios para preservar la equivalencia sintáctica y coherencia semántica. Por ejemplo, si tomamos $M$ a ser el conjunto de finito o contable $\sigma$-estructuras, podemos probar todavía el correspondiente teorema de completitud de la lógica de primer orden. En este sentido, la elección de $M$ a ser el conjunto de todos los $\sigma$-estructuras es arbitraria.

Otros teoremas de completitud

Decimos que el "teorema de completitud" general "lógica" es el teorema que la consistencia sintáctica es equivalente a la coherencia semántica de la lógica.

• Hay una natural teorema de completitud para intuitionistic la lógica de primer orden. Aquí dejamos $c$ es el cierre operador derivados de cualquiera de los habituales sistemas deductivos para intuitionistic lógica, y deje $M$ el conjunto de modelos de Kripke.

• Hay un teorema de completitud de segundo orden de la lógica (en un fijo de la firma) con la semántica de Henkin. Aquí dejamos $c$ es el cierre operador de la derivada de la costumbre deductivo sistema de segundo orden de la lógica, y deje $M$ el conjunto de Henkin modelos. Por otro lado, si dejamos $M$ ser el conjunto de todos los "completa" de los modelos, el correspondiente teorema de completitud falla, debido a que esta clase de modelos es demasiado pequeño.

• Hay similares integridad teoremas para proposicional y de primer orden de la lógica modal utilizando marcos de Kripke.

En cada uno de esos tres casos, el desarrollo histórico que comenzó con un sistema deductivo, y el correspondiente conjunto de modelos fue identificado más tarde. Pero, en otros casos, podemos comenzar con un conjunto de modelos y busca un sistema deductivo (incluyendo, en este sentido, un conjunto de axiomas) que conduce a una generalizada del teorema de completitud. Esto está relacionado con un problema común en el modelo de la teoría, que es determinar si una determinada clase de estructuras es axiomatizable".

Answer 2

La forma usual de la integridad teorema es: $ T \models \phi \implies T \vdash\phi$, o sea que si $\phi$ es verdadera en todos los modelos de $\mathcal{M} \models T$, entonces no es una prueba de $\phi$$T$. Esto es no trivial de la declaración, estructuras y modelos acerca de conjuntos de operaciones y relaciones que cumplen condenas. Las pruebas de ignorar los conjuntos con estructura y da reglas para derivar nuevas frases de edad.

Si usted va a segundo orden de la lógica, esto ya no es cierto. Podemos tener una teoría de la $PA$, que sólo tiene un modelo de $\mathbb N \models PA$, pero hay frases $PA \models \phi$ $PA \not\vdash \phi$ ("cierto, pero no es demostrable" de las oraciones). Esto se deduce del teorema de la incompletitud, que dice que la verdad en el modelo en particular $\mathbb N$ no puede ser sujetado por las pruebas. El camino de primer orden de la lógica evita esto es por el hecho de que una de primer orden de la teoría no se puede definir sólo un modelo $\mathbb N \models PA$. Tiene que admitir también la no-estándar de los modelos (esto se deduce de Lowenheim-Skolem).

Este teorema, junto con la solidez teorema $T\vdash \phi \implies T\models \phi$ dar una fuerte correspondencia entre la sintaxis y la semántica de primer orden de la lógica.

Su principal confusión es que la consistencia aquí es una noción sintáctica, por lo que directamente no tiene nada que ver con los modelos. La correspondencia entre la forma usual de la integridad teorema, y su forma es mediante el uso de una contradicción en lugar de $\phi$, y tomando el contrapositivo. Así que si $T \not \vdash \bot$ ($T$ es coherente), a continuación,$T \not \models \bot$. Es decir, si $T$ es consistente, entonces existe un modelo de $\mathcal M \models T$ tal que $\mathcal M \not \models \bot \iff \mathcal M \models \top$, pero eso es una tautología, por lo que acabamos de conseguir que existe un modelo de $T$.

Answer 3

Usted puede pensar en esto como una prueba de que el conjunto teórico de las construcciones son realmente lo suficientemente potente como para la construcción de modelos de teorías coherentes. Y a la inversa, que el método deductivo prueba de que realmente es lo suficientemente potente como para demostrar que las declaraciones acerca de una teoría que debe ser verdadera en todos los modelos.

A priori, esto no podría haber sido cierto. Aquí está un ejemplo que podría demostrar esto. Vamos a suponer que el primer orden de teoría de los números reales es consistente (más precisamente, de la "teoría de real de campos cerrados"). Podemos construir una nueva teoría mediante la adición a la teoría de los números reales:

• Una nueva constante símbolo $W$
• Un axioma $1 < W$
• Un axioma $1 + 1 < W$
• Un axioma $1 + 1 + 1 < W$
• ... y así sucesivamente

Esta teoría es consistente! En realidad es muy fácil de probar: como sigue.

• La teoría constituida sólo por tomar el primer $N$ de estos nuevos axiomas, más que todos los axiomas es, obviamente, consistente: simplemente podemos interpretar $W$$N + 2$, y obtenemos un modelo de esta teoría.

• Si la teoría constituida por todos estos nuevos axiomas eran inconsistentes, entonces podríamos usar los axiomas para demostrar una contradicción. Sin embargo, las pruebas tienen sólo un número finito de pasos, y por lo que dicha prueba sólo puede utilizar un número finito de los nuevos axiomas. Pero ya hemos demostrado que no se puede derivar una contradicción utilizando sólo un número finito de axiomas.

Sin embargo, no es en absoluto evidente de cómo ir sobre la construcción de un conjunto que podría ser un modelo de una teoría. (al menos, no hasta que he visto la idea de ultrapowers)

---

Puede ser útil saber que las de segundo orden, la lógica es que no se completa, en este sentido, si nos requieren modelos de segundo orden teorías que tienen la propiedad de que la (de segundo orden) tipo de todos los subtipos de $X$ ser interpretado como el juego de poder de la interpretación de $X$.

Esto puede ser interpretado como decir que las reglas para hacer las pruebas de segundo orden, la lógica no es lo suficientemente potente como para probar todas las cosas que deben ser cierto en todos ZFC-conjunto teórico de los modelos de segundo orden de la teoría.

Answer 4

Incluso hoy en día la relación entre todo esto y la computabilidad no es lo suficientemente enfatizada.

¿Qué significa "de acuerdo"? Esto significa que usted no puede deducir una contradicción. Tu medio de la deducción debe ser (1) y (2) eficaz, pero también nos gustaría que fuese (3) completa.

El "sonido" significa que si usted puede deducir $\alpha$$\mathcal T$, $\alpha$ es verdadera en toda la estructura en la que todos los miembros de $\mathcal T$ son verdaderas.

"Efectivo" significa que no hay un algoritmo para comprobar la validez de sus deducciones. Que la mencionada conexión con la computabilidad.

"Completa" significa que usted puede deducir todo lo que usted debería ser capaz de deducir. Si $\alpha$ es verdadera en toda la estructura en la que todos los miembros de $\mathcal T$ son verdaderas, entonces usted debería ser capaz de deducir $\alpha$. "Incompleta" significaría para algunos $\alpha$$\mathcal{T}$, sería el caso de que $\alpha$ es verdadera en toda la estructura en la que todos los miembros de $\mathcal T$ son verdaderas, pero su medio de deducción son insuficientes para demostrar que. Eso significa que $\mathcal{T}\cup\{\sim\alpha\}$ sería coherente! Eso es lo "coherente". Esto significa que usted no puede deducir una contradicción. Pero no habría una estructura en la que todo lo en $\mathcal{T}\cup\{\sim\alpha\}$ es cierto. Sería una constante de la teoría con ningún modelo. "Completa" significa que el método de la deducción de las cosas es suficiente para deducir $\alpha$ $\mathcal{T}$ si $\alpha$ es verdadera en toda la estructura en la que todos los miembros de $\mathcal T$ son verdaderas. Pero eso es lo mismo que decir que si su método de la deducción no es suficiente para demostrar que $\alpha$ es verdadera en toda la estructura en la que todos los miembros de $\mathcal T$ son verdaderas, $\alpha$ es falso en alguna estructura en la que todos los miembros de $\mathcal{T}$. "La estructura" significa que existe una estructura. Así la integridad significa que no existe una estructura de la satisfacción de una teoría, si la teoría es consistente.

Es una consecuencia de Gödel de la incompletitud teorema de que no puede haber teorema de completitud de segundo orden de la lógica. Eso significa que cada método de deducción de segundo orden de la lógica, que es sólido y eficaz es incompleta: no se puede deducir todo lo que usted debería ser capaz de deducir. Lo consistencia significa dependerá, entonces, de que el sistema de la deducción que se use, pero no importa la que sea, habrá algunas teorías consistentes con ningún modelo. Pero van a ser "coherente" sólo porque no son lo suficientemente potente como para encontrar la contradicción.

Answer 5

$T$ es consistente significa que no hay ninguna manera en que usted puede obtener una contradicción con sintáctica manipulaciones. Se trata de una noción sintáctica y significa que mientras usted se pega a las propias reglas acerca de la escritura de pruebas no hay manera de llegar a una conclusión de la forma $\alpha\wedge\neg\alpha$. Es claro de inmediato que sólo porque no hay ninguna manera de escribir una prueba de una contradicción, nos puede venir para arriba con una estructura que "hace $T$ true" en el interior de ($T$ conste que significa que usted puede venir para arriba con una estructura de este tipo)? Si es así, debe haber una "opción obvia" para este tipo de estructura. ¿Cuál sería?

Creo que si usted piensa acerca de las preguntas de arriba verás que Gödel integridad teorema no es tan evidente como se pensó al principio.