Diskussion:Satz des Euklid

Vielleicht wär ein Hinweis auf 'Lemma von Euklid' bzw. 'Eindeutigkeit der Primfaktorzerlegung' noch sinnvoll, ohne hab ich nämlich nicht verstanden, warum (z+1) 'ne neue Primzahl/in neue Primfaktoren zerlegbar sein muss.

Wie die Beispiele zeigen, ist (Z+1) doch nicht unbedingt eine Primzahl. Deshalb müsste die Schlussfolgerung aus Euklid's Ansatz wohl heissen: (Z+1) ist entweder eine Primzahl oder durch mindestens eine Primzahl teilbar, die grösser als PN ist. Da BEIDE Alternativen der Annahme widersprechen, ist bewiesen, dass es keine grösste Primzahl gibt. Ich kann allerdings nicht sagen, ob Euklid dies schon so oder ähnlich formuliert hat.

Du hast recht: Z+1 ist nicht notwendig selbst eine Primzahl. Selbst mit der Annahme, dass man mit p1, ..., pn alle Primzahlen hat, folgt nur, dass Z+1 einen Primteiler hat, der nicht einer der p1, ..., pn ist. (Er muss nicht notwendig groesser als pn sein.)

Soweit ich weiss, hat Euklid "nur" gezeigt, dass keine endliche Zahl ausreicht, alle Primzahlen zu zaehlen. Er nimmt dazu n Primzahlen p1, ..., pn, und folgert, dass der Primteiler von Z+1 eine weitere Primzahl ist. Daraus folgt, dass es mehr als n Primzahlen gibt.

Da das nun fuer jede natuerliche Zahl n gilt, gibt es unendlich viele.

Aber auch ich gebe zu, dass mir die Originalversion nicht bekannt ist, sondern nur einige Varianten, die man in der Schule und waehrend des Studiums lernt. Alle diese Varianten stimmen aber im Kern ueberein. --SirJective 12:26, 20. Nov 2003 (CET)

Ich denke schon, dass jeder Primteiler von (Z+1) grösser als pn sein muss (wenn vorhanden), da p1...pn ja per Definition schon alle angenommenen Primzahlen enthält.

Ich denke eher, wenn schon p1, ..., pn ALLE Primzahlen sind, dann hat jeder Primteiler von Z+1 wahlweise überhaupt keine Eigenschaften, oder er hat alle Eigenschaften - weil es ihn nicht gibt (schliesslich stimmt er mit keinem pi überein). (NB: Welche Eigenschaften haben nicht existierende Objekte?) --SirJective 21:40, 20. Nov 2003 (CET)

Der untere Ergänzung ist zwar richtig, verwirrt aber anscheinend in dieser Formulierung die Leser. Denn der Beweisschritt, dass die Zahl Z+1 eine Primzahl sei, folgt eben aus den Beweisprämissen und führt diese zum Widerspruch. Heizer 11:24, 23. Nov 2003 (CET)

Vorsicht: Es wird nirgends vorausgesetzt, dass die p1 bis pn die ersten n Primzahlen sein müssen. Möglicherweise hat man ja irgendwo eine zwischendurch vergessen. Also etwa p1=2, p2=5, p3=11. Dann ist der kleinste Primteiler von Z+1=111 die 3. Möglicherweise sollte man die Beispiele auf der Seite anderst wählen. --Berni 22:11, 2. Jan 2004 (CET)

Hab den Absatz im Beweis entsprechend angepasst. Zusätzliche Beispiele, bei denen zwischendurch Faktoren weggelassen sind, halte ich für hilfreich. (Hab nur gerade keine Lust zu rechnen *g*) --SirJective 13:48, 3. Jan 2004 (CET)

Aber ich ;-) Hab' die Beispiele überarbeitet --Berni 16:00, 3. Jan 2004 (CET)

Lassen wir die Frage, ob alle Teiler von (Z+1) größer als PN sind (1 ist auf jeden Fall kleiner), mal offen und fragen uns, ob die Aussage Euklids, es gibt keine letzte Primzahl, überhaupt innerhalb seines Axiomensystems zulässig ist. Es heißt sein Beweis sei einfach und elementar, aber ich fürchte, daß er keineswegs elementar ist. Wie wir wissen, spielen große Primzahlen in der Kryptologie eine wichtige Rolle. Um solche Verschlüsselungs-Primzahlen zu erhalten, müssen selbst die heute leistungsfähigsten Rechner Tage oder Wochen rechnen. Andererseits kann man beliebig große Primzahllücken konstruieren. Daraus folgt, daß die Folge der Primzahlen recht "dünn" wird, wenn die Zahlen genügend groß sind. Meine Überlegung ist nun folgende: Wenn selbst die leistungsfähigsten Rechner (selbst bei zig-milliardenfach gesteigerter Rechenleistung gegenüber heute) in endlicher Zeit keine neue, größere Primzahl mehr ausrechnen können (z.B. weil das Alter des Universums nicht ausreichen würde, um in dieser Zeit eine noch größere Primzahl auszurechnen), kann man dann überhaupt zulässigerweise davon sprechen, die Folge der Primzahlen reiße nicht ab?

