Umkehrabbildung zu NxN->N

[h***@googlemail.com]

Hallo Till,

Ich suche die Umkehrfunktion zu einer Funktion, die 2-Tupel aus natürlichen
Zahlen auf natürliche Zahlen abbildet.
Geht das überhaupt? Oder geht das nur nicht in meinen Kopf rein?
Die Funktion bildet folgendermaßen ab: (k,l)->k(2l+1)-1

Daß es mit Deiner Funktion nicht geht, hat Dir ja schon Martin gezeigt.
Es gibt aber durchaus eine Funktion, mit der das geht, und das ist die - in
b
| a-->
| | 0 1 2 3
--+-------------
0 | 0 1 3 6
1 | 2 4 7
2 | 5 8
2 | 9
Viele Grüsse,
Simon

Genau wie Till, suche ich die Umkehrfunktion für meine
f:(x,y) := (x+y)(x+y+1)/2+x Funktion f: NxN->N
Man muss die Bijektivität und die Bijektion g:NxNxN->N

LG Helena

[Carlos Naplos]

Hallo Helena

Post by h***@googlemail.com
Genau wie Till, suche ich die Umkehrfunktion für meine
f:(x,y) := (x+y)(x+y+1)/2+x Funktion f: NxN->N

Auch zu dieser Funktion gibt es keine Umkehrfunktion, weil sie nicht
injektiv ist. Denn z.B. f(0,0) = f(0,-1).

Für eine potentielle Umkehrfunktion f° von f müsste gelten:
f°(f(x,y)) = (x,y)
Dann wäre aber (0,0) = f°(f(0,0)) = f°(f(0,-1)) = (0,-1), ein Widerspruch.

Post by h***@googlemail.com
Man muss die Bijektivität und die Bijektion g:NxNxN->N

Huch?

lg
CN

[Detlef Müller]

Post by Carlos Naplos
Hallo Helena

Post by h***@googlemail.com
Genau wie Till, suche ich die Umkehrfunktion für meine
f:(x,y) := (x+y)(x+y+1)/2+x Funktion f: NxN->N

Auch zu dieser Funktion gibt es keine Umkehrfunktion, weil sie nicht
injektiv ist. Denn z.B. f(0,0) = f(0,-1).

Achtung: Der Definitionsbereich ist NxN, nicht ZxZ,
also liegt (0,-1) nicht im Definitionsbereich!

Gruß,
Detlef

[Detlef Müller]

[...]

Post by h***@googlemail.com

b
| a-->
| | 0 1 2 3
--+-------------
0 | 0 1 3 6
1 | 2 4 7
2 | 5 8
2 | 9
Viele Grüsse,
Simon

Genau wie Till, suche ich die Umkehrfunktion für meine
f:(x,y) := (x+y)(x+y+1)/2+x Funktion f: NxN->N

Die Formel entspricht wohl der abgebildeten Aufzählung
(glaube ich mal).

Post by h***@googlemail.com
Man muss die Bijektivität und die Bijektion g:NxNxN->N

Was muß man die?
Zeigen? Finden?
Mal sehen.

Surjektiv ist f ja nach dem Diagonal-Argument oben.

Nun kann man entweder versuchen, noch Injektivität zu
zeigen, oder eine Umkehrabbildung zu finden.

Sei also n aus N gegeben.

Da die Folge k*(k+1)/2 mit k aus N (immer mit 0) streng
monoton gegen unendlich wächst, gibt es ein eindeutiges
k=h(n) mit

(0) k*(k+1)/2 <= n < (k+1)*(k+1)+1)/2.

Wir setzen

(1) x_n := n - k*(k+1)/2,

dies ist eine natürliche Zahl >= 0 wegen (0).

soll

n = k*(k+1)/2 + x = (x+y)(x+y+1)/2 +x

gelten, folgt

k*(k+1) = (x+y)(x+y+1) =>

(2) k^2+k = (x+y)^2 + (x+y).

Für t>=0 ist die Funktion t ---> t^2 + t injektiv.

Damit folgt aus (2) notwendig y = k - x

Umgekehrt rechnet man damit sofort mit y_n := k - x_n
sofort
f(x_n,y_n) = (x_n+y_n)(x_n+y_n+1)/2 + x_n
= k*(k+1)/2 + n - k*(k+1)/2
= n
nach.

Fehlt noch zu überlegen, daß y_n >= 0 gilt.
Wir setzen also ein:

y_n = k - x_n = k - (n - k*(k+1)/2)

Post by h***@googlemail.com
k - ((k+1)*(k+2)/2- k*(k+1)/2) (wegen (0))

