Themenbereiche Themenbereiche Profile Hilfe/Anleitungen Help    
Recent Posts Last 1|3|7 Days Suche Suche Tree Tree View  

F : NxN --> N

ZahlReich - Mathematik Hausaufgabenhilfe » ---- Archiv: Universitäts-Niveau » Lineare Algebra » Abbildungen » F : NxN --> N « Zurück Vor »

Autor Beitrag
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Esther
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Samstag, den 28. Oktober, 2000 - 15:32:   Beitrag drucken

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!
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Matroid (Matroid)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Sonntag, den 29. Oktober, 2000 - 20:54:   Beitrag drucken

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

Beitrag verfassen
Das Senden ist in diesem Themengebiet nicht unterstützt. Kontaktieren Sie den Diskussions-Moderator für weitere Informationen.

ad

Administration Administration Abmelden Abmelden   Previous Page Previous Page Next Page Next Page