5 votos

Interacción entre complejidad y segundo teorema de incompletitud

Por lo que estuve leyendo el artículo de Wikipedia sobre Gödel teorema de completitud, la sección en su relación con la integridad. Se dice que la integridad da la existencia de un modelo de la aritmética $\mathcal M \models PA$ donde $\mathcal M \vdash \neg \text{Cons}(PA)$, pero que el número de Gödel de la contradicción no es estándar. Por desgracia, la Wikipedia no da citas para esta afirmación.

¿Por qué la integridad implica la existencia de este modelo? ¿Cómo el número de Gödel de la contradicción de ser no-estándar de evitar la realidad, demostrando que la PA es incompatible? ¿Qué significa "consistente cuando se ve desde fuera"? ¿Cómo funciona eso?

7voto

user27515 Puntos 214

Bueno, hay una cobertura aquí. Si $\mathsf{PA}$ es consistente (que significa en algunos suficientemente agradable meta-teoría, o el "mundo real", no se puede demostrar declaraciones contradictorias), luego por Gödel del Segundo Teorema de la Incompletitud $\mathsf{PA} \not\vdash \mathrm{Cons}(\mathsf{PA})$, y así por un argumento estándar de ello se sigue que $\mathsf{PA} + \neg \mathrm{Cons}(\mathsf{PA})$ es también coherente. Por Gödel Integridad del Teorema no es un modelo de $\mathcal{M}$ de esta teoría. Como $\neg \mathrm{Cons}(\mathsf{PA})$ es una verdadera declaración de ($(\exists x) ( \varphi(x) )$), hay algún objeto $x \in \mathcal{M}$ que exhibe (desde el punto de vista de la $\mathcal{M}$) la inconsistencia de las $\mathsf{PA}$: códigos de prueba de algunos fijos contradicción, el uso de algunos fija la numeración de Gödel.

Ahora si $x$ corresponde a algún tipo de norma número $m \in \mathbb{N}$, luego que el "verdadero" número natural sería el código de una prueba real de una contradicción en $\mathsf{PA}$: el modelo estándar $\mathbb{N}$ "sabe" que cualquiera de las $m$ es un código de una prueba de un fijo de la contradicción, o no lo es, y en este último caso no hay ninguna extensión de $\mathcal{M}$ $\mathbb{N}$ que $m$ código de una prueba de una extensión. Pero esto contradice nuestra suposición de que $\mathsf{PA}$ es consistente.


Anexo

(debido a un comentario más abajo)

Primero vamos a ordenar de conseguir una manija en "no estándar" de los números (y no estándar de los modelos). Bueno, en primer lugar, un modelo de $\mathsf{PA}$ es no estándar si no es isomorfo al estándar del modelo; bastante obvio, supongo. La cosa acerca de los modelos de $\mathsf{PA}$ es que se inicie siempre el mismo: si $\mathcal{M}$ es un modelo de $\mathsf{PA}$, luego los primeros elementos de $\mathcal{M}$ $$0^{\mathcal{M}},\; 1^{\mathcal{M}} {=S}^{\mathcal{M}} ( 0^{\mathcal{M}} ),\; 2^{\mathcal{M}} {=S}^{\mathcal{M}} ( 1^{\mathcal{M}} ),\; 3^{\mathcal{M}} {=S}^{\mathcal{M}} ( 2^{\mathcal{M}} ),\;\ldots$$ y estos objeto de satisfacer a todos los habituales de propiedades aritméticas de la "real" números naturales. De hecho, normalmente le acaba de decir que $\mathbb{N}$ es un segmento inicial de cualquier modelo de $\mathsf{PA}$.

Pero, ¿se puede de todos ellos? Por desgracia, no.

