Funktionen zw. Mengen < Sonstiges < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | 1. Geben Sie ein Beispiel für eine Funktion [mm] \mathbb{N} [/mm] nach [mm] \mathbb{N} [/mm] an, die surjektiv, aber nicht injektiv ist.
2. Gibt es eine Funktion von [mm] \{1,2,3\} [/mm] nach [mm] \{1,2,3\}, [/mm] die injektiv aber nicht surjektiv ist? Geben Sie ein Beispiel an oder begründen Sie kurz, warum es eine solche Funktion nicht gibt. |
$(1.)$ [mm] $f:\mathbb{N}\rightarrow \mathbb{N}$\\
[/mm]
[mm] \begin{equation}
f(x)=
\begin{cases}
1, & \text{wenn } x=1 \\
x-1, & \text{wenn } x\neq 1\\
\end{cases}
\end{equation}
[/mm]
$(2.)$ Es gibt keine Funktion [mm] $f:A\rightarrow [/mm] A$ (mit [mm] $|A|<\infty$ [/mm] ), die injektiv, aber nicht surjektiv [mm] ist.\\
[/mm]
[mm] $x,y\in A$\\
[/mm]
a) Wenn $f$ injektiv ist, dann gibt es für jedes $y$ genau ein $x$ mit [mm] $f(x)=y$.\\
[/mm]
b) Wenn $f$ nicht surjektiv ist, dann gibt es mindestens ein $y$ für das nicht gilt [mm] $f(x)=y$\\
[/mm]
Sei $f$ injektiv und nicht [mm] surjektiv.\\
[/mm]
[mm] $\Leftrightarrow(\forall [/mm] y| [mm] \exists!x:f(x)=y)\wedge (\exists y|f(x)\neq [/mm] y)$
Bei 2 weiß ich nicht weiter. Gibt es vielleicht einen besseren Weg als den ich angefangen habe?
Außerdem: ist es überhaupt wichtig, dass A endlich ist?
Mir ist zwar klar, dass ich auch einfach die 6 Fälle auflisten könnte mit injektiven Funktionen, aber das hilft mir ja später nicht.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 07:26 Fr 28.10.2016 | | Autor: | tobit09 |
Hallo sinnlos123!
> [mm](1.)[/mm] [mm]f:\mathbb{N}\rightarrow \mathbb{N}[/mm][mm] \\[/mm]
>
> [mm] \begin{equation}
f(x)=
\begin{cases}
1, & \text{wenn } x=1 \\
x-1, & \text{wenn } x\neq 1\\
\end{cases}
\end{equation}[/mm]
![[ok]](/images/smileys/ok.gif "[ok]")
> [mm](2.)[/mm] Es gibt keine Funktion [mm]f:A\rightarrow A[/mm] (mit
> [mm]|A|<\infty[/mm] ), die injektiv, aber nicht surjektiv [mm]ist.\\[/mm]
Diese Vermutung stimmt in der Tat für jede endliche Menge A.
> [mm]x,y\in A[/mm][mm] \\[/mm]
> a) Wenn [mm]f[/mm] injektiv ist, dann gibt es für
> jedes [mm]y[/mm] genau ein [mm]x[/mm] mit [mm]f(x)=y[/mm][mm] .\\[/mm]
Nach Definition der Injektivität gibt es für jedes [mm] $y\in [/mm] A$ HÖCHSTENS ein [mm] $x\in [/mm] A$ mit f(x)=y.
> b) Wenn [mm]f[/mm] nicht
> surjektiv ist, dann gibt es mindestens ein [mm]y[/mm] für das nicht
> gilt [mm]f(x)=y[/mm][mm] \\[/mm]
... für das kein [mm] $x\in [/mm] A$ mit $f(x)=y$ existiert.
> Bei 2 weiß ich nicht weiter. Gibt es vielleicht einen
> besseren Weg als den ich angefangen habe?
>
> Außerdem: ist es überhaupt wichtig, dass A endlich ist?
Ja. Denn z.B. [mm] $f\colon\IN\to\IN,\quad [/mm] f(n):=n+1$ ist injektiv, aber nicht surjektiv.
Sei A eine endliche Menge und [mm] $f\colon A\to [/mm] A$ injektiv.
Wir zeigen, dass f dann auch surjektiv ist.
Da A endlich ist, können wir A in der Form [mm] $A=\{a_1,\ldots,a_n\}$ [/mm] für ein [mm] $n\in\IN_0$ [/mm] mit [mm] $a_i\not=a_j$ [/mm] für [mm] $i\not=j$ [/mm] schreiben.
Betrachte nun die Menge [mm] $A':=\{f(a_1),\ldots,f(a_n)\}\subseteq [/mm] A$.
Wie viele verschiedene Elemente enthalten A' und A jeweils?
Viele Grüße
Tobias
|
|
|
| |
|
Hallo Tobias,
Oh man, ok da muss ich wohl noch mehrmals Injektivität und Surjektivität lernen.
Also $A$ hat ja dann n Elemente.
Und nach Definition von "Teilmenge" hat $A'$ höchstens n, aber vielleicht auch weniger Elemente.
Außerdem:
es ist eine Funktion, daher: jedes Element des Definitionsbereiches(d) muss ein Element des Wertebereichs(w) haben, so dass gilt f(d)=w.
Daher kam ich dadrauf, dass für jedes [mm] y\in [/mm] A [mm] \underline{genau} [/mm] ein [mm] x\in [/mm] A mit f(x)=y existiert.
Weil
(mindestens) und (höchstens) [mm] \gdw [/mm] genau
Oder überseh ich hier etwas?
Viele Grüße
Jan
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:49 Fr 28.10.2016 | | Autor: | tobit09 |
> Oh man, ok da muss ich wohl noch mehrmals Injektivität und
> Surjektivität lernen.
>
> Also [mm]A[/mm] hat ja dann n Elemente.
Ja.
> Und nach Definition von "Teilmenge" hat [mm]A'[/mm] höchstens n,
> aber vielleicht auch weniger Elemente.
OK. Es lässt sich aber noch mehr sagen:
Für jede Wahl von [mm] $i,j\in\{1,\ldots,n\}$ [/mm] mit [mm] $i\not=j$ [/mm] gilt [mm] $f(a_i)\not=f(a_j)$. [/mm] (Warum?)
Also enthält [mm] $A'=\{f(a_1),\ldots,f(a_n)\}$ [/mm] genau n verschiedene Elemente (nämlich [mm] $f(a_1),\ldots,f(a_n)$).
[/mm]
Nun ist also $A'$ eine n-elementige Teilmenge der n-elementigen Menge A.
Daher kann nur $A'=A$ gelten.
Insbesondere [mm] $A\subseteq [/mm] A'$.
Warum ist also $f$ surjektiv?
> Außerdem:
> es ist eine Funktion, daher: jedes Element des
> Definitionsbereiches(d) muss ein Element des
> Wertebereichs(w) haben, so dass gilt f(d)=w.
Ja, für alle [mm] $x\in [/mm] A$ existiert ein [mm] $y\in [/mm] A$ mit $f(x)=y$. (*)
> Daher kam ich dadrauf, dass für jedes [mm]y\in[/mm] A
> [mm]\underline{genau}[/mm] ein [mm]x\in[/mm] A mit f(x)=y existiert.
Nein, das kannst du so direkt nicht folgern.
Die Aussage (*) sagt ja nicht, dass für jedes [mm] $y\in [/mm] A$ ein [mm] $x\in [/mm] A$ mit $f(x)=y$ existiert.
Die Aussage "Für jedes [mm] $y\in [/mm] A$ existiert ein [mm] $x\in [/mm] A$ mit f(x)=y." ist gerade die übliche Definition von "f surjektiv".
> Weil (mindestens) und (höchstens) $ [mm] \gdw [/mm] $ genau
Ja. Aber das "mindestens" liegt nur vor, wenn f surjektiv ist.
(Das ist f in unserem Fall zwar, aber das müssen wir erst noch zeigen.)
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:54 Fr 28.10.2016 | | Autor: | tobit09 |
Vielleicht noch mal der Übersicht halber unabhängig von der Aufgabe:
Sei [mm] $f\colon X\to [/mm] Y$ eine beliebige Abbildung.
Dann gelten die Äquivalenzen:
f ist injektiv genau dann, wenn für alle [mm] $y\in [/mm] Y$ HÖCHSTENS ein [mm] $x\in [/mm] X$ mit $f(x)=y$ existiert.
f ist surjektiv genau dann, wenn für alle [mm] $y\in [/mm] Y$ MINDESTENS ein [mm] $x\in [/mm] X$ mit $f(x)=y$ existiert.
f ist also injektiv und surjektiv gleichzeitig (d.h. bijektiv) genau dann, wenn für alle [mm] $y\in [/mm] Y$ GENAU ein [mm] $x\in [/mm] X$ mit $f(x)=y$ existiert.
|
|
|
| |
|
Nur zur Bestätigung:
Also mit Menge [mm] \{1,2\} [/mm] auf [mm] \{1,2\}
[/mm]
wäre
1->2 als einziger Punkt trotzdem eine Abbildung?
Anders gefragt: wenn f nur für manche x einen Wert hat, ist es dann trotzdem eine Abbildung?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 09:12 Fr 28.10.2016 | | Autor: | tobit09 |
> Nur zur Bestätigung:
>
> Also mit Menge [mm]\{1,2\}[/mm] auf [mm]\{1,2\}[/mm]
>
> wäre
>
> 1->2 als einziger Punkt trotzdem eine Abbildung?
Nein.
> Anders gefragt: wenn f nur für manche x einen Wert hat,
> ist es dann trotzdem eine Abbildung?
Nein.
JEDE Abbildung [mm] $f\colon X\to [/mm] Y$ erfüllt die Bedingung
(1) Für jedes [mm] $x\in [/mm] X$ existiert ein [mm] $y\in [/mm] Y$ mit $f(x)=y$.
Nur SURJEKTIVE Abbildungen [mm] $f\colon X\to [/mm] Y$ erfüllen darüber hinaus die Bedingung
(2) Für jedes [mm] $y\in [/mm] Y$ existiert ein [mm] $x\in [/mm] X$ mit $f(x)=y$.
|
|
|
| |
|
Es ist eine injektive Abb., daher:
a) für jedes a im Definitionsbereich existiert ein a_' mit f(a)=a' (Abb.-Def)
b) für jedes a' existiert maximal ein a mit f(a)=a' (injektiv)
Aus a) folgt:
1)wenn n Elemente in A sind, so gibt es genau n verschiedene [mm] a\in [/mm] A.
2)Außerdem, da die Abbildung von A nach A geht, gibt es höchstens n verschiedene [mm] a'\in [/mm] A, da es sonst auch mehr als n verschiedene a gäbe.
Aus b) folgt:
es gibt mindestens n verschiedene [mm] a'\in [/mm] A,
da sonst zu einem a' mehr als ein a existiert mit f(a)=a'
aus a)2) und b) :
(es gibt maximal n verschiedene a') und (es gibt höchstens n verschiedene a')
das bedeutet, es gibt genau n verschiedene a'.
Daraus folgt:
für jedes a' gibt es genau ein a mit f(a)=a' [mm] \rightarrow [/mm] für jedes a' existiert mindestens ein a mit f(a)=a'
Somit ist die Funktion auch surjektiv.
Bis hierhin richtig?
Nun bliebe übrig: Sei [mm] f:A\rightarrow [/mm] A eine nicht injektive Abbildung.
Zu zeigen: Dann ist f auch nicht surjektiv.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:52 Fr 28.10.2016 | | Autor: | tobit09 |
> Es ist eine injektive Abb., daher:
>
> a) für jedes a im Definitionsbereich existiert ein a_' mit
> f(a)=a' (Abb.-Def)
>
> b) für jedes a' existiert maximal ein a mit f(a)=a'
> (injektiv)
Ja.
(Schreibe am besten jeweils explizit dazu, dass du [mm] $a'\in [/mm] A$ und [mm] $a\in [/mm] A$ meinst. Also z.B. bei b): "für jedes [mm] $a'\in [/mm] A$ existiert maximal ein [mm] $a\in [/mm] A$ mit ...")
> Aus a) folgt:
>
> 1)wenn n Elemente in A sind, so gibt es genau n
> verschiedene [mm]a\in[/mm] A.
(Das kannst du kurz so schreiben: Sei n die Anzahl der Elemente von A.)
> 2)Außerdem, da die Abbildung von A nach A geht, gibt es
> höchstens n verschiedene [mm]a'\in[/mm] A, da es sonst auch mehr
> als n verschiedene a gäbe.
Du meinst offenbar etwas anderes als du schreibst:
A hat genau n Elemente, also gibt es natürlich genau n verschiedene [mm] $a'\in [/mm] A$.
Du meinst wohl eher: Es gibt höchstens n verschiedene [mm] $a'\in [/mm] A$ mit der Eigenschaft, dass ein [mm] $a\in [/mm] A$ mit $f(a)=a'$ existiert.
Kurz: [mm] $A':=f(A)=\{a'\in A\;|\;\exists a\in A\colon f(a)=a'\}\subseteq [/mm] A$ enthält höchstens n Elemente.
(Mit $f(A)$ meine ich hier das Bild von A unter f.)
> Aus b) folgt:
>
> es gibt mindestens n verschiedene [mm]a'\in[/mm] A,
Wieder meinst du etwas anderes: A'=f(A) enthält mindestens n Elemente.
> da sonst zu einem a' mehr als ein a existiert mit f(a)=a'
Mit dieser Begründung kann ich persönlich nicht so viel anfangen. Aber möglicherweise meinst du es korrekt.
> aus a)2) und b) :
>
> (es gibt maximal n verschiedene a') und (es gibt höchstens
> n verschiedene a')
>
> das bedeutet, es gibt genau n verschiedene a'.
... [mm] $a'\in [/mm] A'$.
Jetzt kommt der Clou: Daher muss $A'$ als n-elementige Teilmenge von A schon mit ganz A übereinstimmen, d.h. es gilt $A'=A$.
> Daraus folgt:
>
> für jedes a' gibt es genau ein a mit f(a)=a' [mm]\rightarrow[/mm]
> für jedes a' existiert mindestens ein a mit f(a)=a'
>
> Somit ist die Funktion auch surjektiv.
Wir wussten nach Definition von A' schon von Anfang an: Für jedes [mm] $a'\in [/mm] A'$ existiert mindestens ein [mm] $a\in [/mm] A$ mit $f(a)=a'$.
Die neue Erkenntnis aus $A'=A$ ist nun: Für alle [mm] $a'\in [/mm] A$ (!) existiert mindestens ein [mm] $a\in [/mm] A$ mit $f(a)=a'$, d.h. f ist surjektiv.
> Bis hierhin richtig?
Durch die fehlenden Angaben, wann du [mm] $a'\in [/mm] A'$ und wann du [mm] $a'\in [/mm] A$ betrachten möchtest, bin ich mir nicht sicher, ob dir die Argumentation klar ist.
Möglicherweise ja, möglicherweise nein.
Ich möchte dir einmal präsentieren, wie ich den Beweis formulieren würde:
Sei A eine endliche Menge und [mm] $f\colon A\to [/mm] A$ injektiv.
Da A endlich ist, hat A die Gestalt [mm] $A=\{a_1,\ldots,a_n\}$ [/mm] für gewisse [mm] $a_1,\ldots,a_n$ [/mm] mit [mm] $a_i\not=a_j$ [/mm] für alle [mm] $i,j\in\{1,\ldots,n\}$ [/mm] mit [mm] $i\not=j$.
[/mm]
Sei [mm] $A':=\{f(a_1),\ldots,f(a_n)\}$.
[/mm]
Wir behaupten [mm] $f(a_i)\not=f(a_j)$ [/mm] für alle [mm] $i,j\in\{1,\ldots,n\}$ [/mm] mit [mm] $i\not=j$.
[/mm]
Beweis dieser Behauptung:
Seien [mm] $i,j\in\{1,\ldots,n\}$ [/mm] mit [mm] $i\not=j$. [/mm] Dann gilt [mm] $a_i\not=a_j$. [/mm] Da $f$ injektiv ist, folgt wie gewünscht [mm] $f(a_i)\not=f(a_j)$.
[/mm]
A' ist also eine n-elementige Teilmenge der n-elementigen Menge A.
Daher gilt $A'=A$.
Zum Nachweis der Surjektivität von f sei [mm] $y\in [/mm] A$.
Gesucht ist ein [mm] $x\in [/mm] A$ mit $f(x)=y$.
Wegen [mm] $y\in [/mm] A=A'$ existiert ein [mm] $i\in\{1,\ldots,n\}$ [/mm] mit [mm] $y=f(a_i)$.
[/mm]
Daher leistet [mm] $x:=a_i$ [/mm] das Gewünschte.
> Nun bliebe übrig: Sei [mm]f:A\rightarrow[/mm] A eine nicht
> injektive Abbildung.
> Zu zeigen: Dann ist f auch nicht surjektiv.
Unsere ursprüngliche Behauptung ( $f: [mm] A\to [/mm] A$ injektiv für endliches A impliziert f surjektiv) ist fertig gezeigt.
Was du jetzt offenbar zeigen möchtest, ist eine neue Behauptung.
Auch diese Behauptung stimmt.
Ihr Nachweis ist sicherlich eine gute Übung.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:59 Fr 28.10.2016 | | Autor: | sinnlos123 |
Vielen Dank für deine ausführliche Antwort,
ich brauche etwas Zeit um sie zu verstehen.
Ich schreibe nachdem ich es nachvollzogen habe es mal mit meinen Worten.
Du hast recht, für die Aufgabe ist es tatsächlich genügend nur die eine Richtung zu zeigen.
Für spätere Aufgaben ist denke ich die Äquivalenz jedoch sehr nützlich.
Insgesamt jedoch: ich finde ich habe mindestens einen erheblichen Denkfehler, darausfolgt dann offensichtlich beliebiges.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:22 Fr 28.10.2016 | | Autor: | tobit09 |
> Insgesamt jedoch: ich finde ich habe mindestens einen
> erheblichen Denkfehler, darausfolgt dann offensichtlich
> beliebiges.
Möchtest du versuchen zu schildern, wo das Problem liegt?
Oder möchtest du erst einmal selbst auf Fehlersuche gehen?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:51 Fr 28.10.2016 | | Autor: | sinnlos123 |
"(es gibt maximal n verschiedene a') und (es gibt höchstens n verschiedene a') "
ist ein und das selbe, ich habe allerdings, warum auch immer höchstens UND mindestens hier gelesen.
Dadrauf beruht meine Folgerung, dass f surjektiv ist, was offensichtlich Quatsch ist.
Wie gesagt, ich guck mir das nochmal genau an :)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:54 Fr 28.10.2016 | | Autor: | tobit09 |
> "(es gibt maximal n verschiedene a') und (es gibt
> höchstens n verschiedene a') "
Du hast dich hier nur verschrieben. Tatsächlich hattest du "höchstens" und "mindestens" überlegt.
|
|
|
| |
|
Guten Mittag Tobias,
Sei A eine endliche Menge und eine Abbildung [mm] f:A\rightarrow [/mm] A nicht injektiv.
Da A endlich ist, hat A die gestalt [mm] A=\{a_1,...,a_n\} [/mm] für gewisse [mm] a_1,...,a_n [/mm] mit [mm] a_i\noteq a_j [/mm] für alle [mm] i,j\{1,...,n\} [/mm] mit [mm] i\noteq [/mm] j.
Sei [mm] A':=\{f(a_1),...,f(a_n)\}.
[/mm]
Wir behaupten, dass [mm] f(a_i)=f(a_j) [/mm] für gewisse [mm] i,j\in\{1,...,n\} [/mm] mit [mm] i\noteq [/mm] j. (ist das überhaupt zu zeigen? folgt doch aus der Def)
Beweis dieser Behauptung:
Seien [mm] i,j\in\{1,...,n\} [/mm] mit [mm] i\noteq [/mm] j. Dann gilt [mm] a_i\noteq a_j. [/mm] Da f nicht injektiv ist, folgt wie gewünscht [mm] f(a_i)=f(a_j) [/mm] für gewisse i,j.
A' ist also eine m-elementige echte Teilmenge der n-elementigen Menge A, wobei insbesondere m<n gilt.
Oder anders: in A' sind weniger Elemente als in A aufgrund der Tatsache, dass f manchen [mm] a,b\in [/mm] A das gleiche [mm] c\in [/mm] A' zuordnet.
Zum Nachweis, dass f nicht surjektiv sein kann sei [mm] y\notin A'\wedge y\in [/mm] A. Das ein solches y existiert ist Tatsache.(wirkt irgendwie doof "sei" und "Tatsache")
Surjektivität erfordert aber, dass zu jedem [mm] y\in [/mm] A (Zielmenge) es mindestens ein [mm] x\in [/mm] A gibt mit f(x)=y, oder anders ausgedrückt:
|A'| müsste gleich |A| sein. (stimmt dies?)
Wie aber schon gezeigt, ist dadurch dass f nicht injektiv ist |A'|<|A|.
Da es sich um endliche Mengen handelt, gilt dies.
Somit ist f auch nicht surjektiv.
Ich möchte das ohne das mir bekannte Pidgeon hole Prinzip zeigen (oder Variationen davon).
Siehst du hier Fehler?
Viele Grüße
Jan
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:12 Sa 29.10.2016 | | Autor: | tobit09 |
> Sei A eine endliche Menge und eine Abbildung [mm]f:A\rightarrow[/mm]
> A nicht injektiv.
>
> Da A endlich ist, hat A die gestalt [mm]A=\{a_1,...,a_n\}[/mm] für
> gewisse [mm]a_1,...,a_n[/mm] mit [mm]a_i\noteq a_j[/mm] für alle
> [mm]i,j\{1,...,n\}[/mm] mit [mm]i\noteq[/mm] j.
>
> Sei [mm]A':=\{f(a_1),...,f(a_n)\}.[/mm]
> Wir behaupten, dass [mm]f(a_i)=f(a_j)[/mm] für gewisse
> [mm]i,j\in\{1,...,n\}[/mm] mit [mm]i\noteq[/mm] j. (ist das überhaupt zu
> zeigen? folgt doch aus der Def)
Ja, das folgt aus der Definition von Injektivität und der Gestalt von A:
Da f nicht injektiv ist, existieren [mm] $c,d\in [/mm] A$ mit [mm] $c\not=d$, [/mm] aber $f(c)=f(d)$.
Wegen [mm] $c,d\in A=\{a_1,\ldots,a_n\}$ [/mm] existieren [mm] $i,j\in\{1,\ldots,n\}$ [/mm] mit [mm] $c=a_i$ [/mm] und [mm] $d=a_j$. [/mm] Wegen [mm] $c\not=d$ [/mm] ist auch [mm] $i\not=j$.
[/mm]
Es gilt [mm] $f(a_i)=f(c)=f(d)=f(a_j)$.
[/mm]
> Beweis dieser Behauptung:
> Seien [mm]i,j\in\{1,...,n\}[/mm] mit [mm]i\noteq[/mm] j. Dann gilt [mm]a_i\noteq a_j.[/mm]
(Das benötigst du hier gar nicht.)
> Da f nicht injektiv ist, folgt wie gewünscht [mm]f(a_i)=f(a_j)[/mm]
> für gewisse i,j.
...mit [mm] $i\not=j$.
[/mm]
Sei m die Anzahl der Elementen von A'.
> A' ist also eine m-elementige echte Teilmenge der
> n-elementigen Menge A, wobei insbesondere m<n gilt.
> Oder anders: in A' sind weniger Elemente als in A aufgrund
> der Tatsache, dass f manchen [mm]a,b\in[/mm] A das gleiche [mm]c\in[/mm] A'
> zuordnet.
Ja.
Sollte man formaler argumentieren wollen: Die $n-1$ vielen Elemente [mm] $f(a_1),\ldots,f(a_{j-1}),f(a_{j+1}),\ldots,f(a_n)$ [/mm] sind (wegen [mm] $f(a_j)=f(a_i)$ [/mm] und [mm] $i\not=j$) [/mm] bereits sämtliche Elemente von A'. Damit hat A' höchstens n-1 und damit weniger als n Elemente.
> Zum Nachweis, dass f nicht surjektiv sein kann sei [mm]y\notin A'\wedge y\in[/mm]
> A. Das ein solches y existiert ist Tatsache.(wirkt
> irgendwie doof "sei" und "Tatsache")
Genau das gilt es zu begründen! Das Argument ist nach deiner Vorarbeit aber einfach:
Da A' eine echte Teilmenge von A ist, existiert ein [mm] $y\in [/mm] A$ mit [mm] $y\notin [/mm] A'$.
Nun kommst du schnell zum Ziel:
Es genügt zu zeigen, dass kein [mm] $x\in [/mm] A$ mit $f(x)=y$ existiert.
(Dies folgt im Wesentlichen aus [mm] $y\notin [/mm] A'$. Im Einzelnen:)
Angenommen es gibt doch ein [mm] $x\in [/mm] A$ mit $f(x)=y$.
Dann hätte x wegen [mm] $x\in A=\{a_1,\ldots,a_n\}$ [/mm] die Gestalt [mm] $x=a_k$ [/mm] für ein [mm] $k\in\{1,\ldots,n\}$.
[/mm]
Damit wäre [mm] $y=f(x)=f(a_k)\in [/mm] A'$ im Widerspruch zur Wahl von y.
> Surjektivität erfordert aber, dass zu jedem [mm]y\in[/mm] A
> (Zielmenge) es mindestens ein [mm]x\in[/mm] A gibt mit f(x)=y, oder
> anders ausgedrückt:
> |A'| müsste gleich |A| sein. (stimmt dies?)
Surjektivität von f ist äquivalent zu $A'=A$, wie man sich überlegen kann. Insbesondere würde, wenn f surjektiv wäre, also in der Tat $|A'|=|A|$ gelten.
Ich würde genauer begründen, warum im Falle $f$ surjektiv bereits $A'=A$ gelten müsste:
Angenommen f surjektiv. Zu zeigen ist $A'=A$.
[mm] $A'\subseteq [/mm] A$ gilt nach Definition von A'.
Zum Nachweis von [mm] $A'\supseteq [/mm] A$ sei [mm] $y\in [/mm] A$. Zu zeigen ist [mm] $y\in [/mm] A'$.
Da f als surjektiv angenommen wurde, gibt es ein [mm] $x\in [/mm] A$ mit $f(x)=y$.
Insbesondere [mm] $y=f(x)\in [/mm] A'$.
> Wie aber schon gezeigt, ist dadurch dass f nicht injektiv
> ist |A'|<|A|.
Ja.
> Da es sich um endliche Mengen handelt, gilt dies.
(Das brauchst du nicht erneut zu begründen.)
> Somit ist f auch nicht surjektiv.
Ja.
> Ich möchte das ohne das mir bekannte Pidgeon hole Prinzip
> zeigen (oder Variationen davon).
Natürlich haben wir einiges Verständnis über natürliche Zahlen bzw. endliche Mengen genutzt, das im Rahmen einer solchen Aufgabe wohl vorausgesetzt werden darf.
Das Schubfachprinzip haben wir nirgendwo direkt angewendet.
> Siehst du hier Fehler?
Nein.
Ich denke, du hast die Zusammenhänge verstanden.
Ein paar Stellen, an denen sich die Notation des Beweises optimieren lässt, habe ich dir ja genannt.
|
|
|
| |
|
Hi, gut, ich denke ich muss dann nur noch weniger Tipfehler machen und etwas mehr Horizont haben als 3 Aussagen aufeinmal hehe.
Ich habe einen kürzeren Beweis gefunden, allerdings verstehe ich ihn nicht ganz:
Sei $A$ eine endliche Menge und $f: [mm] A\to [/mm] A$ eine beliebige Abbildung.
Für jedes [mm] $a\in [/mm] A$, sei $N(a)$ die Anzahl von Elementen in $A$ die abgebildet sind auf $a$.
Dann [mm] $\sum_a [/mm] N(a) = n = |A|$ weil jedes Element von $A$ auf irgendein Element von $A$ abgebildet ist.
Wenn $f$ surjektiv ist, dann [mm] $N(a)\ge [/mm] 1$ für alle $a$.
Wenn $f$ nicht injektiv ist, dann [mm] $N(a_0)>1$ [/mm] für mindestens ein [mm] $a_0$. [/mm]
Aber dann [mm] $\sum_a [/mm] N(a) > n$, was ein Widerspruch ist.
Wenn $f$ injektiv ist, dann [mm] $N(a)\le [/mm] 1$ für alle $a$.
Wenn $f$ nicht surjektiv ist, dann [mm] $N(a_0)<1$ [/mm] für mindestens ein [mm] $a_0$. [/mm]
Aber dann [mm] $\sum_a [/mm] N(a) < n$, was ein Widerspruch ist.
Somit gilt für endliche Mengen:
$f: [mm] A\to [/mm] A$ ist injektiv [mm] $\Leftrightarrow$ [/mm] $f: [mm] A\to [/mm] A$ ist surjektiv
Somit gibt es keine Funktion $f: [mm] \{1,2,3\}\to \{1,2,3\}$, [/mm] die injektiv, aber nicht surjektiv ist.
(dieser Beweis scheint einwandfrei zu sein, da hoch bewertet und auf Math stack exchange)
___________________________________
was ich nicht verstehe :
er benutzt [mm] a_0, [/mm] aber sagt nicht wozu es gehört.
er benutzt eine Summenformel ohne einen Indize, wäre [mm] $\sum_{a_i} N(a_i) [/mm] und dann noch i definieren, nicht "korrekter"? (die Summe an sich verstehe ich)
Die Folgerungen aus injektiv und surjektiv müssten glaube ich erst gezeigt werden bzw vorrausgesetzt sein oder?
(der originale Beweis ist in englisch, daher etwaige merkwürdige Formulierungen)
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:49 Sa 29.10.2016 | | Autor: | tobit09 |
> Ich habe einen kürzeren Beweis gefunden, allerdings
> verstehe ich ihn nicht ganz:
>
> Sei [mm]A[/mm] eine endliche Menge und [mm]f: A\to A[/mm] eine beliebige
> Abbildung.
> Für jedes [mm]a\in A[/mm], sei [mm]N(a)[/mm] die Anzahl von Elementen in [mm]A[/mm]
> die abgebildet sind auf [mm]a[/mm].
> Dann [mm]\sum_a N(a) = n = |A|[/mm] weil jedes Element von [mm]A[/mm] auf
> irgendein Element von [mm]A[/mm] abgebildet ist.
> Wenn [mm]f[/mm] surjektiv ist, dann [mm]N(a)\ge 1[/mm] für alle [mm]a[/mm].
> Wenn [mm]f[/mm] nicht injektiv ist, dann [mm]N(a_0)>1[/mm] für mindestens
> ein [mm]a_0[/mm].
> Aber dann [mm]\sum_a N(a) > n[/mm], was ein Widerspruch ist.
> Wenn [mm]f[/mm] injektiv ist, dann [mm]N(a)\le 1[/mm] für alle [mm]a[/mm].
> Wenn [mm]f[/mm] nicht surjektiv ist, dann [mm]N(a_0)<1[/mm] für mindestens
> ein [mm]a_0[/mm].
> Aber dann [mm]\sum_a N(a) < n[/mm], was ein Widerspruch ist.
> Somit gilt für endliche Mengen:
> [mm]f: A\to A[/mm] ist injektiv [mm]\Leftrightarrow[/mm] [mm]f: A\to A[/mm] ist
> surjektiv
> Somit gibt es keine Funktion [mm]f: \{1,2,3\}\to \{1,2,3\}[/mm],
> die injektiv, aber nicht surjektiv ist.
>
> (dieser Beweis scheint einwandfrei zu sein, da hoch
> bewertet und auf Math stack exchange)
Seine Idee gefällt mir sehr gut, seine Notation nicht zu 100 Prozent.
> was ich nicht verstehe :
>
> er benutzt [mm]a_0,[/mm] aber sagt nicht wozu es gehört.
Da meinte der Autor, es sei aus dem Kontext klar.
Gemeint ist [mm] $a_0\in [/mm] A$.
> er benutzt eine Summenformel ohne einen Indize, wäre
> [mm]$\sum_{a_i} N(a_i)[/mm] und dann noch i definieren, nicht
> "korrekter"? (die Summe an sich verstehe ich)
Korrekt wäre [mm] $\sum_{a\in A}$ [/mm] statt [mm] $\sum_{a}$.
[/mm]
Letzteres wird manchmal als Kurzschreibweise für ersteres verwendet, wenn man für aus dem Kontext verständlich hält, über was für a summiert werden soll.
> Die Folgerungen aus injektiv und surjektiv müssten glaube
> ich erst gezeigt werden bzw vorrausgesetzt sein oder?
Das kommt darauf an, wie detailliert man den Beweis führen möchte.
Es gelten folgende Äquivalenzen:
f ist injektiv [mm] $\iff$ [/mm] für alle [mm] $a\in [/mm] A$ gibt es höchstens ein [mm] $b\in [/mm] A$ mit $f(b)=a$ [mm] $\iff$ [/mm] für alle [mm] $a\in [/mm] A$ ist [mm] $N(a)\le [/mm] 1$.
f ist surjektiv [mm] $\iff$ [/mm] für alle [mm] $a\in [/mm] A$ gibt es mindestens ein [mm] $b\in [/mm] A$ mit $f(b)=a$ [mm] $\iff$ [/mm] für alle [mm] $a\in [/mm] A$ ist [mm] $N(a)\ge [/mm] 1$.
|
|
|
| |
|
Dieser Beweis lässt sich ja leicht auf endliche Mengen A, B mit |A|=|B| erweitern.
Beziehungsweise anders ausgedrückt:
Wenn A durch B ausdrückbar ist UND B durch A ausdrückbar ist,
dann ist [mm] A\equiv [/mm] B. (richtig?)
(ich denke da jetzt an das Alphabet und die Zahlen 1 bis 27)
Also müsste man all dies eigentlich nicht nochmal für [mm] A\not= [/mm] B zeigen oder?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:18 Sa 29.10.2016 | | Autor: | tobit09 |
> Dieser Beweis lässt sich ja leicht auf endliche Mengen A,
> B mit |A|=|B| erweitern.
Ja, sowohl unserer als auch der von dir zitierte funktionieren analog auch in diesem allgemeineren Fall.
> Beziehungsweise anders ausgedrückt:
>
> Wenn A durch B ausdrückbar ist UND B durch A ausdrückbar
> ist,
Was meinst du mit "ausdrückbar"?
> dann ist [mm]A\equiv[/mm] B. (richtig?)
Was bedeutet [mm] $\equiv$ [/mm] hier?
> (ich denke da jetzt an das Alphabet und die Zahlen 1 bis
> 27)
1 bis 26?
Wenn A und B endliche Mengen sind, gilt $|A|=|B|$ genau dann, wenn eine bijektive Abbildung [mm] $f:A\to [/mm] B$ existiert.
> Also müsste man all dies eigentlich nicht nochmal für
> [mm]A\not=[/mm] B zeigen oder?
Geschmacksfrage. Für mich genügt es zu wissen, dass die Beweise analog im allgemeineren Fall funktionieren.
Man kann auch den allgemeineren Fall auf den speziellen Fall zurückführen.
Je nachdem, was man dabei nicht als bekannt voraussetzt, dürfte dies jedoch recht umständlich werden.
|
|
|
|
