Prueba de infinitos números primos

Aquí está la prueba del libro que estoy leyendo que prueba que hay infinitos números primos:

Queremos mostrar que no es el caso de que solo haya un número finito de números primos. Supongamos que hay un número finito de números primos. Mostraremos que esta suposición conduce a una contradicción. Dejar pag 1 , pag 2 , . . . , pag norte sean todos los primos que hay. Dejar X = pag 1 . . . pag norte ser su producto y dejar y = X + 1 . Entonces y norte y y 1 , entonces hay un primo q tal que q y . Ahora q debe ser uno de pag 1 , . . . , pag norte ya que estos son todos los números primos que hay. Por eso q X . Desde q y y q X , q ( y X ) . Pero y X = 1 . De este modo q 1 . Pero desde q es primo, q 2 . Por eso q no divide a 1. Así hemos llegado a una contradicción. Por lo tanto, nuestra suposición de que solo hay un número finito de números primos debe ser incorrecta. Por lo tanto, debe haber infinitos números primos.

Tengo un par de preguntas/comentarios con respecto a esta prueba. Usaré un ejemplo simple para ayudar a ilustrar mis preguntas:

Supongamos que solo existen 6 números primos: 2 , 3 , 5 , 7 , 11 , 13

Dejar X = pag 1 pag 2 pag 3 pag 4 pag 5 pag 6 = 30 , 030

Dejar y = X + 1 = 30 , 030 + 1 = 30 , 031

Preguntas/Comentarios:

  1. La prueba dice que hay un primo q tal que q y y eso q debe ser cualquiera pag 1 , pag 2 , pag 3 , pag 4 , pag 5 , o pag 6 . Sin embargo, ninguno de los 6 primos enumerados, ( 2 , 3 , 5 , 7 , 11 , 13 ) , divide 30 , 031 . De hecho, los únicos divisores para 30 , 031 son 1 , 59 , 509 y 30 , 031 . Entonces, ¿la prueba no se descompone aquí ya que no hay número primo? q que divide y ?

  2. La factorización prima de 30 , 031 es 59 × 509 . Estos dos números son factores de 30 , 031 y son de hecho primos en sí mismos ya que solo son divisibles por sí mismos o por 1. ¿He demostrado que existe > 6 primos? Si es así, ¿qué puedo concluir ahora que he demostrado esto?

  3. no entiendo porque la contradicción q divide 1 y q no divide 1 nos lleva a la suposición de que los números primos finitos deben estar equivocados. Entiendo cómo llegamos a la contradicción. No entiendo por qué la contradicción nos lleva a la conclusión de que la suposición de que solo hay un número finito de números primos es incorrecta.


Mis disculpas por la larga publicación. Gracias por cualquier y toda la ayuda.

