Beweis der Bijektivität einer Funktion von N x N -> N

26.04.2014, 14:30

PKlink

Beweis der Bijektivität einer Funktion von N x N -> N

Hallo,

ich sitze zurzeit an einer Funktion von N x N -> N, deren Bijektivität ich beweisen soll. Die Funktionsvorschrift lautet:

$\begin{eqnarray*} f(x, y) = (x + y)(x + y + 1)/2 + x \end{eqnarray*}$

Die Surjektivität der Funktion habe ich beweisen können, indem ich die korrekte Funktionsweise von folgendem Zählverfahren gezeigt habe:

Es gilt (0, 0) = 0.
Sei z Element von N und (x, y) Element von N x N. Dann erhält man z + 1, indem man entweder:
1. f(x+1, y-1) berechnet, wenn y > 0 gilt
2. f(0, x+1) berechnet, wenn y = 0 gilt

Mein Problem liegt bei der Injektivität. Wenn ich versuche $\begin{eqnarray*} f(x, y) = f(w, z) \rightarrow (x, y) = (w, z) \end{eqnarray*}$ zu zeigen, verliere ich mich in Fallunterscheidungen und weiß spätestens für den Fall $\begin{eqnarray*} x \neq w \land y \neq z \end{eqnarray*}$ nicht, wie ich diesen Beweisen soll.

Ich habe hier und auch in anderen Foren nach Lösungen gesucht, allerdings wurden dort meistens andere Bijektionen behandelt oder auf das Cantor'sche Diagonalverfahren verwiesen (ich fand ein Forum, indem diese Funktion untersucht wurde - der Fragensteller suchte aber nur einen Beweis der Surjektivität).

Es wäre super wenn mir jemand hier weiterhelfen könnte! Freude

Gruß Pascal

Edit: Ich habe den Beitrag glaube ich im flaschen Unterforum gepostet. Ich glaube er gehört eher in die Analysis. Wenn jemand über den Beitrag stolpert der ihn verschieben kann, wäre es super wenn er das richtig stellt.

26.04.2014, 14:36

bijektion

Auf diesen Beitrag antworten »

Hallo,

hast du dir die Abbildung bereits grafisch veranschaulicht?
Dann sollte dir direkt etwas auffallen smile

Zitat:

Cantor'sche Diagonalverfahren verwiesen

Das in etwa.

26.04.2014, 14:46

PKlink

Auf diesen Beitrag antworten »

Ja ich habe mir das ganze Veranschaulicht (so bin ich auf den Beweis der Surjektivität gekommen) und mir ist auch klar, dass das ganze mit einem Verweis auf Cantor praktisch erledigt wäre, wenn man Q als N x N interpretiert.

Allerdings liegt Cantor außerhalb des Stoffes der Vorlesung (es geht um Formale Grundlagen der Informatik, also Sprachen, Automaten, ... - dazu haben wir nur die grundlegenden Definition und Sätze von Mengen, Relationen, Funktionen und dann Strukturen behandelt). Es wird also von uns erwartet, die Bijektivität durch den Beweis von Injektivität und Surjektivität der Funktion zu zeigen.

26.04.2014, 15:15

bijektion

Auf diesen Beitrag antworten »

Dann stell es dir grafisch dar.
Betrachte anschließend Spalten, d.h. für $\begin{eqnarray*} s\in \mathbb{N} \end{eqnarray*}$ heißen alle Paare $\begin{eqnarray*} (x,y) \in \mathbb{N}^2 \end{eqnarray*}$ mit $\begin{eqnarray*} x+y=s \end{eqnarray*}$ in einer Spalte liegend.
Man erkennt schnell, dass sich die Funktionswerte von Paaren einer Spalte um maximal $\begin{eqnarray*} s \end{eqnarray*}$ unterscheiden, denn es ist ja $\begin{eqnarray*} f(x,y)=x+\frac{s \cdot (s+1)}{2} \end{eqnarray*}$ .
Damit sollte die Injektivität in einer Spalte kein Problem darstellen.
Bleibt noch zu zeigen, dass ein Element immer nur in einer Spalte liegen kann; das sollte aber kein Problem darstellen.

26.04.2014, 17:13

PKlink

Auf diesen Beitrag antworten »

Habe es mit deinem Tipp geschafft. Vielen Dank für die Hilfe!

27.04.2014, 10:10

bijektion

Auf diesen Beitrag antworten »

Gerne

Neue Frage »

Antworten »

Beweis der Bijektivität einer Funktion von N x N -> N

Verwandte Themen