Da es sicherlich eine natuerliche Zahl gibt, bis zu der man in Einerschritten selbst mit dem schnellsten Computer des Universums nicht in der (als endlich angenommenen) Lebenszeit des Universums zaehlen kann, kann man dann ueberhaupt zulaessigerweise davon sprechen, die Folge der natuerlichen Zahlen reisse nicht ab?

(Wenn wir davon ausgehen, dass unser 'Supercomputer' in endlicher Zeit nur endlich viele Einerschritte zaehlen kann, dann wird er in der endlichen Lebensspanne des Universums nur, sagen wir, A Schritte zaehlen koennen. Woher wissen wir dann, dass es noch eine Zahl A+1 gibt?)

Andererseits kann man natuerlich auch Zahlen durch Formeln ausdruecken. Geht man nicht in Einerschritten, sondern multipliziert jedesmal mit 10, erreicht man eine viel groessere Zahl (10^A, um genau zu sein), jedoch keine Zahl, die noch groesser ist.

Nebenbei kann man mit den endlich vielen Elementarteilchen im (bekannten) Universum ueberhaupt nur endlich viele Zahlen beschreiben (denn es gibt nur endlich viele Zustaende des Universums selbst). "Gibt" es dann ueberhaupt unendlich viele natuerliche Zahlen?

Ich sage ja, denn die Existenz natuerlicher Zahlen und grosser Primzahlen ist nicht an ihre Berechenbarkeit gebunden. Andere sagen nein, denn es existiert nur, was berechenbar ist.

Das gleiche Problem stellt sich bei den rationalen Zahlen. Wenn man sagt, daß die Zahlengerade der rationalen Zahlen überall dicht ist und trotzdem beliebig viele Irrationalzahlen dazwischen schieben kann, geht man stillschweigend, ohne daß das in Euklids Axiomensystem ausdrücklich gefordert ist, davon aus, daß man über unbegrenzte Zeit und unbegrenzte Rechenkapazität verfügt.

Kein Axiomensystem, welches reelle Zahlen (so wie ich sie kenne) definiert, macht Aussagen ueber Berechenbarkeit. Ebensowenig ist Berechenbarkeit eine Voraussetzung fuer Existenz. Andere Axiomensysteme, die Berechenbarkeit fordern, liefern nicht alle reellen Zahlen, sondern nur 'berechenbare Zahlen'. (Und selbst die sind nicht alle als endlicher Dezimalbruch darstellbar, sondern nur als Turingmaschine.)

Dieses Axiom hat Euklid nicht eingesetzt und es dürfte auch schwer fallen, es überhaupt als selbstverständlich, jedem Vernünftigen einleuchtend hinzustellen.

Jeder hinreichend Vernuenftige wird feststellen, dass an dieser Stelle Meinungen aufeinanderprallen, und Vorstellungen von reellen Zahlen, die nicht kompatibel sind. Daher eruebrigt sich eine Diskussion ueber die "Selbstverstaendlichkeit" der Notwendigkeit der Berechenbarkeit.

Ich vermute, daß diese Überlegung nicht allen Mathematikern gefallen wird, aber ich halte sie trotzdem für legitim und frage mich, ob man diese stillschweigende Annahme voraussetzen darf, ohne sich um eine Begründung für sie zu bemühen.

Die Annahme, Berechenbarkeit sei notwendig fuer die Existenz von Zahlen, hast du gemacht. Es gibt genug Mathematiker, die diese Annahme nicht machen, sich aber bewusst sind, dass nicht alle ihre Objekte berechenbar sind. Trotzdem existieren sie in dem Sinne, dass ihre Existenz keine Widersprueche innerhalb(!) des Axiomensystems hervorruft.

Meines Erachtens ist es durchaus fraglich, ob man aus Euklids Beweis, daß die Folge der Primzahlen nicht abreißt, folgern darf, die Folge der Primzahlen sei unendlich. Denn diese Folgerung setzt stillschweigend voraus, daß man über unbegrenzte Zeit und Rechenkapazität verfügt, obwohl das in den Axiomen Euklids nicht ausdrücklich vorausgesetzt wird bzw. voraussetzbar ist.

