Bijektivität: Beweisen, dass f : IN x IN -> IN f(x,y):= (x+y)*(x+y+1)/2 + x bijektiv ist.

Question

Hi, ich bin neu an der Universität und jetzt habe ich zum ersten mal die... Ehre Beweise auszuführen In der Schule mussten wir sowas (zum Glück) ja noch nie machen und ich hab jetzt so überhaupt keinen Plan z.B. müssen wir
Beweisen, dass f : IN x IN -> IN f(x,y):= (x+y)*(x+y+1)/2 + x bijektiv ist;
jetzt weiß ich schon wie man Bijektivität im Allgemeinen beweisen muss, also sprich, man schaut ob die Funktion Injektiv und Surjektiv ist. Aber ich hab absolut keinen Plan wie man sowas in der Praxis macht, ich habs schon mehrmals probiert, und bin immer gescheitert, (T-T)

Comments

Ich würde zuerst mal prüfen, ob die Funktionswerte tatsächlich alle in IN liegen:

Grund: 

(x+y)*(x+y+1) ist das Produkt von einer geraden mit einer ungeraden Zahl und daher gerade (und nicht neg.).

 Division durch 2 immer noch in IN. 

+ x ändert daran auch nichts.

Das wäre somit in Ordnung. 

Rechne nun einige Funktionswerte aus. Z.B. mit einer Wertetabelle.

Am besten wäre, wenn du eine Vorschrift angeben könntest, die zu jedem k ∈ N das zugehörige Urbild (x_(k), y_(k)) bestimmt. 

Answer 1

schön das du die allgemeine Vorgehensweise kennst. Hier musst du diese im grunde nur auf diesen Fall anwenden.

Es handelt sich bei der besagten Funktion um die Cantorsche Paarungsfunktion. Ihre Bijektivität ist sehr interessant, da man mit ihr explizit zeigt, dass die Menge \(\mathbb{N} \times \mathbb{N} \) abzählbar ist.

Ihre Wohldefiniertheit hat dir ja schon Lu's Kommentar offenbart.

Wenn du die Injektivität zeigen möchtest, musst du zeigen,

dass für \( (a,b), (c,d) \in \mathbb{N} \times \mathbb{N} \) mit \(a \neq c \vee b \neq d  \) stets \(f(a,b) \neq f(c,d) \) gilt.

Hinweis: Hier brauchst du eigentlich nur die Fälle \( a+b = c +d \) und o.B.d.A \(a+b < c+d \) zu betrachten.

Für die Surjektivität musst du nun zeigen, dass es \( \forall m \in \mathbb{N} \) ein Tupel \( (a,b) \in \mathbb{N} \times \mathbb{N} \) existiert, so dass \( f(a,b) = m \) gilt.

Hier kannst du mit der Substitution \( a+b = n \) arbeiten und den kleinen Gauß verwenden um korrekt abzuschätzen.

Eine Umkehrfunktion gibt es im übrigen auch, diese ist aber nicht sofort ersichtlich.

Gruß