Bijektivität einer Abbildung < Abbildungen < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Zeigen Sie, dass die durch die Vorschrift
f(n,m) := [mm] \bruch{1}{2} [/mm] (n+m-1)(n+m-2)+m
erklärte Abbildung f: [mm] \IN [/mm] x [mm] \IN \to \IN [/mm] bijektiv ist. |
Hallo,
ich muss o.a. Aufgabe Beweisen und hänge ein wenig in den Seilen. Zuerst wollte ich mal zeigen, dass diese Abbildung injektiv ist und dann dass sie surjektiv ist, was sie automatisch bijektiv macht.
Aber genau da ist mein Problem. Um zu zeigen, dass die Abbildung injektiv ist, hab ich damit angefangen einen Widerspruch herbei zu konstruieren indem ich ersteinmal behaupte, die Funktion sei nicht injektiv.
Also (a,b) [mm] \not= [/mm] (c,b) [mm] \Rightarrow [/mm] f(a,b) = f(c,b)
Das kann ich dann sinnvoll bis [mm] (a+b)^2 [/mm] -3a = [mm] (c+b)^2 [/mm] -3c auflösen.
Jetzt könnte ich ja sagen, dass das nur gleich sein kann, wenn a=c ist und hätte somit meinen Widerspruch.
GEHT DAS SO???
Vielen Dank
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:02 Do 06.11.2008 | | Autor: | Marcel |
Hallo,
> Zeigen Sie, dass die durch die Vorschrift
>
> f(n,m) := [mm]\bruch{1}{2}[/mm] (n+m-1)(n+m-2)+m
>
> erklärte Abbildung f: [mm]\IN[/mm] x [mm]\IN \to \IN[/mm] bijektiv ist.
eine schöne Aufgabe, die uns beweist: [mm] $\IN$ [/mm] und [mm] $\IN \times \IN$ [/mm] sind gleichmächtig. Wenngleich man das auch schneller sehen kann 
> Hallo,
>
> ich muss o.a. Aufgabe Beweisen und hänge ein wenig in den
> Seilen. Zuerst wollte ich mal zeigen, dass diese Abbildung
> injektiv ist und dann dass sie surjektiv ist, was sie
> automatisch bijektiv macht.
>
> Aber genau da ist mein Problem. Um zu zeigen, dass die
> Abbildung injektiv ist, hab ich damit angefangen einen
> Widerspruch herbei zu konstruieren indem ich ersteinmal
> behaupte, die Funktion sei nicht injektiv.
>
> Also (a,b) [mm]\not=[/mm] (c,b) [mm]\Rightarrow[/mm] f(a,b) = f(c,b)
Ne, wenn dann $(a,b) [mm] \not=(c,d)$ $\Rightarrow$ [/mm] $f(a,b) [mm] \not=f(c,d)\,.$
[/mm]
> Das kann ich dann sinnvoll bis [mm](a+b)^2[/mm] -3a = [mm](c+b)^2[/mm] -3c
> auflösen.
>
> Jetzt könnte ich ja sagen, dass das nur gleich sein kann,
> wenn a=c ist und hätte somit meinen Widerspruch.
Ne, das verstehe ich nicht. Du kannst natürlich zur Injektivität auch zeigen:
$f(a,b)=f(c,d)$ [mm] $\Rightarrow$ $(a,b)=(c,d)\,,$ [/mm] also:
$f(a,b)=f(c,d)$ [mm] $\Rightarrow$ [/mm] $a=c$ und [mm] $b=d\,.$
[/mm]
Wenn Du das machst:
Du startest mit
$$ [mm] \bruch{1}{2}(a+b-1)(a+b-2)+b= \bruch{1}{2}(c+d-1)(c+b-2)+d\,$$
[/mm]
rechnest ein wenig rum und gelangst (hoffentlich) zu
[mm] $$(a+b)^2-3a-b=(c+d)^2-3c-d\,.$$
[/mm]
Zeige nun halt, dass diese Gleichung nicht gelten kann, wenn $a [mm] \not=c$ [/mm] oder wenn $b [mm] \not=d\,.$ [/mm] Das kannst Du natürlich auch so machen:
Zeige:
1.) Wenn die letzte Gleichung gilt und $a=c$, dann muss auch [mm] $b=d\,$ [/mm] sein.
(Wenn Du nachher zu sowas wie [mm] $$(\star)\;\;\;b(b+2c-1)=d(d+2c-1)$$ [/mm] gelangst (ich hoffe mal, dass ich mich nicht verrechnet habe),
so kann diese Gleichung nur gelten, wenn [mm] $b=d\,.$ [/mm] Andernfalls kann man nämlich o.B.d.A. $b < d$ annehmen, aber dann wäre in [mm] $(\star)$ [/mm] die linke Seite $<$ als die rechte...)
2.) Wenn die letzte Gleichung gilt und $b=d$, dann muss auch [mm] $a=c\,$ [/mm] sein.
Gruß,
Marcel
|
|
|
| |
|
> eine schöne Aufgabe, die uns beweist: [mm]\IN[/mm] und [mm]\IN \times \IN[/mm]
> sind gleichmächtig. Wenngleich man das auch schneller
> sehen kann
Hallo Marcel,
möglicherweise meinst du mit "schneller sehen" ziemlich
genau das, was man in der Tabelle der Funktionswerte
(siehe meinen Beitrag weiter unten) sieht, oder ?
Al
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:49 Sa 08.11.2008 | | Autor: | Marcel |
Hallo,
> > eine schöne Aufgabe, die uns beweist: [mm]\IN[/mm] und [mm]\IN \times \IN[/mm]
> > sind gleichmächtig. Wenngleich man das auch schneller
> > sehen kann
>
>
>
> Hallo Marcel,
>
> möglicherweise meinst du mit "schneller sehen" ziemlich
> genau das, was man in der Tabelle der Funktionswerte
> (siehe meinen Beitrag weiter unten) sieht, oder ?
nein. Ich habe die Tabelle ja auch benutzt, um einen Induktionsbeweis für die Surjektivität zu liefern (aber irgendwo ist da entweder bei meinen Diagonalen oder bei Deinen der Wurm drin; meine laufen von oben rechts nach unten links, Deine von unten links nach oben rechts. Ich hatte mich da aber anfangs eh verzettelt, weil hier auch blöderweise $f(n,m)=...$ anstatt $f(m,n)=...$ steht. Da sollen die Leute, die die Aufgabe bearbeiten, nochmal selber gucken, wer von uns beiden sich da vertut... Edit: Achtung: Dass sich unsere Matrizen nicht decken, liegt daran, dass ich $f(n,m)$ in der $n$-ten Spalte und $m$-ten Zeile abtrage, während Al $f(n,m)$ in der $n$-ten Zeile und $m$-en Spalte abträgt (was bzgl. der Interpretation einer "doppelt unendlichen Matrix" eigentlich auch besser ist). Ich fand die Diagonalen so aber schöner sortiert ). Ich meint das so:
Es ist klar, dass eine Injektion [mm] $\IN \to \IN \times\IN$ [/mm] existiert, also ist hat [mm] $\IN \times \IN$ [/mm] schonmal mindestens abzählbar unendlich viele Elemente. Dass [mm] $\IN \times \IN$ [/mm] auch wirklich abzählbar ist, erkennt man wegen
[mm] $$\IN \times \IN=\bigcup_{m \in \IN}\bigcup_{n \in \IN}\{(m,n)\}\,$$
[/mm]
da abzählbare Vereinigungen abzählbarer Mengen wieder abzählbar sind. Also man braucht gar keine konkrete Funktionsangabe, wenn man diesen Satz zur Verfügung hat.
Gruß,
Marcel
|
|
|
| |
|
> Dass [mm]\IN \times \IN[/mm] auch wirklich abzählbar ist, erkennt man wegen
> [mm]\IN \times \IN=\bigcup_{m \in \IN}\bigcup_{n \in \IN}\{(m,n)\}\,[/mm]
>
> da abzählbare Vereinigungen abzählbarer Mengen wieder
> abzählbar sind. Also man braucht gar keine konkrete
> Funktionsangabe, wenn man diesen Satz zur Verfügung hat.
Na schön, wenn man sich auf so starke Sätze beruft, wird
vieles zum Kinderspiel. Aber hinter diesem Satz steckt ein
Beweis, der haargenau auf solchen Überlegungen beruht,
wie sie in dieser Aufgabe explizit verlangt werden.
Gruß al-Chw.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:06 Sa 08.11.2008 | | Autor: | Marcel |
Hallo,
> > Dass [mm]\IN \times \IN[/mm] auch wirklich abzählbar ist, erkennt
> man wegen
> > [mm]\IN \times \IN=\bigcup_{m \in \IN}\bigcup_{n \in \IN}\{(m,n)\}\,[/mm]
>
> >
> > da abzählbare Vereinigungen abzählbarer Mengen wieder
> > abzählbar sind. Also man braucht gar keine konkrete
> > Funktionsangabe, wenn man diesen Satz zur Verfügung hat.
>
>
>
> Na schön, wenn man sich auf so starke Sätze beruft, wird
> vieles zum Kinderspiel. Aber hinter diesem Satz steckt
> ein
> Beweis, der haargenau auf solchen Überlegungen beruht,
> wie sie in dieser Aufgabe explizit verlangt werden.
ja klar. Bzw. im Prinzip ist das hier ja das gleiche, wie die Gleichmächtigkeit von [mm] $\IN$ [/mm] und [mm] $\IQ$ [/mm] zu beweisen. Aber man sollte das dennoch mal gesehen und auch verstanden haben (ich meine nicht Dich, bei Dir weiß ich, dass Du das alles weißt ), denn ansonsten käme man vll. noch auf die Idee, die Gleichmächtigkeit von [mm] $\IN$ [/mm] zu [mm] $\underbrace{\IN \times \IN \times ... \times \IN}_{n \text{ mal}}=\produkt_{k=1}^n \IN$ [/mm] (für festes $n [mm] \in \IN$) [/mm] mit Angabe einer Bijektion zu beweisen. Und dann wird's (evtl.) wild, während es mit der obigen Notation und diesem Satz fast trivial ist
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:37 Fr 07.11.2008 | | Autor: | s40rty1 |
| Aufgabe | | zeigen sie, dass die durch die vorschrift f(n,m):= (1/2)(n+m-1)(n+m-2)+m erklärte Abbildung f:NxN-->N bijektiv ist. |
Ich habe auch ein problem bei dieser aufgabe. injektivität habe ich beweisen können allerdings bekomme ich die surjektivität nicht bewiesen. hatte einen ansatz mit vollständiger induktion aber bin nicht weitergekommen. hoffe mir kann jemand helfen.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 01:09 Sa 08.11.2008 | | Autor: | Marcel |
Hallo,
> zeigen sie, dass die durch die vorschrift f(n,m):=
> (1/2)(n+m-1)(n+m-2)+m erklärte Abbildung f:NxN-->N bijektiv
> ist.
> Ich habe auch ein problem bei dieser aufgabe. injektivität
> habe ich beweisen können allerdings bekomme ich die
> surjektivität nicht bewiesen. hatte einen ansatz mit
> vollständiger induktion aber bin nicht weitergekommen.
> hoffe mir kann jemand helfen.
vielleicht hilft Dir ja folgendes "Muster":
[mm] \begin{eqnarray*}
\\
(1,1)_{1} & \;\;(2,1)_{\blue{2}} & \;\;(3,1)_{\green{4}} & \;\;(4,1)_{\red{7}} & \;\;...
\\
(1,2)_{\blue{3}} & \;\;(2,2)_{\green{5}} & \;\;(3,2)_{\red{8}} & \;\;... & \;\;...
\\
(1,3)_{\green{6}} & \;\;(2,3)_{\red{9}} & \;\;... & \;\;... & \;\;...
\\
(1,4)_{\red{10}} & \;\;... & \;\;... & \;\;... & \;\;...
\\
\;\;...&\;\;...&\;\;...&\;\;...&\;\;...&\;\;...
\\
\\
\\
\end{eqnarray*}
[/mm]
(Die $(1).$ unten bitte vergessen, ich bekomme sie nicht weg.)
Laufe mal die Diagonalen von rechts oben nach links unten ab und schaue auf die Funktionswerte (ich habe sie als Index jeweils drangeschrieben). Jetzt muss man nur noch schauen, welcher Zusammenhang zwischen den Indizes und den Zeilen/Spalten dieser "unendlichen Matrix" besteht und das auch noch mathematisch ausdrücken, danach sollte man wissen, wie man zu einem Index das zugehörige Paar findet.
(Man kann ja auch mal nach und nach die Spalten untersuchen und schauen, welche Funktionswerte dort angenommen werden (also welche Indizes dort auftauchen)).
P.S.:
Als Beweistipp:
Nummerieren wir mal die Diagonalen von links nach rechts. Jetzt schreiben wir mal die "Diagonalurbildmengen" auf (Du wirst gleich sehen, was ich damit meine):
[mm] $D_1=\{(1,1)\}\,$ $D_2=\{(2,1),(1,2)\}\,,$ $D_3=\{(3,1),(2,2),(1,3)\}\,,$ $D_4=\{(4,1),(3,2),(2,3).(1,4)\}...$
[/mm]
Fällt Dir was auf? Für jedes $k [mm] \in \IN$ [/mm] setzen wir [mm] $D_k:=\{(r,s): r,s \in \IN \text{ und }r+s=k+1\}\,.$
[/mm]
Ich behaupte nun, dass für jedes $n [mm] \in \IN$ [/mm] gilt:
[mm] $$f\left(\bigcup_{k=1}^n D_k\right)$$
[/mm]
enthält ( bzw. ist genau [mm] $\black{=}$ [/mm] ) [mm] $\left\{t \in \IN: t \le \frac{n}{2}(n+1)\right\}\,.$ [/mm] Das kannst Du über Induktion zeigen.
Als Tipp: Wenn $n [mm] \in \IN$ [/mm] ist, so ist bei der $n+1$-en Diagonale das Element oben rechts gerade [mm] $(n+1,\;1)\,.$ [/mm] Berechne mal [mm] $f(n+1,\;1)\,.$ [/mm] Das letztstehende Element unten links in dieser Diagnalen ist [mm] $(1,\;n+1)\,$ [/mm] berechne mal [mm] $f(1,\;n+1)\,.$ [/mm] Dann überlege Dir mal, wie Du beim Induktionsbeweis [mm] $f(n+1-k,\;1+k)$ [/mm] für [mm] $k=1,...,n\,$ [/mm] ins Spiel bringen kannst.
P.P.S.:
Ich hoffe, Dir ist klar, dass diese ganzen Überlegungen + Induktionsbeweis (über die Diagonalelementmengen, den Du noch bitte ausführen solltest) die Surjektivität von $f$ liefern?
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:06 Sa 08.11.2008 | | Autor: | hrttoz |
Hallo.
Ich sitze gerade an der gleichen Aufgabenstellung.
Erstmal Danke, die Hinweise haben mir sehr weitergeholfen.
Zu dem Ausdruck
$ [mm] \left\{t \in \IN: t \le \frac{n}{2}(n+1)\right\}\,. [/mm] $
habe ich aber noch eine Frage:
müsste es nicht heißen $ t = [mm] \frac{n}{2}(n+1) [/mm] $?
Denn sonst könnte t doch 0 sein und die Funktion wäre dann nicht mehr surjektiv.
Mit dem Induktionsbeweis komme ich leider auch nicht so gut klar.
Bis jetzt habe ich:
$ [mm] f(n+1,\;1)\,. [/mm] = [mm] \bruch{n}{2}*(n+1) [/mm] + 1 $
und
$ [mm] f(1,\;n+1)\,. [/mm] = [mm] \bruch{n}{2}*(n+1) [/mm] + n+1 $
Ist das soweit richtig und wie bringe ich das ganze in $ [mm] f(n+1-k,\;1+k) [/mm] $ ein
Gruß
Gerrit
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:37 Sa 08.11.2008 | | Autor: | Marcel |
Hallo,
> Hallo.
>
> Ich sitze gerade an der gleichen Aufgabenstellung.
>
> Erstmal Danke, die Hinweise haben mir sehr weitergeholfen.
>
> Zu dem Ausdruck
> [mm]\left\{t \in \IN: t \le \frac{n}{2}(n+1)\right\}\,.[/mm]
> habe
> ich aber noch eine Frage:
> müsste es nicht heißen [mm]t = \frac{n}{2}(n+1) [/mm]?
> Denn sonst
> könnte t doch 0 sein und die Funktion wäre dann nicht mehr
> surjektiv.
also zunächst ist bei mir $0 [mm] \notin \IN$ [/mm] (ich schreibe also [mm] $\IN_0=\IN \overset{d}{\cup}\{0\}$, [/mm] wobei [mm] $\overset{d}{\cup}$ [/mm] "disjunkt vereinigt mit" bedeuten soll). Und [mm] $\left\{t \in \IN: t \le \frac{n}{2}(n+1)\right\}$ [/mm] ist nichts anderes als [mm] $\left\{1,2,...,\frac{n}{2}(n+1)\right\}\,.$ [/mm] Wichtig ist hier eher, dass auch [mm] $\frac{n}{2}(n+1) \in \IN\,.$ [/mm] Da gibt es aber zwei mögliche Argumente: [mm] $\{n,n+1\} \subseteq \IN$ [/mm] enthält stets eine gerade (und eine ungerade) Zahl. Das andere Argument ist, dass die Summe endlich vieler natürlicher Zahlen stets wieder eine natürliche Zahl ist und dann gilt [mm] $\frac{n}{2}(n+1)=\sum_{k=1}^n k\,.$
[/mm]
Und [mm] $f\left(\bigcup_{k=1}^n D_k\right)=\left\{t \in \IN:\;t \le \frac{n}{2}(n+1)\right\}$ [/mm] ist schon richtig. Die Menge [mm] $\{t \in \IN:\;t=(n/2)(n+1)\}$ [/mm] ist doch eine einelementige, genauer [mm] $=\{(n/2)(n+1)\}\,.$ [/mm] Mach' es Dir notfalls nochmal klar, indem Du [mm] $f(D_1)\,,$ $f(D_1 \cup D_2)\,,$ $f(D_1 \cup D_2 \cup D_3)\,,$ [/mm] und vielleicht auch noch [mm] $f(D_1 \cup D_2 \cup D_3 \cup D_4)$ [/mm] mal aufschreibst.
> Mit dem Induktionsbeweis komme ich leider auch nicht so gut
> klar.
> Bis jetzt habe ich:
>
> [mm]f(n+1,\;1)\,. = \bruch{n}{2}*(n+1) + 1[/mm]
>
> und
>
> [mm]f(1,\;n+1)\,. = \bruch{n}{2}*(n+1) + n+1[/mm]
> Ist das soweit richtig
Ja, aber den letzten Term schreibe ich noch ein wenig um (warum, siehst Du später):
[mm] $$\bruch{n}{2}*(n+1) [/mm] + [mm] (n+1)=(n+1)\left(\frac{n}{2}+1\right)=\frac{n+1}{2}(n+2)\,.$$ [/mm]
> und wie bringe ich das ganze in
> [mm]f(n+1-k,\;1+k)[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
ein
Na okay. Im Induktionsschritt geht man davon aus, dass für ein $n \in \IN$ gilt, dass $f\left(\bigcup_{k=1}^n D_k\right)$ die Menge $\left\{1,...,\;\frac{n}{2}(n+1)\right\}$ enthalte. Zu zeigen ist nun, dass $f\left(\bigcup_{k=1}^{n+1} D_k\right)$ die Menge $\left\{1,...,\;\frac{n+1}{2}(n+2)\right\}$ enthält.
Das heißt aber (wegen der Induktionsvoraussetzung) nichts anderes, als, dass man zeigen soll, dass $\left\{\blue{\frac{n}{2}(n+1)+1},\;...,\;\frac{n+1}{2}(n+2)\right\} \subseteq f(D_{n+1})$ gilt (es gilt sogar Gleichheit, aber das sehen wir erst gleich).
Nun gilt aber:
$\blue{f(n+1,1)=\frac{n}{2}(n+1)+1\,.$ Das ist schonmal gut (ich hoffe, Du siehst, wieso).
Jetzt mache ich mal folgendes:
$(\star)\;\;\; f(n+1-k,1+k)=\frac{1}{2}(n+1-k+1+k-1)(n+1-k+1+k-2)+1+k=\frac{1}{2}n(n+1)+1+k\,.$
Nun stehen auf der $(n+1)\,$en Diagonale gerade genau die Elemente $(n+1-k,1+k)$ für $k=0,...,n\,.$
Siehst Du nun, wie argumentieren kannst?
(Du hast schon separat ausgerechnet, was $f(n+1-k,1+k)$ für $k=0$ und was $f(n+1-k,1+k)$ für $k=n$ ist. Was sagt uns $(\star)$ denn, welchen Wert $f(n+1-\tilde{k},1+\tilde{k})$ hat, wenn $\tilde{k}=k+1$? Warum liefert das alles zusammen gerade $\left\{\frac{n}{2}(n+1)+1,\;...,\;\frac{n+1}{2}(n+2)\right\} \subseteq f(D_{n+1})$?)
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:11 So 09.11.2008 | | Autor: | hrttoz |
Hallo.
Vielen Dank für deine Erläuterungen. Ich hoffe folgender Gedankengang ist richtig:
$ [mm] \left\{1,...,\;\frac{n}{2}(n+1)\right\} [/mm] $ ist die Menge aller Tupel auf den Diagonalen, also die Menge aller Urbilder.
$ [mm] \left\{{\frac{n}{2}(n+1)+1},\;...,\;\frac{n+1}{2}(n+2)\right\} \subseteq f(D_{n+1}) [/mm] $
ist die Menge aller Tupel auf der folgenden Diagonale.
Sie beginnt oben rechts bei [mm] ${\frac{n}{2}(n+1)+1}$ [/mm] und endet ganz unten links bei [mm] ${\frac{n+1}{2}(n+2)}$
[/mm]
Das k ist sozusagen der Zeiger, der die Tupel auf der Diagonalen zwischen oben links und unten rechts beschreibt.
$ [mm] f(n+1-\tilde{k},1+\tilde{k}) [/mm] $ mit $ [mm] \tilde{k}=k+1 [/mm] $ hat den Wert:
$ [mm] \frac{1}{2}n(n+1)+1+k+1\ [/mm] $
Das sagt mir nun, dass es
auf der Diagonalen zu jedem Bild ein Tupel (Urbild)(n,m) gibt. Somit ist die Funktion surjektiv.
Ich hoffe ich habe alles richtig verstanden und deine Mühe hat sich gelohnt.
Vielen Dank nochmal.
Gruß
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 02:40 Mo 10.11.2008 | | Autor: | Marcel |
Hallo,
> Hallo.
>
> Vielen Dank für deine Erläuterungen. Ich hoffe folgender
> Gedankengang ist richtig:
>
> [mm]\left\{1,...,\;\frac{n}{2}(n+1)\right\}[/mm] ist die Menge aller
> Tupel auf den Diagonalen, also die Menge aller Urbilder.
uh, Du drückst Dich entweder sprachlich ganz falsch aus oder missverstehst etwas. [mm] $\left\{1,...,\;\frac{n}{2}(n+1)\right\}$ [/mm] ist die Menge der ersten [mm] $\frac{n}{2}(n+1)$ [/mm] natürlichen Zahlen (eine Zahl selbst ist doch kein Tupel). Diese Menge ist das Bild der Tupel der ersten [mm] $\black{n}$ [/mm] Diagonalen unter [mm] $\black{f}$.
[/mm]
> [mm]\left\{{\frac{n}{2}(n+1)+1},\;...,\;\frac{n+1}{2}(n+2)\right\} \subseteq f(D_{n+1})[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Das ist die Bildmenge der Tupel (unter der Funktion $\black{f}$), die sich auf der $\black{n}+1$en Diagonale befinden.
> ist die Menge aller Tupel auf der folgenden Diagonale.
??? Die Menge $\left\{{\frac{n}{2}(n+1)+1},\;...,\;\frac{n+1}{2}(n+2)\right\}$ ist die Menge der natürlichen Zahlen, die bei $\frac{n}{2}(n+1)+1}$ startet und bei $\frac{n+1}{2}(n+2)$ endet!
> Sie beginnt oben rechts bei [mm]{\frac{n}{2}(n+1)+1}[/mm] und endet
> ganz unten links bei [mm]{\frac{n+1}{2}(n+2)}[/mm]
Du sprichst hier quasi von "den" Urbildern (im Sinne von Eindeutigkeit) der Menge [mm] $\left\{{\frac{n}{2}(n+1)+1},\;...,\;\frac{n+1}{2}(n+2)\right\}\,.$ [/mm] Das kann man machen; allerdings sollte man sich dann darauf berufen, dass die Funktion schon vorher als injektiv erkannt wurde. Ich selbst zeige hier eigentlich einen Weg auf, der, wenn man in getrennt von der Injektivität betrachtet, nichtsdestotrotz die Surjektivität liefert. Im Endeffekt läuft es darauf hinaus, dass man für die $n$-te natürliche Zahl innerhalb der ersten $n$ Diagonalen (mindestens) ein Tupel findet, so dass $f$ angewendet auf dieses Tupel gerade $n$ ergibt. Ob dieses das einzige ist, interessiert uns eigentlich bei der Surjektivität nicht. Wichtig ist nur, dass man herausfindet: Innerhalb der ersten $n$ Diagonalen gibt es mindestens ein solches Tupel.
> Das k ist sozusagen der Zeiger, der die Tupel auf der
> Diagonalen zwischen oben links und unten rechts
> beschreibt.
> [mm]f(n+1-\tilde{k},1+\tilde{k})[/mm] mit [mm]\tilde{k}=k+1[/mm] hat den
> Wert:
> [mm]\frac{1}{2}n(n+1)+1+k+1\[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
> Das sagt mir nun, dass es
> auf der Diagonalen zu jedem Bild ein Tupel (Urbild)(n,m)
> gibt. Somit ist die Funktion surjektiv.
Ähm ja, so ähnlich. Eigentlich war meine Argumentation so:
Per Induktion zeigt man, dass das Bild der Tupel der ersten $\black{n}$ Diagonalen unter $\black{f}$ gerade $\left\{1,\;...\;\frac{n}{2}(n+1)\right\}$ ist. Dabei sieht man im Induktionsschritt folgendes:
Das Bild des Tupels (n+1,1) unter $f$ ist gerade $\frac{n}{2}(n+1)+1$ (vgl. $ \blue{f(n+1,1)=\frac{n}{2}(n+1)+1\,. $ von hier). Weiter war dort $ [mm] (\star)\;\;\; f(n+1-k,1+k)=\frac{1}{2}(n+1-k+1+k-1)(n+1-k+1+k-2)+1+k=\frac{1}{2}n(n+1)+1+k\,. [/mm] $ so dass man erkennt hat, dass wenn [mm] $\tilde{k}=k+1$ [/mm] ist, dass dann auch
[mm] $$f(n+1-\tilde{k},1+\tilde{k})=\frac{1}{2}n(n+1)+1+\tilde{k}=\underbrace{\frac{1}{2}n(n+1)+1+k}_{=f(n+1-k,1+k)}+1\,.$$
[/mm]
Das zeigt, dass, wenn man $k$ um eins erhöht, dann erhöht sich auch der zugehörige Funktionswert um eins. Der Sinn und zweck von [mm] $(\star)$ [/mm] war es, dass man erkennt, dass die Bilder der $n+1$en Diagonale unter [mm] $\black{f}$ [/mm] genau die natürlichen Zahlen von [mm] $\frac{n}{2}(n+1)+1$ [/mm] bis [mm] $\frac{n+1}{2}(n+2)$ [/mm] liefert.
Damit ist der Beweis, dass [mm] $\black{f}$ [/mm] surjektiv ist, nun einfach:
Es sei $N [mm] \in \IN$ [/mm] irgendeine natürliche Zahl. Dann gilt $N [mm] \in f\left(\bigcup_{k=1}^N D_k\right)\,,$ [/mm] da [mm] $f\left(\bigcup_{k=1}^N D_k\right)$ [/mm] ja alle natürlichen Zahlen von $1$ bis [mm] $\frac{N}{2}(N+1)$ [/mm] enthält und es ist [mm] $\frac{N}{2}(N+1) \ge N\,.$ [/mm] Das bedeutet aber nichts anderes, als, dass es innerhalb der ersten $N$ Diagonalen (mindestens) ein Tupel $(s,t)$ (mit insbesondere $(s,t) [mm] \in \IN \times \IN$) [/mm] gibt, so dass [mm] $f(s,t)=N\,.$ [/mm] Da $N [mm] \in \IN$ [/mm] beliebig war, gilt das für alle $N [mm] \in \IN$. [/mm] Also ist [mm] $\black{f}$ [/mm] surjektiv.
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 09:58 Mo 10.11.2008 | | Autor: | hrttoz |
> uh, Du drückst Dich entweder sprachlich ganz falsch aus
> oder missverstehst etwas.
Ich hatte dein "Muster" von oben im Kopf und hab nur die Tupel gesehen.
Mit dem Abstand einer Nacht, sehe ich das Ganze nun klar.
Vielen Dank und Gruß
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:26 Sa 08.11.2008 | | Autor: | s40rty1 |
vielen dank schon einmal soweit, ich muss mir das jetzt mal in ruhe zu gemühte führen, vielleicht komme ich ja weiter...
|
|
|
| |
|
Ich habe mir mal eine Tabelle einiger Funktionswerte gemacht.
Hier ist sie:
[mm] \pmat{ 1 &3&6&10&15&21 \\ 2&5&9&14&20&27\\4&8&13&19&26&34\\7&12&18&25&33&42\\11&17&24&32&41&51\\16&23&31&40&50&61}
[/mm]
In der n-ten Zeile und m-ten Spalte steht f(n,m)
Man kann daraus wohl auch erkennen, wie man vorgehen
müsste, um die Funktion f aufzustellen.
![[winken]](/images/smileys/winken.gif "[winken]")
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:57 Sa 08.11.2008 | | Autor: | Marcel |
Hallo,
> Ich habe mir mal eine Tabelle einiger Funktionswerte
> gemacht.
> Hier ist sie:
>
> [mm]\pmat{ 1 &3&6&10&15&21 \\ 2&5&9&14&20&27\\4&8&13&19&26&34\\7&12&18&25&33&42\\11&17&24&32&41&51\\16&23&31&40&50&61}[/mm]
>
> In der n-ten Zeile und m-ten Spalte steht f(n,m)
>
> Man kann daraus wohl auch erkennen, wie man vorgehen
> müsste, um die Funktion f aufzustellen.
>
>
>
so eine Tabelle habe ich ja bei der Surjektivität angedeutet (bzw. eine [mm] "$\IN \times \IN$"-Matrix, [/mm] Du weißt, was ich meine).
Aber ich glaube, ich sehe auch, was mich irritiert hat:
Bei Dir steht in der $n$-ten Zeile und $m$-ten Spalte [mm] $f(n,m)\,,$ [/mm] bei mir steht allerdings in der $m$-ten Zeile und $n$-ten Spalte [mm] $f(n,m)\,.$ [/mm]
Deine Notation ist im "Matrix-Sinne" etwas angepasster Ich habe quasi die Transponierte Deiner Matrix angegeben, was ja hier nicht wirklich schlim ist (Deine Notation ist bzgl. der LA eigentlich besser, da zuerst Zeilen, später Spalten ).
Gruß,
Marcel
|
|
|
| |
|
zuerst Zeilen, später Spalten
hallo Marcel,
diese Eselsbrücke sehe ich zum ersten Mal.
Sie regt mich zu einer weiteren an:
"zuerst den Zähler, nachher den Nenner"
(angenommen, dass man beim Schreiben des
Bruches oben anfängt, so wie wir Brüche auch
benennen: "drei Viertel")
Auch die Schreibweise $\ [mm] \IQ=\{\bruch{z}{n}\ |\ z\in\IZ , n\in\IN\}$ [/mm]
ist sehr eingängig.
Beim Korrigieren einer Schülerarbeit fand ich
einmal am oberen Blattrand fett eingerahmt
den Text:
GAG
HHA
Ich rätselte, was mir da mitgeteilt werden sollte:
Gag ? h(a)ha ? ein Scherz ?
bis mir dämmerte, dass dies Merkregeln für die
Definitionen von sin, cos und tan am rechtwinkligen
Dreieck waren.
Später habe ich eine ausgereiftere Version davon
angetroffen:
SINGH (häufigster Name in Indien)
COSAH (ital. "cosa")
TANGA (indianischer Lendenschurz ...)
|
|
|
|
