vollst. Induktion:Bijektivität < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:58 Do 02.06.2011 | | Autor: | Cashima |
| Aufgabe | Sei Mn:= [mm] \{ k \IN : k \le n \} [/mm] . Zeigen Sie durch vollständige Induktion, dass jede injektive Abbildung f: Mn [mm] \to [/mm] Mn schon bijektiv ist.
Hinweis: Betrachten Sie auf Mn+1 die Abbildung g [mm] \circ [/mm] f mit
g: Mn+1 [mm] \to [/mm] Mn+1, g(j) := [mm] \{ \begin{cases} n+1, & \mbox{für } j \mbox{ = f(n+1)} \\ f(n+1), & \mbox{für } j \mbox{ = n+1} \\ j, & \mbox{sonst } \end{cases} \} [/mm] |
Ich bin wegen eines Umzug (aus einem anderen Bundesland) leider 3 Wochen nach Studienbeginn erst hergezogen und habe deshalb noch Probleme Sachverhalte zu beweisen (auszuformulieren geht noch besser als es mathematisch zu schreiben).
Meine Überlegungen:
1. klar, Injektivität von f: Mn [mm] \to [/mm] Mn nachweisen.
2. Surjektivität nachweisen.
3. Bijektivität nachweisen.
Soweit ist der Verlauf klar. Kriterien für die Injektivität: [mm] \forall [/mm] x1,x2 : f(x1)=f(x2) [mm] \Rightarrow [/mm] x1=x2
Kriterien für die Surjektivität: [mm] \forall [/mm] y [mm] \varepsilon [/mm] B [mm] \exists [/mm] A: f(x) = y
Bijektiv, wenn beides erfüllt ist.
Aber wie geht man das Ganze nun an, wenn man es via vollständiger Induktion beweisen soll??
Was ist der Induktionanfang? Ich finde es noch sehr schwierig aus der Aufgabenstellung die "Startüberlegung" zu erstellen.
Ich würde mich super freuen, wenn mir jemand helfen kann. Klar kann man alles googlen - das hilft vielleicht vorerst bei der Aufgabenabgabe (man muss 50% richtig haben, Abgabe Montag), aber nicht bei der Klausur- deshalb möchte ich es wirklich gerne verstehen!
Vielen lieben Dank im Voraus!
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt
|
|
| |
|
| Status: |
(Antwort) noch nicht fertig  | | Datum: | 21:24 Do 02.06.2011 | | Autor: | sangham |
Ind.Anfang n=1
d.h. [mm] M_1 [/mm] = [mm] \{1\}, [/mm] jede inj. abb f: 1 [mm] \to [/mm] 1 ist bij. -- ist trivial, da wir hier nur die Identität formulieren können.
Ind.Vor. ist dann jede inj. abb f: Mn [mm] \to [/mm] Mn ist bij.
Ind.Schluss (zu zeigen) es gilt auch für n+1
dabei ist dann der hinweis mit g zu verwenden und auszunutzen, dass es für f, definiert auf Mn schon gilt.
das für den start... other's are welcome
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:25 Di 07.06.2011 | | Autor: | Cashima |
Hi Sangham!
Danke für deine schnelle Antwort - ich war am Wochenende in der Heimat, wo ich leider kein Internet hatte. Aber hier mein Lösungsversuch:
I.V.:
Mn := [mm] \{ k \in \IN : k \le n \} [/mm] f: Mn [mm] \to [/mm] Mn z.z. für jedes n
I.A.:
n=1 ("1" da kleinste mögliche einzusetzende Zahl, da k [mm] \in \IN
[/mm]
M1 := [mm] \{ 1 \} [/mm]
f: [mm] \{ 1 \} \to \{ 1 \}
[/mm]
[mm] \to [/mm] bijektiv, da für jedes "y" genau ein "x" (oder wie kann man hier die Bijektivität mathematisch korrekt begründen?)
I.S.:
z.z. : es gilt auch für n+1
g : Mn+1 [mm] \to [/mm] Mn+1
Mn+1 := [mm] \{ k \in \IN : k \le n+1 \}
[/mm]
g( f(n+1)) := n+1 [mm] \to [/mm] hier gilt bereits Bijektivität, da für jeden X-Wert genau ein Y-Wert herauskommt (korrekt? wie formuliert man es richtig?)
g (n+1) := n+1 (bringt uns irgendwie nicht wirklich weiter!?)
g(f(x)) := f(x) [mm] \to [/mm] aus der Kombination von g(f(n+1)) und g(f(x)) ergibt sich, dass es für jedes f(x) gilt (wie formuliert man es? Das alte Problem.. ;)
[mm] \to [/mm] was zu beweisen war.
Kann man die Aufgabe so lösen? Was kanni ch besser schreiben / formulieren? Vielen Dank schon einmal!! :)
|
|
|
| |
|
Ich häng den Post mal direkt an deine ursprüngliche Frage drann, er bezieht sich aber auf alle drei Posts dadrüber (die Frage und die zwei Mitteilungen).
Fangen wir mit deiner leichtesten Frage an:
Eine Funktion heißt bijektiv, wenn sie sowohl injektiv als auch surjektiv ist.
Und ja, das ist mathematisch korrekt und wird auch im Normalfall so benutzt.
Falls du es in Zeichen haben möchtest:
f $M [mm] \to [/mm] N$ bijektiv [mm] $\gdw \forall [/mm] y [mm] \in [/mm] N [mm] \exists! [/mm] x [mm] \in [/mm] M: f(x) = y$
Hierbei steht das [mm] $\exists!$ [/mm] für "es existiert GENAU EIN"
Nun zur Induktion.
Da du ja noch ein paar Probleme mit dem Formalen hast versuche ich mal zu verdeutlichen wie genau eine Induktion normalerweise aussehen sollte.
Man fängt klassischerweise damit an zu sagen was genau man wie zeigen möchte:
zu zeigen: [mm] $\forall [/mm] n [mm] \in \IN$ [/mm] und Mn := [mm] $\{ k \in \IN | k \leq n \}$ [/mm] gilt:
Ist $f: Mn [mm] \to [/mm] Mn$ injektiv so ist f auch bijektiv.
Beweis durch vollständige Induktion über $n [mm] \in \IN$:
[/mm]
(IA):
(IV):
(IS):
Die Zeile "Beweis durch..." mag überflüssig erscheinen, aber ich würde dir raten sie dir anzugewöhnen.
Es gibt nämlich durchaus Aufgaben, da ist nicht sofort klar, dass man eine Induktion vorhat und es gibt auch Aufgaben da weiß man nicht über welche Variable jetzt induziert wird (in diesem Fall könnte ja vielleicht jemand eine Induktion über k versuchen^^).
Nun zu den drei Teilen der Induktion:
Im Induktionsanfang nimmst du dir die kleinste Zahl und rechnest nach.
Das hast du hier eigendlich schon ganz gut gemacht.
In der Induktionsvoraussetzung schreibst du nun genau was du voraussetzt.
Das mag zwar jetzt am Anfang unsinnig erscheinen, denn die Voraussetzung wird immer lauten "Es gelte die Aussage für ein $n [mm] \in \IN$", [/mm] aber es gibt auch Induktionen mit Voraussetzungen in einer etwas anderen Form, also immer schön aufschreiben.^^
Vor allem hier kommt es auf Kleinigkeiten an. "Es gelte die Aussage für ein $n [mm] \in \IN$" [/mm] ist eine richtige Voraussetzung, "Es gelte die Aussage für alle $n [mm] \in \IN$" [/mm] ist falsch (nur mal als Beispiel^^).
Im Induktionsschluss oder auch Induktionsschritt musst du dann aus der Voraussetzung folgern.
In diesem Fall musst du zeigen "gilt die Aussage für n so gilt sie auch für n+1".
Soweit erstmal genug Theorie, jetzt zumindest schonmal den Anfang und die Voraussetzung schwarz auf weiß:
(IA): n = 1
Mn = M1 = {1}
Es gibt genau eine Funktion, die M1 auf sich selbst abbildet, nämlich:
f: {1} [mm] $\to$ [/mm] {1}, 1 [mm] $\mapsto$ [/mm] 1
Diese Funktion ist offensichtlich bijektiv. [mm] $\checkmark$
[/mm]
(IV): Es gelte die zu zeigende Aussage für ein $n [mm] \in \IN$.
[/mm]
(IS): $n [mm] \to [/mm] n+1$:
...
Bevor der Schluss formal aufgeschrieben werden kann muss man sich natürlich überlegen, was man (inhaltich) schreiben will.
Du hast in der (IV) vorausgesetzt, dass alle injektiven Abbildungen von Mn auf sich selbst bijektiv sind.
Nun musst du das ganze auf M(n+1) erweitern.
Hierbei kann dir die Funktion g helfen, denn ist f injektiv so ist g bijektiv (das darfst du gerne zeigen ;) ).
Falls das nicht klappt (aber nur falls!) kannst du dir auch folgendes überlegen:
Für f: M(n+1) [mm] $\to$ [/mm] M(n+1) gilt es genau zwei Fälle zu unterscheiden:
1. f(n+1) = n+1, also n+1 wird auf sich selber abgebildet.
Ist das der Fall und weißt du, dass f injektiv ist, so muss f ja auch auf den ersten n Werten injektiv sein, denn da n+1 auf sich selber geht ändert das nichts an der Injektivität.
Somit weißt du hier mit (IV) recht schnell, dass f bijektiv ist.
Im zweiten Fall wird n+1 nicht auf sich selbst abgebildet.
Nehmen wir wieder an f war auf den ersten n Werten injektiv.
Nun wird n+1 nicht auf sich selbst abgebildet sondern auf einen der ersten n Werte, dieser wird also doppelt getroffen (Frage an dich: wieso war er vorher nicht "frei", wieso weißt du sofort, dass er jetzt doppelt getroffen wird?). Damit f auf allen n+1 Werten also wieder injektiv ist muss besagter zweite Wert also jetzt auf n+1 abgebildet werden (wieso reicht es den Fall zu betrachten, wo der auf n+1 geht, wieso muss man nicht die Fälle betrachten wo er irgendwo anders hingeht?)
Das heißt also du nimmst praktisch dein n+1 und "tauscht" es an irgend eine Position rein.
Dass die Funktion dadurch bijektiv bleibt (was sie nach (IV) ja war) darfst du dann wiederrum zeigen. ;)
Und de facto steckt hinter der Funktion g auch nicht sehr viel mehr als diese Überlegung, nur hübsch schwer verständlich verpackt. xD
Da ich immer noch nicht genug geschwafelt habe hier noch zwei Tipps:
1. Übe unbdingt das formal korrekte Aufschreiben der Induktion.
Induktionsaufgaben sind eine der wenigen Aufgaben, wo du schon allein für das formale die Hälfte der Punkte kassierst (zumindest anfänglich^^); und wo du auf der anderen Seite auch sehr viele Punkte verlieren kannst wenn das formale falsch ist, selbst wenn der Beweis inhaltlich richtig ist.
2. Mache dir klar, wieso jede Funktion zwischen zwei endlichen Mengen mit gleichvielen Elementen sofort bijektiv ist, wenn sie entweder injektiv oder surjektiv ist. (Mal dir einfach mal zwei Mengen mit je vier Elementen hin und versuche eine Abbildung zu finden, die surjektiv aber nicht injektiv oder anders herum ist; dann wirst du sehr schnell merken was ich meine^^)
Diese Tatsache wird nämlich an verschiedensten Stellen in Mathe wieder auftauchen; und wenn du sie jetzt verstehst ist es dann leichter. ;)
So, jetzt hab ich dich total zugetextet.
Versuch mal den Induktionsschluss möglichst schön und richtig aufzuschreiben.
Es mag sein dass du das richtige meintest, aber auch mit drei zugedrückten Augen ist das noch nicht zu erkennen.^^
|
|
|
|
