Zeigen sie das diese Abbildung eine Bijektion ist: N x N → N f(m,n) = 2 hoch m (2n+1) -1

Question

Aufgabe:

Zeigen Sie das die folgende Aufgabe eine Bijektion ist.

N x N → N f(m,n) = 2^m (2n+1) -1

Problem/Ansatz:

Beweise der Surjektivität.

∀ g ∈ N gibt es mindestens ein Paar (m,n) mit f(m,n) =g

Ich vermute, dass es surjektiv ist, da ich zu jeder probierten Zahl die ich für g eingesetzt habe ein Paar gefunden habe.

Nun weiß ich aber leider nicht wie ich, mein Wissen als Verallgemeinerung für diese Aufgabe, beweisen kann.

Ich bin dankbar über jede Hilfe !

Liebe Grüße

Comments

Gehört die 0 bei euch zu N ? Wie bekommt man denn die ?

oder war es so:

https://www.mathelounge.de/170739/bijektivitat-nachweisen-abbildung-paaren-definitionsbereich

---

Ja, 0 gehört mit zu N

---

Wenn ich für f(0,0) einsetze, also 2⁰ (2*0+1)-1 = 0

oder?

---

Und wie bekommst du die 2 ?

Ach so, ist schon klar.

---

Wenn du g in der Form \( 2^m(2n+1) - 1 \) schreiben willst, dann soll also $$ g + 1 = 2^m(2n+1) $$ sein.

Ist dir nicht klar, warum du eine natürliche Zahl immer in der Form \( 2^m u \) mit \( u \) ungerade schreiben kannst?

Answer 1

Du kannst doch jede Zahl eindeutig zerlegen in den "geraden Anteil" 2^m, d.h. die höchste Zweierpotzenz, die darin aufgeht, und den "ungeraden Anteil" 2n+1, das ist der Rest. Die "-1", um alles um eins nach Links zu schieben, braucht es wohl, weil N hier die Null enthalten soll: 2⁰(2*0+1)-1=0

Comments

Vielen lieben Dank, deine Antwort hat mir sehr geholfen !

---

Bitteschön):