Bijektivität der Kodierungsfunktion?

Hi, zwei Lösungsvorschläge, ein sehr kurzer und ein langer:

Der kurze: "Rate" eine Umkehrfunktion f^-1 und zeige, dass gilt: f(f^-1(n)) = n, sowie f^-1(f(x,y)) = (x,y). Dadurch zeigst du, dass sowohl f, als auch f^-1 bijektiv sind.

Der lange:

Zuerst die Surjektivität, die ist sehr einfach zu beweisen durch vollständige Induktion nach n = f(x,y):

A(n) = es gibt x und y aus N (Menge der natürlichen Zahlen inklusive 0), sodass f(x,y) = n.

Ind.Anf. A(0): 0 = binokoeff(0+0+1; 2) + 0, also x=0, y=0. Korrekt.

Induktionsschritt A(n) -> A(n+1): Es gelte die Induktionsannahme: Es gibt x_n und y_n aus N mit n = binokoeff(x_n + y_n + 1; 2) + x_n, wobei x_n bzw. y_n das zu n gehörende x bzw. y ist.

Dann gilt: n+1 = binokoeff(x_n + y_n + 1; 2) + x_n + 1.

Fall 1: y_n > 0: n+1 = binokoeff((x_n + 1) + (y_n - 1) + 1; 2) + (x_n + 1). Also x_(n+1) = x_n + 1 und y_(n+1) = y_n - 1.

Fall 2: y_n = 0:

n+1 = binokoeff(x_n + y_n + 1; 2) + x_n + 1

= binokoeff(x_n + 1; 2) + binokoeff(x_n + 1; 1)

(wegen des bekannten Gesetzes binokoeff(a+1; b) = binokoeff(a;b) + binokoeff(a; b-1))

= binokoeff(x_n + 2; 2) = binokoeff(0 + (x_n + 1) + 1; 2) + 0.

Also x_(n+1) = 0 und y_(n+1) = x_n+1.

Induktionsschritt Korrekt.

Also gibt es für jedes n aus N ein x und y, sodass n = f(x,y). Damit ist die Surjektivität bewiesen.

Jetzt die Injektivität:

Für einen einfachen Beweis sei festgehalten, dass gilt:

binokoeff(a+1; 2) = Summe_{k=1 bis a} k, also die Summe aller natürlicher Zahlen <= a.

Gezeigt wird: f(a, b) = f(c, d) => a=c und b=d:

Sei f(a, b) = f(c, d).

binokoeff(a+b+1; 2) + a = binokoeff(c+d+1; 2) + c

<=> Dann gilt mit obigem Satz

a + Summe_{k=1 bis a+b} k = c + Summe_{k=1 bis c+d} k

Wir zeigen, dass a=c gelten muss:

Sei ohne Einschränkung der Allgemeinheit a<c.

Betrachte die Gleichheit

a + Summe_{k=1 bis a+b} k = c + Summe_{k=1 bis c+d} k.

<=>

Summe_{k=1 bis a+b} k = (c-a) + Summe_{k=1 bis c+d} k

Wegen a<c ist (c-a)>0, also ist die Summe auf der linken Seite größer als die auf der rechten, also gilt a+b > c+d.

Subtraktion der rechten Summe bringt

Summe_{k=c+d+1 bis a+b} k = (c-a)

wobei nach obiger Herleitung die linke Summe aus mindestens einem Summanden besteht. Also:

Summe_{k=c+d+1 bis a+b} k = (c-a)

<=>

c+d+1 + Summe_{k=c+d+2 bis a+b} k = (c-a)

<=>

d+a+1 + Summe_{k=c+d+2 bis a+b} k = 0

Die linke Seite ist wegen dem "+1" aber stets größer 0 (die Summe, sowie a,b,c,d können ja nicht kleiner 0 sein, weil sie natürliche Zahlen sind). Widerspruch. Auf dieselbe Weise zeigt, man, dass a nicht größer als c sein kann. Daraus folgt: a=c.

Weiterhin gilt:

a + Summe_{k=1 bis a+b} k = c + Summe_{k=1 bis c+d} k

<=> (wegen a=c)

Summe_{k=1 bis a+b} k = Summe_{k=1 bis a+d} k

=> b=d

Also gilt: f(a, b) = f(c, d) => a=c und b=d, was zu beweisen war.