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:M_Hammer_Kruse hat geschrieben: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.
M_Hammer_Kruse hat geschrieben: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:
M_Hammer_Kruse hat geschrieben:Dazu muss 3 in die Summe aus (n*m) und n zerfallen.
Machen wir mal weiter:
M_Hammer_Kruse hat geschrieben: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.
M_Hammer_Kruse hat geschrieben: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.
M_Hammer_Kruse hat geschrieben: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.
M_Hammer_Kruse hat geschrieben: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 !
M_Hammer_Kruse hat geschrieben:Da ist also n=2 und es muss n*m=1 sein.
Das ist jetzt die korrigierte Fassung, Mike hatte versehentlich n*m' geschrieben.
M_Hammer_Kruse hat 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.
M_Hammer_Kruse hat geschrieben: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.
M_Hammer_Kruse hat geschrieben:q.e.d.
Wer diese Abkürzung nicht kennt, das heisst: quod erat demonstrandum, also "was ein zu Beweisendes war".
M_Hammer_Kruse hat geschrieben: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