Peano-Axiome: warum sind 2 und 3 Primzahlen ?

[ralfkannenberg]

Hallo zusammen,

an sich ist der Thread-Titel völlig falsch, denn um Primzahlen ermitteln zu können muss eine Division definiert sein und das ist mit Hilfe der Peano-Axiome nicht möglich. Da braucht es also noch etwas mehr und wir wollen stillschweigend annehmen, dass wir die Halbgruppe, die aus den Peano-Axiomen definiert ist, zu einer minimalen Gruppe (bis auf Isomorphie) erweitert haben und auf ihr eine Multiplikation definiert haben.

Dann haben wir also eine Menge, die isomorph zu den ganzen Zahlen ist, wir betrachten nur die positiven und dann haben wir schon alles, was wir für Primzahlen benötigen.

Nun, 2 ist eine Primzahl, weil sie nur durch 1 und durch sich selber teilbar ist, und 3 ist eine Primzahl, weil sie nur durch 1 und durch sich selber teilbar ist. Das weiss jeder.

Man könnte es auch so formulieren, dass eine Primzahl eben keine "echten" Teiler hat, wobei ein echter Teiler eine Zahl ist, die ein Teiler ist und die echt grösser als 1 und echt kleiner als die Zahl selber ist.

Aber das 2 und 3 nun Primzahlen sind haben wir letztlich durch "Ausprobieren" herausgefunden, indem man einfach alle potenziellen Teiler bis und mit der Zahl "ausprobiert" haben, wobei es schon genügen würde, alle potenziellen Teiler bis zur Quadratwurzel auszuprobieren, denn wenn wir zwei Teiler einer Zahl haben, so ist stets einer der beiden kleiner oder gleich der Quadratwurzel und die andere stets grösser oder gleich die Quadratwurzel.

Wenn ich also wissen will, ob 49 eine Primzahl ist, so genügt es, alle Primzahlen bis zur 7 auszuprobieren, denn wenn sich ein grösserer Teiler findet, so ist der andere Teiler eben kleiner als 7.

Schön und gut, genug repetiert.

Peano-Axiome:
Wir wollen die Aufgabe nun so lösen, dass wir nur die Peano-Axiome verwenden und nichts anderes. Für grössere Zahlen ist das umständlich, aber für 2 und 3 ganz witzig machbar.

Ich stelle mir diesen Thread am ehesten als eine Art Lehrgespräch vor, in dem wir zahlreiche Ideen sammeln, die können auch mal etwas auf den Holzweg führen; mal schauen, wohin uns das führen wird. Ich hoffe natürlich auch, selber etwas "mitnehmen" zu können.

Ich fange mal mit der 2 an, weil das so einfach ist, dass man es fast schon übersieht:

Dadurch, dass die 1 ja kein "echter" Teiler ist, ist 2 der kleinst-mögliche echte Teiler überhaupt.

Und der "kleinst-mögliche echte Teiler überhaupt" kann also nicht einen noch kleineren echten Teiler haben. Somit ist 2 eine Primzahl.


Freundliche Grüsse, Ralf

[M_Hammer_Kruse]

Ja, das ist für die Drei auch nicht wirklich schwer.

Nach Peano ist die Multiplikation mit Hilfe des Induktionsaxioms definiert:
Es ist n*0=0 für alle n und n*m'=n*m+n für alle m und ihre jeweiligen Nachfolger m'.

Nun kann man schauen, ob die 3 in zwei echte Teiler n und m' zerlegbar ist.
Dazu muss 3 in die Summe aus (n*m) und n zerfallen.
Nun gibt es nur die folgenden Möglichkeiten, 3 in eine Summe zu zerlegen: 3+0, 2+1, 1+2 und 0+3.
(Die Ausschließlichkeiten dieser Summenmöglichkeiten muss man vorher nachgewiesen haben.
Dazu ist das Induktionsaktiom und die Peanosche Summendefinition nötig.)

Diese vier Möglichkeiten untersuchen wir jetzt näher:
(Dabei sei vorausgesetzt, dass
a) die Kommutativität der Multiplikation schon gezeigt ist und
b) 1 nicht echt faktorisierbar ist.)

In allen Fällen ist der zweite Summand, also n, einer der beiden Teiler.
Da entfallen schon mal die Möglichkeiten 3+0, 2+1 und 0+3, weil 0, 1 bzw. 3 keine echten Teiler sind.

Es bleibt also nur noch die Zerlegung 3=1+2 als erfolgversprechender Kandidat.
Da ist also n=2 und es muss n*m'=1 sein.
Dies widerspricht der Nicht-Faktorisierbarkeit der 1.
Es gibt also kein m, so dass 2*m=1 ist und daher auch kein m', mit dem 2*m'=3 ist.

