Beweis Wir skizzieren eine Bijektion $f : \N \times \N \rightarrow \N$, indem wir für jeden Punkt $(x,y) \in \N \times \N$ angeben, auf welche natürliche Zahl er abgebildet werden soll:

Wir zerlegen $\N \times \N$ also in fallende Diagonale und gehen jede Diagonale von rechts unten nach links oben durch. Dadurch können wir die zweidimensionale Gestalt von $\N \times \N$ "aufdröseln" und dem eindimensionalen $\N$ zuordnen.\(\square\)

Beweis Falls Sie es vergessen haben: eine Funktion $f: A \rightarrow B$ heißt injektiv, wenn für alle verschiedenen $a, a' \in A$ auch $f(a) \ne f(a')$ gilt. Wenn $f$ also "kollisionsfrei" ist.

Sei $q \in \Q$ eine rationale Zahl. Wir können $q$ als gekürzten Bruch schreiben, also

mit $a \in \Z$ und $b \in \N^+$ und $\gcd(a,b) = 1$. Mit $\gcd(a,b)$ bezeichnen wir den größten gemeinsamen Teiler (greatest common divisor) von $a$ und $b$. Wir definieren nun also $f_1(q) := (a,b) \in \Z \times \N$. Dies ist injektiv: zwei verschiedene rationale Zahlen $q$ und $q'$ haben verschiedene Darstellung als gekürzter Bruch, und somit gilt auch $f_1(q) \ne f_1(q')$.

Wir haben nun also eine Injektion $f_1 : \Q \rightarrow \Z \times \N$. Mitund gilt $\Z \times \N \approx \N \times \N \approx \N$, und somit gibt es eine Bijektion $f_2 : \Z \times \N \rightarrow \N$. Die Verknüpfung $f := f_2 \circ f_1 : \Q \rightarrow \N$ ist nun die gewünschte injektive Funktion $f$ von $\$Q$ nach $\N$. \(\square\)

Beweis Dies ist ganz einach: da $\N \subseteq \Q$ gilt, können wir jedes $n$ einfach bei sich belassen. Die Funktion

ist die gewünschte Injektion. Man nennt so eine Funktion auch die Einbettung von $\N$ in $\Q$. \(\square\)

Beweis Wir definieren eine Bijektion $f: \N \rightarrow \Q$, indem wir die Beweisidee vonwiederholen. Wir zeichnen $\Z \times \N^+$ schematisch, löschen aber die Paare $(a,b)$, die nicht einem gekürzten Bruch entsprechen.

Die Punkte sind die Elemente von $\Z \times \N^+$. Die schwarzen Punkte sind jene Punkte $(x,y)$ mit $\gcd(x,y)=1$. Diese stehen nun in Bijektion mit den rationalen Zahlen. Die entsprechenden rationalen Zahlen habe ich daneben geschrieben - die negativen habe ich aus Gründen der Übersichtlichkeit weggelassen. Sie befinden sich spiegelverkehrt auf der linken Seite. Wir müssen nun eine Aufzählung der schwarzen Punkte finden, also eine Bijektion von $\N$ in die Menge der schwarzen Punkte:

Das funktioniert natürlich: wir überspringen einfach die gelöschten Punkte. Wir können allerdings nicht bequem eine geschlossene Formel dafür angeben. Auf dem "fünften Hütchen", das von $\frac{4}{1}$ nach $\frac{-4}{1}$ läuft, sind zum Beispiel alle Punkte bis auf $(0,5)$ schwarz, was daran liegt, dass $5$ eine Primzahl ist und somit alle $(x,y)$ mit $x+y = 5$ und $x, y \geq 1$ teilerfremd sind. Streng genommen müssten wir uns davon überzeugen, dass unendlich viele schwarze Punkte übrigbleiben. Das ist aber einfach, weil alle Punkte der Form $(x,1)$ der Zahl $\frac{x}{1}$ entsprechen, und das ist ja ein gekürzter Bruch.\(\square\)

Beweis. Hier ist eine Idee: wir interpretieren den Bitstring $a_1 a_2 \dots a_n$ als $n$-stellige Binärzahl, also

Leider geht das schief, weil $0$, $00$, $000$ etc. alle auf $0$ abgebildet werden. Ebenso $1$, $01$, $001$ und so weiter. Wir könnten uns behelfen und dem String eine 1 voranstellen, also beispielsweise

Formal also

Eine äquivalente Interpretation: wir sortieren erst einmal die Bitstrings nach ihrer Länge. Dann gehen wir $\{0,1\}^n$ lexicographisch durch, also von $00\dots0$ bis $11\dots$. Diese Reihenfolge durchläuft ganz $\{0,1\}^*$ und ordnet jedem Bitstring eine natürliche Zahl zu. Also:

Das haut nicht ganz hin, weil die $0$ nie drankommt. In der Tat stellt die obige Tabelle eine Bijektion $\{0,1\}^* \rightarrow \N^+$ dar. Dies ist leicht korrigiert, indem wir 1 abziehen: die Funktion

ist eine Bijektion von $\{0,1\}^*$ nach $\N$. \(\square\)