La factorización única requiere una descomposición en primos única. Si no pag existe, debe haber un nuevo primo...
El punto del argumento es que debe haber algún primo que no esté en la lista que divide el número que produce. ¡Tu ejemplo lo confirma! Encontraste dos de esos números primos. 59 , 509 ninguno de los cuales está en la lista. Por lo tanto, su lista no puede haber sido completa.
La prueba asume que hay un número finito de números primos, pero luego muestra que, dadas las condiciones, este no puede ser el caso. Por lo tanto, la falla está en tu suposición, ya que todos los argumentos en la prueba son matemáticamente válidos.
Gracias por las rápidas respuestas a todos. ¿Podrías explicar un poco más sobre el #3?. ¿Por qué esta contradicción nos lleva al hecho de que la suposición de que hay un número finito de números primos debe ser incorrecta?
Como se indicó anteriormente, todos sus argumentos matemáticos son correctos cuando comenzó desde su suposición original. Sin embargo, eres conducido a un punto en la prueba que es imposible. Si los argumentos matemáticos son sólidos y correctos, ¿qué queda para que haya errores...? Por lo tanto, la suposición original debe ser incorrecta.
2) En este caso que haya al menos 7 números primos. Pero si generalizas esto, que p1p2...pn+1 nunca es divisible por p1,...,pn entonces p1,.....pn no puede ser una lista de todos los números primos. No puede existir tal lista. Entonces no puede haber un número finito de números primos.
3) asumimos que p1,.....pn son todos los números primos. Sabemos que p1....pn +1 tiene un factor primo q. Como p1,....,pn son todos los primos que hay, q = pi, uno de esos primos. Entonces pi|p1....pn y pi|p1....pn. asi que pi| 1. Lo cual es imposible. Así que una de nuestras suposiciones debe estar equivocada. La única suposición que no podemos justificar es que p1,...,.pn son todos los primos que hay. Pero si hay un número finito de números primos, podemos enumerar todos los números primos y esos serían todos los números primos que hay. Entonces eso no puede pasar. Entonces hay un número infinito de números primos.
Creo que lo que falta es que no estás redefiniendo lo que significa ser primo cuando asumes una lista de posibles primos. No está cambiando "x es primo" para que signifique "x está en esta lista". Entonces, está demostrando que la lista es inconsistente con el significado definido de primo, porque puede encontrar nuevos números que se ajusten a ese molde.
"La prueba establece que hay un primo q tal que q∣y... Sin embargo, ninguno de los 6 números primos enumerados divide 30 031. De hecho, los únicos divisores de 30 031 son 1, 59 509 y 30 031. ¿Entonces la prueba no se rompe? aquí abajo ya que no hay q primo que divida a y?" - pero acabas de encontrar un primo q que divide a y . 59 y 509 son primos que dividen y. No decía que los primos tenían que estar en la lista.
¿Cómo puede esto no ser un engaño?

Respuestas (9)

Este es un excelente ejemplo de una prueba que tradicionalmente se expresa como una prueba por contradicción, pero que se entiende mucho mejor de manera constructiva. Desde un punto de vista constructivo, la prueba muestra que dada cualquier lista de números primos pag 1 , , pag norte hay un primo q (cualquier divisor primo de pag 1 pag 2 pag norte + 1 ) que es distinto de cada pag i . Entonces, dado cualquier conjunto finito de primos, podemos encontrar un primo que no esté en ese conjunto.