q.e.d.

Gruß
mike

[ralfkannenberg]

Hallo Mike,

besten Dank ! - Ich drucke mir das mal aus und lese das dann in Ruhe durch ...

Ich hatte eher an eine einfachere, nicht-algebraische bzw. nicht-zahlentheoretische Lösung gedacht, die in die Richtung geht, dass die kleinst-mögliche Nicht-Primzahl das Produkt der beiden kleinst-möglichen Teiler ist (also 2*2=4) und dass die 3 eben kleiner als dieses Produkt ist, weil die 1 kleiner als die 2 ist, also 3=2' < 4=2".

Und das jetzt halt in der Sprache der Nachfolger übersetzt und dabei verwenden, dass die Nachfolger eindeutig sind, z.B. 2" = (1')" = (1")'.


Freundliche Grüsse, Ralf

[ralfkannenberg]

Da ist also n=2 und es muss n*m'=1 sein.

Hallo Mike,

das ist ein sehr schöner Beweis, denn Du uns vorgestellt hast, ich glaube, da ist noch ein kleiner Schreibfehler: das m im Zitat sollte ungestrichen sein.

Was aber nichts am Argument ändert.

Ich werde Deinen Beweis heute abend heute abend noch den Laien im Forum erläutern.


Freundliche Grüsse, Ralf

[Herr Senf]

Hi, dann brauch ich nicht einschalten Matheallergie, sind ja nur zwei eingeladen

heute abend heute abend

[M_Hammer_Kruse]

Hallo Ralf,

ja, das muss m heißen.
Allerdings finde ich, dem Beweis fehlt die Eleganz. Er ist vielleicht korrekt, aber eine Fallunterscheidung ist immer ein wenig wie hilfloses Herumeiern ohne umfassende Idee. Damit bezieht er sich auf den konkreten Einzelfall und öffnet wenig Türen für eine verallgemeinerte Betrachtung.

Gruß
mike

[ralfkannenberg]

Allerdings finde ich, dem Beweis fehlt die Eleganz. Er ist vielleicht korrekt, aber eine Fallunterscheidung ist immer ein wenig wie hilfloses Herumeiern ohne umfassende Idee.

Hallo Mike,

interessant, wie man das unterschiedlich beurteilt: ich habe diesen Teil, bei dem Du die unechten Teiler ausschliesst, als ganz besonders elegant empfunden.

Vielleicht deswegen, weil bei so einer kleinen Zahl wie der 3 alle "kleineren" natürlichen Zahlen mit Ausnahme der 2 darin Erwähnung finden. Weil es nicht ein stupides Abzählen ist, sondern jede dieser Zahlen schon alle möglichen "Rollen" ausfüllt, also diejenige des "Nullelementes", diejenige des "Einselementes" sowie diejenige der Zahl selber, die ja auch ein unechter Teiler ist, also der 3.

Ja das ist ja gerade die Schönheit des Argumentes, dass man eben mit einer so einfachen, aber eben auch notwendigen Betrachtung bereits fast alle Kandidaten ausschliessen kann. Es kommt mir ein bisschen wie ein Theaterstück mit Kindern vor: 4 Kinder spielen mit und 3 von ihnen bekommen eine bedeutsame Rolle: Nullelement, Einselement und Zahl selber.

Und es sind bedeutsame Rollen, auch wenn sie dem Laien irgendwie banal vorkommen mögen.

Und dann verbleibt nur noch eine seperate Rolle, diejenige des bis anhin einigen bekannten echten Teilers, und diese Rolle, die die 2 - also 1' - innehat, wird dann einer eigenen Betrachtung unterzogen.


Freundliche Grüsse, Ralf

[ralfkannenberg]

Hallo zusammen,

ich möchte nun also den Beweis von Mike etwas laienverständlicher darstellen.

Mike's Beweisidee ist eigentlich einfach:

1. er definiert eine Multiplikation aus den Peano-Axiomen heraus - der Laie sieht das nicht auf den ersten Blick, weil der "+1-Operator" mit dem Nachfolger-Apostroph gekennzeichnet wird, also n' = n+1

2. er macht aus der Multiplikation eine Summe, bezüglich der etwas gelten muss

3. er untersucht die verschiedenen Fälle, kann 3 von ihnen einfach ausschliessen und betrachtet dann den vierten Fall genauer


Gehen wir nun also mal Schritt für Schritt durch:

Nach Peano ist die Multiplikation mit Hilfe des Induktionsaxioms definiert:
Es ist n*0=0 für alle n und n*m'=n*m+n für alle m und ihre jeweiligen Nachfolger m'.

Das sieht ganz schrecklich aus, doch es ist ganz einfach.

Wie kann man eine Multiplikation von der Zahl n definieren ? Nun, man definiert sie für m=0, dann nimmt man an, dass sie schon für m definiert sei und definiert sie für m+1. Man beachte, das Mike streng genommen nur eine Multiplikation "auf einer Seite" definiert, aber das ist völlig genügend.

Wir wissen, dass man Peano-Axiome und vollständige Induktion im wesentlichen synonym verwenden darf, d.h. etwas hochgestochen nennt man diese 3 Schritte "Induktionsverankerung", "Induktionsannahme" und "Induktionsbehauptung", nur dass die Induktionsbehauptung in diesem Falle keine Behauptung, sondern eine Definition ist.

Für 0 ist die Multiplikation so definiert:

(1) n * 0 = 0

Sei die Multiplikation schon bis zur natürlichen Zahl m definiert, dann muss man noch definieren, wie sie für m+1 aussieht:

(2) n * (m+1) = n*m + n ; das folgt ja schon aus dem Distributivgesetz.

Da die Multiplikation bis m definiert ist, ist der Ausdruck n*m bekannt und dazu noch +n zu addieren ist ebenfalls bekannt.

Nun schreiben wir Gleichung (2) noch in der Sprache des Nachfolgeoperators, also statt der additiven (+1)-Schreibweise mit Hilfe des Nachfolger-Apostrophs:

(2) n * m' = n*m + n

Und das ist genau das, was Mike geschrieben hat.

Hier ist noch etwas anzumerken: Mike setzt die Peano-Axiome so, dass 0 das Startelement ist. Und stillschweigend der Nachfolge-Schritt den Wert +1 hat, an sich könnte man auch den Wert (-20) für den "Nachfolgeoperator" wählen, das würde den Peano-Axiomen nicht widersprechen. Üblicherweise wählt man aber die Schrittweite +1 und variiert den Startwert je nach Anwendung; meist wählt man 0 oder 1. Ich selber bin da etwas puristisch und bevorzuge die 1 als Startwert; im vorliegenden Fall ist es aber viel zweckmässiger, die 0 als Startelement zu wählen, weil man dann nämlich wie oben gesehen die Multiplikation so bequem definieren kann.

Nun kann man schauen, ob die 3 in zwei echte Teiler n und m' zerlegbar ist.

Hierzu sind 2 Sachen zu sagen: erstens ist die Zahl 3 eben dann keine Primzahl, wenn man sie in zwei echte Teiler zerlegen kann. Und zweitens fällt auf, dass Mike den rechten Teiler als Nachfolger geschrieben hat. Das darf er ohne Einschränkung der Allgemeinheit tun, denn mit Ausnahme des Startelementes sind alle Peano-Zahlen Nachfolger einer anderen Peano-Zahl.

Und wenn er das Produkt 3 = n * m' eben in dieser Form schreibt, so kann er Gleichung (2) anwenden, und das ist ja gerade die Beweisidee, die Mike anwenden will.

Der "Ausnahme"-Fall 3=n*0 kann nicht vorkommen, weil 3=n*0=0 gilt, die Zahl 3 aber von 0 verschieden ist; somit ist der zweite Faktor also tatsächlich ein Nachfolger einer Peano-Zahl.

Wir setzen also:

(3) 3 = n * m'

Und nun kann man die Gleichung (2) anwenden, so dass gilt:

3 = n * m' = n*m + n, also 3 = n*m + n.

Das ist genau das, was Mike nun weiter geschrieben hat:

Dazu muss 3 in die Summe aus (n*m) und n zerfallen.

Machen wir mal weiter:

Nun gibt es nur die folgenden Möglichkeiten, 3 in eine Summe zu zerlegen: 3+0, 2+1, 1+2 und 0+3.
(Die Ausschließlichkeiten dieser Summenmöglichkeiten muss man vorher nachgewiesen haben.
Dazu ist das Induktionsaktiom und die Peanosche Summendefinition nötig.)

Ich denke, man darf diesen Nachweis etwas schlampig führen: dadurch, dass das Startelement 0 ist, wird bei der Nachfolgerbildung stets eine Zahl grösser als 0 herauskommen. Als Summanden können nur 0,1,2 und 3 vorkommen, denn wenn ein Summand gleich 4 wäre, so muss auch die Summe mindestens den Wert 4 annehmen. Dem wäre nicht so, wenn wir als Startelement z.B. -1 gewählt hätten, dann müssten wir auch die beiden Fälle 4 + (-1) und (-1) + 4 betrachten.

Pedantisch müsste man analog zur Definition der Multiplikation auch noch eine Definition der Addition vornehmen und dann eine vollständige Induktion darüberlegen, dass jede andere Summandenbildung ausser den von Mike genannten eine Summe von mindestens 4 ergibt.

Diese vier Möglichkeiten untersuchen wir jetzt näher:
(Dabei sei vorausgesetzt, dass
a) die Kommutativität der Multiplikation schon gezeigt ist und
b) 1 nicht echt faktorisierbar ist.)

