¿La capacidad de decisión tiene algo que ver con los números primos?

Question

Nota: he modificado la pregunta para hacerla más clara y más relevante. Que hace que algunas de las referencias a la versión anterior ya no puede contener. Espero que las víctimas no se furioso sobre esto.

---

Motivación:

Recientemente el Ritmo de Nielsen, la pregunta "¿Cómo podemos reconocer un número entero dentro de los racionales?". Que me recuerda a esta pregunta que tenía en el pasado, pero no tienen la oportunidad de hacer ya que no sabía de MO.

Parece ser que existen algunas pruebas que sugieren algunas de las posibles relaciones entre decidability y los números primos:

1) Tameness y desenfreno de las estructuras

Uno de los slogan de la modelo moderno de la teoría es el "Modelo de la teoría de = la geografía de domar las matemáticas". Domar a la estructura, que son estructuras en las que un modelo de la aritmética no puede ser definido y por lo tanto no tenemos teorema de la incompletitud. Una estructura que no es manso es salvaje.

Las siguientes estructuras son mansos:

• Algebraica de campos cerrados. Demostrado por Tarski.

• Real de campos cerrados e.g $\mathbb{R}$. Demostrado por Tarski.

• p-ádico de campos cerrados e.g $ \mathbb{Q}_p$. Demostrado por Ax y Kochen.

Tame estructuras a menudo se comportan muy bien. Tame estructuras a menudo admite la eliminación de cuantificador es decir, cada fórmula es equivalente a un cuantificador de fórmula libre, por lo tanto los conjuntos definibles tiene una simple descripción. Tame estructuras son decidable yo.e hay un programa que nos diga qué afirmaciones son verdaderas en estas estructura.

Las siguientes estructuras son comodines;

• Número Natural (Gödel teorema de la incompletitud)

• Número racional ( Julia Robinson)

Salvaje estructura se comporta mal (curiosamente). No hay ningún programa nos dice que las declaraciones son verdaderas en estas estructuras.

Una de las diferencia entre los mansos de la estructura y salvaje de la estructura es la presencia de prime en la tarde. La sugerencia es más fuerte para el caso de p-ádico de campo, podemos ver esto como deshacerse de todo a excepción de una prima.

2) El uso de los números primos en la prueba del teorema de la incompletitud

La prueba de los teoremas de incompletitud tiene algunas de fantasía partes y algunas partes aburridas. La fantasía de las partes implica la de Gödel punto Fijo lema y otras cosas. Las partes aburridas implica la prueba de que las pruebas pueden ser codificados utilizando número natural. Yo soy de los convencidos de que la aburrida parte es en realidad más profunda. Recuerdo que en algún lugar en la prueba necesitamos utilizar el teorema del Resto Chino, y por lo tanto invocar algo relacionado con los números primos.

3) Decidability de la aritmética de Presburger y Skolem aritmética ( extraído de la respuesta de Concesión de Olney Passmore)

La aritmética de Presburger es la aritmética de número natural, con sólo la adición. Skolem aritmética es la aritmética de número natural con sólo la multiplicación.

Ilusión: La condición de que los números primos o algo por igual definible en la teoría implica imperfección. Por el contrario Si una teoría es incompleta, la incompletud venir de algo así como primos.

---

Preguntas:

(siguiente sugerencia por François G. Dorais)

Dirección: Considere un sistema delimitado de la aritmética, supongamos que los números primos son definibles en el sistema. No implica imperfección.

Hacia atrás: Considere un sistema delimitado de la aritmética, supongamos que el sistema puede demostrar el teorema de la incompletitud, de los números primos es definible en el sistema? es la enumeración de primer definible? es el primer factorización de la función definible?

---

Estado de la respuesta:

Para la dirección de avance: Un débil teoría de la prime no implica imperfección. Para más detalles, véase la respuesta de Concesión de Olney Passmore y respuesta de Neel Krishnaswami

Para la dirección hacia atrás: La incompletitud no es necesario venir de prime. Todavía no está claro si se debe venir algo igual prime. Para más detalles, véase la respuesta de Joel David Hamkins.

---

Pues tal vez esta es toda la información que puedo obtener, acepto la primera respuesta por Joel David Hamkins. Muchas gracias a la Subvención de Olney Passmore y Neel Krishnaswami que también se señalan aspectos importantes.

Recientemente, Francois G. Dorais también publicar un nuevo e interesante respuesta.

Answer 1

