Abenteuer-Universum

Wie beweist man, dass jede ganze Zahl abgezählt werden kann? Klar, die Inuition ist:

1. 0
2. 1
3. -1
4. 2
5. -2
...

Aber wie würde man beweisen, dass wirklich jede ganze Zahl in dieser Kette eineindeutig einer nat. Zahl zugeordnet werden kann? Indirekt? Wie würde so ein Beweis aussehen?

Die Abbildung für z aus Z auf n aus N lautet

|z|: 2|z|
-|z|: 2|z| - 1 (ohne z = 0)

Also

0,1,2,3,4,... wird abgebildet auf 0,2,4,6,8,...
-1,-2,-3,-4,... wird abgebildet auf 1,3,5,7,...

Über die Eindeutigkeit bzw Bijektivität der Abbildung.
Man muss im Grunde genommen primär zeigen, dass -1^(n mod 2) * 1/2 *( n - (n mod 2) ) surjektiv bzgl Z und streng monoton ist.

tomS hat geschrieben:Die Abbildung für z aus Z auf n aus N lautet

|z|: 2|z|
-|z|: 2|z| - 1 (ohne z = 0)

Also

0,1,2,3,4,... wird abgebildet auf 0,2,4,6,8,...
-1,-2,-3,-4,... wird abgebildet auf 1,3,5,7,...

Aha. Und dass das wirklich für jedes z aus Z gilt läuft dann über die All-Einführung, wo man letztlich mit PL aus z auf "for all" z schließt?

na ja, man kann die Bijektivität mittels Induktion natürlich exakt beweisen

tomS hat geschrieben:na ja, man kann die Bijektivität mittels Induktion natürlich exakt beweisen

die vollständige Induktion?

ja, per vollständiger Induktion; und bestimmt noch auf andere Art und Weise ;-)

tomS hat geschrieben:ja, per vollständiger Induktion; und bestimmt noch auf andere Art und Weise

Damit beweist du aber nur, dass jeder nat. Zahl genau eine ganze Zahl zugeordnet wird, oder? Um zu beweisen, dass jeder ganzen Zahl genau eine nat. Zahl zugeordnet ist, braucht es ein anderes Induktionsaxiom als das, was ich kenne (Peano 5) oder irre ich mich da? (Aber das sollte im Ergebnis kein Problem sein, bei ganzen Zahlen müsste man mit n+1 und n-1 alles beweisen können.)

Du meinst, man müsste zwei Beweise führen, um die Bijektivität zu zeigen? Das glaube ich nicht.

Ich denke, Induktion ist nicht der einzig mögliche Weg; was sicher sofort funktioniert ist ein Widerspruchsbeweis:
1) zunächst ist klar, dass du per definitionem ganz Z ausschöpfst
2) dann ist klar, dass du mit der ersten Abbildungsvorschrift alle geraden Zahlen ausschöpfst; du musst einmal annehmen, du würdest auf eine beliebige gerade Zahl 2k nicht abbilden; dann führst du das zu einem Widerspruch; dann musst du annehmen, du würdest verschiedene z auf das selbe 2k abbilden; das führst du wiederum auf einen Widerspruch
3) analog

Damit hast du m.E. die Bijektivität gezeigt; und das ist ja das Ziel

Ja, so geht es auf jeden Fall. Interessant ist aber eben der Induktionsbeweis, weil zB mit Peano 5 nur Aussagen über IN bewiesen werden, nicht über Z. Daher mein Zweifel, ob man mit Peano 5 den vollen Beweis der Bijektivität führen kann, der ja darin bestehen muss, dass sowohl jede nat. Zahl zu genau einer ganzen Zahl, als auch jede ganze Zahl zu genau einer nat. Zahl gehört.