Umkehrabbildung zu NxN->N
Till Meyer
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
Viele Grüße,
Till
Martin Fuchs
f (5,1) = 5 * (2*1 + 1) - 1 = 15 - 1 = 14
und
f (1,7) = 1 * (2*7 + 1) - 1 = 15 - 1 = 14
=> f ist nicht injektiv
Bei Dir müssen die natürlichen Zahlen der 1 beginnen, sonst würde
f(0,0) nicht nach |N abbilden).
Dann wäre der kleinste Funktionswert f(1,1) = 2, also ist f auch nicht
surjektiv
=> f ist nicht bijektiv, es kann daher keine Umkehrabbildung
existieren.
mf
Simon Barner
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
dieser NG von mir bereits mehrfach zitierte - Kantor'sche Diagonalnummerierung:
b
| a-->
| | 0 1 2 3
--+-------------
0 | 0 1 3 6
1 | 2 4 7
2 | 5 8
2 | 9
Viele Grüsse,
Simon
Brian M. Scott
<bar...@in.tum.de> wrote:
>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
>dieser NG von mir bereits mehrfach zitierte - Kantor'sche Diagonalnummerierung:
Wie z.B. f(m,n) = (m+n)(m+n+1)/2 + n.
[...]
Brian
Till Meyer
(k,l)->2^k * (2l+1)-1 ?
Martin Fuchs
> (k,l)->2^k * (2l+1)-1 ?
Die ist bijektiv, besitzt also eine Umkehrfunktion.
(Man muss ein bisschen überlegen, um zu sehen, dass sie injektiv und
surjektiv ist)
Ob Du die aber auch explizit angeben kannst ... ?
(scheint mir im Moment nicht so, ich lasse mich aber gern belehren)
mf
Peter Luschny
> dieser NG von mir bereits mehrfach zitierte - Kantor'sche Diagonalnummerierung:
Meinst du Georg Ferdinand Ludwig Philipp Cantor?
http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Cantor.html
Gruss Peter
Hermann Kremer
Falls nicht, gäbe es noch den
Moritz Benedikt Cantor
http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Cantor_Moritz.html
(mit obigem weder verwandt noch verschwägert)
und den
Leonid Witaljewitsch Kantorowitsch
http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Kantorovich.html
Gruß
Hermann
--
>Gruss Peter
>
Brian M. Scott
f(n) = max{k <= n : 2^k | n+1}
g(n) = (n/2^f(n) - 1)/2
n |--> (f(n), g(n))
Explizit, sogar primitiv rekursiv, wenn auch ein bisschen
hässlich.
Brian
Martin Fuchs
> g(n) = (n/2^f(n) - 1)/2
> n |--> (f(n), g(n))
beeindruckend.
Kannst Du mal ein paar Tips zu Deinem Lösungsweg geben ?
mf
Brian M. Scott
<martin...@gmx.net> wrote:
>> f(n) = max{k <= n : 2^k | n+1}
>> g(n) = (n/2^f(n) - 1)/2
Korrektur: g(n) = ((n+1)/2^(f(n) - 1)/2
>> n |--> (f(n), g(n))
>beeindruckend.
>Kannst Du mal ein paar Tips zu Deinem Lösungsweg geben ?
Wir hatten die Funktion (k,l)->2^k * (2l+1)-1. '-1' ist eine
kleine Belästigung, also fort mit ihm: lieber betrachte ich die
Funktion h(k,l) = 2^k * (2l + 1).
Jede natürliche Zahl n lässt sich eindeutig in zwei Faktoren
zerlegen, wodurch die eine eine Potenz von 2, die andere ungerade
ist. Diese Zerlegung gibt die Umkehrfunktion zu h; ich habe sie
nur beschrieben.
Brian
Brian M. Scott
Scott) wrote:
>On Mon, 11 Nov 2002 22:43:55 +0100, "Martin Fuchs"
><martin...@gmx.net> wrote:
>>> f(n) = max{k <= n : 2^k | n+1}
>>> g(n) = (n/2^f(n) - 1)/2
>Korrektur: g(n) = ((n+1)/2^(f(n) - 1)/2
Argh! g(n) = ((n+1)/2^f(n) - 1)/2
[...]
Brian
helen...@googlemail.com
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
helen...@googlemail.com schrieb am 21.04.2015 um 16:05:
> Genau wie Till, suche ich die Umkehrfunktion für meine
> f:(x,y) := (x+y)(x+y+1)/2+x Funktion f: NxN->N
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.
> Man muss die Bijektivität und die Bijektion g:NxNxN->N
lg
CN
Detlef Müller
> Am Montag, 11. November 2002 01:11:19 UTC+1 schrieb Simon Barner:
>> | 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
(glaube ich mal).
> Man muss die Bijektivität und die Bijektion g:NxNxN->N
>
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)
> 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
> LG Helena
>
--
Dr. Detlef Müller,
http://www.mathe-doktor.de oder http://mathe-doktor.de
Detlef Müller
> Hallo Helena
>
> helen...@googlemail.com schrieb am 21.04.2015 um 16:05:
>
>> 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).
>
also liegt (0,-1) nicht im Definitionsbereich!
Gruß,
Detlef
helen...@googlemail.com
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
> Am Dienstag, 21. April 2015 18:00:20 UTC+2 schrieb Detlef Müller:
>>> f:(x,y) := (x+y)(x+y+1)/2+x Funktion f: NxN->N
>>
>> 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,
>
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).
>
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