Abenteuer-Universum

Wozu braucht es eigentlich das Induktionsaxiom?

Wenn ich beweise, dass '0 € X' und dass 'n € X -> n' € X' (n € IN), dann kann ich doch allein daraus folgern, dass X für alle n gilt. Beweisskizze: Wir nehmen an, es gäbe ein n, welches nicht Element in X wäre. Entweder dieses n wäre das Anfangselement 0. Das widerspräche dem Beweis des Induktionsanfangs (0 € X). Oder dieses n wäre irgendein anderes Element. Dann hätte es einen Vorgänger n-1. Daraus folgt sofort, dass 'n-1 € X -> n € X' falsch wäre, was dem Beweis des Induktionsschritts (n € X -> n' € X) widerspricht. Da beiden Möglichkeiten in einem Widerspruch enden muss die Annahme, es gäbe ein n, welches nicht Element in X wäre, falsch sein und daraus wiederum folgt, dass alle n in X sein müssen, ganz ohne Nutzung des Induktionsaxioms. Wozu also?

Die Frage ist also, warum z.B. hier:
https://de.wikipedia.org/wiki/Peano-Axi ... alisierung
das 5. Axion nicht aus den Axiomen 1-4 folgt.

Gegenbeispiel:
Betrachte die Menge {0, 1/2, 1, 3/2, 2, 5/2, 3, ...} mit n'=n+1, d.h. 0'=1, (1/2)'=3/2, 1'=2 usw.
Diese erfüllt die Axiome 1-4, aber nicht 5.

Ich verstehe deinen Beitrag nicht so ganz. Mir geht es darum: In meinem ersten Beitrag habe ich ganz allgemein gezeigt, dass ich nur aufgrund der Peano Axiome 1-4 und der üblichen Logik einen vollständigen Induktionsbeweis führen kann. Peano 5 scheint schlicht und einfach überflüssig. ME wäre der einzige Grund für Peano 5, dass man Widerspruchsbeweise nicht akzeptiert. Kann ich mir aber nicht vorstellen.

Nur, damit ich dich richtig verstehe:
Du denkst nicht, dass man Peano 5 aus 1-4 folgern kann, sondern das Problem ist ein anderes?

breaker hat geschrieben:Du denkst nicht, dass man Peano 5 aus 1-4 folgern kann, sondern das Problem ist ein anderes?

Ah, ok, also ja ich denke, dass man Peano 5 aus Peano 1-4 folgern kann, deshalb frage ich mich ja, was Peano 5 soll. Ich habe ja in meinem o.g. Beitrag gezeigt, dass ich nur mit Peano 1-4 und klass. Logik das beweisen kann, was man auch mit Peano 5 beweisen kann und damit ist Peano 5 überflüssig. Das verstehe ich nicht und da muss ich wahrscheinlich etwas nicht verstehen.

Sorry, nochmal: Über welches der beiden Probleme sollen wir reden:
1. Ob Peano 5 aus 1-4 hergeleitet werden kann, oder
2. Ob Peano 5 überflüssig ist, weil man in praktischen Situationen ohne es auskommt ?

Das sind zwei völlig verschiedene Probleme!

breaker hat geschrieben:1. Ob Peano 5 aus 1-4 hergeleitet werden kann, oder

Darüber wollen wir hier reden und mein Beweisangebot für die These findet man im ersten Beitrag hier.

Ok, dann folgendes:

1. Was hast du gegen mein Gegenbeispiel,
2. Willst du, dass ich konkret den Fehler in deinem Beweis finde?

Oben bei 1-4 werden Axiome für die einzelnen Elemente usw definiert.
5 ist notwenig, damit man überhaupt vollständige Induktion betreiben kann.
-> Ohne "5" könnte man meinen, dass N aus mehr als nur einer Kette an Elementen besteht.
5 macht die Struktur der natürlichen Zahlen eindeutig.

Als Beispiel:
element X
A element X
element X

