Der Satz von Euklid für Dummies

[Pippen]

Ich habe mal versucht, den Satz von Euklid so zu beweisen, so dass man ihn nur mit rudimentären Mathekenntnissen verstehen kann, ziemlich schwierig, weil dieser Beweis mehr an Wissen voraussetzt als man ahnt. Ich wäre dankbar, wenn der eine oder andere mal drüberschauen kann, ob das alles halbwegs stimmt, insbesondere die Struktur des Beweises. Denn ich muss sagen: Wenn ich mir vorstelle, dass dieser Beweis so ziemlich das Einfachste in der math. Beweistheorie ist, dann frage ich mich, wie viele kompliziertere Beweise schlicht ungültig sind und niemand hat es bemerkt, so ähnlich wie man sich bei komplexeren Rechnungen ja auch mal verrechnen kann. Selbst die Hilfe des Computers reicht da nicht, denn der kann sich - wenn auch seltener - ja auch mal verrechnen (oder ist das ausgeschlossen?). Das wirft dann die Frage nach einem Beweis für einen Beweis auf und das klingt nach einem gefährlichen Regress^^.

1. Wir nehmen an, es gäbe nur endlich viele Primzahlen p1, p2,...,p_max.

2. Wir definieren eine Zahl P = p1 x p2 x ... x p_max +1.

3. Es gibt nun nur 2 Möglichkeiten:

3.1. P ist eine Primzahl, dann ist das ein Widerspruch zu 1., denn P wäre als Produkt aller Primzahlen größer als p_max und damit nicht in der Liste von 1., obwohl es eine Primzahl wäre.

3.2. P ist keine Primzahl.

3.2.1. Jede natürliche Zahl größer als 1 hat als kleinsten Teiler eine Primzahl p_klT. (Zwischenbeweis: Jede nat. Zahl größer 1 hat einen kleinster Teiler aufgrund des Wohlordnungsprinzips von IN. Wir nehmen an, der kleinster Teiler p_klT einer nat. Zahl n größer 1 ist keine Primzahl. Wenn p_klT keine Primzahl ist, dann muss p_klT durch eine nat. Zahl a teilbar sein, die nicht 1 oder p_klT ist. Wenn aber p_klT durch a teilbar ist und n durch p_klT, dann ist auch n durch a teilbar (Transivität, die man ebenfalls beweisen könnte/müsste ). Doch damit entsteht ein Widerspruch, weil a kleiner als p_klT sein muss und damit p_klT nicht der kleinste Teiler von n sein könnte, so dass die Annahme, p_klT sei keine Primzahl falsch sein muss.)

3.2.2. Damit hat P einen kleinsten Teiler p_klT, eine Primzahl, die daher in der Liste in 1. stehen müsste und die damit auch P - 1 teilen müsste (eben weil das Produkt P-1 ein Vielfaches von u.a. p_klT ist). Daraus folgt, dass p_klT auch die Differenz P - (P - 1) teilen muss. (Zwischenbeweis: a|b & a|c -> a|b - c. Wir definieren b/a = x und c/a = y. b/a - c/a = x - y (k). Daraus folgt durch Multiplikation mit a auf beiden Seiten: b - c = ka. Damit teilt a die Differenz b - c.) Doch P - (P-1) = 1 und 1 hat keine Primzahl als Teiler. Damit ist entweder p_klT kein kleinster Teiler von P oder steht nicht in der Liste von 1. Ersteres widerspricht 3.2.1. und damit 3.2., was zu 3.1. führte und damit zu einem Widerspruch zu 1., letzteres widerspricht direkt 1.

4. Da beide Möglichkeiten 3.1. und 3.2. zu einem Widerspruch zu 1. führen ist die Annahme in 1. falsch, es gäbe endlich viele Primzahlen.

[tomS]

Sieht irgendwie recht kompliziert aus; was gefällt dir an folgender Variante nicht? welcher Beweisschritt fehlt dir?

1. Annahme: Es existiert eine endliche, vollständige Liste P = {p[down]1[/down], p[down]2[/down],...,p[down]max[/down]} aller Primzahlen; d.h. es gäbe nur endlich viele Primzahlen.

2. Wir definieren eine Zahl q = p[down]1[/down] * p[down]2[/down] * ... * p[down]max[/down] + 1.

3. Es gibt nun 2 Möglichkeiten:

3.1. q ist eine Primzahl. Das ist ein Widerspruch zu (1), denn es wäre q > p[down]max[/down], d.h. q wäre nicht in der Liste enthalten, diese wäre demzufolge im Widerspruch zur Annahme unvollständig.

