Autor |
Beitrag |
Esther
| Veröffentlicht am Samstag, den 28. Oktober, 2000 - 15:32: |
|
Abbildung NxN-->N, F(x,y)=y+(x+y)(x+y+1)/2; Injektivität schon bewiesen, zeige ob Abbildung surjektiv (und damit bijektiv). Wär toll, wenn das jemand lösen könnte! |
Matroid (Matroid)
| Veröffentlicht am Sonntag, den 29. Oktober, 2000 - 20:54: |
|
Hi Esther, surjektiv heißt doch, daß für alle Elemente n aus N ein Element (x,y) aus NxN existiert, mit F(x,y)=n. Dazu genügt es für ein beliebiges n ein Paar (x,y) anzugeben. Aber zuerst noch etwas zur Bedeutung dieser Abbildung. Wenn man beweisen will, daß NxN gleichmächtig zu N ist, dann geht man so vor, daß man sich das Zahlengitter aus NxN vorstellt und nun jedem Punkt in dem Gitter eine natürliche Zahl als Ordnungsnummer gibt. Dem Punkt (0,0) gibt man die 0, dann geht man einen Schritt nach rechts und numeriert alle Punkte (x,y) mit x+y=1. Anschließend alle Punkte mit x+y=2 usw. Im Zahlengitter stehen dann die Nummern so: 20 14 19 9 13 18 5 8 12 17 2 4 7 11 16 0 1 3 6 10 15 Also man vergibt die Nummern immer auf den Diagonalen von unten nach oben. Die erste vergegebene Ordnungszahl ist 0! Die in der Aufgabe gegegeben Abbildungsvorschrift F ist genau die, die diese Ordnungszahlen für jeden Punkt der Zahlenebene angibt. Die Frage nach der Surjektivität ist also: Welcher Punkt (x,y) der Zahlenebene hat die Ordnungsnummer n? Dazu muß man sich zuerst überlegen, in welcher Diagonalen der Punkt mit Ordnungszahl n liegt. Dazu wiederum muß man wissen, wieviele Punkte durch die ersten m Diagonalen abgezählt sind. Sei d(m) die Anzahl der Punkte auf den ersten m Diagonalen. Wir vereinbaren, daß der Punkt (0,0) auf der Diagonalen 1 liegt und darum ist d(1)=1. Es ist d(m)=m*(m+1)/2 (evtl. Induktionsbeweis). Auch kann man formulieren: d(m) = d(m-1)+m, m>1 und d(1)=1. Zu einer gegebenen Ordnungszahl n>0 können wir nun ein maximales m und Zahlen reN finden, mit n = d(m) + r und dabei ist r<m. Das letzter folgt aus der angegebenen Rekursion für d(m). Also suchen wir ein maximales m mit n = m*(m+1)/2 +r. So eines gibt es immer, dafür kann man wieder einen Induktionsbeweis machen. Nun gibt m+1 gibt die Diagonale an, auf der n liegt. Das "+1" ist erforderlich, weil die Numerierung mit 0 begonnen hat. Alle Punkte (x,y) auf der Diagonalen haben x+y=m Beispiel: Die ersten Glieder der Folge d(n): d(1)=1 d(2)=3 d(3)=6 d(4)=10 d(5)=15 Wähle n=13 => m=4, also liegt die 13 auf der 5-ten Diagonalen. Auf der 5-ten Diagonalen liegen 5 Punkte. Es ist 13 mod 10 = 3 = r. Darum (x,y) = (4-3,0+3) = (1,3). Tatsächlich ist 3+(1+3)*(1+3+1)/2 = 13. Das war ein langer Weg. Jetzt verwenden wir die gezeigten Ergebnisse, das ist dann ganz einfach: F sujektiv folgt aus: Für neN existiert (x,y)eNxN mit F(x,y)=n, nämlich (x,y) = (m-r,r) mit einem maximalen meN für das gilt: n = d(m) + r Beweis: F(m-r,r) = r+(m-r+r)(m-r+r+1)/2 = r + m*(m+1)/2 = r + d(m). qed. Gruß Matroid |
|