Nachweis Injektivität < Funktionen < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:59 Do 17.10.2013 | | Autor: | phychem |
Hallo
Ich komm grad mit einem eigentlich ziemlich simplen Nachweis nicht klar. Folgendes:
Es geht darum zu beweisen, dass sich für jede unendliche Menge M eine injektive Abbildung
f: [mm] \IN \to [/mm] M
finden lässt. Ich glaub mal gehört zu haben, dass man dies wie folgt zeigen kann:
Eine Menge M ist ja genau dann unendlich, wenn sich eine Selbstabbildung finden lässt, die zwar injektiv nicht aber surjektiv ist. Es sei also
s: M [mm] \to [/mm] M
eine injektive aber nicht surjektive Selbstabbildung. Man findet dann ein [mm] a\inM, [/mm] das nicht im Bild von s liegt:
a [mm] \not\in [/mm] im(s)
Nun definiere man rekursiv:
f: [mm] \IN \to [/mm] M , f(0):=a f(n+1):=s(f(n))
Dies ist gerade die gesuchte injektive Abbildung.
Mein Problem: Der Injektivitätsnachweis. Ich kann ja relativ einfach induktiv beweisen, dass stets [mm] f(n+1)\not=f(n) [/mm] ist, aber das reicht ja nicht aus. Wie kann ich ganz allgemein zeigen, dass [mm] f(n)\not=f(m) [/mm] für [mm] n\not=m [/mm] ist?
Sollte eigentlich ziemlich einfach sein aber irgendwie will es mir nicht gelingen...
|
|
| |
|
Hallo phychem,
(kommt übrigens dieser Nick davon, dass du Physik und
Chemie studierst ... ?)
> Es geht darum zu beweisen, dass sich für jede unendliche
> Menge M eine injektive Abbildung
> f: [mm]\IN \to[/mm] M
> finden lässt. Ich glaub mal gehört zu haben, dass man
> dies wie folgt zeigen kann:
>
> Eine Menge M ist ja genau dann unendlich, wenn sich eine
> Selbstabbildung finden lässt, die zwar injektiv nicht aber
> surjektiv ist. Es sei also
> s: M [mm]\to[/mm] M
> eine injektive aber nicht surjektive Selbstabbildung. Man
> findet dann ein [mm]a\inM,[/mm] das nicht im Bild von s liegt:
> s(a) [mm]\not\in[/mm] im(s) ![[haee]](/images/smileys/haee.gif "[haee]")
Hast du dies wirklich so gemeint ?
Dies widerspräche doch der Definition von im(s) !
Ich denke, das sollte so lauten:
$\ [mm] a\in [/mm] M$ mit $\ [mm] a\notin [/mm] im(s)=s(M)$
oder
$\ [mm] a\in\ [/mm] \ [mm] M\smallsetminus [/mm] s(M)$
> Nun definiere man rekursiv:
> f: [mm]\IN \to[/mm] M , f(0):=b f(n+1):=s(f(n))
Wo kommt das b her ? Oben hattest du nur ein a .
> Dies ist gerade die gesuchte injektive Abbildung.
>
> Mein Problem: Der Injektivitätsnachweis. Ich kann ja
> relativ einfach induktiv beweisen, dass stets
> [mm]f(n+1)\not=f(n)[/mm] ist, aber das reicht ja nicht aus. Wie kann
> ich ganz allgemein zeigen, dass [mm]f(n)\not=f(m)[/mm] für [mm]n\not=m[/mm]
> ist?
> Sollte eigentlich ziemlich einfach sein aber irgendwie will
> es mir nicht gelingen...
Ich befürchte, dass du bei der Definition der rekursiven
Folge etwas nicht richtig wiedergegeben hast. So wie
es dasteht, kann ich mir auch keinen Reim daraus machen.
LG , Al-Chw.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:27 Do 17.10.2013 | | Autor: | phychem |
Ja, ich hab da ein paar "Schreibfehler" gemacht und bevor ichs überarbeiten konnte hast du schon geantwortet ;)
Gemeint war natürlich a [mm] \not\in [/mm] im(s) und "b" sollte natürlich a sein.
Habs überarbeitet.
|
|
|
| |
|
> Ja, ich hab da ein paar "Schreibfehler" gemacht und bevor
> ichs überarbeiten konnte hast du schon geantwortet ;)
OK
Hier geht's weiter ...
LG , Al
|
|
|
| |
|
> Es geht darum zu beweisen, dass sich für jede unendliche
> Menge M eine injektive Abbildung
> f: [mm]\IN \to[/mm] M
> finden lässt. Ich glaub mal gehört zu haben, dass man
> dies wie folgt zeigen kann:
>
> Eine Menge M ist ja genau dann unendlich, wenn sich eine
> Selbstabbildung finden lässt, die zwar injektiv nicht aber
> surjektiv ist. Es sei also
> s: M [mm]\to[/mm] M
> eine injektive aber nicht surjektive Selbstabbildung. Man
> findet dann ein [mm]a\inM,[/mm] das nicht im Bild von s liegt:
> a [mm]\not\in[/mm] im(s)
> Nun definiere man rekursiv:
> f: [mm]\IN \to[/mm] M , f(0):=a f(n+1):=s(f(n))
> Dies ist gerade die gesuchte injektive Abbildung.
>
> Mein Problem: Der Injektivitätsnachweis. Ich kann ja
> relativ einfach induktiv beweisen, dass stets
> [mm]f(n+1)\not=f(n)[/mm] ist, aber das reicht ja nicht aus. Wie kann
> ich ganz allgemein zeigen, dass [mm]f(n)\not=f(m)[/mm] für [mm]n\not=m[/mm]
> ist?
> Sollte eigentlich ziemlich einfach sein aber irgendwie will
> es mir nicht gelingen...
Hallo,
da bin ich nochmal. Ich habe mir mal eine Skizze
gemacht und möchte noch vorschlagen, dass wir
als Bezeichnungen verwenden:
$\ [mm] a_0:=\ [/mm] a$
$\ [mm] a_{n+1}\ [/mm] :=\ [mm] s(a_n)\qquad (n\in\IN_0)$
[/mm]
Dann haben wir sowas wie eine Zahlenfolge
oder Punktfolge [mm] _{n\in\IN_0} [/mm] , deren Anfangsglied
[mm] a_0 [/mm] nicht in s(M) liegt, aber alle weiteren Glieder
(die jeweils eindeutig festgelegt sind, nachdem [mm] a=a_0
[/mm]
feststeht) liegen in s(M).
Ich argumentiere zunächst mal anschaulich und
möglicherweise etwas "naiv":
Hätte die Folge nicht unendlich viele voneinander
verschiedene Glieder, so müsste sie nach endlich
vielen Schritten periodisch werden, also in einen
gewissen Zyklus einmünden, der sich dann ewig
wiederholen müsste.
Nun ginge es darum, von dieser intuitiven Betrachtung
ausgehend einen Beweis (wohl in Form eines Wider-
spruchsbeweises) zu machen.
Ein Konflikt mit der Annahme der Injektivität von s
müsste doch dann wohl genau an der Stelle entstehen,
wo das "Anfangsstück" der Folge in den nachher
immer wieder durchlaufenen Zyklus "einmündet".
An dieser Stelle müsste ein gewisses Glied [mm] a_k
[/mm]
mit zwei voneinander verschiedenen "Vorgänger-
Gliedern" sitzen, also [mm] a_k=s(a_i)=s(a_j) [/mm] mit [mm] i\not=j
[/mm]
Dabei wäre [mm] a_i [/mm] das letzte Glied des vor-periodischen
Anfangsstückes der Folge und [mm] a_j [/mm] das letzte Glied
der ersten Periode [mm] (a_k, a_{k+1},a_{k+2}, [/mm] .... , [mm] a_j),
[/mm]
wobei [mm] a_{j+1}=a_k [/mm] .
So, das wäre mal eine Idee als Ansatz. Bleibt die
Frage, wie man daraus einen einigermaßen
"professionellen" Beweis (etwa mittels vollständiger
Induktion) macht.
LG , Al-Chw.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:23 Do 17.10.2013 | | Autor: | tobit09 |
Hallo Al-Chwarizmi,
> da bin ich nochmal. Ich habe mir mal eine Skizze
> gemacht und möchte noch vorschlagen, dass wir
> als Bezeichnungen verwenden:
>
> [mm]\ a_0:=\ a[/mm]
> [mm]\ a_{n+1}\ :=\ s(a_n)\qquad (n\in\IN_0)[/mm]
>
> Dann haben wir sowas wie eine Zahlenfolge
> oder Punktfolge [mm]_{n\in\IN_0}[/mm] , deren Anfangsglied
> [mm]a_0[/mm] nicht in s(M) liegt, aber alle weiteren Glieder
> (die jeweils eindeutig festgelegt sind, nachdem [mm]a=a_0[/mm]
> feststeht) liegen in s(M).
> Ich argumentiere zunächst mal anschaulich und
> möglicherweise etwas "naiv":
> Hätte die Folge nicht unendlich viele voneinander
> verschiedene Glieder, so müsste sie nach endlich
> vielen Schritten periodisch werden, also in einen
> gewissen Zyklus einmünden, der sich dann ewig
> wiederholen müsste.
Du begründest also (naiv), dass [mm] $(a_n)_{n\in\IN}=(f(n))_{n\in\IN}$ [/mm] unendlich viele voneinander verschiedene Glieder hat.
Dann müsste man noch kurz überlegen, dass die Injektivität von $f$ folgt.
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:28 Do 17.10.2013 | | Autor: | phychem |
Danke für die ausführliche Antwort.
Einen ähnliche Idee hatte ich auch. Aber leider gelang mir kein "wirklicher" Beweis, vorallem wurde es ziemlich schnell sehr kompliziert.
Mit Tobits Idee hab ich aber gerade einen sehr kurzen und eleganten Beweis gefunden.
Ich werd ihn gleich mal als Antwort and Tobit schreiben.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:13 Do 17.10.2013 | | Autor: | tobit09 |
Hallo phychem!
> Es geht darum zu beweisen, dass sich für jede unendliche
> Menge M eine injektive Abbildung
> f: [mm]\IN \to[/mm] M
> finden lässt. Ich glaub mal gehört zu haben, dass man
> dies wie folgt zeigen kann:
>
> Eine Menge M ist ja genau dann unendlich, wenn sich eine
> Selbstabbildung finden lässt, die zwar injektiv nicht aber
> surjektiv ist. Es sei also
> s: M [mm]\to[/mm] M
> eine injektive aber nicht surjektive Selbstabbildung. Man
> findet dann ein [mm]a\inM,[/mm] das nicht im Bild von s liegt:
> a [mm]\not\in[/mm] im(s)
> Nun definiere man rekursiv:
> f: [mm]\IN \to[/mm] M , f(0):=a f(n+1):=s(f(n))
> Dies ist gerade die gesuchte injektive Abbildung.
>
> Mein Problem: Der Injektivitätsnachweis. Ich kann ja
> relativ einfach induktiv beweisen, dass stets
> [mm]f(n+1)\not=f(n)[/mm] ist, aber das reicht ja nicht aus. Wie kann
> ich ganz allgemein zeigen, dass [mm]f(n)\not=f(m)[/mm] für [mm]n\not=m[/mm]
> ist?
> Sollte eigentlich ziemlich einfach sein aber irgendwie will
> es mir nicht gelingen...
Sei für [mm] $n\in\IN$ [/mm] die Aussage $A(n)$ gegeben durch
$A(n):=$"Für alle [mm] $m\in\IN$ [/mm] mit $n<m$ gilt [mm] $f(n)\not=f(m)$".
[/mm]
Zeige nun per Induktion nach $n$, dass $A(n)$ für alle [mm] $n\in\IN$ [/mm] gilt.
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:56 Do 17.10.2013 | | Autor: | phychem |
Gute Idee!
Der Beweis:
Induktionsanfang: n=0
A(0)= Für alle m>0 ist f(m) [mm] \not= [/mm] f(0)
Das ist offensichtlich richtig, denn es ist f(0)=a [mm] \not\in [/mm] im(s) und f(m)=s(f(m-1)) [mm] \in [/mm] im(s)
Induktionsschluss: Es sei bewiesen:
A(n) = Für alle m>n ist f(m) [mm] \not= [/mm] f(n)
Nun gilt es A(n+1) zu beweisen, also dass für alle m>n+1 [mm] f(m)\not=f(n+1) [/mm] ist.
(i) f(n+1) = s(f(n))
(ii) f(m) = s(f(m-1)) , m>n+1
Da [mm] m-1\ge [/mm] n+1 bzw. insbesondere m-1>n ist, f(n) gemäss Induktionsannahme verschieden von allen f(m') mit m'>n ist und die Funktion s injektiv ist, folgt aus (i) und (ii) gerade, dass [mm] f(n+1)\not=f(m) [/mm] für alle m>n+1 gilt.
Beweis vollständig.
Ach es wäre halt so einfach gewesen.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:02 Do 17.10.2013 | | Autor: | tobit09 |
> Der Beweis:
>
>
> Induktionsanfang: n=0
>
> A(0)= Für alle m>0 ist f(m) [mm]\not=[/mm] f(0)
>
> Das ist offensichtlich richtig, denn es ist f(0)=a [mm]\not\in[/mm]
> im(s) und f(m)=s(f(m-1)) [mm]\in[/mm] im(s)
>
>
> Induktionsschluss: Es sei bewiesen:
>
> A(n) = Für alle m>n ist f(m) [mm]\not=[/mm] f(n)
>
> Nun gilt es A(n+1) zu beweisen, also dass für alle m>n+1
> [mm]f(m)\not=f(n+1)[/mm] ist.
>
> (i) f(n+1) = s(f(n))
>
> (ii) f(m) = s(f(m-1)) , m>n+1
>
> Da [mm]m-1\ge[/mm] n+1 bzw. insbesondere m-1>n ist, f(n) gemäss
> Induktionsannahme verschieden von allen f(m') mit m'>n ist
> und die Funktion s injektiv ist, folgt aus (i) und (ii)
> gerade, dass [mm]f(n+1)\not=f(m)[/mm] für alle m>n+1 gilt.
Sehr schön! ![[ok]](/images/smileys/ok.gif "[ok]")
|
|
|
|
