Beweis zur Bijektivität von g(n,m): (|Ν,|Ν)=>|Ν, (n,m) => n+1/2(n+m-1)(n+m-2)

Question

Aufgabe:

n,m ∈ |Ν=|Ν\{0}

g(n,m): (|Ν,|Ν)=>|Ν

(n,m) => n+1/2(n+m-1)(n+m-2)

zz. g ist Bijektiv

Problem/Ansatz:

Bin mir nicht sicher wie ich genau das Beweisen kann.

Ich muss ja beweisen dass gilt:

∀ y ∃ (n,m): y=g(n,m) d.h. Jede Nat. Zahl wird "getroffen"

und

∀ (n,m),(k,l) ∈ (|N,|N): g(n,m)=g(k,l) <=> n=k und m=l

Nun weis ich nicht wie genau ich das beweisen kann.

Die Sachen die ich so rumprobiert habe haben nicht geholfen

Das einzige was ich noch weis ist, wenn

n^2+m^2+2nm-n-3m+2=2*l;   l∈|N ∪ {0}

gilt habe ich ∀ y ∃ (n,m): y=g(n,m) bewiesen.

Könnte mir jemand tipps geben wie ich auf den Beweis komme

MfG

Simon

Answer 1

Es müsste dann doch für jedes y = g(n, m) eine eindeutige Idendifikation von n und m geben.

m = (√(8·y - 8·n + 1) - 2·n + 3)/2

n = (√(8·y + 8·m - 7) - 2·m + 1)/2

Comments

Danke hatte daran hatte ich nicht gedacht, macht Sinn.

Answer 2

Das ist die Funktion zu "Cantors Diagonalverfahren"

g(1,1)=1
g(1,2)=2

g(2,1)=3

Damit werden die Paare sozusagen durchnummeriert

  1      2       4        7

 3      5       8

 6      9

10

und g(n,m) bedeutet also in der n-ten Zeile in der m-ten Spalte

steht die passende Nummer.

Wenn du die Surjektivität beweisen willst, nimmst du am besten vollst. Induktion.

Also zeige: Zu jedem k∈N gibt es ein Paar (n,m) mit g(n,m)=k.

Für k=1 ist g(1,1)=1.

Wenn es für ein  k∈N so ein Paar gibt, dann musst du beim

Induktionsschritt 2 Fälle unterscheiden:

1. Fall   m=1   (Du bist am Ende einer Diagonale.)

             also gibnt es ein n mit  k= g(n,1)

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

                    = n+1/2n(n-1)  = (n^2+n)/2  #

Dann gilt g(1, n+1) = (nach Def. von g)

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

         =  1+1/2(1+n)n

         = (n^2 + n + 2)/2  also wegen #

         = k+1.

2. Fall m>1  (Also bist du irgendwo auf einer Diagonale.)

Dann zeigst du durch Nachrechnen wie bei Fall 1, dass

  g(n+1,m-1)=k+1  ist.

Comments

Danke.

also

k=g(n,m)=...=1/2(n^2+m^2+2nm-n-3m+2)

um auf das nächste größere k zu kommen müssen wir eines zeile runter und eine spalte links:

g(n+1,m-1)=...=1/2(n^2+m^2+2mn-n-3m+4)=1/2(n^2+m^2+2mn-n-3m+2)+1

=k+1

ok. habe es glaube ich verstanden,

wie kommt man am besten auf so einen beweis bzw. wie erkennt man ihn?

Denn das mit der Anordnung hatte ich auch entdeckt gehabt, hatte sie nur transformiert, konnte damit aber nichts anfangen.

---

Wenn du das mit den Diagonalen schon bemerkt hattest,

war es ja eigentlich klar, dass man zwei Fälle unterscheiden muss

um zur nächsten Zahl zu kommen:

Entweder in der Diagonale vorangehen oder nach oben springen.