+1 por enfatizar el aspecto constructivo de esta prueba.
Excepto que este proceso en realidad no construye un nuevo número primo (el ejemplo y = 30031 siendo compuesto).
@DanielR.Collins Entonces, ¿cómo funciona el proceso que da un divisor primo de pag 1 pag 2 pag norte + 1 no puede construir un nuevo número primo?
@Rob: creo que el punto de Daniel es que la prueba construye un número entero y > 1 que no es divisible por pag 1 , pag 2 , …, pag norte , y luego afirma que debe haber un primo q tal que q y , pero no construye q .
^ Sí, eso es todo.
Esta no es una prueba constructiva. Es una prueba de existencia que se entiende mejor por contradicción. Voto negativo voto negativo voto negativo voto negativo
@Scott Pero hay un algoritmo simple para generar un divisor primo de cualquier número entero.
@JackM sí, pero es terriblemente lento. O ( 10 yo ) específicamente.
@JanDvorak: sí, la prueba también conduce a una estimación muy pobre de la tasa de crecimiento de los números primos (me parece recordar que esto se discute en el libro de Hardy y Wright sobre teoría de números). No obstante, sigue siendo constructivo.
@JackM: ¡así es! Gracias.
@djechlin Esta es una prueba constructiva y estás completamente equivocado. El conjunto de divisores de un entero positivo es finito. Ahora solo toma el elemento mínimo mayor que 1 en el conjunto de divisores; esto es obviamente primo. ¿Dirías que encontrar el elemento mínimo en un conjunto finito de números enteros no es constructivo? Por cierto, la prueba por contradicción parece implicar que pag 1 pag 2 pag norte + 1 es principal, que es la principal fuente de confusión en los novatos.
@egreg No veo una razón intuitiva para llamarlo constructivo . Supongamos que escribiera una prueba de que debe haber un contraejemplo de la conjetura de Frankl que tenga como máximo 1000 elementos, sin ningún indicio de cuál podría ser ese contraejemplo. Esto significaría enumerar todos los elementos en PAG ( PAG ( [ 1000 ] ) ) , un conjunto finito, y probarlos daría el contraejemplo. Pero yo no llamaría a esta prueba constructiva. Sin embargo, entiendo la noción de que es más constructivo que otras pruebas, así que pregunto: ¿Existe un significado ampliamente aceptado para la palabra constructivo ?
@JiK Dada cualquier familia (finita) de números primos, el procedimiento encuentra un número primo que no pertenece a la lista. ¿ Qué más necesitas para llamar a esto constructivo ?
@egreg ¡Un algoritmo de tiempo polinomial para encontrar ese primo dada la entrada podría ser bueno! No sé, por eso pregunté qué significa la palabra.
@JiK ¿Por qué debería ser tiempo polinomial? Eso es completamente irrelevante.
@egreg ¿Existe un significado ampliamente aceptado para la palabra constructivo?
@JiK: ¿Sería suficiente para usted "cada declaración de existencia y distinción de caso se puede codificar como una función recursiva"?
@JohannesKloos No lo sé. Afortunadamente, mi opinión no importa porque no decido lo que es ampliamente aceptado.
Podría ser útil pensar en la prueba en términos puramente teóricos. Dejar PAG denote el conjunto de números primos (este es un conjunto gracias al esquema de especificación del axioma). El teorema de Euclides establece que PAG es un conjunto numerable infinito. Desde PAG está contenido en los números naturales norte , basta con demostrar que PAG es simplemente infinito . Para mostrar esto, basta mostrar que para todo subconjunto finito F PAG de los numeros primos PAG , el complemento PAG F es un conjunto no vacío.
Diría que , en general , la prueba es directa/constructiva, pero hay muchas instancias más pequeñas dentro de la prueba que utilizan una prueba rápida por contradicción.
Puede usar pequeños lemas que involucren prueba por contradicción en su prueba, de la infinidad de números primos, pero no son necesarios.
  1. La prueba se derrumba en cierto sentido. Has llegado a una contradicción, lo que significa que la hipótesis de que hay un número finito de números primos no puede ser cierta.

  2. Pensaste que tenías 6 primos, encontraste 2 extra. ¿Puedes simplemente agregar estos dos a tu lista y obtener todos los números primos? Si repite el proceso en estos 8 números primos, encontrará que tendrá aún MÁS números primos considerando el producto + 1. Puede seguir y seguir y nunca se quedará sin números primos. Esta es la idea de la prueba. Utiliza la contradicción porque puede hacerlo todo en un solo paso y evitar el problema potencial de hacer el proceso infinitamente muchas veces.

Supongamos que solo existen 6 números primos: 2,3,5,7,11,13

Sin embargo, ninguno de los 6 números primos enumerados (2,3,5,7,11,13) divide 30,031.

Entonces ya tenemos una contradicción. Como solo hay 6 primos (lo supusimos al principio) y ninguno de ellos divide 30.031, entonces 30.031 debe ser primo. Sin embargo, 30.031 no es uno de los únicos 6 números primos que existen. Entonces 30,031 no puede ser primo, pero debe ser primo.

Así que la prueba funciona. De hecho, funciona exactamente igual independientemente del conjunto de números que supongamos que son los únicos primos que existen. Por lo tanto, ningún conjunto finito de números puede incluir todos los números primos que existen. Por lo tanto, hay un número infinito de números primos.

Creo que quieres decir "... ningún conjunto finito de números..."

Usted pregunta en el n. ° 1 si la prueba se rompe. No. Lo que falla es la suposición de que no hay más números primos. Asumiste que tenías una lista completa de números primos. Luego construiste un número que no es divisible por ninguno de los números primos de tu lista. Solo quedan dos posibilidades: o el número que construiste es primo o es divisible por un número que no está en tu lista. De cualquier manera, su lista no está completa, lo que contradice su suposición inicial.

En pocas palabras, asumió que tenía una lista completa y al usar esa suposición probó que la lista no estaba completa. Por lo tanto, la suposición debe ser incorrecta.

La respuesta a #3 es básicamente la misma. Al encontrar una contradicción cuando hizo una suposición, probó que la suposición era incorrecta.