Das sehe ich anders. Mit meinem obigen Abschnitt stelle ich dir die Frage, ob die Menge aller natuerlichen Zahlen unendlich ist. Ich denke, eine konsistente Antwort muss lauten: Wenn es notwendig ist, Zahlen berechnen zu koennen damit sie existieren, dann gibt es auch nur endlich viele natuerliche Zahlen. Damit waere klar, dass es nur endlich viele Primzahlen gibt.

Ich würde mich über Zusendungen und Diskussionsbeiträge freuen. Meine Email-Adresse lautet: harald@haraldtrachmann.de (21.11.2003 1045h)

Leider hab ich nicht wirklich Lust, mich auf eine Grundsatzdiskussion einzulassen (hatte ich schon - so intensiv wie vergeblich - in news:de.sci.mathematik, Thema "Widersprueche der Mengenlehre"), daher hoffe ich, dass du dich aus verschiedenen Quellen selbst informierst, welche unterschiedlichen Ansichten es da gibt (Stichworte sind z.B. : mathematischer Konstruktivismus, Unendlichkeitsaxiom). --SirJective 11:52, 21. Nov 2003 (CET)

Erst mal vielen Dank für Deine schnelle und moderate Antwort. Ich denke, wir sollten meinen Ausgangspunkt beachten, der von der elementaren Mathematik, wie sie Euklid und dem normalen Schulunterricht zur Verfügung stand, ausging. Demnach wäre es keineswegs korrekt, Euklids Beweis als selbstverständlich hinzustellen, da er nicht Axiome voraussetzen darf, die Peano und Fraenkel erst im letzten Jahrhundert aufgestellt haben. Ich stimme Dir aber zu, daß meine Überlegung streng genommen schon für die Folge der natürlichen Zahlen, ihre Produkte, Ihre Potenzen etc. gilt. Ich stehe auf dem Standpunkt, daß man weder über das unendlich Kleine, noch unendlich Große etwas hinreichend Sicheres sagen kann und darf, weil es sich unseren Untersuchungen entzieht. Hier würde ich durchaus etwas mehr Zurückhaltung begrüßen. Immerhin hast Du darauf verwiesen, daß hier gegensätzliche Meinungen aufeinanderprallen und da wollen wir nicht streiten, sondern das Problem unentschieden lassen. Das Wichtigste dürfte auch in der Mathematik sein, daß sie den Mathematikern Spaß macht. [Benutzer: Harald Trachmann 22:07, 21. Nov 2003(CET)]

Wenn man alle Primzahlen nimmt, die kleiner als n sind, und aufmultipliziert zu Z; dann ist (Z+1) entweder selber eine Primzahl oder hat einen Primteiler, der größer als n und kleiner als (Z+1) ist. Wenn man aber irgendwelche n Primzahlen nimmt z. B. p1=2 und p2=7, also n=2, diese aufmultipliziert zu (Z+1)=2*7+1=15=3*5, dann ist nicht mehr zwangsweise die größer und kleiner Relation vorhanden!

Vom mathematischen Standpunkt ist der Beweis http://de.wikipedia.org/wiki/Euklids_Primzahlbeweis richtig. Es gibt einen Widerspruch; allerdings sollte man dazu in der Beweisführung (Z+1) nicht als Primzahl bezeichnen, da dies keine schlüssigeg Folgerung ist. Die richtige und schlüssige Folgerung ist: Es gibt eine weitere Zahl mit den Eigenschaften einer Primzahl, die (Z+1) teilt und ungleich 1 ist (i. B. kann dies auch (Z+1) sein), daher können die angenommenen n Primzahlen nicht alle sein und es ergibt einen Widerspruch. Der induktive Ansatz (wie er z. B. auch bei der Definition der natürlichen Zahlen verwendet wurde) ergibt nun die unendliche Anzahl an Primzahlen.

Wenn alles Berechnbar sein muß, was existiert, dann steht die heutige Mathematik nicht mehr! Alles bricht zusammen. Beispielsweise der Integralbegriff wie ihn wahrscheinlich jeder aus der Schule kennt ist der Riemann'sche Integralbegriff. In der Schule wird dieser normalerweise mittels Intervallschachtelung eingeführt. Dabei muß zwangsweise die Intervallanzahl, mit der das Integral approximiert wird (also diese Summenschreibweise eines Integrals), gegen unendlich gehen.

