Äquivalenz Prinzip vom kleinsten Element und Prinzip der vollständigen Induktion.

Christoph

mathematikpraktikant schrieb:

Ich habe ein Verständnisproblem mit dieser Aussage, die im Beweis benutzt wird:

Wegen a $\in$ IN \ {1} ist also a - 1 $\in$ IN

Kann mir bitte mal jemand erklären, wie es zu dieser Schlussfolgerung kommt?

Die Zahl a ist die kleinste Zahl, für die ε nicht gilt. Zuerst wird ausgeschlossen, dass a = 1 ist. Also ist a != 1, oder anders gesagt: $$a \in \mathbb{N}\setminus{1}$$. Da jede natürliche Zahl außer 1 einen eindeutigen Vorgänger besitzt, hat auch a einen Vorgänger: a - 1. Damit ist $$a-1\in \mathbb{N}$$.

Erst danach wird argumentiert, dass ε für a-1 ebenfalls nicht gelten kann, das aber ein Widerspruch zur Minimalität von a ist.

Ja, erst wird ausgeschlossen, das a = 1 ist. Es ist also a ≠ 1.
Darum wundert es mich ja, das a - 1 zutreffen soll, mit a $\in$ IN \ {1}. Denn a - 1 ist ja auch gleich 1 und es soll ja nicht auf 1 zutreffen. Das ist mir immer noch ein Rätsel!

Ok, ich glaube langsam geht mir ein Licht auf: man tut also so, als ob a-1 zuträfe, obwohl man von vornherein sehen kann, das es nicht zutreffen kann.
( Das ist wohl das, was mir nicht in den Kopf ging. )
Und dann zeigt man es, indem man zeigt, das (ii) nicht erfüllt wird.

mathematikpraktikant schrieb:

...man tut also so, als ob a-1 zuträfe, obwohl man von vornherein sehen kann, das es nicht zutreffen kann ...

häh? wie kann man denn so tun, als ob a-1 zuträfe wenn man doch leicht zeigen kann, das a-1 auch 1 ist(wie du schon geschrieben hast), oder hier:

Mups schrieb:

Wenn mit |N die Zahlen 1,2,3,4.... gemeint sind, dann bedeutet a € |N \ {1}, dass a € {2,3,4,...}. Dann ist a - 1 € {1,2,3,4...}

man sieht doch das a-1 (auch) = 1 ist, aber 1 soll nicht zutreffen, dann kann doch auch a - 1 nicht zutreffen, da kann ich doch nicht so tun als ob.

Bahnhofversteher schrieb:

häh? wie kann man denn so tun, als ob a-1 zuträfe wenn man doch leicht zeigen kann, das a-1 auch 1 ist

Hmm, gute Frage. Das frage ich mich jetzt auch.

MamboKurt

also was man hier macht ist ein beweis durch widerspruch.
man will hier zeigen, dass wenn (i) und (ii) gelten man aus (I) folgern kann, dass ε aus (i) und (ii) für alle n in |N gilt.

-sei U={x in |N | [e]epsilon[/e](x) ist falsch} nicht leer
-nach (I) gilt nun, dass diese Menge ein kleinstes element a hat
-da a([e]ne[/e]1 (i)) minimal ist mit dieser eigenschaft gilt [e]epsilon[/e](a-1) ist wahr
-aus (ii) folgt nun aber, dass [e]epsilon[/e](a) wahr sein muss
-es folgt, dass [e]epsilon[/e](a) falsch (da in U) und wahr sein muss
-wenn U also nicht leer ist kommt es zu einem widerspruch, also ist U leer
-es folgt unmittelbar, dass [e]epsilon[/e] für alle n in |N gelten muss

man zeigt hier, dass ε wahr und falsch ist für ein element in |N, wenn U nicht leer ist. das ist genau der widerspruch, den wir erzeugen wollten, um zu zeigen, dass die annahme U≠{} falsch sein muss.

PS: a-1 ist nicht auch 1. a-1 kann 1 sein. wir sind in der mathematik und nicht in der quantenmechanik.

MamboKurt schrieb:

PS: a-1 ist nicht auch 1. a-1 kann 1 sein. wir sind in der mathematik und nicht in der quantenmechanik.

Eben!
a-1 ist 1, für ein a $\in$ IN\{1} mit a = 2.
Daher ist also a-1 = 1 und man darf nicht schreiben, das a-1 zutrifft!

Bahnhofversteher schrieb:

Eben!
a-1 ist 1, für ein a $\in$ IN\{1} mit a = 2.
Daher ist also a-1 = 1 und man darf nicht schreiben, das a-1 zutrifft!

Eben nicht, nachdem mir endlich einm Lichtlein aufgegangen ist:
a-1 kann doch nicht 1 werden, weil doch a $\in$ IN\{1} ist.
Die 1 ist doch da gar nicht drin.

Grüße,
m.

wenn a in {2,3,...} enthalten ist, dann kann doch a=2 und somit a-1=1 sein !?

u_ser-l schrieb:

wenn a in {2,3,...} enthalten ist, dann kann doch a=2 und somit a-1=1 sein !?

Stimmt auch wieder! Also, mir ist es immer noch nicht klar, wieso es im Beweis heißt:

ε trifft also auf a - 1 zu

XFame

Warum soll denn das auf a-1 nicht zutreffen koennen? a ist nunmal das kleinste Element, auf das es NICHT zutrifft. Da ε per Definition auf die 1 zutrifft, kann a nicht 1 sein. Also ist a-1 eine natuerliche Zahl, die kleiner als a ist. Somit muss ε auf a-1 zutreffen. Nach dem Prinzip der vollstaendigen Induktion muss ε dann aber auch fuer a selbst gelten. Widerspruch.

also eigentlich ist der Beweis, um den es geht, doch ganz einfach, wenn man beim Induktionsprinzip ergänzt, daß unter den Vorauss. i & ii die Eigenschaft $$\varepsilon$$
für alle natürlichen Zahlen gilt. Sonst wäre die Aussage witzlos.

"<="
Sei M nichtleer und es gelte das Ind.Prinz.

Annahme: M hat kein min. Sei E(x) die Eigenschaft "x <= m für alle m in M".
Daß E(1) gilt, ist klar.
Gilt E(x), aber nicht E(x+1), dann ist x = min M, im Widerspruch zur Annahme.

Also ist die Annahme falsch. M hat also ein min.

"=>"

Das ist sogar noch einfacher.

Es gelte, daß jedes nichtleere M ein min hat.

Sei E(x) eine beliebige Eigenschaft mit E(1) und mit:

(*) "E(x) => E(x+1)" für alle x.

Annahme: E gilt nicht für alle natürlichen Zahlen. Sei M die Menge der x, für die E(x) nicht gilt.

Nach Vorauss. existiert y := min M. Dann gilt E(y-1), aber nicht E(y). Widerspruch zu (*)

Also Annahme falsch.

qed

Ja, der Beweis mag einfach sein, aber er ist nicht mit meiner Denkweise kompatibel. Ich stelle mir immer noch vor, das a-1 = 1 ist, das steht im Widerspruch zur Aussage, das a-1 zutrifft. Irgendwie löst das eine "das verstehe ich nicht - Endlosschleife" aus.

XFame

mathematikpraktikant schrieb:

Ich stelle mir immer noch vor, das a-1 = 1 ist, das steht im Widerspruch zur Aussage, das a-1 zutrifft.

Und genau da liegt dein Fehler, das ist kein Widerspruch. Niemand hat behauptet, dass es fuer 1 nicht zutrifft, im Gegenteil.

XFame schrieb:

Und genau da liegt dein Fehler, das ist kein Widerspruch. Niemand hat behauptet, dass es fuer 1 nicht zutrifft, im Gegenteil.

Genau so sieht es aus. Im Nachhinein weiss ich auch nicht mehr, warum ich so davon überzeugt war, das es für 1 nicht zutrifft.

Doofes Gefühl wenn da etwas nicht klar ist, dann mag ich gar nicht weiter lernen, aber zum Glück habe ich es nun endlich doch noch kapiert und kann beruhigt weiter machen.

Danke für eure Geduld.
Gruß,
m.