La respuesta a la #2 es no, no probaste nada al notar que 59 y 509 son primos. Estás tratando de probar que hay una lista finita de números primos. Si elige un conjunto particular de números primos como lo hizo {2, 3, 5, 7, 11, 13} y demuestra que ese conjunto en particular no contiene todos los números primos, un escéptico simplemente diría que necesita agregar más números primos (como 59 y 509) porque no hiciste tu conjunto lo suficientemente grande. La prueba tiene que ser más general, por lo que no dice cuántos números primos hay en el conjunto finito. La prueba está escrita de modo que funcione sin importar qué tan grande sea el conjunto finito.

Punto 1: Es un teorema que cualquier número natural norte > 1 tiene un factor primo. La demostración es fácil: para cualquier número norte > 1 , el número natural más pequeño a > 1 que divide norte es primo (si no fuera primo, no sería el más pequeño).

Punto 2: Sí, has demostrado que hay más de seis números primos. ¿Así que lo que? La prueba por contradicción no supone que sólo hay seis, sino que hay un número finito de ellos.

Punto 3: En realidad, no es realmente una prueba por contradicción stricto sensu . Está demostrado que toda lista finita de números primos es incompleta.

Aquí hay un enfoque no matemático de la lógica detrás de la prueba por contradicción...

Suponga que su suposición es que un sospechoso de un brutal asesinato es inocente porque dijo que no pudo haber estado en el lugar donde la persona fue asesinada. Sientes que posiblemente esté diciendo la verdad, pero lo que sí sabes es que hay otros 5 sospechosos. Sabes con 100% de certeza debido a los detalles del caso que no puede haber más de otros 5 sospechosos a través de información comprobada. Pero, la policía puede verificar usando evidencia física obvia, como cámaras de video, que los 5 sospechosos posiblemente no sean culpables. Entonces hay otro sospechoso o el que se supone inocente es culpable. Pero dijimos que era imposible considerar a otros sospechosos. Por lo tanto, nuestro sospechoso original es culpable.

Esto es exactamente lo que sucede en una prueba por contradicción.

Esto es bueno. Pero creo que una mejor analogía es que tienes 6 sospechosos y asumes que estos son los únicos seis posibles sospechosos en el mundo. Luego, las cámaras muestran que todos y cada uno son inocentes. Por lo tanto, nuestra suposición de que tenemos a todos los sospechosos es incorrecta y, por lo tanto, hay una séptima persona posible que podría haberlo hecho (y lo hizo).
Joder.... tienes razón. Tenía sentido lógico cuando lo escribí... pero el tuyo es mejor.
El tuyo tiene sentido. Y es una prueba por contradicción. Solo pensé que para esta prueba en particular esta es una analogía más cercana. Yo no diría que el tuyo estuvo mal ni nada.
Ese era mi objetivo original; comprender por qué funciona la contradición. Pero el tuyo hace eso Y es análogo al problema en cuestión. Gracias
Si elimina los detalles extraños, su ejemplo no implica prueba por contradicción. Lo que dices sobre "tu suposición" y lo que "sientes" es irrelevante para el resultado: si se sabe que una de cada seis personas es culpable y cinco de esas personas son inocentes, entonces solo hay una posibilidad para el culpable fiesta. La misma objeción se aplica a la variante de fleablood. En una prueba por contradicción, se hace uso de la hipótesis falsa.
Si asume que su sospechoso es inocente y sabe que hay un número finito de sospechosos, entonces ESTÁ utilizando el hecho de que la suposición es inocente porque entonces está tratando de demostrar que los sospechosos restantes son culpables asumiendo que el suyo es inocente. Estaba tratando de "humanizar" y "legitimar" el ejemplo de una manera que el OP pudiera entender en un nivel no matemático, por eso elegí la palabra sentir. Al probar la infinidad de números primos, puede "sentir" o intuir el camino para ayudar a mostrarlo lógicamente.
@Eleven-Eleven: permítanme decirlo de nuevo: si se sabe que una de un conjunto dado de seis personas es culpable y si se sabe que cinco de esas personas son inocentes, entonces solo hay una posibilidad para la parte culpable. Este argumento no implica prueba por contradicción.
Supongamos que una persona específica de nuestros seis sospechosos es inocente y que es imposible que ningún otro sospechoso esté involucrado. Esto implica que la persona no es culpable. Esto implica que uno de los sospechosos restantes debe ser culpable. Pero no es sospechoso 1 debido a la evidencia... y no es sospechoso 2 debido a la evidencia... y... y no es sospechoso 5 debido a la evidencia. Por lo tanto, ninguno de los 5 sospechosos restantes es culpable, lo que significa que el sospechoso original debe ser culpable. Acabo de usar la implicación de la suposición para mostrar que "P" y "no P" son válidos bajo la suposición...
La declaración ( A B C D mi F ) ( ¬ A ¬ B ¬ C ¬ D ¬ mi ) F es válida en la lógica proposicional intuicionista. Por lo tanto, puede probarse sin el principio de prueba por contradicción. Está confundiendo ex falso quodlibet con la ley del tercero excluido.
voy a conceder Lo entiendo.

