Verwendung des Well Ordering-Prinzips zum Beweis der Rückwärtsinduktion der Form 2n2n2^{n}

Annehmen Ω ⊆ N so dass :

( 1 ) : 2 N ∈ Ω , ∀ N ∈ N .

( 2 ) : Wenn N ∈ Ω Und ∀ N ≥ 2 , Dann N − 1 ∈ Ω ,

Mein Hauptziel ist:

Zeige, dass Ω = N

Ich habe es geschafft, dies leicht zu beweisen, indem ich zwei Fälle für genommen habe ϕ ( M ) := 2 M für einige M ∈ N eine für die M ist eine Potenz von zwei und andere, für die es nicht ist, und in beiden Fällen kann darauf geschlossen werden ϕ ∈ Ω .

Dies möchte ich nun beweisen 2 N Variation der Induktion, aber dieses Mal war ich neugierig zu sehen, wie das Prinzip der guten Ordnung funktionieren würde. Ich stelle meine Strategie vor:

[Strategie] : Das nehmen wir im Widerspruch an Ω ist eine echte Teilmenge von N . Das bedeutet, dass N ∖ Ω ≠ ∅ eine nicht leere Teilmenge von N , dann haben wir nach dem Ordnungsprinzip, dass es ein kleinstes Element gibt P ∈ N . Ich dachte nun daran, den Widerspruch zu erreichen, indem ich das beweise P + N ∉ Ω was der Tatsache widerspricht, dass 2 P > P ∈ Ω .

[Frage] : Die Beweismethode P + N ∉ Ω scheint mir nicht trivial, auch wenn es sich als trivial herausstellen könnte. Ich dachte daran, Induktion zu verwenden, um dies zu beweisen, aber ich habe kein klares Argument für den Basisfall und den induktiven Schritt.

Jede Hilfe wird sehr geschätzt, da ich neu bin und immer noch selbst Elemente der Mengenlehre lerne : )

Ist dein N die Menge der positiven ganzen Zahlen, oder enthält sie 0 ?
der Satz N beginnt immer mit 1 .
Okay; bei mir, wie bei vielen anderen, fängt es immer bei an 0 .
Ich werde in diesem Fall der Mehrheit folgen : )
Leider sind beide Verwendungen ziemlich verbreitet; ich bevorzuge N für die nicht negativen ganzen Zahlen und Z + für die positiven ganzen Zahlen, aber es gibt viele Variationen in der Verwendung, und manchmal muss man einfach fragen, welche Version jemand verwendet.
Tatsächlich habe ich nie erfahren, warum Peano seine Axiome konstruierte, ohne sie einzuschließen 0 als erstes Element von N .

Antworten (1)

Es ist ein wenig schwierig, und das ist es nicht N ∖ Ω wessen kleinstes Element Sie verwenden möchten.

Wenn N ∖ Ω ≠ ∅ , lassen P ∈ N ∖ Ω . Wir wissen das N < 2 N für jede N ∈ N , So P < 2 P , Und 2 P ∈ Ω von ( 1 ) . Lassen S = { N ∈ N : 2 P − N ∉ Ω } ; 2 P − ( 2 P − P ) = P ∉ Ω , So 2 P − P ∈ S , und deshalb S ≠ ∅ . Lassen M = Mindest S .

2 P ∈ Ω , So 2 P − 1 ∈ Ω von ( 2 ) , und deshalb M > 1 . Aber dann M − 1 ∈ N ∖ S , So 2 P − M + 1 = 2 P − ( M − 1 ) ∈ Ω , Und ( 2 ) sorgt dann dafür 2 P − M = ( 2 P − M + 1 ) − 1 ∈ Ω , im Widerspruch zu der Wahl von M . Das zeigt dieser Widerspruch N ∖ Ω kann schließlich nicht nicht leer sein und daher das Ω = N .

Vielen Dank für Ihre Antwort, sie stellte sich als noch banaler heraus, als ich dachte.
@deerclaysup: Sehr gerne.
Warum ist P + 1 ∈ Ω ? Wir haben nur genommen P das kleinste Element zu sein, das nicht drin ist Ω ; alles größer als P könnte so oder so gehen.
@MishaLavrov: Weil ich den Fehler gemacht habe, zwei Leuten gleichzeitig zu antworten und nicht klar gedacht habe; Wenn das OP die Annahme zurückzieht, werde ich diesen Unsinn löschen.
@deerclaysup: Ich entschuldige mich: Ich hatte einen schlimmen mentalen Schluckauf und die Behauptung, dass P + 1 ∈ Ω ist Unsinn, da die Induktion hier nach unten geht. Wenn Sie die Annahme entfernen, lösche ich die Antwort, bis ich sie beheben kann (oder jemand eine richtige Antwort veröffentlicht).
Es ist in Ordnung, Brian!, ich werde noch an deinen Ansatz denken.
@deerclaysup: Nein, damit das Argument funktioniert, müsste ich das wissen P war das größte Mitglied N ∖ Ω .
@deerclaysup: Und ich habe es jetzt komplett neu geschrieben, damit es funktioniert.
Nochmals vielen Dank, es ist wunderschön und viel strenger als mein vorheriger Beweis.
@deerclaysup: Gern geschehen. Was ich damit gemacht habe S ist eine leicht hinterhältige Art, die Jagd nach dem größten Element in die Jagd nach dem kleinsten umzuwandeln, so dass man sich wirklich auf eine gute Ordnung berufen kann.
Verwendung des Well Ordering-Prinzips zum Beweis der Rückwärtsinduktion der Form 2n2n2^{n}
AntwortenHierDatenschutz-Bestimmungen1y, 0v