Esta pregunta se refiere a una discusión en otro mensaje de la junta. Euclides prueba de la infinitud de los números primos es una prueba indirecta (un.k.una. la prueba por contradicción, reductio ad absurdum, modus tollens). Mi entendimiento es que Intuitionists rechazar tales pruebas, porque se basan en la Ley del Medio Excluido, que ellos no aceptan. ¿Existe una relación directa y constructiva de la prueba de la infinitud de los números primos?
Respuestas
¿Demasiados anuncios?
Debido a una muy propagado error histórico, es comúnmente creído erróneamente que Euclides de la prueba por contradicción. Esto es falso. Euclides de la prueba, de hecho fue presentado en el obvio constructivo de la moda. Ver Hardy y Woodgold del Intelligencer artículo[1] para un análisis detallado de la historia (basada en parte en muchos de los sci.matemáticas debates [2]).
Una variante que merece ser mejor conocido es la siguiente folclore de una línea de prueba de que hay infinitamente muchos primeros enteros
$\rm\qquad\qquad N\ (N+1)\ $ tiene un conjunto más amplio de factores primos que no $\rm\:N.$
debido a $\rm\,N+1>1\,$ es coprime a$\,\rm N\,$, por lo que tiene un factor primo que no divide $\rm\,N.$ Curiosamente, Ribenboim cree que esta prueba sea de cosecha reciente, atribuyéndolo a Filip Saidak. Pero recuerdo ver variantes publicado hace mucho tiempo. ¿Alguien sabe de su historia?
Para aún más opciones, aquí es una versión de Euclides prueba reformulada en infinito descenso formulario. Si hay sólo un número finito de números primos, entonces dado cualquier prime $\rm\:p\:$ existe un menor número primo, es decir, el mínimo factor de $> 1$ $\rm\ 1 + $ el producto de todos los números primos $\rm \ge p\:.$
Merece ser conocido mucho mejor que la de Euclides constructiva de la prueba generaliza muy ampliamente a cualquier fewunit anillo, es decir, cualquier anillo de tener un menor número de unidades de elementos - ver mi prueba aquí. $ $ La idea clave es que Euclides de la construcción de un nuevo primer generaliza a partir de los elementos ideales, es decir, dado un poco de máxima ideales $\rm\ P_1,\ldots,P_k\:,\: $ una simple caja argumento que emplean $\rm CRT$ deduce que $\rm\ 1+P_1\:\cdots\:P_k\ $ contiene un nonunit, que se encuentra en algunas máxima ideal que, por construcción, es comaximal (tan distintas) a partir de la inicial max ideales $\rm\:P_1,\ldots,P_k\:.$
[1] Michael Hardy; Catherine Woodgold
El Primer Simplicidad.
La Matemática Intelligencer, Volumen 31, Número 4, 44-52.
DOI enlace; $\ $
Springer link; $\ $
link gratis
[2] Nota: Aunque el artículo [1] no hace ninguna mención de tal, parece que tiene fuertes raíces en frecuente de la lesión.matemáticas discusiones - en la que el primer autor participó brevemente. Un grupos de Google de búsqueda en los grupos de noticias de usenet de la lesión.matemáticas para "Euclides plutonio" va a subir muchos largos debates sobre diversas interpretaciones erróneas de Euclides de la prueba.
Bryan Roth
Puntos
3592
Su pregunta se basa en un concepto erróneo común. De hecho Euclides prueba es completamente constructiva: se da un algoritmo que, al ser dado como entrada cualquier conjunto finito de números primos, salidas de un número primo que no está en el conjunto.
Añadido: Por un poco más matemático de problemas relacionados con el algoritmo anterior, véase el Problema 6 aquí. (Este es uno de los más interesantes problemas en el primer conjunto de problemas de una avanzados de pregrado de la teoría de números curso que me enseñe a partir de tiempo al tiempo).
Adam Kahtava
Puntos
383
El teorema de euclides es intuitionistic. Dado cualquier conjunto finito de números primos, su producto más uno no es divisible por ninguno de los números primos y por lo tanto es divisible por algunos de los mejores no en S. Esto le da un hormigón límite superior en el n-ésimo prime-aunque, por supuesto, es astronómico.
encomiast3
Puntos
11
He aquí una sencilla prueba directa de que no sólo muestra que hay un número infinito de números primos, pero le da un límite inferior en cuántos de los números primos son menos de $N$. La idea viene de Erdős.
Deje $\pi(N)$ el número de números primos $\leq N$ para un entero positivo N. Cualquier entero positivo $\leq N$ puede ser escrita en la forma $$B^2{p_1}^{e_1} {p_2}^{e_2} ... {p_{\pi(N)}}^{e_{\pi(N)}}$$ where the $e_i$'s are 0 or 1 and $B\leq \sqrt$N.
Hay en la mayoría de las $2^{\pi(N)}\sqrt N$ números posibles de esta forma, y por eso tenemos $$2^{\pi(N)}\sqrt{N}\geq N$$ which gives us $$\pi(N)\geq {\log{N}\over{2 \log 2}}$$ lo que es claramente acotada.
Esta idea se utiliza en Erdos' nice prueba de que $\sum {1\over p}$ diverge, a pesar de que es una prueba por contradicción y así no llegaría al intuitionist de la escuela. Va como esta. Asumir la suma converge. A continuación, hay algunos $k$ tal que ${\sum_{i \geq k+1}} {1\over p_i} < 1/2$. Llame a los números primos $\leq p_k$ la "pequeña" de los números primos y los números primos $\geq p_{k+1}$ de los "grandes" de los números primos. Podemos dividir los enteros positivos $\leq N$, para cualquier N, en dos grupos: aquellos que son divisibles por un "grande" de la primera, y los que no lo son. Un límite superior en el número divisible por un "grande" prime es $N/2$ (esto proviene de la suposición de que la suma de los recíprocos de los grandes números primos es $\leq 1/2$), y un límite superior en el número no divisible por un "grande" prime es $2^k\sqrt N$. Dado que estas dos categorías se incluyen todos los enteros positivos $\leq N$, debemos tener $N/2+2^k \sqrt N \geq N$. Sin embargo, esto no es cierto para suficientemente grande $N$, y así tenemos nuestra contradicción, y la serie diverge.