La prueba es esencialmente sobreexplicar. El punto de contradicción habría sido mucho más claro si el autor hubiera:

  1. Lo alcancé antes.
  2. Introdujo menos notación.

Desde pag 1 pag norte + 1 no puede tener ninguno de pag 1 , . . . , pag norte como factor primo ya tenemos una contradicción.

El resto es solo explicarle a la muerte por qué pag 1 , . . . , pag norte no pueden ser factores primos de y = pag 1 pag norte + 1 lo cual debe quedar claro ya que y es 1 lejos de ser un múltiplo de cualquiera de esos números primos.

Creo que el gif realmente no se ajusta a este sitio, aunque no puedo decir si hay una regla específica contra tales cosas.
@YuriyS: Hmm... ¡Lamento saber que la gente puede encontrarlo inapropiado! ¡Esa no era de ninguna manera mi intención! ¿Crees que funcionaría mejor eliminando el gif y dejando el enlace y la forma de hablar, o todo eso está ofuscando los puntos que traté de hacer?
@String: su enlace a una película de dibujos animados de un animal muerto golpeado es desproporcionado y ofensivo.
@RobArthan: Lo siento, en algunas partes del mundo, una caricatura de este tipo se consideraría simplemente una forma divertida de ilustrar el dicho sobre golpear a un caballo muerto. Sin ánimo de ofender, solo un tono ligero. No puedo evitar que la gente se ofenda, así que lo eliminé. Todavía me desconcierta cómo ofendería una caricatura que coincidiera con el contenido de un dicho. Soy de Dinamarca, después de todo.
@String: en MSE es más fácil usar un lenguaje neutral. Como soy inglés (después de todo), me permito señalar que la frase cliché es en realidad " flagear a un caballo muerto" y no tiene las connotaciones que crees que tiene (no es "explicar hasta la muerte", es usar un cansino viejo argumento que ha perdido todo interés o relevancia). Tu caricatura no ayuda con eso.
  1. Bueno... sí... se descompone. Asumiste que solo hay 6 números primos y llegaste a una contradicción. Has demostrado con éxito que no solo hay 6 números primos.
  2. Bajo el supuesto de que solo hay 6 primos, 30,031 no es factorizable.
  3. En la prueba por contradicción, usted prueba la proposición A suponiendo que A no es verdadera y, a través de una serie de pasos lógicos, llega a una imposibilidad, demostrando así que A debe ser verdadera. Al mismo tiempo, en esta prueba, asumimos que hay un número finito de números primos. Después de una serie de inferencias lógicas llegamos a una contradicción. Dado que la única suposición que hicimos en el proceso es que hay un número finito de números primos, esa suposición debe ser incorrecta.
  1. Cualquiera 6 los números primos que consideraste no son todos los números primos, o 30031 es un nuevo primo. De cualquier manera la suposición es falsa. Prueba por contradicción.
  2. No, no has demostrado que existen dos números primos más. En este ejemplo sí, pero no en general
  3. Una vez más, según su suposición, llegó a algo imposible que q divide 1 . No hay tal q excepto 1 .

Empezar con 2 , 3 , 5 siendo los únicos números primos. Entonces tendrías 31 como el nuevo número. 2 , 3 , 5 no dividir 31 . Pero a diferencia de tu caso, 31 es un número primo. Entonces la suposición es incorrecta.