Frage von DerEinacheJunge, 67

Ist diese Funktion bijektiv?

f: N x N -> N

f(x,y) := [ [(x+y)(x+y+1)]/2 ] +x

würde mich über hilfe freuen

Hilfreichste Antwort - ausgezeichnet vom Fragesteller
von kreisfoermig, 22

Die beigefügten Bilder stellen graphisch dar, was im Beweis gemacht wird. Dies verschafft ein graphisches der Schlüsselstelle im Beweis „ƒ(x,y) = #Vorgänger in der linearen OR (ℕ²,<_lex)“. Anhand dieser Erkenntnis, beweist man dann die Injektivität und Surjektivität (es ist „bildlich“ irgendwie offensichtlich, dennoch muss man dies formal beweisen wie im Dokument).

Falls dir das Graphische nicht einfällt, so lässt sich Injektivität und Surjektivität wie gesagt durch stumpfes Rechnen zeigen. Zur Surjektivität siehe Anmerkung im Dokument. Zur Injektivität:

Seien (x,y)≠(x´,y´) in ℕ². Zu zeigen: ƒ(x,y)≠ƒ(x´,y´).

Fall 1. es gilt x+y = x´+y´ und x=x´. Dann folgt aus beiden Gleichungen y=y´. Also gilt (x,y)=(x´,y´). Widerspruch! Also ist dieser Fall unmöglich.

Fall 2. es gilt x+y = x´+y´ und x≠x´. Dann gilt ½(x+y)(x+y+1)=½(x´+y´)(x´+y´+1). Aufgrund dieser Gleichheit und der Ungleicheit x≠x´ gilt ½(x+y)(x+y+1) + x ≠ ½(x´+y´)(x´+y´+1) + x´. Das heißt ƒ(x,y) ≠ ƒ(x´,y´).

Fall 3. es gilt k:=x+y < x´+y´=:k´. Dann gilt

ƒ(x,y) = ½(x+y)(x+y+1) + x
= ½k(k+1) + x
≤ ½k(k+1) + x+y
= ½k(k+1) + k
< ½k(k+1) + k+1
k k+1 k´
= ∑ i + k+1 = ∑ i ≤ ∑ i
i=1 i=1 i=1

= ½k´(k´+1)
≤ ½k´(k´+1) + x´
= ½(x´+y´)(x´+y´+1) + x´
= ƒ(x´,y´).

Also ƒ(x,y) < ƒ(x´,y´). Insbesondere gilt ƒ(x,y) ≠ ƒ(x´,y´).

Fall 4. es gilt x´+y´ < x+y. Dann gilt analog zu Fall 3 ƒ(x´,y´) < ƒ(x,y), also gilt ƒ(x,y) ≠ ƒ(x´,y´).

Da nur Fälle 2–4 möglich sind gilt in auf jeden Fall ƒ(x,y) ≠ ƒ(x´,y´). Darum ist ƒ injektiv.

Kommentar von DerEinacheJunge ,

Hey! also wirklich danke, ich verstehe die injektivität. kannst du mir nochmal zeigen wie surjektiv mit stumpfen rechen bewiesen werden kann?

Kommentar von kreisfoermig ,

hey, das steht im Dokument: die kleine Anmerkung nach dem durch die schwarze Kiste markierten Ende des Beweises.

Antwort
von YanMeitner, 35

Ich hoffe, es ist noch nicht zu spät.

Bijektiv heißt ja injektiv und surjektiv. Betrachte doch mal die Punkte x=0;y=0 und x=0;y=-1 Das könnte eine Hilfe sein, wenn du an die Injektivität denkst.

Kommentar von ProfFrink ,

Die Antwort lässt Du ja offen. Nun könnte Dein Beispiel darauf hindeuten, dass die Funktion nicht bijektiv ist. Aber es gilt ja die Einschränkung dass wir das Ganze in den Mengen |ℕxℕ|=|ℕ|“
betrachten sollen. Wenn nun negative Zahlen nicht zugelassen sind, dann sollte man sich tatsächlich die Ausführungen von kreisfoermig anschauen. Er kommt zu "Ja, es ist bijektiv"-Schlussfolgerung.

Antwort
von kreisfoermig, 38

Ja, es ist. Kurz gefasst: die Punkte in ℕ x ℕ listest du auf, indem du die Elemente quasi in einem Dreieck aufzählst, wobei du dieses nach und nach vergrößerst. Es gilt ƒ(x,y) = Position von (x,y) in dieser Reihenfolge. Anhand dieser Erkenntnis lässt sich die Injektivität und Surjektivität leicht beweisen.

Ein vollständiger Beweis steht in §1.4 mit Überschrift „Nachweis von |ℕxℕ|=|ℕ|“ in dem auf meinem Profil verlinkten Dokument. (Klicke auf meinen Namen, dann auf den overleaf.com-Link dort.)

Diese Funktion ist ein relativ Standardbeispiel von einer Bijektion zw. den beiden Mengen.

Kommentar von DerEinacheJunge ,

Brilliant, leider reichen meine Mathekentnisse nicht aus um den Beweis voll zu verstehen

Kommentar von DerEinacheJunge ,

Was meinst du mit " < lex "

Kommentar von kreisfoermig ,

Das war bloß ein (passender) Name, den ich für die lineare Ordnungsrelation wählte; der Name  spielt keine Rolle. Im Grunde formalisiert der Beweis im Dokument bloß das, was ich oben schrieb. Du kannst z. T. mithilfe eines Diagramms argumentieren, um es übersichtlicher zu machen ; )

Alternativ rechne man stumpf (wie in meiner Anmerkung über Surjektivität), was zwar evtl zugänglicher/leichter scheint, weist aber kein echtes Verständnis bzgl. der Warum-Frage (warum funktioniert diese Wahl von f) auf.

Ein Beweis mittels <_lex sowie einer mittels eines Diagramms leitet die Beschaffenheit von f her, und verschafft somit im Gegensatz zum stumpfen Rechnen echtes Verständnis.

Kommentar von kreisfoermig ,

(lex = lexikalisch; die OR ist nicht ganz DIE lexikalische OR, ist aber eine Art davon.)

Keine passende Antwort gefunden?

Fragen Sie die Community

Weitere Fragen mit Antworten