3.2. q ist keine Primzahl. Dann müsste ein Primteiler p aus P existieren, d.h. ein p, das q ohne Rest teilt. Dieses p aus P kann jedoch nicht existieren, den es ist offensichtlich q / p[down]i[/down] = n[down]i[/down] Rest 1 für alle p[down]i[/down] aus P. D.h. der gesuchte Primteiler p von q wäre nicht in der Liste enthalten, diese wäre demzufolge im Widerspruch zur Annahme unvollständig.

4. Da beide Möglichkeiten (3.1) und (3.2) zu einem Widerspruch zu (1) führen ist die Annahme (1) falsch. Daraus folgt, es muss unendlich viele Primzahlen geben.

q.e.d.

[breaker]

Anmerkung:
pi bezeichnet nicht die Kreiszahl , sondern die i-te Primzahl p[down]i[/down].

[tomS]

ja

[Pippen]

Sieht irgendwie recht kompliziert aus; was gefällt dir an folgender Variante nicht? welcher Beweisschritt fehlt dir?

1. Annahme: Es existiert eine endliche, vollständige Liste P = {p[down]1[/down], p[down]2[/down],...,p[down]max[/down]} aller Primzahlen; d.h. es gäbe nur endlich viele Primzahlen.

2. Wir definieren eine Zahl q = p[down]1[/down] * p[down]2[/down] * ... * p[down]max[/down] + 1.

3. Es gibt nun 2 Möglichkeiten:

3.1. q ist eine Primzahl. Das ist ein Widerspruch zu (1), denn es wäre q > p[down]max[/down], d.h. q wäre nicht in der Liste enthalten, diese wäre demzufolge im Widerspruch zur Annahme unvollständig.

3.2. q ist keine Primzahl. Dann müsste ein Primteiler p aus P existieren, d.h. ein p, das q ohne Rest teilt. Dieses p aus P kann jedoch nicht existieren, den es ist offensichtlich q / p[down]i[/down] = n[down]i[/down] Rest 1 für alle p[down]i[/down] aus P. D.h. der gesuchte Primteiler p von q wäre nicht in der Liste enthalten, diese wäre demzufolge im Widerspruch zur Annahme unvollständig.

4. Da beide Möglichkeiten (3.1) und (3.2) zu einem Widerspruch zu (1) führen ist die Annahme (1) falsch. Daraus folgt, es muss unendlich viele Primzahlen geben.

q.e.d.

Die rot markierten Stellen sind für mich als Laien nicht selbstverständlich und bedürfen einen Zwischenbeweises. Bei mir findet man beide. Das ist wichtig, weil Euklid's Beweis diese Dinge voraussetzt, aber natürlich ein Nicht-Mathematiker nicht weiß (so ging es jedenfalls mir), dass jede nat. Zahl einen Primteiler hat und dass wegen des +1 der Primteiler so nicht existieren kann.

Noch eine Frage, die ich schon angedeutet habe: Wie stellt der Mathematiker sicher, dass kompliziertere Beweise nicht durch Rechenfehler ungültig sind? Das spielt ja auch eine Rolle für unsere parallele Diskussion zur Skepsis in der Mathematik. Kann man sowas überhaupt sicher ausschließen? Denn mE können sich selbst Computer immer mal wieder verrechnen....

[breaker]

Noch eine Frage, die ich schon angedeutet habe: Wie stellt der Mathematiker sicher, dass kompliziertere Beweise nicht durch Rechenfehler ungültig sind? Das spielt ja auch eine Rolle für unsere parallele Diskussion zur Skepsis in der Mathematik. Kann man sowas überhaupt sicher ausschließen? Denn mE können sich selbst Computer immer mal wieder verrechnen....

Natürlich kann man das nie völlig ausschließen.

[Stephen]

Ich hatte mich hier mal darüber informiert:
https://www.youtube.com/watch?v=piY6tA41xnQ
Leider ist die Tonqualität nicht überragend. Dafür aber die Frisur des Professors

Gruß
Steffen

[tomS]

@Pippen:

Die erste rote Stelle muss man nicht beweisen.

Die zweite rote Stelle ist offensichtlich, dein Beweis m.E. zu kompliziert. Wir haben

q = p[down]1[/down] * p[down]2[/down] * ... * p[down]max[/down] + 1

Wir nehmen an, p aus P sei der gesuchte Primteiler, d.h.

q = p[down]1[/down] * p[down]2[/down] * ... p * ... * p[down]max[/down] + 1

Damit ist

q / p = n + 1 / p

Das ist elementares Rechnen; man sieht dem q diese Eigenschaft unmittelbar und ohne weiteren Beweis an. Aber man kann natürlich diese Nebenrechnung ausführen.