= k - (k+1)(k+2-k)/2 = k - (k+1) = -1

aus y_n > -1 folgt aber, da y_n ganzzahlig ist y_n >= 0,
fertig.

Die Umkehrabbildung lautet also mit obigen Bezeichnungen

f^(-1): N --> N, n ---> (x_n, y_n).

Gruß,
Detlef

Post by h***@googlemail.com
LG Helena

[h***@googlemail.com]

Post by Detlef Müller
[...]

Post by h***@googlemail.com

b
| a-->
| | 0 1 2 3
--+-------------
0 | 0 1 3 6
1 | 2 4 7
2 | 5 8
2 | 9
Viele Grüsse,
Simon

Genau wie Till, suche ich die Umkehrfunktion für meine
f:(x,y) := (x+y)(x+y+1)/2+x Funktion f: NxN->N

Die Formel entspricht wohl der abgebildeten Aufzählung
(glaube ich mal).

Post by h***@googlemail.com
Man muss die Bijektivität und die Bijektion g:NxNxN->N

Was muß man die?
Zeigen? Finden?
Mal sehen.
Surjektiv ist f ja nach dem Diagonal-Argument oben.
Nun kann man entweder versuchen, noch Injektivität zu
zeigen, oder eine Umkehrabbildung zu finden.
Sei also n aus N gegeben.
Da die Folge k*(k+1)/2 mit k aus N (immer mit 0) streng
monoton gegen unendlich wächst, gibt es ein eindeutiges
k=h(n) mit
(0) k*(k+1)/2 <= n < (k+1)*(k+1)+1)/2.
Wir setzen
(1) x_n := n - k*(k+1)/2,
dies ist eine natürliche Zahl >= 0 wegen (0).
soll
n = k*(k+1)/2 + x = (x+y)(x+y+1)/2 +x
gelten, folgt
k*(k+1) = (x+y)(x+y+1) =>
(2) k^2+k = (x+y)^2 + (x+y).
Für t>=0 ist die Funktion t ---> t^2 + t injektiv.
Damit folgt aus (2) notwendig y = k - x
Umgekehrt rechnet man damit sofort mit y_n := k - x_n
sofort
f(x_n,y_n) = (x_n+y_n)(x_n+y_n+1)/2 + x_n
= k*(k+1)/2 + n - k*(k+1)/2
= n
nach.
Fehlt noch zu überlegen, daß y_n >= 0 gilt.
y_n = k - x_n = k - (n - k*(k+1)/2)

Post by h***@googlemail.com
k - ((k+1)*(k+2)/2- k*(k+1)/2) (wegen (0))

= k - (k+1)(k+2-k)/2 = k - (k+1) = -1
aus y_n > -1 folgt aber, da y_n ganzzahlig ist y_n >= 0,
fertig.
Die Umkehrabbildung lautet also mit obigen Bezeichnungen
f^(-1): N --> N, n ---> (x_n, y_n).
Gruß,
Detlef

Post by h***@googlemail.com
LG Helena

--
Dr. Detlef Müller,
http://www.mathe-doktor.de oder http://mathe-doktor.de
[...]

Post by h***@googlemail.com

b
| a-->
| | 0 1 2 3
--+-------------
0 | 0 1 3 6
1 | 2 4 7
2 | 5 8
2 | 9
Viele Grüsse,
Simon

Genau wie Till, suche ich die Umkehrfunktion für meine
f:(x,y) := (x+y)(x+y+1)/2+x Funktion f: NxN->N

Die Formel entspricht wohl der abgebildeten Aufzählung
(glaube ich mal).

Post by h***@googlemail.com
Man muss die Bijektivität und die Bijektion g:NxNxN->N

Was muß man die?
Zeigen? Finden?
Mal sehen.
Surjektiv ist f ja nach dem Diagonal-Argument oben.
Nun kann man entweder versuchen, noch Injektivität zu
zeigen, oder eine Umkehrabbildung zu finden.
Sei also n aus N gegeben.
Da die Folge k*(k+1)/2 mit k aus N (immer mit 0) streng
monoton gegen unendlich wächst, gibt es ein eindeutiges
k=h(n) mit
(0) k*(k+1)/2 <= n < (k+1)*(k+1)+1)/2.
Wir setzen
(1) x_n := n - k*(k+1)/2,
dies ist eine natürliche Zahl >= 0 wegen (0).
soll
n = k*(k+1)/2 + x = (x+y)(x+y+1)/2 +x
gelten, folgt
k*(k+1) = (x+y)(x+y+1) =>
(2) k^2+k = (x+y)^2 + (x+y).
Für t>=0 ist die Funktion t ---> t^2 + t injektiv.
Damit folgt aus (2) notwendig y = k - x
Umgekehrt rechnet man damit sofort mit y_n := k - x_n
sofort
f(x_n,y_n) = (x_n+y_n)(x_n+y_n+1)/2 + x_n
= k*(k+1)/2 + n - k*(k+1)/2
= n
nach.
Fehlt noch zu überlegen, daß y_n >= 0 gilt.
y_n = k - x_n = k - (n - k*(k+1)/2)