Ich sehe eigentlich nicht, wo Du die Kommutativität der Multiplikation verwendest; also braucht man diese auch nicht vorauszusetzen.

Dass 1 nicht echt faktorisierbar ist ... - hmmm, das muss ich mir noch überlegen, weswegen das einfach folgt. Das geht sicher ganz einfach, aber ich will jetzt damit keine Zeit verlieren, zumal wohl niemand ernsthaft in Erwägung ziehen wird, dass dem nicht so sei. Vermutlich kann man die 1 clever in die Gleichung (2) einsetzen und dann folgt das sofort.

In allen Fällen ist der zweite Summand, also n, einer der beiden Teiler.
Da entfallen schon mal die Möglichkeiten 3+0, 2+1 und 0+3, weil 0, 1 bzw. 3 keine echten Teiler sind.

Ich kann mir einfach nicht helfen, ich finde diesen Schritt wahnsinnig elegant: Mike beschränkt sich auf den 2.Faktor und schliesst 3 Kandidaten ganz elementar aus.

Es bleibt also nur noch die Zerlegung 3=1+2 als erfolgversprechender Kandidat.

Dadurch, dass Mike die Fälle 2+1 und 1+2 seperat betrachtet brauchen wir nicht vorgängig zu beweisen, dass die Addition kommutativ ist. Auch das ist sehr schön !

