Hay un primer orden de la prueba en $(\mathbb{N},+,*,\le)$ que no hay ningún límite superior en números primos. es decir, que la $$\neg\exists{q}{\forall{p}{(\forall{m,n}\space m*n=p\rightarrow m=1\vee n=1)\rightarrow p\le q}}$$
Si no, alguien puede dar un ejemplo de una escuela primaria de la extensión de $(\mathbb{N},+,*,\le)$ en los que hay un mayor prime.
De primer orden PA demuestra que hay unboundedly muchos de los números primos (que yo tome responde a la intención de la pregunta). Básicamente, se pueden replicar en el PA el conocido argumento de que se ejecuta "Tome cualquier $n$, entonces cualquier factor principal de $n! + 1$ es mayor que $n$, etc.". Para ello, podemos mostrar cómo definir el factorial en PA (utilizando el $\beta$-función truco, suponiendo que el factorial no está incorporada), demostrar PA sabe que la función tiene el requisito de propiedades, probar PA sabe de los hechos básicos acerca de la divisibilidad, etc. etc.
Para más detalles, véase, por ejemplo, Kaye, maravillosos Modelos de la Aritmética de Peano, la Sección 5.3.
Debido a que las funciones recursivas son representables, el habitual de las pruebas pueden llevarse a cabo en primer orden de la aritmética de Peano. Las diversas pruebas de inducción es necesario establecer los resultados básicos son todas las instancias de la PA esquema de inducción.
Añadido: no necesitamos la representatividad de maquinaria para formalizar una versión de la norma "Euclides" de la prueba. Para que realmente no necesitamos el factorial de función. Todo lo que necesitamos es el hecho de que para todas las $x\ge 0$, existe un $y\ge 1$ tal que para todos los $t$$1\le t\le x$, $t$ divide $y$.
El estándar de pruebas de la costumbre de divisibilidad de los resultados, lo que es más importante que cualquier número natural mayor que $1$ es divisible por algún primo, puede ser casi mecánicamente traducido a pruebas en PA.
Aquí es un semi-formal de la prueba de esta afirmación en PA. Por semi-formal, me refiero a que voy a utilizar términos como "es primo" o "dividir", que no son parte de la base de la lengua, pero que se puede expresar fácilmente en ella, y voy a suponer que usted ya ha construido una biblioteca básica de un número teórico de los hechos.
Lema 1: Para todos los $n >1$, hay un primer dividiendo $n$.
Prueba: Por inducción sobre $n$. Caso Base $n=2$ es trivial. Supongamos que la instrucción para $n<m$. Si $m$ es primo, entonces es también cierto para $n=m$. Si $k$ es un divisor no trivial de $m$, entonces, por inducción, $k$ tiene un divisor primo lo $n$ lo hace así. $\square$
Lema 2: Para todos los $n \geq 1$ existe $N \geq 1$ tal que, para todos los $k$$1 \leq k \leq n$,$k|N$.
Prueba: Por inducción sobre $n$. Caso Base $n=1$ es trivial. Si $M$ es divisible por todos los $k$$1 \leq k < m$, $Mm$ es divisible por todos los $k$ con $1 \leq k \leq m$. $\square$
Teorema: Para todos los $n$, no es un primo mayor que $n$.
Prueba: Por el Lema 2, hay un $N$ tal que $k|N$$1 \leq k \leq n$. Por el Lema 1, hay un primer $p$ que se divide $N+1$. Si $p \leq n$,$p|N$$p|N+1$, una contradicción. Por lo $p>n$, como se desee. $\square$.
Es interesante notar que el Lema 2 se afirma una relación de crecimiento exponencial. (Es decir, es un teorema de la forma $\forall n \exists N : \cdots$ donde el menor $N$ la satisfacción de las $\cdots$ es exponencial en $n$.) Es conocido que ciertos muy débil fragmentos de PA no se puede demostrar la existencia de una relación de crecimiento exponencial; sería interesante saber si se puede demostrar la infinitud de los números primos.
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.