Anexar a la lengua de $\mathsf{PA}$ una nueva constante símbolo $c$, y deje $T$ ser la teoría de la ampliación de $\mathsf{PA}$ obtenido por la adición de $\ulcorner n \urcorner < c$ como un nuevo axioma para cada número natural $n$ (donde $\ulcorner n \urcorner$ denota el término $\overbrace{S \cdots S}^{n\text{ times}}0$). Por el Teorema de Compacidad, si $\mathsf{PA}$ es consistente, entonces también lo es $T$. Si $\mathcal{M}$ es un modelo de $T$, entonces considere el $c^\mathcal{M}$. Para cada número natural $n$ $\mathcal{M} \models \ulcorner n \urcorner < c$ se sigue que $n <^{\mathcal{M}} c^{\mathcal{M}}$. Es decir, $c^{\mathcal{M}}$ no corresponde a ningún número natural.

Un objeto en un no estándar del modelo de $\mathsf{PA}$ que no corresponden a un número natural se llama no estándar de la serie. Una cosa debe quedar clara: cualquier número no estándar viene después de que todos los números normalizados. Por supuesto, si $x \in \mathcal{M}$ es un número no estándar, entonces es$S^{\mathcal{M}}(c)$$S^{\mathcal{M}} ( S^{\mathcal{M}} ( c ) )$. También, $c$ tendrá un inmediato predecesor , que también es no estándar. En la práctica, la colección de números no estándar es bastante desordenado.

Uno muy útil idea es la siguiente. Si $\mathcal{M}$ es un modelo de $\mathsf{PA}$, vamos a llamar a un subconjunto $I \subseteq \mathcal{M}$ un corte (en $\mathcal{M}$), si se trata de un vacío, segmento inicial de $\mathcal{M}$ que es cerrado bajo el sucesor del operador. (Por lo $\mathbb{N}$ es un corte en cualquier modelo de $\mathsf{PA}$. El siguiente hecho que es interesante:

Recepción De Lema. Supongamos que $\mathcal{M}$ es un modelo no estándar de $\mathsf{PA}$, e $I \subsetneq \mathcal{M}$ es un corte. Supongamos que $\varphi ( x , y_1 , \ldots , y_n )$ es una fórmula y $a_1 , \ldots , a_n \in \mathcal{M}$ son tales que para cada una de las $z \in I$ hay un $x \in I$ tal que $$\mathcal{M} \models x \geq z \wedge \varphi ( x , a_1 , \ldots , a_n ).$$ A continuación, hay un $x \in \mathcal{M} \setminus I$ tal que $\mathcal{M} \models \varphi ( x , a_1 , \ldots , a_n )$.

Vamos a aplicar esto en dos maneras:

  • En primer lugar, no hay ninguna fórmula $\sigma (m)$ tal que $$\mathcal{M} \models \sigma ( x ) \quad \Leftrightarrow \quad x\text{ is standard}$$ para cualquier modelo de $\mathcal{M}$ $\mathsf{PA}$ y cualquier $x \in \mathcal{L}$. (Simplemente porque $\mathbb{N}$ es un corte en cualquier modelo, y si $\mathcal{M}$ es un modelo no estándar, a continuación, $\mathbb{N}$ es un corte adecuado, y por tanto si $\sigma (x)$ es una fórmula verdadera acerca de todos los números normalizados, por el Derrame Lema debe ser también verdad acerca de un número no estándar.

  • No es difícil mostrar que si $\mathrm{Formula}_{\mathsf{PA}} (x)$ indica la fórmula para distinguir los números naturales de la codificación de las fórmulas de aquellos que no lo hacen, entonces el conjunto de todos los números naturales $n$ tal que $\mathbb{N} \models \mathrm{Formula}_{\mathsf{PA}} (n)$ es ilimitado, así que, si $\mathcal{M}$ es un no-modelo estándar de $\mathsf{PA}$, por el Derrame Lema hay un número no estándar $x \in \mathcal{M}$ tal que $\mathcal{M} \models \mathrm{Formula}_{\mathsf{PA}} (x)$. Pero no se puede descodificar esta $x$ en una fórmula real de $\mathsf{PA}$: puede ser de no estándar ("infinito") de longitud, o se puede emplear "variables" no estándar de los índices. Pero como $\mathcal{M}$ no puede decir el estándar de números de números no estándar, por lo $\mathcal{M}$ sólo "piensa" que $x$ códigos de una fórmula.

Ahora, cabe recordar que la $\mathrm{Cons}(\mathsf{PA})$ es sólo una fórmula (la frase). Hemos construido a tener cierta importancia en virtud de una adecuada interpretación, pero esta importancia crítica utilizado la idea de que el "verdadero" números naturales estaban siendo utilizados.

Entonces, ¿qué pasa si un modelo no estándar $\mathcal{M}$ satisface $\neg \mathrm{Cons}(\mathsf{PA})$, incluso si el modelo estándar no? Ser un poco más exacto que el anterior, $\neg \mathrm{Cons} ( \mathsf{PA} ) \equiv (\exists x ) ( \mathrm{Proof}_{\mathsf{PA}} ( x , \ulcorner \psi \urcorner ) )$ donde $\psi$ es algunos fijos contradictoria de la sentencia. Si $\mathcal{M} \models \neg \mathrm{Cons} ( \mathsf{PA} )$, entonces no debe ser algo de $x \in \mathcal{M}$ tal que $\mathcal{M} \models \mathrm{Proof}_{\mathsf{PA}} ( x , \ulcorner \psi \urcorner ) )$. Pero si $x$ eran de un número estándar, se seguiría que $\mathbb{N} \models \mathrm{Proof}_{\mathsf{PA}} ( x , \ulcorner \psi \urcorner ) )$, que hemos asumido no puede ser el caso. Así que esta $x$ debe ser no estándar.