Nein, nicht unbedingt. Es würde völlig reichen, wenn man die Intervallschachtelung hinreichend genau macht. Die meisten Nullfolgen sind schon nach relativ wenigen Schritten genau genug. Die Frage ist halt, ob wir immer auf die Genauigkeit ganzzahliger Ergebnisse abheben sollten. Ich meine, daß diese Forderung viel zu streng und aufwendig ist.

Was ist denn nun unendlich? Wie berechnet sich nun das Integral? Also existiert das Integral, obwohl es nicht berechenbar ist. Naja, eigentlich etwas komplizierter, aber im wesentlichen existiert alles, was nach einer Vorschrift aufbaubar ist (um nicht berechenbar zu sagen). Und es spielt dabei keine Rolle, wie lange das dauert.

Das ist die Frage! Möglicherweise haben sich die älteren Mathematiker darüber gar nicht den Kopf zerbrochen, weil es für sie nicht wichtig oder aktuell war. Aber ich meine schon, daß wir nicht irgendwelche Vorschriften zugrundelegen dürfen, die sich in Endlosschleifen verlieren, ohne daß am Ergebnis sich etwas ändert.

Die Mathematik will ganz prinzipiell Strukturen bauen und verstehen. Dabei kann man nicht zwangsweise jeden Punkt dieser Struktur angeben, aber jeder Punkt ist genau betrachtbar sein.

Auch das dürfte schwer sein, da jedes Ordnungsprinzip ab einer bestimmten Größe nicht mehr handbar wird.

Widerspruchsbeweis ?

Euklids Beweis ist kein Widerspruchsbeweis. Es ist ein ziemlicher Anachronismus, Euklid solche Gedanken zu "Endlichkeit" und "Unendlichkeit" unterzuschieben.

Behauptung: Es gibt mehr Primzahlen als jede vorgelegte Menge von Primzahlen

Beweis: Man hat eine vorgelegte Menge von Primzahlen p1, p2, .., pr Dann hat die Zahl p1 * p2 * ... * pr + 1 keine der Primzahlen p1 bis pr als Teiler. Also gibt es eine weitere Primzahl q.e.d.

Die Annahme "Es gibt eine endliche Menge von Primzahlen" ist für die Behauptung und den Beweis völlig überflüssig und wurde von Euklid nicht benutzt. Daher ist es auch kein Widerspruchsbeweis. Euklid hat weder in dem Satz noch im Beweis die Begriffe endlich und unendlich benutzt (wie auch ?) Ich würde den Abschnitt gern ändern. UlrSchimke 00:40, 20. Feb 2006 (CET)

Die Bezeichnung "Widerspruchsbeweis" ist ja ohnehin kaum zu fassen, wenn man da nicht etwas unterschieben will, das gar nicht gemeint ist, wie z.B. ein Beweis, der ohne das Prinzip des tertium non datur nicht funktioniert oder so.--Gunther 00:50, 20. Feb 2006 (CET)

Ich habe jetzt nochmal nachgelesen. Im Beweis selber wird doch ein Widerspruchsargument benutzt, aber "endlich" und "unendlich" nicht. Ich habe den Beweis jetzt ergänzt UlrSchimke 00:18, 28. Feb 2006 (CET)

Der Beweis ist korrekt, das ist gut, denn meistens wird er falsch dargestellt, aber Beispiele zu einem Widerspruchsbeweis??? Das ist äusserst bedenklich... Wenn dann müsste man schreiben: Es ist nicht richtig, dass 2,3,5 die einzigen Primzahlen sind, denn ... usw. Aber Beispiele? Genaugenommen sind das eigenständige Aussagen, also Sätze, die Spezialfälle des Satzes von Eukild sind. Die Bezeichnung "Beispiele" ist schlecht.--128.101.154.21 22:40, 22. Feb 2006 (CET)

Beispiele

Du hast recht, "Beispiele" gefällt mir auch nicht so recht zumindest würd ich etwas anders formulieren. Ich wüde nicht:

   * Angenommen, 2, 3, 5, 7 und 11 seien die einzigen Primzahlen. Dann berechnet man 2311 = weitere Primzahl.

schreiben, sondern das Beispiel mehr wie Euklid ausführen, wenn er schreibt: „Es gibt mehr Primzahlen als jede vorgelegte Anzahl von Primzahlen.“.

Man lege sodann { 2, 3, 5, 7, 11 } als Menge von Primzahlen vor und berechne daraus 2311. Man erhält eine neue Primzahl, die nicht in der vorgelegten Anzahl von Primzahlen enthalten ist. Man erspart sich auf diese Weise auch das Widerspruchsargument.

Offen gestanden, gefällt mir die Formulierung "Angenommen, X und Y seien die einzigen Primzahlen" überhaupt nicht. (nicht signierter Beitrag von 81.10.251.217 (Diskussion) 10:32, 22. Apr 2006)

