Die Menge N \times N ist abzählbar unendlich Cantorsche Paarungsfunktion beweis der bijektivität

24.11.2014, 03:14	Tjok	Auf diesen Beitrag antworten »
Die Menge N \times N ist abzählbar unendlich Cantorsche Paarungsfunktion beweis der bijektivität Meine Frage: Im unserem Script steht in einem Theorem das die Mengen $\begin{eqnarray} \mathbb{Z} \end{eqnarray}$ und $\begin{eqnarray} \mathbb{N}\times \mathbb{N} \end{eqnarray}$ abzählbar unendlich sind. Unter abzählbar unendlich verstehe ich das es eine bijektive Funktion von $\begin{eqnarray} \mathbb{N} \rightarrow \mathbb{N}\times \mathbb{N} \end{eqnarray}$ gibt. Also das beide Mengen dieselbe Kardinalität besitzen. Um zu Zeigen das $\begin{eqnarray} \mathbb{N}\times \mathbb{N} \end{eqnarray}$ abzählbar unendlich ich müssen wir eine solche Funktion angeben und zeigen das diese bijektiv ist. Im Script haben wir dazu die Cantorsche Paarungsfunktion $\begin{eqnarray} g(x,y) = \frac{(x+y-2)(x+y-1)}{2} + y \end{eqnarray}$ geben. (Wüsste auch nicht wie man auf sowas alleine kommen sollte). Der beweis das die Cantorsche Paarungsfunktion bijektiv ist steht leider nicht drin.(Ist dem Leser überlassen) Ich weiß das ich zeigen muss das diese Funktion Injektiv und Surjektiv ist. Meine Ideen: Mir fällt es leider schwer zu beweisen das diese Funktion Injektiv und Surjektiv ist. Für die Injektivität denke ich das Ich das hier Zeigen muss $\begin{eqnarray} \forall (x,y) , (x',y') \in \mathbb{N}\times \mathbb{N}: (g((x,y)) = g((x',y'))) \Rightarrow (x,y) = (x',y') \end{eqnarray}$ gilt. Ich denke das ich das mit einem Widerspruchsbeweis machen muss. Dazu sei Annahme das $\begin{eqnarray} g(x,y) = g(x',y') \end{eqnarray}$ beliebig mit $\begin{eqnarray} (x,y)\neq (x'y') \end{eqnarray}$ Daraus habe ich $\begin{eqnarray} g(x,y) = \frac{(x+y-2)(x+y-1)}{2} + y = \frac{(x'+y'-2)(x'+y'-1)}{2} +y' \end{eqnarray}$ Nun denke ich das ich es soweit umformen muss das ich am Ende stehen habe $\begin{eqnarray} (x,y) = (x',y') \end{eqnarray}$ . Und das dann ein Widerspruch zur Annahme sein soll. Ich komm einfach nicht drauf wie ich es umformen soll das daraus ein Tupel wird. An die Surjektivität habe ich mich noch nicht versucht.
24.11.2014, 09:18	bijektion	Auf diesen Beitrag antworten »
Zur Injektivität kannst du dir zuerst die Abbildung zeichnen. Dann erkennst du, das es Sinn macht, die Abbildung auf "Spalten" $\begin{eqnarray} l \in \mathbb{N} \end{eqnarray}$ zu betrachten, d.h. auf den Punkten $\begin{eqnarray} x,y\in\mathbb{N} \end{eqnarray}$ die $\begin{eqnarray} x+y=l \end{eqnarray}$ erfüllen. Die Injektivität folgt dann mit vollständiger Induktion
24.11.2014, 15:14	Tjok	Auf diesen Beitrag antworten »
Die Abbildung ist im Script gegeben also gezeichnet. Ich erkenne aber nicht wirklich daran das es sinn macht. Muss ich jetzt irgendwie dieses $\begin{eqnarray} g(x,y) = g(x',y') \end{eqnarray}$ so runterbrechen das man sieht das es gleich ist ? Das ist doch die Annahme wenn ich das gezeigt habe wie soll ich daraus erkennen das die Tupel auch gleich sind. BTW ist das den bisher richtig was ich mir da zusammengebastelt habe ich bin nämlich Anfänger und mache ständig Form Fehler und irgendwelche Sachen die kein Sinn ergeben?

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »