Bijektivität von g : N × N → N, (m, n) → 2^{m−1}(2n − 1) nachweisen. Abbildung mit Paaren in Definitionsbereich

Question

Hallo Mathematiker ;)

ich verzweifle gerade an der folgenden Aufgabe:

Zeigen Sie, dass die Abbildung

g : N × N → N,   (m, n) → 2^ (m−1) (2n − 1)

bijektiv ist.

Mein Ansatz war Injektivität und Surjektivität nachzuweisen, scheitere aber an beidem, weil der Definitionsbereich voller Paare aus dem kartesischen Produkt von Natürlichen Zahlen ist und ich daher zwei Variablen in der Gleichung habe.

Mir ist aufgefallen, dass das g((m,n)) nur eine ungerade Zahl gibt wenn m = 1 ist, da bei 2⁰(2n -1) die -1 nicht mal zwei genommen wird. Wie mir das helfen soll ist mir allerdings schleierhaft

Kann mir irgendjemand helfen?

Comments

sicher mit der Definition?

g : N × N → N,   (m, n) → 2m−1(2n − 1) 

Dies 1 in der Definition wäre ja überflüssig. Das wäre ja:

g : N × N → N,   (m, n) → 2m−(2n − 1) = 2m - 2n + 1

---

Entschuldigung, die Abbildung sollte eigentlich heißen:
g : N × N → N,   (m, n) → 2^ (m−1)  (2n − 1)

Das mit den Potenzen in der Symbolleiste scheint nicht zu klappen

---

EDIT: Habe es in der Überschrift berichtigt. Im Text musste ich einen Leerschlag nach dem ^  einfügen. Warum ist mir auch schleierhaft.

Answer 1

2^{m-1} nimmt die 1 und dann alle 2er Potenzen an.

2n - 1 nimmt alle ungeraden Zahlen an.

Mit

f(0, n) = 2^0 * (2n-1)      werden alle ungeraden natürlichen Zahlen angenommen.

Mint

f(1,n) = 2^1 * (2n-1) bekommt man alle geraden Zahlen, die den Faktor 2 genau einmal enthalten.

f(2,n) = 2^2*(2n-1) bekommt man alle geraden Zahlen, die den Faktor 2 genau zweimal enthalten.

usw. ergibt ganz N. Also Surjektivität bewiesen.

Da die Primfaktorzerlegung eindeutig ist, kann man jeder Zahl aus N ein Paar (m,n) zuordnen.

Da das eine eindeutige Anzahl Faktoren 2 und einen ungeraden Faktor ergibt, ist die Abbildung bijektiv.

Comments

Vielen Dank für die fixe Antwort.
Leider ist bei uns die Primfaktorzerlegung noch nicht bei uns definiert, heißt wir dürften sie nicht verwenden.
Ist das Problem auch anders lösbar?

---

Darfst du denn deine Zahlen nicht faktorisieren?

Du musst einfach so lange wie möglich den Faktor 2 ausklammern.

Die Anzahl 2er Faktoren ist m-1 , aus der übrigbleibenden ungeraden Zahl bestimmst du das n.

So kommst du von jeder natürlichen Zahl auf ein Zahlenpaar (m,n).

Answer 2

(m, n) → 2^{m-1} (2n − 1)

injektiv:  Wenn zwei Paare die gleiche Zahl als Bild y haben, dann könnte man diese Zahl in

Primfaktoren zerlegen.  Seien  k der Primfaktoren 2en, dann kann man schreiben y=2^k * u

und u ist dann ungerade und besteht aus all den Primfaktoren, die nicht 2 sind.

Also ist y das Bild von Paaren der Art (k;n1) und (k;n2). Denn durch die Abbildungsvorschrift

wird jedes Bild ja in der Form 2^k * u gegeben.

Dann muss aber gelten 2n1 - 1 = 2n2 - 1   also   n1=n2.

surjektiv:

Sei y aus IN. Auch hier machen wir wieder die Primfaktorzerlegung und fassen sie zu

y = 2^k * u zusammen.     Damit das u = 2n -1 wird, muss n= (u+1) / 2 gelten und

(u+1) / 2 ist aus IN, da u ungerade ist.

Also ist y das Bild von  ( k  ;   (u+1)/2 )      q.e.d.