Naja, bei Widerspruchsbeweisen muss man nun einmal falsche Annahmen treffen. Aber ansonsten Zustimmung.--Gunther 10:36, 22. Apr 2006 (CEST)

Wie wäre es denn mit "Angenommen, X und Y seien alle Primzahlen" --Arbol01 11:44, 22. Apr 2006 (CEST)

Ich bin dafür den Abschnitt Beispiel ganz zu löschen. Dieser Artikel geht über einen Satz, der eine Aussage zur Anzahl der Primzahlen trifft. Mit Hilfe dieses Satzes lässt sich nun mal nichts berechnen. Also kann man auch keine Beispiele angeben. Die jetzigen „Beispiele“ sind m. E. nur Zahlenspielereien. --Squizzz 13:27, 22. Apr 2006 (CEST)

Oh doch! Es läßt sich mit jeder endlichen Menge an Primzahlen zeigen, daß weitere, noch unbekannte Primzahlen existieren müssen. --Arbol01 02:00, 23. Apr 2006 (CEST)

Ausserdem wird der Satz von Euklid erst durch Beispiele für viele Leute verständlich. --Arbol01 02:02, 23. Apr 2006 (CEST)

@Squizzz: Der Beweis hat durchaus eine konstruktive Komponente, die man an einem Beispiel illustrieren kann. Manche andere Beweise der Unendlichkeit der Menge der Primzahlen liefern kein Verfahren, um aus einer endlichen Menge weitere Primzahlen zu gewinnen.--Gunther 02:15, 23. Apr 2006 (CEST)

Zwei unterscheidliche Beweise ?

Ich denke nicht, das der urspüngliche Beweis von Euklid sich wirklich essentiell von dem zuvor dargestellten unterscheidet. Die kleinste Zahl m in Euklid's Beweis ist genau das Produkt aller Primzahlen. Dies ist jedoch für den Beweis überhaupt nicht wesentlich wie diese Zahl berechnet werden kann.

Eigentlich könnte man sich auf die ursprüngliche Form von Euklid beschränken.

Ich habe mir den vermeintlichen Beweis von Euklid mal genauer angesehen. Da ist doch einiges etwas sehr seltsam formuliert. Ich halte es doch für zweifelhaft, dass dies wirklich die Orginalform des Beweises ist.

Der Beweis in seiner jetztigen Form ist unverständlich und wohl auch falsch. Ich werde mal einen nachvollziehbaren Beweis einfügen.

(nicht signierter Beitrag von Fsswsb (Diskussion | Beiträge) 12:29, 23. Apr 2006)

Der Beweis folgt in der jetzigen Form Euklid und ist korrekt. Wenn Du ihn nicht verstehst, dann unterlasse weitere Änderungen und erläutere, welcher Punkt Dir unklar ist.--Gunther 13:39, 23. Apr 2006 (CEST)

Einleitungssatz

Wie wäre es, statt "Der Satz von Euklid besagt, dass es keine größte Primzahl gibt. Dies ist gleichwertig zu der Aussage, dass es unendlich viele Primzahlen gibt." als Einleitung "Der Satz von Euklid besagt, dass jede endliche Menge von Primzahlen unvollständig ist." zu Verwenden? --Arbol01 13:41, 23. Apr 2006 (CEST)

Auf jeden Fall sollte das mit der größten Primzahl raus, davon ist ja nirgends die Rede. Aber ich denke schon, dass "dass es unendlich viele Primzahlen gibt" eine zulässige Modernisierung von Euklids Aussage darstellt. Wie er es formuliert hat, steht ja gleich danach.--Gunther 13:44, 23. Apr 2006 (CEST)

Sorry, das war auch nicht meine Absicht. Also "Der Satz von Euklid besagt, dass jede endliche Menge von Primzahlen unvollständig ist." statt "Der Satz von Euklid besagt, dass es keine größte Primzahl gibt." --Arbol01 13:46, 23. Apr 2006 (CEST)

Das Problem dabei ist halt, dass "unvollständig" weder Fachsprache noch wirklich allgemeinverständlich ist. Ich denke, dass "Der Satz von Euklid besagt, dass es unendlich viele Primzahlen gibt." als Einleitung völlig ausreichend ist, zusammen mit dem jetzigen zweiten Absatz.--Gunther 13:49, 23. Apr 2006 (CEST)

Auch gut! Ich kann die Bedenken bezüglich des unvollständig nachvollziehen. --Arbol01 13:53, 23. Apr 2006 (CEST)