Da ist also n=2 und es muss n*m=1 sein.

Das ist jetzt die korrigierte Fassung, Mike hatte versehentlich n*m' geschrieben.

Dies widerspricht der Nicht-Faktorisierbarkeit der 1.

Weil gilt: 1=1*1, aber da 1=n*m und n=2 führt das zu einer Gleichung 1=2*m und damit zu einem Widerspruch.

Es gibt also kein m, so dass 2*m=1 ist und daher auch kein m', mit dem 2*m'=3 ist.

Zur Erinnerung: nach Gleichung (3) gilt ja n*m'=3, also 2*m'=3. Mike hat also gezeigt, dass es ein solches m' nicht geben kann.

q.e.d.

Wer diese Abkürzung nicht kennt, das heisst: quod erat demonstrandum, also "was ein zu Beweisendes war".

Gruß
mike

Danke schön für diesen eleganten und schönen Beweis. Ganz schön ist eben auch die Beweisidee, die Bedingung eines Produktes auf die Bedingung einer Summe zurückzuführen.


Freundliche Grüsse, Ralf

[M_Hammer_Kruse]

Hallo Ralf,

danke für die Mühe, die Sache so ausführlich zu erläutern.

Ich will noch zwei Dinge ergänzen.

Erstens:
Die verwendete Definition der Multiplikation ist natürlich nicht auf meinem Mist gewachsen, die stammt laut Wikipedia von Peano selbst.
Bis gestern abend kannte ich nur die Peano-Axiome als Konstruktionsmethode für die Menge der natürlichen Zahlen selbst ohne jede Verknüpfungsoperation. Die Axiome kennen zunächst mal nur den Nachfolgerbegriff. Und sie definieren damit irgendeine Menge, in der es eine Halbordnung gibt. In der kann man dann erstmal weder adddieren noch multiplizieren, sondern nur schrittweise Treppenstufen zum nächsten Element hochsteigen. Wenn man da über Primzahlen reden will, muss man sich erstmal drüber klarwerden, wie man in so einer Treppenstufen-Menge überhaupt multiplizieren kann. Und auf der Suche nach einer Anregung dazu stieß ich dann darauf, dass Peano selbst diese Frage schon gelöst hat. Mit Hilfe der Definition, die ich zitiert habe, schafft er eine Multiplikation (und auf ähnliche Weise auch eine Addition), welche die Peano-Menge hinsichtlich dieser Operationen isomorph zu den natürlichen Zahlen macht. Einfach genial.

Zweitens:
Das Verfahren, so nach Teilern einer Zahl zu suchen, wie ich es gemacht habe (und dann für die drei zu finden, dass es keinen echten Teiler gibt), beruht gerade darauf, die Peano-Definition n*m'=n*m+n für die Multiplikation umzukehren. Denn nach Peano gibt es das Produkt von n und m', weil es schon eines für n und den Vorgänger m gibt. Und das neue Produkt n*m' ist um n größer als das schon bekannte m*n. ("um n größer" heißt hier: "der n. Nachfolger".)

