Parece muy confuso que el verdadero campo cerrado (que también puede ser utilizado como la teoría del número real) es decidable, mientras que la aritmética de Peano, que parece ser un subconjunto de los reales campo cerrado es indecidible.
¿Qué estoy haciendo mal?
Como William señaló en su respuesta, la Aritmética de Peano es cierto de primer orden de la teoría que describe las propiedades de la $\mathbb{N}$, los números naturales (es decir, $\mathbb{N}\models\text{PA}$). Sin embargo, es incompleta (como se muestra por Gödel), y por lo tanto no es igual a la teoría completa de los números naturales, que se denota $\text{Th}(\mathbb{N})$, que se compone de todos de primer orden de las declaraciones verdaderas de $\mathbb{N}$. La situación es diferente con la teoría de la real campos cerrados - esta es una teoría completa, y $\mathbb{R}\models \text{RCF}$, lo $\text{RCF} = \text{Th}(\mathbb{R})$.
Su principal confusión, sin embargo, parece ser acerca de cómo $\text{Th}(\mathbb{N})$ puede ser mucho más complicado de lo que $\text{Th}(\mathbb{R})$, a pesar del hecho de que $\mathbb{N}\subset \mathbb{R}$. Si $\text{Th}(\mathbb{R})$ es decidable, ¿por qué no podemos utilizar el procedimiento de decisión para decidir en todas las cuestiones acerca de la $\mathbb{N}$?
Este fenómeno es posible porque no hay una sola de primer orden de la fórmula (en nuestro idioma,$\{0,1,+,\cdot\}$), que recoge los números naturales como un subconjunto de los reales. Para decidir si un enunciado es verdadero acerca de la $\mathbb{N}$ con una pregunta acerca de $\mathbb{R}$, tendríamos que de alguna manera garantizar que todos los cuantificadores a hablar sólo de los números enteros.
Para ilustrar la dificultad, consideremos la oración $\phi:\forall x\,\exists y\, (y+y = x)$. $\phi$ es ciertamente falsa en $\mathbb{N}$. Pero el uso de la decidability de $\text{Th}(\mathbb{R})$ ver esto, tendríamos que ser capaces de expresar que para todos los números naturales $x$ no es un número natural $y$ tal que $y+y = x$, lo que no podemos hacer. Permitir que las variables de alcance de más de $\mathbb{R}$, $\phi$ es cierto.
Intuitivamente, se pregunta acerca de la divisibilidad como este que hacen que $\text{Th}(\mathbb{N})$ mucho más complicada que la de $\text{Th}(\mathbb{R})$. La fórmula $\psi(x,y):\exists z (x = y\cdot z)$, expresan que $y|x$, da acceso a toda la complejidad de los números primos. Por el contrario, los reales son muy homogéneo: $\psi(x,y)$ es cierto en un par de reales $(a,b)$ siempre $b\neq 0$.
La razón principal de que el primer orden de la teoría de los reales es mucho más simple que Diophantine (entero) análogos es que los asociados de la geometría es mucho más simple. Es decir, los conjuntos definibles por real polinomio (en)las ecuaciones - los llamados semi-algebraicas conjuntos - puede ser descompuesto en un finito número de células (por ejemplo, cilindros), donde, en cada célula, cada definición de polinomio tiene signo constante. Por lo tanto, la prueba de la verdad de primer orden instrucción se reduce a un finito número de pruebas en constante señal de las células, que es trivialmente se decidió por simplemente a evaluar los polinomios en cualquier punto de la celda. Esto proporciona un algoritmo para decidir la verdad de primer orden de las declaraciones acerca de los reales - el llamado cilíndrico algebraica de descomposición (CAD) algoritmo (una efectiva realización de Tarski del famoso método de eliminación de cuantificadores para los reales).
Por ejemplo, en el caso unidimensional los conjuntos definibles en el primer orden lenguaje de $\rm\:\mathbb R\:$ son simplemente finito uniones de intervalos. Así, por ejemplo, para probar si $\rm\ f(x) > 0\ \Rightarrow g(x) > 0\ $ podemos emplear Sturm del Teorema de partición de la $\:\mathbb R\:$ por el finito número de raíces de $\rm\:f,\:g\:,\:$ y, a continuación, elija un punto de $\rm\:r\:$ en cada intervalo de tiempo y probar si $\rm\ f(r)>0\ \Rightarrow\ g(r)>0\:.\:$ El CAD algoritmo funciona de forma análoga en las dimensiones superiores, por la proyección de mayores dimensiones de las celdas hacia abajo a dimensiones inferiores. La clave de la propiedad es el resultado de Tarski y Seidenberg que el semi-algebraicas conjuntos son conservados por las proyecciones. La estructura esencial se ha generalizado en el modelo teórico de estudio de o-un mínimo de estructuras.
Esto contrasta con el estudio de (de primer orden) Diophantine ecuaciones. Cualquiera que haya estudiado la teoría de los números rápidamente aprecia la enorme complejidad de la estructura de los conjuntos de soluciones de entero de ecuaciones polinómicas, por ejemplo, ecuaciones de Pell, curvas elípticas, etc. Undecidability resultados implican que no puede ser de simple uniforme recursiva del procedimiento de decisión como para que los reales. Cada salto a una dimensión superior puede requerir completamente nuevas ideas. Pero esto no debe ser visto como un perjuicio. Más bien, el resultado es una fuente inagotable de ricos problemas que constantemente desafío de nuestro ingenio.
Cuando usted habla de decidability en este contexto, la media de la decidability de la teoría, no de cualquier modelo en particular.
La teoría de la real campos cerrados y la aritmética de peano son diferentes teorías. El axioma de la real cerrada campos incluyen todos los axiomas de anillo. Aritmética de Peano no. De Peano aritmética incluyen la inducción, mientras que el axioma de la real campos cerrados no. Como las teorías, es decir, conjuntos de fórmulas, la Aritmética de Peano y Real de campos cerrados son simplemente diferentes. Para decir que uno es un subconjunto de otra no tiene sentido.
Puede ser confuso el concepto de modelos con la teoría. Los números reales pueden ser un modelo de real de campos cerrados y el número natural es un modelo de la aritmética de peano dentro de ella. Sin embargo, las fórmulas de bienes de campos cerrados son decidable. En particular, en estas fórmulas, el cuantificador rangos sobre el dominio de los reales de campos cerrados. Por ejemplo, el real campo cerrado puede decidir si existe una solución a algunos de ecuaciones; sin embargo, los cuantificadores rango en el dominio de la real campos cerrados. Usted no sabe nada acerca de si esta solución se encuentran en los números naturales, por ejemplo.
Como otros señalan, la principal razón de esta aparente paradoja de la situación (todos los números naturales son números reales, pero la teoría de que la primera es mucho más complicado que el segundo), es porque los números naturales no son definibles en el lenguaje de la RCF.
Podemos utilizar el mismo lenguaje para hablar de ellos, decir $\{0,1,+,\cdot\}$ y números naturales son una subestructura de los números reales. Sin embargo por ser un subsructure no hacer las cosas más simples. Tomemos, por ejemplo, los números primos, qué se puede esperar que su teoría en el lenguaje mismo es más simple que la teoría de los números naturales? No necesita ser el caso. El principal problema, como otros han de señalar es la cuantificación. La cuantificación sobre números naturales puede generar muy complicado conjuntos (aritmética jerarquía) donde como la cuantificación más reales, de hecho no si sólo tenemos que añadir para el idioma, a continuación, cada cuantificado fórmula es equivalente a la fórmula, sin cuantificadores de reales, es decir, cuantificadores no aumentar la complejidad de los conjuntos consideramos que sí y puede ser eliminada (y que es la forma en que está demostrado que la RCF es decidable). Podemos demostrar que esto no es posible para los números naturales, cuantificadores puede aumentar la complejidad de los conjuntos. El undecidability siguen esencialmente por el hecho de que podemos hablar de cómputo de las máquinas en las teorías como PA y mucho más débiles de las teorías acerca de los números naturales.
Puede ser útil para mirar algo en el medio: el considerar enteros. Podemos definir los números naturales mediante el hecho de que cada número natural es equivalente a la suma de cuatro cuadrados. Por lo tanto, van a ser tan complejo como el de los números naturales. Otro de los más difíciles de establecer en el medio: considerar los números racionales. Su teoría es igualmente indecidible, sin embargo muestran que podemos definir los números naturales en su teoría es mucho más complicado (este buen resultado es originalmente debido a Julia Robinson). Otro ejemplo: considere los números complejos. Su teoría de la ACF es incluso más simple que el de los números reales.
Para hacer aún más claro, si sólo tenemos que añadir un predicado con el lenguaje, que nos dice que los números reales son números naturales, entonces la teoría de los números reales con este predicado se convierte en indecidible. El principal problema es que sin ese predicado números naturales son indistinguibles de otros números reales en el idioma.
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.
