Warum zählen rationale Zahlen zu den abzählbar-unendlichen Mengen?
warum soll die Mächtigkeit der rationalen Zahlen gleich der natürlichen Zahlen sein? Was ist denn mit den unendlich vielen Brüchen, die zwischen zwei natürlichen Zahlen liegen?
6 Antworten
Ich gebe dir nicht direkt eine Bijektion, da die einfachste Bijektion die Stern-Brocot-Folge ist, zu beweisen, dass dies eine Bijektion ist, ist aber nicht ganz untrivial.
Ich werde nämlich folgenden Satz benutzen: Gibt es eine Injektion f: X -> Y und eine Surjektion g: X -> Y, dann gibt es eine Bijektion b: X -> Y. Wie diese aussieht ist erstmal egal, aber sie existiert und das ist alles was zählt.
Eine Surjektion f: Q -> N zu finden ist sehr einfach, wir definieren f(q) = [|q|], die erst den Betrag nimmt und die Funktion dann auf ihre kleinste nächstgelegene natürliche Zahl schickt. Dann gilt für alle natürlichen n: f(n/1) = n, also haben wir eine Surjektion.
Als nächstes finden wir eine Injektion und das geht auch einfach. Zuerst nehmen wir uns ein Repräsentantensystem R von Q. Die Bruchdarstellung der rationalen Zahlen ist ja nicht eindeutig (z.B. 1/1 = 2/2 usw.), also nehmen wir uns für jede rationale Zahl genau eine Darstellung heraus. Somit ist R im Prinzip dasselbe wie Q, nur dass die Darstellung a/b eindeutig ist. Eine Hilfsfunktion t: Q -> R schickt eine rationale Zahl Q auf ein Tupel (a, b), sodass q = a/b.
Jetzt definieren wir g: Q -> N und schicken eine Zahl q auf 2^(t1(q)) * 3^(t2(q)), also 2^a * 3^b, wenn q nichtnegativ ist und auf 5^(t1(q)) * 7^(t2(q)), wenn q negativ ist. Man bemerke, dass 2, 3, 5 und 7 Primzahlen sind, nach dem Fundamentalsatz der Arithmetik ist diese Funktion also injektiv.
Da wir also eine Surjektion und eine Injektion gefunden haben, muss es auch eine Bijektion f: Q -> N geben, also ist Q abzählbar-unendlich.
LG
In diesem 8-minütigen Video wird recht anschaulich erklärt, warum die ganzen Zahlen (obwohl in 2 Richtungen unendlich) und die rationalen Zahlen (zwischen zweien liegen unendlich viele weitere) abzählbar sind und die reellen Zahlen nicht.
Ist zwar auf Englisch aber trotzdem gut verständlich:
Bei den reellen Zahlen kannst du keine Reihenfolge festlegen, mit den du jedes Element erreichst.
Bei den rationalen Zahlen (auch Brüche genannt) kannst du eine Reihenfolge z.B. auf folgender Weise schaffen:
1/1, 1/2, 2/1, 1/3, 3/1, 1/4, 2/3, 3/2, 4/1, ...
Du gehst also immer nach der Summe des Zähelers und des Nenners eines
Bruches (erst kommen die mit 2 als Summe, dann die mit 3 als Summe usw.).
So kommt jeder Bruch irgendwann dran, denn jeder Bruch (der nicht
gekürzt werden kann) hat eine eindeutige Schreibweise, von der sich die
Summe ergibt.
<
p>Einen Beweis, dass bei den reellen Zahlen keine solche
Reihenfolge möglich ist, findest du auf
http://www.mathepedia.de/Ueberabzaehlbar_unendlich.aspx.</p>
Grüße!
Hallo,
abzählbar ist eine Menge genau dann, wenn man jedem Element dieser Menge eine natürliche Zahl zuweisen kann. Warum dies auch bei den rationalen Zahlen funktioniert, man sie also sortieren und durchzählen kann, siehst Du hier:
https://de.wikipedia.org/wiki/Cantors_erstes_Diagonalargument
Herzliche Grüße,
Willy
Es gibt nun mal eine bijektive Abbildung zwischen den Natürlichen Zahlen und den Rationalen, intuitiv ist das zwar nicht, aber trotzdem richtig.
Keine Ahnung, 9 oder so, gibt ja auch nicht nur genau eine bijektive Abbildung, sondern mehrere. Das wichtige ist, dass man weiß, dass es einen gibt.
ich hätte dann nur mal gerne den bijektiven Partner der rationalen Zahl 1,5 genannt bekommen ^^