Bien, ¿qué significa esto? De acuerdo a la definición de $\mathrm{Proof}_{\mathsf{PA}}$ significa que $\mathcal{M}$ "piensa" que $x$ códigos de una secuencia de números, y cada número en la secuencia de los códigos de una fórmula, y estas fórmulas constituyen una prueba de $\psi$. Pero, igual que el anterior, algo acerca de esta codificado "prueba" de que va a ser no estándar: puede tener no estándar ("infinito") de longitud, o puede involucrar no estándar fórmulas. Esta dice que el $x$ no realmente codificar una prueba de una contradicción en $\mathsf{PA}$, pero sólo eso $\mathcal{M}$ "piensa" que lo hace.

6voto

Mauro ALLEGRANZA Puntos 34146

Simplificando un poco, Gödel del Teorema de Completitud de la lógica de primer orden (con uno de los "habituales" de los sistemas de prueba, es decir, la lógica de los axiomas+reglas de inferencias) dice que :

$\Gamma \vDash \varphi$ fib $\Gamma \vdash \varphi$,

es decir, todas las consecuencias lógicas de un conjunto de sentencias son contrastables con la (lógica) de las reglas y axiomas.

Si la aplicamos a $\mathsf {PA}$, $\Gamma$ es el conjunto de f-o los axiomas de Peano.

El teorema anterior dice que todos los f-o fórmulas de $\mathsf {PA}$ que son demostrables a partir de los axiomas de Peano son las consecuencias lógicas de los axiomas, es decir, que debe ser verdadera en todos los modelos de los axiomas.

Gödel Incompletenss Teorema dice que $\mathsf {PA} \nvdash Cons(\mathsf {PA})$.

Pero, si asumimos $\mathsf {PA}$ consistente, y esta suposición es necesaria para la prueba de G Incompletenss Th, tenemos que la fórmula $Cons(\mathsf {PA})$ es verdadero.

$Cons(\mathsf {PA})$ siendo improbable de f-o los axiomas de Peano, tenemos que es no una consecuencia lógica de los axiomas.

Y si no es una consecuencia lógica de los axiomas, no es cierto en todos los modelos de los axiomas, yo.e.debe ser falso en algunos de sus modelos.

Pero sabemos que es verdad en el "standard" modelo de $\mathbb N$; por lo tanto, debe ser falsa en algunos "no-estándar" del modelo.

Entonces, Arthur argumento de la siguiente manera.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X