Goedel hizo, de hecho, utilizar el teorema del resto Chino en su prueba del teorema de la Incompletitud. Esto fue utilizado en lo que usted describe como el `aburrido' parte de la prueba, el arithmetization de sintaxis. Contemporáneo a menudo, los investigadores de acuerdo con su evaluación, sin embargo, que la arithmetization de la sintaxis es profunda. Esta es la parte de la prueba que revela la auto-referencial de la naturaleza de la primaria a la teoría de números, por ejemplo, ya que al hablar acerca de los números de podemos, en efecto, hablar de las declaraciones que involucran números. En última instancia, nos llega de esta manera a una sentencia que afirma su propia unprovability, y esto le da el Teorema de la Incompletitud de inmediato.

Pero hay otros métodos de codificación, además de el teorema del Resto Chino, y no todas ellas implican números primos directamente. Por ejemplo, la única razón por la Goedel necesario CRT fue la que trabajó en un número muy limitado de lenguaje formal, sólo el anillo de la teoría del lenguaje. Pero uno puede fácilmente trabajar en un lenguaje más rico, con todas las funciones recursivas primitivas, y la prueba de que procede la mayoría de los casos como los de antes, con un poco de tiempo más fácil para la parte de codificación, que no implica el de los números primos. Otras pruebas formalizar la teoría en la hereditario finito de conjuntos de HF, que es mutuamente interpretado con los números naturales N y, a continuación, la codificación es fundamentalmente un conjunto teórico, involucrando también los no primos de los números, especialmente.

Answer 2

En respuesta a su declaración: "parece que la condición de que los números primos son definibles en la teoría implica imperfección."

Los números primos de ser definible en una media aritmética, la teoría no conduce necesariamente a la incompletitud. La teoría de Skolem aritmética ($Th(\langle\mathbb{N},*\rangle)$) es decidable y admite la eliminación de cuantificadores (es la primaria de la verdadera teoría de la débil directa de la potencia del modelo estándar de la aritmética de Presburger, así Feferman-Vaught cuantificador-eliminación de elevación se aplica). Un predicado de primalidad fácilmente puede ser expresado en el lenguaje de esta teoría. Esto es debido a Skolem y Mostowski inicialmente, y a Feferman-Vaught cuando obtenidos en términos de debilidad de competencias directas.

Por otra parte, Skolem aritmética extendido con el orden usual restringido a los números primos es decidable, admite eliminación de cuantificadores, y en el hecho de $Th(\langle\mathbb{N},*,<_p\rangle)$ e $Th(\langle\omega^\omega,+\rangle)$ son reducibles el uno al otro en el tiempo lineal. Esto es debido a Francoise Maurin (ver "la Teoría de La Multiplicación de Enteros con el Fin Restringido a los números Primos en Decidable" - J. de la Lógica Simbólica, Volumen 62, número 1 (1997), 123-130).

Tenga en cuenta que en este último caso, el pedido no puede ser la ordenación de los números naturales, ya que esto permitirá definir un sucesor predicado, y Julia Robinson mostró sucesor y la multiplicación son suficientes para la definición de adición.

Answer 3

El papel de los números primos en Gödel del Teorema de la Incompletitud puede ser entendida mejor mirando Robinson Q, que es una de las más débiles de las teorías de la aritmética para que Gödel del Teorema de la Incompletitud de las suspensiones. Robinson derivados de su original axiomas para Q mirando los axiomas de la PA que se utilizaron en la prueba de que cada computable función puede ser representada en PA, que es la parte clave de Gödel del argumento.

Una simple teoría que interpreta Robinson Q es la teoría de la discreta ordenada de los anillos con la inducción para abrir las fórmulas, es decir, el esquema φ(0) ∧ ∀x(f(x) → φ(x+1)) → ∀x(x ≥ 0 → φ(x)), donde φ es un cuantificador libre de fórmula en el lenguaje de las ordenadas de los anillos, el cual puede contener variables libres distinto de x. (Sólo el cuantificador existencial en el axiomatization de Q, es decir, en el axioma x = 0 ∨ ∃y(x = Sy), puede ser eliminado ya que ahora tenemos la resta.)

La teoría de la discreta ordenada anillos con abrir la inducción ha interesado a muchos lógicos. El primer estudio de esta teoría fue Shepherdson (Un no-modelo estándar de una variable libre fragmento de la teoría de números, SEÑOR161798) que demostró que esta teoría no puede probar que √2 es irracional. De ello se desprende que Robinson Q no puede demostrar la irracionalidad de √2. Desde la irracionalidad de √2 es consecuencia de una única factorización en números primos, Robinson Q no se puede demostrar que.

Shepherdson del modelo en el que √2 es racional es el anillo S cuyos elementos son las expresiones de la forma $$a_0 + a_1T^{q_1} + \cdots + a_kT^{q_k}$$ donde T es indeterminado, los exponentes 0 < q₁ < ... < q_k son positivos racionales, el coeficiente a₀ es un número entero, y el resto de los coeficientes a₁,...,a_k son reales números algebraicos. La positividad es determinado por el signo de los principales coeficiente_k; esto equivale a hacer T infinitamente grande. El hecho de que este satisface abrir la inducción es muy notable. En este anillo S, el único de los números primos son los números primos de ℤ, así que simplemente no existen infinitos números primos. Por lo tanto, Robinson Q no puede demostrar que los números primos son ilimitados.

Todavía extraño discretos ordenó anillos abiertos de inducción han sido construidos por Macintyre y el Marcador (los números Primos y sus residuos anillos en los modelos de abrir la inducción, SEÑOR1001418). Por ejemplo, la construcción de un anillo donde hay unboundedly muchos de los números primos, pero todos los infinitos números primos son congruentes con 1 modulo 4.

Es, al parecer, todavía se desconoce si el axioma de inducción para delimitada cuantificador fórmulas (IΔ₀) demuestra que el ilimitado de números primos. Este problema fue planteado por Wilkie y el primer parcial de la respuesta vino de Alan Woods, quien vinculado a un principio del palomar, junto París, Wilkie, y Woods (Provability del principio del palomar y la existencia de infinitos números primos, SEÑOR973114) mostró que el ilimitado de números primos es comprobable en muy pequeña extensión de IΔ₀. (Ver también este artículo reciente de Bosques y Cornaros MR2518806.)

Lo anterior demuestra que una buena teoría de los números primos y factorización no es necesario para Gödel del Teorema de la Incompletitud. Sin embargo, esto debe ser tomado con un grano de sal. La característica clave de Robinson Q es que se interpreta correctamente la aritmética básica en cuanto al estándar de números naturales se refiere, y nada más. El hecho de que Robinson Q no dice mucho acerca de lo que está sucediendo fuera de la norma enteros no significa que ciertas características, como la primalidad, que conforman la rica y compleja estructura de la norma números enteros es completamente irrelevante para Gödel del Teorema de la Incompletitud.

Answer 4

Otra de las pruebas que creo que podría ser relevante: La prueba de los teoremas de incompletitud tiene algún capricho parte y algunos aburridos parte. La fantasía es la de Gödel punto Fijo lema y otras cosas. La perforación es la prueba de que las pruebas pueden ser codificados utilizando número natural. Yo soy de los convencidos de que la aburrida parte es quizás más profundo. Recuerdo que en algún lugar en la prueba necesitamos utilizar el teorema del Resto Chino, y por lo tanto invocar algo relacionado con los números primos.

La clave de bits en la imperfección prueba de ello es el hecho de que la multiplicación es total. Esto es lo que le permite construir libremente representaciones de los términos de las representaciones de los términos.

Dan Willard ha dado "auto-verificación de" lógicas, que son lógicas para que un auto-consistencia principio puede ser consistentemente añadido. Allí, el truco es quitar la adición y la multiplicación, y reemplazarlos con la resta y la división. En estos lógica, la totalidad de la multiplicación no es demostrable, y por lo que la lógica puede representar su Gödel codificaciones, pero no puede hacer lo suficiente con ellos para que el punto fijo lema ir a través de.

Puesto que la multiplicación y la de los números primos van juntos como avellanas y chocolate, dichos ajustes al estado de la multiplicación probablemente sugieren que hay profundas conexiones con la teoría de los números. Pero no sé lo suficiente como para decir!

Answer 5

Usted podría estar interesado en A. Grzegorczyk del papel "Undecidability sin arithmetization." (Studia Logica, 79(2): 163-230, 2005) en el que se prescinde de arithmetization por completo (pero no prescindir de codificación, por supuesto). Usted también puede estar interesado en los siguientes papel corto que precede es: "Decidability sin las matemáticas." (Anales de la Pura y Aplicada de la Lógica, 126(2004) 309-312). Su teoría formal de interés es una teoría de la concatenación él llama a $TC$, lo que él es capaz de demostrar lo indecidible. Una pista en cuanto a cómo lo hace está contenida en el resumen de su ponencia "Decidability sin las matemáticas.":

"En el documento se propone una nueva definición de la eficacia (la computabilidad, general de la recursividad, algoritmicity). Un buen nombre para esta versión de la eficacia es discernibility. Esta definición se basa en el hecho de que todos los cálculos puede ser reducido a la operación de discernimiento de los símbolos fundamentales y la concatenación de las fórmulas. Este enfoque de la eficacia nos permite formular la prueba de undecidability de tal manera que arithmetization de la sintaxis puede ser reemplazado por el uso de la concatenación en metalogic."

Esta (para mí, al menos) plantea la siguiente generalización de su pregunta:

'¿Qué principio(s) de concatenación permitir(s) para llevar esto a cabo?'