Ich kehre das jetzt um, indem ich sage: Ein Produkt n*m' kann es nur geben, wenn es schon n Schritte tiefer auf der Peano-Treppe ein Produkt n*m mit dem Vorgänger von m' gibt. Für die Primzahleigenschaft der 3 genügt es dann zu zeigen, dass ein jenes Vorgängerprodukt nicht gibt.

Aber die Sache erlaubt eine Verallgemeinerung: Wenn ich z. B. wissen will, ob 13 eine Primzahl ist, dann kann ich u. A. untersuchen, ob es einer Faktorisierung mit dem Faktor 5 gibt.
Also Ansatz 13=5*m''''+5. Das ist nur lösbar, wenn es ein Produkt 8=5*m''' gibt.
Um das zu testen: Neuer Ansatz 8=5*m''+5 oder 3=5*m'.
Da muss ich wieder neu ansetzen und bekomme 3=5*m+5. Und das geht schon deswegen nicht, weil rechts mit dem Summanden 5 merh steht als links. Da kann ich mit der Additon von 5*m nichts mehr werden und schließe: 13 besitzt keinen Faktor 5!

Was habe ich da eigentlich gemacht? Ich habe einer Division mit Rest eingeführt, ohne das Wort Division zu benutzen. Denn ich habe von der zu untersuchenden 13 so lange wiederholt 5 abgezogen, bis es nicht mehr weiter ging. Das war der Fall, als nur noch 3 da waren. Nämlich der Rest.

Und wenn man auf diese Weise für alle in Frage kommenden echten Teiler, also für alle Zahlen von 2 bis 12, untersucht, ob sie als Faktor in 13 enthalten sind, dann wird man feststellen, dass 13 keinen echten Teiler besitzt. Das ist nichts anderes als das, was man sonst auch macht, wenn man untersucht, ob eine Zahl eine Primzahl ist. Nur in der Sprache der Peano-Axiome.

So kann man also mit dem Peano-Axiomen auch eine Divsion konstruieren. Und das ist ja eigentlich auch kein Wunder, weil die Peano-Treppe isomorph zu den natürlichen Zahlen ist. Der Spaß besteht nur darin, die gewohnte Arithmetik einmal ganz formal axiomatisch auf andere Weise aufzubauen.

Aber das empfinden wahrscheinlich nur Mathematiker als Spaß...

Gruß
mike

[ralfkannenberg]

Was habe ich da eigentlich gemacht? Ich habe einer Division mit Rest eingeführt, ohne das Wort Division zu benutzen. Denn ich habe von der zu untersuchenden 13 so lange wiederholt 5 abgezogen, bis es nicht mehr weiter ging. Das war der Fall, als nur noch 3 da waren. Nämlich der Rest.

Hallo Mike,

und damit hast Du den Weg zum Euklidischen Algorithmus geebnet.

Und das ist ja eigentlich auch kein Wunder, weil die Peano-Treppe isomorph zu den natürlichen Zahlen ist. Der Spaß besteht nur darin, die gewohnte Arithmetik einmal ganz formal axiomatisch auf andere Weise aufzubauen.

Genau das ist es und das war eben auch meine Motivation, diesen Thread zu eröffnen. So kann man dann auch die Gültigkeit des Assoziativgesetzes der Addition beweisen. Besonders "geil" aber, wenn man diesen Beweis auf die ganzen Zahlen erweitert. Jedenfalls habe ich das vergangenes Jahr in den Ferien mal so gemacht, aber keineswegs, indem ich 0 und negative Zahlen hinzugefügt habe und somit diese halbgruppe bis auf Isomorphie eindeutig zu einer Gruppe ergänzt habe, sondern indem ich einfach nur den Startpunkt der "Peano-Treppe" um die Summe der Absolutbeträge der 3 involvierten Zahlen nach links verschoben habe.

Die ganzen Zahlen erreichst Du mit diesem Trick zwar nicht, sondern "nur" deren Teilmenge [-M, n] mit n in IN, aber um das Assoziativgesetz der Addition in den ganzen Zahlen zu beweisen reicht diese Menge völlig aus, da es eben eine solche Menge für alle M in IN gibt.

Was ich (wieder einmal) bemerkt habe: sie sind mächtig, diese Peano-Axiome, und keineswegs so willkürlich, wie sie auf den ersten Blick erscheinen mögen.


Freundliche Grüsse, Ralf