Für alle gelte das Axiom 3 (ist kein Nachfolger eines anderen Elementes)
=> N besteht nun aus mehr als einer "Kette".
A könnte sich z.B. zwischen '' und ''' befinden und eine separate "Linie" anfangen.
Wie man sieht muss das Axiom 5 extra postuliert werden um N eindeutig zu machen und nach "oben" zu beschränken.
Ohne Axiom 5 ist auch keine vollständige Induktion auf Peano 1-4 anwendbar, da nicht sicher gestellt ist, dass eine Aussage welche für "alle Nachfolger von A" gilt auch alle Elemente von N betrifft.

Peano 1-4 postulieren die Eigenschaften der Elemente, Peano 5 stellt danach sicher, dass es nur ein Anfangselement gibt.
Aus Peano 1 geht nicht hervor, dass es nur das eine Anfangselement geben muss.
Ohne 5 ist die Definiton von N mehrdeutig und es wäre möglich, dass mehrere verschiedene Strukturen als N bezeichnet werden können.
Das heißt jedes X, welches N beinhaltet wäre selbst auch ein N.

Skeltek hat geschrieben:Oben bei 1-4 werden Axiome für die einzelnen Elemente usw definiert.
5 ist notwenig, damit man überhaupt vollständige Induktion betreiben kann.

Das widerlegt doch mein Beweis im Ausgangsbeitrag. Dort zeige ich, wie man ohne Peano 5 vollständig induziert.

Peano 1-4 postulieren die Eigenschaften der Elemente, Peano 5 stellt danach sicher, dass es nur ein Anfangselement gibt.

Das stellt bereits Peano 1 + 3 sicher!

@breaker: Dein Beweis scheitert doch schon daran, dass dort 1/2 der Nachfolger von 0 und 1 der Nachfolger von 1/2 ist. Am besten wäre es du zeigst mir einen Fehler in meinem Beweis, denn den müsste es ja geben.

Du musst die Axiome anwenden!

Das Nachfolgeraxiom besagt, dass n' = n + 1. Also ist 1 = 0', 2 = 1', ... Und unabhängig davon ist 3/2 = 1/2', 5/2 = 3/2'.

Es ist nicht 1/2 = 0', denn das widerspricht offensichtlich dem Axiom.

Deswegen funktioniert auf dieser Menge die vollständige Induktion unter alleiniger Verwendung des Nachfolgeraxioms nicht, weil damit nicht die ganze Menge erreicht wird und ein "für alle" nicht ableitbar ist. D.h. letztlich hast du zwei um 1/2 versetzte Folgen, und du hast keine Möglichkeit, von einer zur anderen zu gelangen, da n' = n + 1. Und damit bleibt die Induktion immer in einer Folge je Startelement.

Es gibt sicher Beispiele von Sätzen für natürliche Zahlen, die mittels Induktion bewiesen werden, und die für deine Menge nicht gelten. Das sind die Gegenbeispiele.

tomS hat geschrieben:Das Nachfolgeraxiom besagt, dass n' = n + 1. Also ist 1 = 0', 2 = 1', ... Und unabhängig davon ist 3/2 = 1/2', 5/2 = 3/2'.

Deswegen funktioniert auf dieser Menge die vollständige Induktion unter alleiniger Verwendung des Nachfolgeraxioms nicht, weil damit nicht die ganze Menge erreicht wird und ein "für alle" nicht ableitbar ist. D.h. letztlich hast du zwei um 1/2 versetzte Folgen, und du hast keine Möglichkeit, von einer zur anderen zu gelangen, da n' = n + 1. Und damit bleibt die Induktion immer in einer Folge je Startelement.

Mir leuchtet das nicht so recht ein. Sorgt nicht Peano 2 dafür, dass es immer nur genau eine Nachfolgerkette geben kann? In dem Bsp. von breaker hätte die Null zwei Nachfolger (wobei man hier sagen muss, dass 'n+1' den Nachfolger nur vulgär und eigentlich falsch ausdrückt, eigentlich heißt es: n' und das bedeutet: Nachfolger von n). Was auch immer ich für n einsetze, ob nun 5 oder 'a', der Nachfolger ist 5' oder a' und es kann keinen anderen!!! geben.

Ich drehe mal den Spieß mal um, denn dann müsste ja mein folgender Beweis einen Fehler enthalten, der ihn unwirksam macht:

Wenn ich beweise, dass 0 € X und dass n € X -> n' € X,, dann kann ich doch allein daraus folgern, dass X für alle n gilt. Beweisskizze: Wir nehmen an, es gäbe ein n, welches nicht Element in X wäre. Entweder dieses n wäre das Anfangselement 0. Das widerspräche dem Beweis des Induktionsanfangs (0 € X). Oder dieses n wäre irgendein anderes Element. Dann hätte es einen Vorgänger n-1. Daraus folgt sofort, dass n-1 € X -> n € X falsch wäre, was dem Beweis des Induktionsschritts (n € X -> n' € X) widerspricht. Da beiden Möglichkeiten in einem Widerspruch enden muss die Annahme, es gäbe ein n, welches nicht Element in X wäre, falsch sein und daraus wiederum folgt, dass alle n in X sein müssen, ganz ohne Nutzung des Induktionsaxioms.

Pippen hat geschrieben:Mir leuchtet das nicht so recht ein. Sorgt nicht Peano 2 dafür, dass es immer nur genau eine Nachfolgerkette geben kann?

Nein, wieso?

Pippen hat geschrieben: In dem Bsp. von breaker hätte die Null zwei Nachfolger (wobei man hier sagen muss, dass 'n+1' den Nachfolger nur vulgär und eigentlich falsch ausdrückt, eigentlich heißt es: n' und das bedeutet: Nachfolger von n). Was auch immer ich für n einsetze, ob nun 5 oder 'a', der Nachfolger ist 5' oder a' und es kann keinen anderen!!! geben.

Du hast meine Definitionen ignoriert. In meinem Beispiel ist 1 der Nachfolger von 0. Die Zahl 1/2 ich kein Nachfolger von irgendwas!
Allgemein sind bei mir halbzahlige Zahlen nie Nachfolger von ganzzahligen und umgekehrt.

Zu deinem Beweis:
Kannst du den Satz hier

Daraus folgt sofort, dass n-1 € X -> n € X falsch wäre, was dem Beweis des Induktionsschritts (n € X -> n' € X) widerspricht.

nochmal ausführlicher erklären? Mir ist nicht ganz klar, was du damit meinst.

Pippen hat geschrieben:

tomS hat geschrieben:Das Nachfolgeraxiom besagt, dass n' = n + 1. Also ist 1 = 0', 2 = 1', ... Und unabhängig davon ist 3/2 = 1/2', 5/2 = 3/2'.

Deswegen funktioniert auf dieser Menge die vollständige Induktion unter alleiniger Verwendung des Nachfolgeraxioms nicht, weil damit nicht die ganze Menge erreicht wird und ein "für alle" nicht ableitbar ist. D.h. letztlich hast du zwei um 1/2 versetzte Folgen, und du hast keine Möglichkeit, von einer zur anderen zu gelangen, da n' = n + 1. Und damit bleibt die Induktion immer in einer Folge je Startelement.

Mir leuchtet das nicht so recht ein. Sorgt nicht Peano 2 dafür, dass es immer nur genau eine Nachfolgerkette geben kann?

Peano 2 sorgt dafür, dass es für ein n aus N eine unendliche Nachfolgerkette n', n'', ... in N gibt. Peano 2 sorgt nicht dafür, dass für beliebige m,n, ... alle Nachfolgerketten zusammenfallen. Im Beispiel 1/2, 1, 3/2, 2, 5/2, ... gibt es zwei unverbundene Nachfolgerketten 1, 2, 3, ... und 1/2, 3/2, 5/2, ...

tomS hat geschrieben:Im Beispiel 0, 1/2, 1, 3/2, 2, 5/2, ... gibt es zwei unverbundene Nachfolgerketten 1, 2, 3, ... und 1/2, 3/2, 5/2, ...

Einspruch!

In deinem Beispiel gibt es nur die eine Kette: 0, 1/2, 1, 3/2, 2, .... Denn 2 ist zB nur Nachfolger von 3/2, nicht von 1 (das sieht man ja gerade an der Kette). Laut Peano 2 kann jede Zahl nur genau einen Nachfolger haben (n € IN -> n' € IN nicht etwa: n € IN -> (x' € IN), wo x für eine beliebige Zahl ganz unabhängig von n stünde, d.h. 0 hat nur einen Nachfolger: 0' und 0' hat nur einen Nachfolger 0'' usw. Nehmen wir nun zwei Ketten her: a) 0, 1, 2, 3, ... und b) 0, 1/2, 3/2, .... Wo ist da das Problem? Ganz einfach, die Null (die immer am Anfang stehen MUSS) hätte zwei verschiedene Nachfolger und das ist lt. Peano 2 ausgeschlossen, so dass auch zwei unterschiedliche Ketten ausgeschlossen wären. Noch zwei Ketten: 0,1,2,3... und 0,1, 1/2, .... Auch das verbietet Peano 2, weil 1 nur einen bzw. immer den gleichen Nachfolger haben darf.

@breaker:

Wenn ich beweise, dass 0 € X und dass n € X -> n' € X, dann kann ich doch allein daraus folgern, dass X für alle n gilt. Beweisskizze: Wir nehmen an, es gäbe ein n, welches nicht Element in X wäre. Entweder dieses n wäre das Anfangselement 0. Das widerspräche dem Beweis des Induktionsanfangs (0 € X). Oder dieses n wäre irgendein anderes Element. Dann hätte es einen Vorgänger n-1. Daraus folgt sofort, dass n-1 € X -> n € X falsch wäre, denn die Konklusion (n) wäre per Annahme falsch, während der Antecedens (n-1) durch den bewiesenen Induktionsschritt (n € X -> n' € X) wahr wäre, weil durch Einsetzung gilt: (n-1)-1 € X -> n-1 € X und da sind Antecedens und Konklusion beide wahr, weil wir ja nur für n - nicht auch für n-1 oder n-1-1 - angenommen haben, es sei kein Element von X. Das widerspricht dem Beweis des Induktionsschritts (n € X -> n' € X). Da beiden Möglichkeiten in einem Widerspruch enden muss die Annahme, es gäbe ein n, welches nicht Element in X wäre, falsch sein und daraus wiederum folgt, dass alle n in X sein müssen, ganz ohne Nutzung des Induktionsaxioms.

In deinem Beispiel gibt es nur die eine Kette: 0, 1/2, 1, 3/2, 2, .... Denn 2 ist zB nur Nachfolger von 3/2, nicht von 1 (das sieht man ja gerade an der Kette). Laut Peano 2 kann jede Zahl nur genau einen Nachfolger haben (n € IN -> n' € IN nicht etwa: n € IN -> (x' € IN), wo x für eine beliebige Zahl ganz unabhängig von n stünde, d.h. 0 hat nur einen Nachfolger: 0' und 0' hat nur einen Nachfolger 0'' usw. Nehmen wir nun zwei Ketten her: a) 0, 1, 2, 3, ... und b) 0, 1/2, 3/2, .... Wo ist da das Problem? Ganz einfach, die Null (die immer am Anfang stehen MUSS) hätte zwei verschiedene Nachfolger und das ist lt. Peano 2 ausgeschlossen, so dass auch zwei unterschiedliche Ketten ausgeschlossen wären. Noch zwei Ketten: 0,1,2,3... und 0,1, 1/2, .... Auch das verbietet Peano 2, weil 1 nur einen bzw. immer den gleichen Nachfolger haben darf.

Sorry, aber das ist einfach alles totaler Quatsch.
Ich habe ganz oben eine Menge definiert und ich habe definiert, was in dieser Menge ein Nachfolger ist. Du kannst danach nicht hergehen und behaupten, dass andere Elemente auch noch Nachfolger sind. Dann redest du von einer anderen Menge.

breaker hat geschrieben:Gegenbeispiel:
Betrachte die Menge {0, 1/2, 1, 3/2, 2, 5/2, 3, ...} mit n'=n+1, d.h. 0'=1, (1/2)'=3/2, 1'=2 usw.
Diese erfüllt die Axiome 1-4, aber nicht 5.

Warum eigentlich nicht?

breaker hat geschrieben:Gegenbeispiel:
Betrachte die Menge {0, 1/2, 1, 3/2, 2, 5/2, 3, ...} mit n'=n+1, d.h. 0'=1, (1/2)'=3/2, 1'=2 usw.
Diese erfüllt die Axiome 1-4, aber nicht 5.

breaker hat geschrieben:mit n'=n+1

Du kannst nicht einfach Addition als Argument einführen, bevor du überhaupt Addition über die Arithmetik definiert hast, aber das nur mal nebenbei...

Natürliche Zahlen = Menge + Arithmetik (Das wird uneinheitlich gehandhabt, vermutlich den Studenten zuliebe)
Die natürlichen Zahlen wie die meisten Menschen sie verstehen sind nicht die Menge an Elementen, sondern die Menge plus der darauf definierten Arithmetik bzw Eigenschaften.

Übrigens folgt in deinem Fall aus n'=n+1 dass 0' = 0+1 = 1/2.
Du has hier die Definition von "+1" unterschlagen, die du brauchst um deine Menge überhaupt zu deklarieren.
Je nachdem was "+1" überhaupt sein soll ist da oben durchaus Axiom5 erfüllt. Alternativ hast du einfach die Definition des Nachfolgers falsch festgelegt.

MaW: Mit Peano 1-4 kann man verschiedene Ketten an natürlichen Zahlen bilden, zB A: 0, 1, 2, 3,... oder B: 0, 1/2, 1/3, 1/4,... oder C: 0, A, B, C, ... usw. Das Problem scheint mir zu sein, dass ich für keine dieser Ketten und damit auch nicht für A (die anderen interessieren uns einfach nicht) beweisen kann, dass wenn 0 € X und n € X -> n' € X, dann alle n € X. Wenn ich annehme, ~(n € X -> n' € X), dann kann ich zwar für die Null den Widerspruch zeigen, aber ansonsten entsteht ein Regress. Nehme ich an, ein Element n sei nicht in X, dann wäre "n-1 € X -> n € X" falsch, aber das widerspricht noch nicht "n € X -> n' € X", denn ich müsste dazu zeigen, dass "n-1 € X" wahr wäre und so entstünde ein Beweisregress (zB müsste n-1-1 € X -> n-1 € X korrekt sein usw. bis runter zur Null), den ich bei unendlichen Mengen nicht gewinne und da käme ein Axiom gerade recht. So reime ich mir das mal vorläufig zusammen^^.

Pippen hat geschrieben: Nehme ich an, ein Element n sei nicht in X, dann wäre "n-1 € X -> n € X" falsch, aber das widerspricht noch nicht "n € X -> n' € X"

Ja
Ich verwende mal unvorsichtigerweise Zahlen dafür:
1 ist Nachfolger von 0.
1 ist auch Nachfolger von 1/2.
Das stört aber nicht weiter, da wir lediglich die natürlichen Zahlen definieren um dann eine Arithmetik dafür zu definieren.
Ob es "darüberhinaus" noch weitere Sachen gibt ist völlig irrelevant.
Die natürlichen Zahlen stören sich nicht daran, dass es noch andere Zahlen gibt.

Peano 5 stellt nur sicher, dass die Definition eindeutig wird.
X={0, 1/2, 1, sqrt(2), 2, 3, 4, 5, ...}
Solange und gilt , DANN ist vollständig in enthalten.
In können sich also auch andere Elemente befinden.

Peano 5 legt also fest, dass es sich bei nicht um handelt, sondern lediglich darin enthalten ist.
Da Peano5 gelten soll, hat man auf die einzige (gleichzeitig kleinste) Menge mit den eigenschaften Peano1-4 eingeschränkt.

Ohne Peano5 würde gelten

Ich hoffe damit ist dir die Bedeutung von Peano5 klarer (obwohl ich eigentlich nur meinen obigen Post in anderen Worten widerholt habe).



Du kannst dir auch mal die englische Wikipedia-Seite ansehen. Dort ist es viel besser beschrieben und etwas ausführlicher. https://en.wikipedia.org/wiki/Peano_axioms
Allerdings entspricht dort Axiom#9 deinem Axiom#5, da die dort erstmal Äquivalenzrelation und so definieren und dafür paar Nummern benutzen.
Das Bild das du rechts auf der englischen Seite siehst kann dabei raus kommen, wenn man Axiom5 bzw auf der englischen Seite Axiom9 weg lässt.
Dort sieht man genau, was passiert, wenn es neben den durch das erste Element 0 induzierten Elementen noch weitere Elemente geben darf.
Der Ring aus schwarzen Domino-Steinen würde ohne Axiom5 auch zu N dazu gehören.
Mit Peano5 schränkt man N auf das ein, was wir als solches kennen.