Bijektivität < Mengenlehre < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:50 Do 07.11.2013 | | Autor: | Ymaoh |
| Aufgabe | Für eine beliebige Menge X bezeichnen wir mit [mm] id_{x} [/mm] die Abbildung
[mm] id_{x}(x)=x, [/mm] für alle x [mm] \in [/mm] X. Wir nennen [mm] id_{x} [/mm] die Identität von X. Sei A eine Menge und f : A [mm] \to [/mm] A eine Abbildung mit der Eigenschaft, dass die n-fache Komposition von f mit sich selbst gleich der Identität von A ist, d.h.
(f [mm] \circ [/mm] f [mm] \circ [/mm] f [mm] \circ.....\circ [/mm] f)(x) = x, für alle x [mm] \in [/mm] A
Entscheiden Sie, ob f bijektiv ist, und beweisen (oder widerlegen) sie ihre Bahauptung. |
Wir hatten davor eine Aufgabe, in der dasselbe für (f [mm] \circ [/mm] f)(x)=x gemacht werden sollte. Da habe ich wie folgt Argumentiert:
f(x) = x ist bijektiv.
Für eine bijektive Verkettung gilt:
A [mm] \to [/mm] B [mm] \to [/mm] C , wobei die erste Abbildung injektiv sein muss, und die zweite surjektiv. Da in diesem Fall f mit sich selbst verkettet wird, gelten beide für f, damit ist es bijektiv. Das müsste doch sitmmen, oder?
Ich weiß aber nciht, wie ich das nun für die hier gestellte Aufgabe beweisen soll. Ich gehe davon aus, das f auch hier bijektiv sein muss.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:15 Do 07.11.2013 | | Autor: | fred97 |
> Für eine beliebige Menge X bezeichnen wir mit [mm]id_{x}[/mm] die
> Abbildung
> [mm]id_{x}(x)=x,[/mm] für alle x [mm]\in[/mm] X. Wir nennen [mm]id_{x}[/mm] die
> Identität von X. Sei A eine Menge und f : A [mm]\to[/mm] A eine
> Abbildung mit der Eigenschaft, dass die n-fache Komposition
> von f mit sich selbst gleich der Identität von A ist,
> d.h.
>
> (f [mm]\circ[/mm] f [mm]\circ[/mm] f [mm]\circ.....\circ[/mm] f)(x) = x, für alle x
> [mm]\in[/mm] A
>
> Entscheiden Sie, ob f bijektiv ist, und beweisen (oder
> widerlegen) sie ihre Bahauptung.
> Wir hatten davor eine Aufgabe, in der dasselbe für (f
> [mm]\circ[/mm] f)(x)=x gemacht werden sollte. Da habe ich wie folgt
> Argumentiert:
> f(x) = x ist bijektiv.
> Für eine bijektive Verkettung gilt:
> A [mm]\to[/mm] B [mm]\to[/mm] C , wobei die erste Abbildung injektiv sein
> muss, und die zweite surjektiv. Da in diesem Fall f mit
> sich selbst verkettet wird, gelten beide für f, damit ist
> es bijektiv. Das müsste doch sitmmen, oder?
> Ich weiß aber nciht, wie ich das nun für die hier
> gestellte Aufgabe beweisen soll. Ich gehe davon aus, das f
> auch hier bijektiv sein muss.
Na ja. Zeigen oder widerlegen sollst Du das.
Für j [mm] \in \{1,...,n\} [/mm] sei [mm] f_j [/mm] die j - fache Komposition von f mit sich selbst.
Nach Vor. ist also [mm] f_n=id_A. [/mm] Weiter ist [mm] f_1=f.
[/mm]
Zur Surjektivität:
für jedes y [mm] \in [/mm] A ist [mm] y=f_n(y)=f(f_{n-1}(y)).
[/mm]
Warum sieht man nun, dass f surjektiv ist ?
Zur Injektivität:
sind a, b [mm] \in [/mm] A und gilt f(a)=f(b), so zeige: a=b.
begründe: [mm] f_j(a))=f_j(b) [/mm] für j [mm] \in \{1,...,n\}
[/mm]
FRED
>
>
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 16:55 Do 07.11.2013 | | Autor: | Ymaoh |
Ich verstehe nicht, warum für alle [mm] y\inA [/mm] gilt:
y= [mm] f_{n}(y)=f(f_{n-1})(y)
[/mm]
Also das y= [mm] f_{n}(y) [/mm] muss gelten, damit bijektivität, also damit auch surjektivität, gegeben ist.
Aber warum [mm] f_{n}(y)=f(f_{n-1})(y) [/mm] ?
Das a=b folgt, so etwas ähnliches hatten wir im Tutorium. Wenn ich das hier anwenden würde, sähe das so aus:
f(a)=f(b)
daraus folgt, dass:
f(f(a))=f(f(b))
also
f [mm] \circ [/mm] f (a) = f [mm] \circ [/mm] f (b)
Da f [mm] \circ [/mm] f bijektiv ist, gilt a=b.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:23 Do 07.11.2013 | | Autor: | Marcel |
Hallo,
>
> Ich verstehe nicht, warum für alle [mm]y\inA[/mm] gilt:
> y= [mm]f_{n}(y)=f(f_{n-1})(y)[/mm]
na, es wurde doch definiert:
[mm] $f_n= [/mm] f [mm] \circ [/mm] f [mm] \circ [/mm] f [mm] \circ [/mm] ... [mm] \circ f\,.$ [/mm] (Das [mm] $f\,$ [/mm] rechterhand taucht n Mal auf!)
Jetzt wäre doch eigentlich die erste Frage: Wie ist die rechte Seite zu verstehen?
Ist das zu lesen als
$f [mm] \circ \red{(}f \circ \blue{\textbf{(}}f \circ [/mm] (f [mm] \circ \ldots)\blue{\textbf{)}} \red{)},$
[/mm]
oder als
[mm] $(...\blue{(}\red{(}f \circ f\red{)} \circ f\blue{)} \circ [/mm] ...) [mm] \circ [/mm] f$
oder wie auch immer...
(Bspw.: Ist mit [mm] $f_3$ [/mm] nun
$f [mm] \circ [/mm] (f [mm] \circ f)\,,$
[/mm]
oder
$(f [mm] \circ [/mm] f) [mm] \circ [/mm] f$
gemeint? Oder ist das egal? Tatsächlich stimmt das zuletzt vermutete, denn
ich sage: ...)
... im Endeffekt ist das glücklicherweise egal, weil bzgl. [mm] $\circ$ [/mm] das Assoziativgesetz
gilt.
Deswegen kann man direkt schreiben
[mm] $f_n=\underbrace{f \circ f \circ \ldots \circ f}_{n \text{ Stück}}=f \circ \Big(\underbrace{f \circ f \circ \ldots \circ f}_{\red{(n-1)\,} \text{ Stück}}\Big)=f \circ f_{n-1},$
[/mm]
und das bedeutet eben insbesondere
[mm] $f_n(y)=(f \circ f_{n-1})(y)=f\red{\textbf{(}}f_{n-1}(y)\red{\textbf{)}}$ [/mm] für alle [mm] $y\,$ [/mm] des entsprechenden Def.-Bereichs.
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:53 Do 07.11.2013 | | Autor: | Ymaoh |
Hmm....also das habe ich jetzt verstanden, aber so ganz komme ich immer noch nicht weiter.
Also, wenn ich das als Verkettung schreibe:
f [mm] \circ f_{n-1}(x) [/mm] = y ist diese Verkettung bijektiv.
Das heißt, nach dem Muster von unserem Tutor wäre das:
[mm] f_{n-1} [/mm] A [mm] \to [/mm] B
f B [mm] \to [/mm] C
Die erste Abbildung muss injektiv sein, die zweite surjektiv, damit wäre f(x)
surjektiv. Aber dann fehlt mir ja noch die injektivität, aber über die kann ich so doch nichts sagen, oder?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:14 Do 07.11.2013 | | Autor: | Marcel |
Hallo,
> Hmm....also das habe ich jetzt verstanden, aber so ganz
> komme ich immer noch nicht weiter.
>
> Also, wenn ich das als Verkettung schreibe:
> f [mm]\circ f_{n-1}(x)[/mm] = y ist diese Verkettung bijektiv.
> Das heißt, nach dem Muster von unserem Tutor wäre das:
> [mm]f_{n-1}[/mm] A [mm]\to[/mm] B
> f B [mm]\to[/mm] C
> Die erste Abbildung muss injektiv sein, die zweite
> surjektiv, damit wäre f(x)
> surjektiv. Aber dann fehlt mir ja noch die injektivität,
> aber über die kann ich so doch nichts sagen, oder?
mir sind Deine Probleme nicht so ganz klar:
Aus $f [mm] \colon \red{A} \to \blue{A}$ [/mm] folgt sofort, dass
[mm] $f_n:=\underbrace{f \circ f \circ ... \circ f}_{n \text{ Stück}}$
[/mm]
auch eine Abbildung $A [mm] \to [/mm] A$ ist. (Klar, oder?)
1. Frage: Ist [mm] $f\,$ [/mm] surjektiv?
Um diese Frage zu beantworten, ist zu klären, ob es
für jedes $y [mm] \in \blue{A}$ [/mm] ein $x [mm] \in \red{A}$ [/mm] mit [mm] $f(x)=y\,$
[/mm]
gibt.
Tipp: Ist $y [mm] \in \blue{A}\,,$ [/mm] so hast Du ja schon
[mm] $f(f_{n-1}(y))=f_n(y)=y$
[/mm]
gesehen. Was bringt Dir das nun, wenn wir
[mm] $x:=f_{n-1}(y)$
[/mm]
definieren (aus welcher Menge ist das insbesondere ein Element)? Siehst
Du ein, dass dies die Surjektivität von [mm] $f\,$ [/mm] beweist?
2. Frage: Ist [mm] $f\,$ [/mm] injektiv?
Dazu gibt es generell zwei Standardbeweismöglichkeiten, wenn man dies
vermutet (es gibt auch noch andere Beweismöglichkeiten):
2a) Man zeigt hier: Für (alle) $a,b [mm] \in \red{A}$ [/mm] mit $a [mm] \not=b$ [/mm] folgt $f(a) [mm] \not=f(b)\,.$
[/mm]
2b) Man zeigt hier: Für (alle) $a,b [mm] \in \red{A}$ [/mm] gilt: Aus [mm] $f(a)=f(b)\,$ [/mm] folgt [mm] $a=b\,.$
[/mm]
(Diese Möglichkeiten sind äquivalent, Stichwort: Kontraposition!)
Ich gehe mal nach Schema 2b) vor:
Seien also $a,b [mm] \in \red{A}$ [/mm] (ansonsten beliebig, aber fest). Zudem gelte nun [mm] $f(a)=f(b)\,.$
[/mm]
Ich definiere mal [mm] $\tilde{a}:=f_{n-1}(a)$ [/mm] und [mm] $\tilde{b}:=f_{n-1}(b)\,.$ [/mm] Denke erstmal drüber nach, warum dann
[mm] $\tilde{a},\tilde{b} \in \red{A}$ [/mm] gilt.
Wenn das klar ist: Daher kannst Du [mm] $f_{n-1}(\tilde{a})$ [/mm] und [mm] $f_{n-1}(\tilde{b})$ [/mm] überhaupt bilden.
Vergleiche dann mal
[mm] $f_{n-1}(\tilde{a})=f_{n-1}(f(a))=(\underbrace{f \circ ... \circ f}_{n \text{ Stück}})(a)=\text{?}$
[/mm]
mit
[mm] $f_{n-1}(\tilde{b})=\text{?}$
[/mm]
P.S.: Kannst Du mal bitte den Satz, den Euer Tutor erwähnt hat, aufschreiben?
Denn zum einen kannst Du Sätze nur dann anwenden, wenn Du geprüft
hast, dass die Voraussetzungen zur Anwendung des Satzes gegeben sind
(wenn man etwa den Satz: "Für $x,y > [mm] 0\,$ [/mm] gilt [mm] $x^2=y^2 \Longrightarrow [/mm] x=y$"
hat, dann kann man natürlich nicht einfach sagen, dass man diesen Satz
auf $x,y [mm] \in \IR$ [/mm] oder $x,y [mm] <0\,$ [/mm] anwenden will - bzw. sagen kann man vieles, aber
es ist halt "sinnlos"), zum anderen musst Du auch aufpassen mit der Sprache:
Wenn man weiß, dass eine Folgerung $A [mm] \Longrightarrow [/mm] B$ wahr ist, so heißt das:
Die Wahrheit von [mm] $A\,$ [/mm] liefert zwingend die Wahrheit von [mm] $B\,.$
[/mm]
Wenn Du nun sagst: "Wenn [mm] $B\,$ [/mm] gilt, dann muss ja auch [mm] $A\,$ [/mm] gelten",
so hat das aber nichts mehr mit $A [mm] \Longrightarrow [/mm] B$ zu tun - sondern dann behauptest
Du, dass Du die Folgerung $B [mm] \Longrightarrow [/mm] A$ benutzen darfst - was dann aber
eines Zusatzbeweises bedarf!
Mir ist bei Dir hier nicht so ganz klar, ob Du da etwas durcheinanderbringst
(z.B. kann es sein, dass Du einen Satz anwenden willst, wo Du gar nicht
die Voraussetzungen des Satzes geprüft hast; oder, was ich eher vermute,
dass Du einen Satz anwenden willst, der Dir eigentlich nur sagt, welche
Bedingungen NOTWENDIG für die Bijektivität der Komposition zweier Abbildungen
sind - Du brauchst aber HINREICHENDE Bedingungen, oder aber, Du machst
es so, wie wir es Dir hier vorgeschlagen haben: Nachrechnen per Definitionem!)
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:36 Fr 08.11.2013 | | Autor: | Ymaoh |
Also zunächst mal das, was unser Tutor gesagt hat:
Ist die Verkettung zweier Funktionen bijektiv, so gilt, dass
die innere Funktion injektiv sein muss, und die äußere surjektiv.
g [mm] \circ [/mm] f
A [mm] \overrightarrow{f} [/mm] B [mm] \overrightarrow{g} [/mm] C
mit: g muss surjektiv sein, f muss injektiv sein.
Deswegen habe ich ja in der Aufgabe, in der f einmal mit sich selbst verkettet wurde ( f [mm] \circ [/mm] f ), und bijektivität für die verkettung gegeben war, so argumentiert, dass f einmal die Bedingung surjektivität und einmal injektivität erfüllen muss, und damit bijektiv ist.
Also, dass, wenn f von A nach A abbildet auch eine Verkettung von f mit sich selbst von A nach A abbildet, ist klar. Aber was mir das alles bringt erkenne ich immer noch nicht. Also entweder stehe ich einfach gewaltig auf dem Schlauch, oder aber ich hab irgendetwas grundlegendes nicht verstanden...
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:17 Fr 08.11.2013 | | Autor: | Marcel |
Hallo,
> Also zunächst mal das, was unser Tutor gesagt hat:
>
> Ist die Verkettung zweier Funktionen bijektiv, so gilt,
> dass
> die innere Funktion injektiv sein muss, und die äußere
> surjektiv.
>
> g [mm]\circ[/mm] f
>
> A [mm]\overrightarrow{f}[/mm] B [mm]\overrightarrow{g}[/mm] C
> mit: g muss surjektiv sein, f muss injektiv sein.
naja, aber der Inhalt des Satzes ist dann:
$g [mm] \circ [/mm] f$ bijektiv [mm] $\Longrightarrow$ $f\,$ [/mm] injektiv und [mm] $g\,$ [/mm] surjektiv.
Da steht also eine NOTWENDIGE Bedingung für die Bijektivität (einer solchen
Komposition zweier Abbildungen). Wenn Du also weißt, dass [mm] ($f\,,g$ [/mm] wie oben)
eine Verkettung $g [mm] \circ [/mm] f$ bijektiv ist (Voraussetzung!), dann ist [mm] $f\,$ [/mm] injektiv
und [mm] $g\,$ [/mm] surjektiv.
Du kannst nicht einfach aus [mm] $\Longrightarrow$ [/mm] dabei ein [mm] $\Longleftarrow$ [/mm] machen!
> Deswegen habe ich ja in der Aufgabe, in der f einmal mit
> sich selbst verkettet wurde ( f [mm]\circ[/mm] f ), und
> bijektivität für die verkettung gegeben war, so
> argumentiert, dass f einmal die Bedingung surjektivität
> und einmal injektivität erfüllen muss, und damit bijektiv
> ist.
S.o.: Du kannst nicht einfach aus notwendigen Bedingungen hinreichende
machen. Wenn Du hier jetzt zeigen könntest, dass [mm] $f_{n-1}$ [/mm] nicht injektiv wäre
oder [mm] $f\,$ [/mm] nicht surjektiv, dann dürftest Du folgern, dass $f [mm] \circ f_{n-1}=f_n$ [/mm] nicht
bijektiv wäre. (Kontraposition!)
Aber so bringt Dir der erwähnte Satz einfach gar nichts!
> Also, dass, wenn f von A nach A abbildet auch eine
> Verkettung von f mit sich selbst von A nach A abbildet, ist
> klar. Aber was mir das alles bringt erkenne ich immer noch
> nicht.
Na, damit Du für Funktionen
$f [mm] \colon [/mm] A [mm] \to [/mm] B$ und $g [mm] \colon [/mm] D [mm] \to [/mm] C$
überhaupt
$g [mm] \circ [/mm] f [mm] \colon [/mm] A [mm] \to [/mm] C$
hinschreiben kannst, muss ja $f(A) [mm] \subseteq [/mm] D$ sein. Für [mm] $D=B\,$ [/mm] hat man
das automatisch (wegen $f(A) [mm] \subseteq [/mm] B$). Es geht mir oben aber vor allem um zwei Dinge:
1. Du sollst Dir klarmachen, dass die Funktionen [mm] $f_n$ [/mm] alle "vernünftig definiert" sind.
Hätte ich z.B. $f(x)=x$ als Funktion [mm] $\IR \to \IR$ [/mm] und [mm] $g(x)=\sqrt{x}$ [/mm] als Funktion
[mm] $[0,\infty) \to \IR\,,$ [/mm] so ist $g [mm] \circ f\,,$ [/mm] was man schnell (und fälschlicherweise) naiv als
Funktion [mm] $\IR \to \IR$ [/mm] vielleicht 'erkennen wollen würde', etwas "unvernünftig
definiertes" - denn wie sähe das (formal) aus? Wo ist hier "das Problem"?
2. Und zum anderen geht es mir halt auch darum, dass Du Dir klarmachst,
dass alle [mm] $f_n$ [/mm] den Definitionsbereich [mm] $A\,$ [/mm] und auch den Zielbereich [mm] $A\,$
[/mm]
haben - denn irgendwie geht sowas ja in die entsprechenden Beweisteile
ein. Aber Du solltest die Beweise auch mal durcharbeiten, ansonsten kannst
Du ja nur raten, an welcher Stelle was wie eingeht...
> Also entweder stehe ich einfach gewaltig auf dem
> Schlauch, oder aber ich hab irgendetwas grundlegendes nicht
> verstanden...
Das weiß ich nicht - oben hast Du auf jeden Fall, wie schon vermutet,
eine notwendige mit einer hinreichenden Bedingung verwechselt...
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:16 Do 21.11.2013 | | Autor: | Ymaoh |
Wir haben diese Aufgabe jetzt noch einmal mit unserem Tutor besprochen, und der sagt, dass die Lösung, die ich für den ersten Teil angedacht hatte, stimmt, und auch auf den zweiten angewandt werden kann. Also das die Bedingung:
(f [mm] \circ [/mm] g)(x) ist bijektiv [mm] \Rightarrow [/mm] g(x) ist surjektiv und f(x) ist injektiv.
(Innere Funktion ist injektiv und Äußere surjektiv)
Das heißt für:
(f [mm] \circ [/mm] f)(x) ist bijektiv [mm] \Rightarrow [/mm] f(x) ist surjektiv und f(x) ist injektiv
Und damit ist f(x) bijektiv.
Für die N-fache Verkettung funktioniert das ebenso:
(f [mm] \circ [/mm] f [mm] \circ [/mm] ............ [mm] \circ [/mm] f)(x) ist bijektiv.
Jetzt können wir klammern, und dann gilt:
[mm] (f_{n-1} \circ [/mm] f(x) [mm] \Rightarrow [/mm] f(x) ist surjektiv und [mm] f_{n-1} [/mm] ist injektiv.
( f(x) [mm] \circ f_{n-1}) \Rightarrow f_{n-1} [/mm] ist surjektiv und f(x) ist injektiv.
Damit ist f(x) bijektiv.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:07 Do 21.11.2013 | | Autor: | Marcel |
Hallo,
> Wir haben diese Aufgabe jetzt noch einmal mit unserem Tutor
> besprochen, und der sagt, dass die Lösung, die ich für
> den ersten Teil angedacht hatte, stimmt, und auch auf den
> zweiten angewandt werden kann. Also das die Bedingung:
>
> (f [mm]\circ[/mm] g)(x) ist bijektiv [mm]\Rightarrow[/mm] g(x) ist
> surjektiv und f(x) ist injektiv.
> (Innere Funktion ist injektiv und Äußere surjektiv)
>
> Das heißt für:
>
> (f [mm]\circ[/mm] f)(x) ist bijektiv [mm]\Rightarrow[/mm] f(x) ist
> surjektiv und f(x) ist injektiv
> Und damit ist f(x) bijektiv.
>
>
> Für die N-fache Verkettung funktioniert das ebenso:
>
> (f [mm]\circ[/mm] f [mm]\circ[/mm] ............ [mm]\circ[/mm] f)(x) ist bijektiv.
> Jetzt können wir klammern, und dann gilt:
>
> [mm](f_{n-1} \circ[/mm] f(x) [mm]\Rightarrow[/mm] f(x) ist surjektiv und
> [mm]f_{n-1}[/mm] ist injektiv.
>
> ( f(x) [mm]\circ f_{n-1}) \Rightarrow f_{n-1}[/mm] ist surjektiv
> und f(x) ist injektiv.
>
> Damit ist f(x) bijektiv.
ja, Du hast recht. Ich hatte da was falsch interpretiert und bin wohl auch
manchmal durcheinandergekommen, ob nun [mm] $f\,$ [/mm] oder [mm] $f_n$ [/mm] bijektiv sein soll.
Natürlich ist es trivial, dass, wenn [mm] $f_n=id$ [/mm] ist, dass dann [mm] $f_n$ [/mm] bijektiv ist.
Sorry für die Verwirrung, aber gut, dass Du da am Ball geblieben bist und
es nicht einfach hingenommen hast.
P.S. Ich glaube, Du hättest nur einmal irgendwo schreiben sollen, dass doch
[mm] $f_n$ [/mm] offensichtlich bijektiv sein muss. Dann wäre mir das auch früher
aufgefallen, dass Deine Argumentation in sich stimmig ist. Aber im Endeffekt
ist es mein Fehler. ![[sorry]](/images/smileys/sorry.gif "[sorry]")
Gruß,
Marcel
|
|
|
|