Post by h***@googlemail.com
k - ((k+1)*(k+2)/2- k*(k+1)/2) (wegen (0))

= k - (k+1)(k+2-k)/2 = k - (k+1) = -1
aus y_n > -1 folgt aber, da y_n ganzzahlig ist y_n >= 0,
fertig.
Die Umkehrabbildung lautet also mit obigen Bezeichnungen
f^(-1): N --> N, n ---> (x_n, y_n).
Gruß,
Detlef

Post by h***@googlemail.com
LG Helena

--
Dr. Detlef Müller,
http://www.mathe-doktor.de oder http://mathe-doktor.de

Genau Aufgabenstellung lautet:
Beweisen Sie,dass f eine Bijektion zwischen N x N und N ist, des Weiteren geben sie eine Bijektion g: N x N x N -> N an ( natürlich mit Beweis).

Bemerkung: Veranschaulichen Sie sich die Umkehrung von f (Stichwort:Cantor´sches Diagonalverfahren)


PS: Ich verstehe dieses Verfahren immer noch nicht :-( Mord an IT Studenten

[Detlef Müller]

Post by Detlef Müller

Post by h***@googlemail.com
f:(x,y) := (x+y)(x+y+1)/2+x Funktion f: NxN->N

...

Post by Detlef Müller
Die Umkehrabbildung lautet also mit obigen Bezeichnungen
f^(-1): N --> N, n ---> (x_n, y_n).

...

Genau Aufgabenstellung lautet: Beweisen Sie,dass f eine Bijektion
zwischen N x N und N ist,

Dazu musst Du nun noch mal genau nachlesen, was eine Bijektion
ist. Das wird Dir hier keiner abnehmen.
Damit im Hinterkopf kannst Du noch einmal überlegen, was hier
eigentlich gezeigt werden muss.

In N x N liegen Paare (x,y) natürlichere Zahlen, denen f dann
eine einzelne natürliche Zahl n=f(x,y) zuordnet.

Zu zeigen ist im Wesentlichen, dass jede Natürliche Zahl n als Bild von
einem Paar (x,y) auftaucht (Surjektivität) und umgekehrt, daß man bei
Kenntnis von n das Paar (x,y) mit n=f(x,y) rekonstruieren kann
("Injektivität": es gibt _nicht_ mehr als ein Urbild von n).

Alternativ kann man sich eine Umkehrabbildung g überlegen, also
g: N --> N x N mit f(g(n))=n und g(f(x,y))=(x,y).
Vermutlich habt Ihr darüber auch Vorlesungsaufzeichnungen.

Hier habe ich zu einem n ein eindeutiges k gefunden, daraus
ein eindeutiges natürliches x bestimmt und dann überlegt, warum
auch das y eindeutig durch f(x,y)=n fest gelegt ist.
Ich denke, das ist technisch die Hauptarbeit an der
Aufgabe. Beide Alternativen, Bijektivität zu zeigen sollten
imo hiermit möglich sein. Wie schwer ein exakter Beweis der
Surjektivität von f wird, weiß ich allerdings nicht (*).

Das nun abgabereif aufbereiten solltest Du schon
selbst.

des Weiteren geben sie eine Bijektion g: N
x N x N -> N an ( natürlich mit Beweis).

Der Teil ist ja dann geschenkt, der Tipp
N x N x N = (N x N) x N
sollte helfen.

Gruß,
Detlef

(*) Am Bildchen ist es ja klar: x+y ist die Schräge, in der das
Paar (x,y) liegt (Schrägen von links oben gezählt) ... die
Anzahl D der Paare in allen Schrägen davor plus x ergibt also
genau die Nummerierung von (x,y), wenn man die Elemente in
den Schrägen immer von links unten nach rechts oben
durch zählt.
Das D ist dabei 0+1+2+...+(x+y-1) und lässt sich auch geschlossen
darstellen ...

| 0 1 2 3 x
--+-------------
0 | 0 2 5 9 ?
1 | 1 4 8 ?
2 | 3 7 12 <--- auf der Schräge wurde von 10 um x=2 weiter gezählt
3 | 6 11
y | 10