Induktion, Mächtigeit, endl.TM < Sonstiges < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Eine Menge M heißt endlich, mit 'Mächtigkeit' |M|=n, falls es eine bijektive Abbildung [mm] f:M\to\{1,...,n\} [/mm] gibt. Die leere Menge [mm] \emptyset [/mm] sei per Definition endlich, mit Mächtigkeit [mm] |\emptyset|=0. [/mm] Beweise durch vollständige Induktion über n:=|M|:
a) Ist M eine endliche Menge , dann ist jede Teilmenge A [mm] \subset [/mm] M endlich mit [mm] |A|\le|M|.
[/mm]
b) Ist [mm] g:M\to [/mm] N eine surjektive Abbildung und M endlich, so ist auch N endlich, mit [mm] |N|\le|M|. [/mm] |
Hallo ihr Lieben :)
Ich habe diese Aufgabe in der Uni aufbekommen und bin dabei total am verzweifeln ...
Ich habe mir schon einiges im Internet zusammengesucht, aber was ich da mache macht für mich einfach keinen Sinn. Mein Lösungsvorschlag war dieser:
IA:
[mm] M=\{1,2,3...n\} [/mm] , |M|:=n
[mm] A=\{1,2,3...n\} [/mm] , [mm] |A|\le|M|
[/mm]
IV:
n [mm] \to [/mm] n+1
[mm] M=\{1,2,3..n,n+1\} [/mm] , |M|:=n+1
[mm] A=\{1,2,3..n,n+1\} [/mm] , |A|:=n+1
IS:
Sei M [mm] \{1,2,3...n,n+1\} \wedge [/mm] A [mm] \subset\{1,2,3...n,n+1\} [/mm]
[mm] \Rightarrow [/mm] n+1 [mm] \in [/mm] A [mm] \vee [/mm] n+1 [mm] \not\in [/mm] A
Fall 1:
n+1 [mm] \not\in [/mm] A : |A| von M = [mm] \{1,2,3...n,n+1\} [/mm] \ {n+1}
[mm] \Rightarrow M=\{1,2,3...n} [/mm] = [mm] |A|\le|M|
[/mm]
Fall 2:
n+1 [mm] \in [/mm] A : [mm] \cup \{n+1\} \wedge [/mm] A [mm] \subset \{1,2,3...n\} [/mm]
=A [mm] \neg\subset \{1,2,3...n,n+1\} [/mm] = [mm] |A|\le|M|
[/mm]
b)
IA: [mm] g:M\to [/mm] N surj, |M| = endlich , [mm] |N|\le|M|
[/mm]
IV: n=1 (richtig, da M nur ein Element hat)
IS:
Sei |M|=n+1 [mm] \wedge [/mm] |N|=n+1 und [mm] g:M\to [/mm] N surj.
Annahme: [mm] g\not= [/mm] inj. [mm] \Rightarrow b\in [/mm] M|g(m) [mm] \not= b\forall [/mm] m [mm] \in [/mm] M
und [mm] a\in [/mm] N|g(n) [mm] \not= a\forall n\in [/mm] N [mm] \Rightarrow [/mm] Z=M\ [mm] \{b\}
[/mm]
[mm] \wedge [/mm] X=N \ [mm] \{a\} \wedge g_N:M\to [/mm] N surj.
Wegen g(b) [mm] \not= [/mm] b [mm] \Rightarrow g(b)\in [/mm] N, also gibt es wegen der Surjektivität von [mm] g_N [/mm] ein Element [mm] n\in [/mm] N mit g(n) = g(b), aber n [mm] \not [/mm] b.
Somit ist N bewiesen und auch das |N| [mm] \le [/mm] |M|ist.
Ich bin um jede Antwort sehr sehr dankbar und hoffe ihr könnt mir helfen!!
Lieben Gruß
Katti
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt
|
|
| |
|
> Eine Menge M heißt endlich, mit 'Mächtigkeit' |M|=n,
> falls es eine bijektive Abbildung [mm]f:M\to\{1,...,n\}[/mm] gibt.
> Die leere Menge [mm]\emptyset[/mm] sei per Definition endlich, mit
> Mächtigkeit [mm]|\emptyset|=0.[/mm] Beweise durch vollständige
> Induktion über n:=|M|:
>
> a) Ist M eine endliche Menge , dann ist jede Teilmenge A
> [mm]\subset[/mm] M endlich mit [mm]|A|\le|M|.[/mm]
Hallo,
![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]") .
Zunächst sollten wir den Ablauf einer vollständigen Induktion klären, mir scheint nämlich, Du hast ihn noch nicht richtig verstanden.
Induktion:
Beh.
Eine Aussage gilt für alle [mm] n\in \IN.
[/mm]
Induktionsanfang
Man zeigt, daß die Aussage für n=1 gilt
Induktionsvoraussetzung
Man nimmt an, daß die Aussage für ein festes [mm] n\in\IN [/mm] gilt.
(Hier ist nichts zu zeigen, tun oder denken. Man schreibt einfach hin:
"Die Aussage gelte für ein [mm] n\in \IN)
[/mm]
Induktionsschluß
Hier wird dann gezeigt, daß die Aussage unter der gemachten Voraussetzung auch für n+1 stimmt.
Nun wenden wir uns Deiner Aufgabe a) zu und schauen erstmal den Ablauf der durchzuführenden Induktion an.
Induktion:
Beh.
Für alle [mm] n\in \IN [/mm] gilt:
Ist M endlich mit |M|=n,
dann ist jede Teilmenge [mm] A\subseteq [/mm] M endlich mit
[mm] |A|\le [/mm] |M|.
Induktionsanfang
Sei M eine Menge mit |M|=1
Zeige nun, daß jede Teilmenge dieser Menge endlich ist.
Induktionsvoraussetzung
Für ein festes [mm] n\in \IN [/mm] gelte:
Ist M endlich mit |M|=n,
dann ist jede Teilmenge [mm] A\subseteq [/mm] M endlich mit
[mm] |A|\le [/mm] |M|
Induktionsschluß
Sei nun M eine Menge mit |M|=n+1.
[Nun mußt Du vormachen, daß jede Teilmenge
endlich ist und höchstens die Mächtigkeit n+1 hat.]
Dann gibt es eine Bijektion
f: [mm] M\to \{1,2,3,...,n,n+1\}.
[/mm]
Sei nun [mm] A\subseteq [/mm] M.
1. Fall:
[mm] A=\emptyset. [/mm] Dann...
2. Fall:
A=M. Dann...
3. Fall:
[mm] A\not=\emptyset [/mm] und [mm] A\not=M.
[/mm]
Dann gibt es ein Element [mm] m\in [/mm] M, welches nicht in A ist.
Sei [mm] M':=M\setminus \{m\}.
[/mm]
Es ist [mm] A\subseteq [/mm] M'.
Zeige nun, daß M' endlich ist mit Mächtigkeitkeit n,
indem Du eine passende Bijektion auf [mm] \{1,2,3,...,n\} [/mm] angibst.
Natürlich baust Du Dir hierfür die Bijektion f etwas um.
Wenn Dir das gelungen ist, weißt Du, daß A Teilmenge einer n-elementigen Menge ist,
und mit der Induktionsvoraussetzung hast Du die Behauptung.
Ich würde vorschlagen, daß wir b) erstmal zurückstellen, bis a) geklärt ist.
Vielleicht schaffst Du dann sogar b) allein.
LG Angela
>
> b) Ist [mm]g:M\to[/mm] N eine surjektive Abbildung und M endlich, so
> ist auch N endlich, mit [mm]|N|\le|M|.[/mm]
> Hallo ihr Lieben :)
>
> Ich habe diese Aufgabe in der Uni aufbekommen und bin dabei
> total am verzweifeln ...
> Ich habe mir schon einiges im Internet zusammengesucht,
> aber was ich da mache macht für mich einfach keinen Sinn.
> Mein Lösungsvorschlag war dieser:
>
> IA:
> [mm]M=\{1,2,3...n\}[/mm] , |M|:=n
> [mm]A=\{1,2,3...n\}[/mm] , [mm]|A|\le|M|[/mm]
>
> IV:
>
> n [mm]\to[/mm] n+1
> [mm]M=\{1,2,3..n,n+1\}[/mm] , |M|:=n+1
> [mm]A=\{1,2,3..n,n+1\}[/mm] , |A|:=n+1
>
> IS:
>
> Sei M [mm]\{1,2,3...n,n+1\} \wedge[/mm] A [mm]\subset\{1,2,3...n,n+1\}[/mm]
> [mm]\Rightarrow[/mm] n+1 [mm]\in[/mm] A [mm]\vee[/mm] n+1 [mm]\not\in[/mm] A
>
> Fall 1:
>
> n+1 [mm]\not\in[/mm] A : |A| von M = [mm]\{1,2,3...n,n+1\}[/mm] \ {n+1}
> [mm]\Rightarrow M=\{1,2,3...n}[/mm] = [mm]|A|\le|M|[/mm]
>
> Fall 2:
>
> n+1 [mm]\in[/mm] A : [mm]\cup \{n+1\} \wedge[/mm] A [mm]\subset \{1,2,3...n\}[/mm]
> =A [mm]\neg\subset \{1,2,3...n,n+1\}[/mm] = [mm]|A|\le|M|[/mm]
>
> b)
>
> IA: [mm]g:M\to[/mm] N surj, |M| = endlich , [mm]|N|\le|M|[/mm]
>
> IV: n=1 (richtig, da M nur ein Element hat)
>
> IS:
>
> Sei |M|=n+1 [mm]\wedge[/mm] |N|=n+1 und [mm]g:M\to[/mm] N surj.
> Annahme: [mm]g\not=[/mm] inj. [mm]\Rightarrow b\in[/mm] M|g(m) [mm]\not= b\forall[/mm]
> m [mm]\in[/mm] M
> und [mm]a\in[/mm] N|g(n) [mm]\not= a\forall n\in[/mm] N [mm]\Rightarrow[/mm] [mm] Z=M\
[/mm]
> [mm]\{b\}[/mm]
> [mm]\wedge[/mm] X=N \ [mm]\{a\} \wedge g_N:M\to[/mm] N surj.
> Wegen g(b) [mm]\not=[/mm] b [mm]\Rightarrow g(b)\in[/mm] N, also gibt es
> wegen der Surjektivität von [mm]g_N[/mm] ein Element [mm]n\in[/mm] N mit
> g(n) = g(b), aber n [mm]\not[/mm] b.
> Somit ist N bewiesen und auch das |N| [mm]\le[/mm] |M|ist.
>
> Ich bin um jede Antwort sehr sehr dankbar und hoffe ihr
> könnt mir helfen!!
>
> Lieben Gruß
>
> Katti
>
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:47 So 26.10.2014 | | Autor: | tobit09 |
Hallo Angela!
(Wie eigentlich immer bei dir:) Eine sehr gute Antwort! ![[ok]](/images/smileys/ok.gif "[ok]")
Nur zwei kleine Anmerkungen:
> > Eine Menge M heißt endlich, mit 'Mächtigkeit' |M|=n,
> > falls es eine bijektive Abbildung [mm]f:M\to\{1,...,n\}[/mm]
> gibt.
> > Die leere Menge [mm]\emptyset[/mm] sei per Definition endlich,
> mit
> > Mächtigkeit [mm]|\emptyset|=0.[/mm] Beweise durch vollständige
> > Induktion über n:=|M|:
> >
> > a) Ist M eine endliche Menge , dann ist jede Teilmenge
> A
> > [mm]\subset[/mm] M endlich mit [mm]|A|\le|M|.[/mm]
> Beh.
> Für alle [mm]n\in \IN[/mm] gilt:
> Ist M endlich mit |M|=n,
> dann ist jede Teilmenge [mm]A\subseteq[/mm] M endlich mit
> [mm]|A|\le[/mm] |M|.
Hier muss mit [mm] $\IN$ [/mm] die Menge aller natürlichen Zahlen einschließlich der 0 gemeint sein.
> Induktionsanfang
> Sei M eine Menge mit |M|=1
> Zeige nun, daß jede Teilmenge dieser Menge endlich ist.
Im Induktionsanfang muss es also |M|=0 statt |M|=1 heißen.
> Induktionsvoraussetzung
> Für ein festes [mm]n\in \IN[/mm] gelte:
> Ist M endlich mit |M|=n,
> dann ist jede Teilmenge [mm]A\subseteq[/mm] M endlich mit
> [mm]|A|\le[/mm] |M|
>
> Induktionsschluß
> Sei nun M eine Menge mit |M|=n+1.
> [Nun mußt Du vormachen, daß jede Teilmenge
> endlich ist und höchstens die Mächtigkeit n+1
> hat.]
> Dann gibt es eine Bijektion
> f: [mm]M\to \{1,2,3,...,n,n+1\}.[/mm]
>
> Sei nun [mm]A\subseteq[/mm] M.
>
> 1. Fall:
> [mm]A=\emptyset.[/mm] Dann...
>
> 2. Fall:
> A=M. Dann...
>
> 3. Fall:
> [mm]A\not=\emptyset[/mm] und [mm]A\not=M.[/mm]
> Dann gibt es ein Element [mm]m\in[/mm] M, welches nicht in A ist.
(Die Unterscheidung zwischen [mm] $A=\emptyset$ [/mm] und [mm] $A\not=\emptyset$ [/mm] erscheint mir (im Gegensatz zur Unterscheidung zwischen $A=M$ und [mm] $A\not=M$) [/mm] überflüssig. Aber sie schadet ja auch nicht und vielleicht steckte ja sogar eine didaktische Idee dahinter?)
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:01 So 26.10.2014 | | Autor: | tobit09 |
Hallo Katti1712 und auch von mir ein herzliches !
Neben Angelas Feststellung, dass dir offenbar der Ablauf der Induktion noch nicht vertraut ist, ist mir noch Folgendes aufgefallen:
Du verwendest in deinen Versuchen die Definition der Endlichkeit und Mächtigkeit nirgendwo.
Daher schlage ich noch folgende kleine Vorübung zum Verständnis dieser Begriffe vor:
Bestimme mal die Mächtigkeit der Menge
[mm] $M:=\{\text{Katti1712}, \text{angela.h.b.}, \text{tobit09}\}$
[/mm]
der bisher an diesem Thread beteiligten User.
Gib dazu eine Bijektion zwischen $M$ und einer Menge der Form [mm] $\{1,\ldots,n\}$ [/mm] (für ein [mm] $n\in\IN$) [/mm] an.
Viele Grüße
Tobias
|
|
|
| |
|
Hallo Angela und Tobias :)
Erst mal vielen Dank, dass ihr mich hier willkommen heißt :)
Und vielen Dank, für die schnellen Antworten, ich bin echt begeistert, dass man hier schon so schnell so tolle Antworten bekommt und auch das einem die Lösung nicht direkt vorweg genommen wird, sondern dass ihr versucht es mir zu erklären, damit ich es selbst verstehe!
Erst mal zu Tobias mit der Vorübung (also für mich würde das dann so aussehen):
Sei M = [mm] \{Katti1712, angela.h.b, tobit09\}
[/mm]
[mm] f:M\to [/mm] N
[mm] f(a_i) [/mm] = [mm] b_i [/mm] für [mm] i\in \{1,...,n\}
[/mm]
[mm] \Rightarrow [/mm] f ist bijektiv
für [mm] a_i \in [/mm] M
[mm] b_i \in [/mm] N
da [mm] f(a_1)=b_1 [/mm] , [mm] f(a_2)=b_2 [/mm] , [mm] f(a_3=b_3)
[/mm]
mit [mm] a_1=Katti1712 [/mm] , [mm] a_2=angela.h.b [/mm] , [mm] a_3=tobit09 [/mm]
Nun zu meiner Aufgabe, also ich bin bis hierhin gekommen, aber weiß bei Fall 3 beim Induktionsschluss nicht weiter:
Behauptung:
Für alle [mm] n\in \IN [/mm] gilt: Ist M endlich mit |M|=n, dann ist jede Teilmenge [mm] A\subset [/mm] M endlich mit [mm] |A|\le [/mm] |M|.
Induktionsanfang:
Nochmal zu Tobias: warum |M|=0 und nicht |M|=1?
Also bei uns gehört null zu den natürlichen Zahlen dazu.
Aber ich habe den Induktionsanfang jetzt mal für beides gemacht:
Sei |M|=1 [mm] \Rightarrow [/mm] Menge M enthält ein Element,
sagen wir [mm] M=\{a\} \Rightarrow \exists [/mm] Teilmenge [mm] A_1 [/mm] und [mm] A_2 [/mm] von M
mit [mm] A_1=\{\emptyset\} [/mm] und [mm] A_2=\{a\}
[/mm]
[mm] \Rightarrow |A_1| [/mm] = [mm] |\{\emptyset\}|=0 [/mm] und [mm] |A_2|=|\{a\}|=1=|M|
[/mm]
[mm] \Rightarrow |M|=|A_2|\ge |A_1|\le [/mm] |M| [mm] \Rightarrow \forall [/mm] Teilmengen A
von M gilt [mm] |M|\ge [/mm] |A| und alle A sind endlich
Sei |M|=0
[mm] \Rightarrow \exists [/mm] genau eine Teilmenge A von M mit [mm] A=\{\emptyset\}
[/mm]
[mm] \Rightarrow |A|=|\{\emptyset\}|=0
[/mm]
[mm] \Rightarrow [/mm] |M|=|A| [mm] \Rightarrow [/mm] Für alle Teilmengen A von M gilt: [mm] |M|\ge|A| [/mm] und alle A sind endlich.
Induktionsvoraussetzung:
Für ein festes [mm] n\in\IN [/mm] gelte: Ist M endlich |M|=n,
dann ist jede Teilmenge [mm] A\subset [/mm] M endlich mit [mm] |A|\le|M|
[/mm]
Induktionsschluss:
[mm] n\to [/mm] n+1
Sei nun M eine Menge mit |M|=n+1
[mm] f:M\to\{1,2,3...n,n+1\}
[/mm]
Sei nun [mm] A\subset [/mm] M
Fall 1:
[mm] A=\emptyset\Rightarrow [/mm] Dann ist |A|=0, da [mm] |\emptyset|=0. [/mm] Und A ist endlich da per Definition [mm] \emptyset [/mm] endlich ist.
Fall 2:
A=M [mm] \Rightarrow [/mm] A ist endlich, da M endlich ist und [mm] |A|\le|M| [/mm] da |M|=|A|=n+1
Fall 3:
[mm] A\not=\emptyset, A\not= [/mm] M
Sei [mm] f:M':=M\backslash\{m\}=\{1,2,3,...,m-1,m+1,...,n,n+1}
[/mm]
Dass die Bijektion so aussieht ist mir klar, da m fehlt, aber ich habe total Probleme damit, weil ich nicht weiß, wie ich das Beweisen soll.
Könnt ihr mir dabei bitte noch mal helfen?
Ich hoffe bis dahin stimmt alles soweit :) Bin auf eure Rückmeldung gespannt!
Lieben Gruß
Katrin
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:55 So 26.10.2014 | | Autor: | tobit09 |
Hallo Katti1712!
> Erst mal vielen Dank, dass ihr mich hier willkommen heißt
> :)
>
> Und vielen Dank, für die schnellen Antworten, ich bin echt
> begeistert, dass man hier schon so schnell so tolle
> Antworten bekommt und auch das einem die Lösung nicht
> direkt vorweg genommen wird, sondern dass ihr versucht es
> mir zu erklären, damit ich es selbst verstehe!
Danke für das Lob! 
> Erst mal zu Tobias mit der Vorübung (also für mich würde
> das dann so aussehen):
>
> Sei M = [mm]\{Katti1712, angela.h.b, tobit09\}[/mm]
Anschaulich enthält diese Menge genau 3 Elemente (nämlich Katti1712, angela.h.b. und tobit09).
Zu überlegen ist nun, warum diese Menge auch nach eurer formalen Definition Mächtigkeit |M|=3 hat.
Zu zeigen ist also, dass es eine bijektive Abbildung
[mm] $f\colon M\to\{1,\ldots,n\}$
[/mm]
für $n=3$ gibt, also eine bijektive Abbildung
[mm] $f\colon M\to\{1,2,3\}$.
[/mm]
Wenn wir irgendeine Abbildung
[mm] $f\colon M\to\{1,2,3\}$
[/mm]
angeben können, die bijektiv ist, wissen wir, dass es eine solche Abbildung gibt.
Insbesondere soll unsere gesuchte Abbildung $f$ überhaupt eine Abbildung von $M$ nach [mm] $\{1,2,3\}$ [/mm] sein, d.h. sie muss jedem Element von $M$ eine der Zahlen 1, 2 oder 3 zuordnen.
> [mm]f:M\to[/mm] N
Hier verrätst du uns leider nicht, was du mit $N$ meinst.
> [mm]f(a_i)[/mm] = [mm]b_i[/mm] für [mm]i\in \{1,...,n\}[/mm]
Hier verrätst du uns leider nicht, was du mit $n$ sowie mit den [mm] $a_i$ [/mm] und den [mm] $b_i$ [/mm] meinst.
> [mm]\Rightarrow[/mm] f ist
> bijektiv
Das kann ich leider nicht prüfen, da ich gar nicht verstanden habe, welche Abbildung du mit f meinst.
> für [mm]a_i \in[/mm] M
> [mm]b_i \in[/mm] N
Eine Abbildung [mm] $f\colon M\to [/mm] N$ ist entweder bijektiv oder nicht bijektiv.
Sie kann nicht "bijektiv für [mm] $a_i\in [/mm] M$ und [mm] $b_i\in [/mm] N$" sein; das ist gar nicht definiert.
> da [mm]f(a_1)=b_1[/mm] , [mm]f(a_2)=b_2[/mm] , [mm]f(a_3=b_3)[/mm]
> mit [mm]a_1=Katti1712[/mm] , [mm]a_2=angela.h.b[/mm] , [mm]a_3=tobit09[/mm]
Achso, jetzt weiß ich, was du mit [mm] $a_1$, $a_2$ [/mm] und [mm] $a_3$ [/mm] meinst.
Aber ich weiß noch nicht, was du mit [mm] $b_1$, $b_2$ [/mm] und [mm] $b_3$ [/mm] meinst.
Wir suchen wie gesagt eine bijektive Abbildung
[mm] $f\colon M\to\{1,2,3\}$,
[/mm]
also eine bijektive Abbildung
[mm] $f\colon\{\text{Katti1712},\text{ angela.h.b.},\text{ tobit09}\}\to\{1,2,3\}$.
[/mm]
Ich gebe mal zwei Abbildungen $f$ und $g$ von [mm] $\{\text{Katti1712},\text{ angela.h.b.},\text{ tobit09}\}$ [/mm] nach [mm] $\{1,2,3\}$ [/mm] an:
[mm] $f\colon \{\text{Katti1712},\text{ angela.h.b.},\text{ tobit09}\}\to\{1,2,3\},\quad [/mm] f(u)=2$ für alle [mm] $u\in\{\text{Katti1712},\text{ angela.h.b.},\text{ tobit09}\}$,
[/mm]
d.h. f ordnet jedem der drei an diesem Thread bisher beteiligten User stets die Zahl 2 zu.
[mm] $g\colon\{\text{Katti1712},\text{ angela.h.b.},\text{ tobit09}\}\to\{1,2,3\},\quad g(u)=\begin{cases}1 & \text{ für }u=\text{Katti1712}\\2 & \text{ für }u=\text{angela.h.b.}\\3 & \text{ für }u=\text{tobit09}\end{cases}$,
[/mm]
d.h. $g$ ordnet dem User Katti1712 die Zahl 1, dem User angela.h.b. die Zahl 2 und dem User tobit09 die Zahl 3 zu.
Untersuche nun die Funktionen f und g auf Injektivität, Surjektivität und Bijektivität!
Falls eine der Funktionen bijektiv ist, hat die Menge [mm] $M=\{\text{Katti1712},\text{ angela.h.b.},\text{ tobit09}\}$ [/mm] wirklich die Mächtigkeit 3.
> Nun zu meiner Aufgabe, also ich bin bis hierhin gekommen,
> aber weiß bei Fall 3 beim Induktionsschluss nicht weiter:
>
> Behauptung:
>
> Für alle [mm]n\in \IN[/mm] gilt: Ist M endlich mit |M|=n, dann ist
> jede Teilmenge [mm]A\subset[/mm] M endlich mit [mm]|A|\le[/mm] |M|.
>
> Induktionsanfang:
>
> Nochmal zu Tobias: warum |M|=0 und nicht |M|=1?
Wir wollen ja am Ende gezeigt haben, dass eine Aussage (nämlich: "Jede Teilmenge [mm] $A\subseteq [/mm] M$ ist endlich mit [mm] $|A|\le|M|$.") [/mm] für JEDE endliche Menge $M$ gilt.
Dazu wollen wir für alle natürlichen Zahlen $n$ (einschließlich der 0) zeigen, dass die Aussage für jede endliche Menge $M$ der Mächtigkeit $n$ gilt.
Damit wir auf diese Weise tatsächlich alle endlichen Mengen $M$ "erwischen"/"abdecken", dürfen wir den Fall $n=0$ nicht außer Acht lassen.
Würden wir den Induktionsanfang mit $n=1$ statt mit $n=0$ wählen, so hätten wir die Aussage "nur" für endliche Mengen $M$ von Mächtigkeit [mm] $\ge1$ [/mm] gezeigt, aber nicht für ALLE endlichen Mengen $M$.
Ich passe den Anfang des von Angela angeführten Induktionsschemas an eure Konvention an, dass die 0 zu den natürlichen Zahlen gehört:
Beh.
Eine Aussage gilt für alle [mm] n\in \IN. [/mm]
Induktionsanfang
Man zeigt, daß die Aussage für n=0 gilt.
> Aber ich habe den Induktionsanfang jetzt mal für beides
> gemacht:
Schön, das schadet zur Übung bestimmt nicht!
> Sei |M|=1 [mm]\Rightarrow[/mm] Menge M enthält ein Element,
> sagen wir [mm]M=\{a\} \Rightarrow\exists[/mm] Teilmenge [mm]A_1[/mm] und [mm]A_2[/mm]
> von M
Du meinst hier: $M$ hat genau zwei Teilmengen [mm] $A_1$ [/mm] und [mm] $A_2$, [/mm] nämlich...
> mit [mm]A_1=\{\emptyset\}[/mm] und [mm]A_2=\{a\}[/mm]
Hier muss es [mm] $A_1=\emptyset$ [/mm] oder [mm] $A_1=\{\}$ [/mm] statt [mm] $A_1=\{\emptyset\}$ [/mm] heißen.
> [mm]\Rightarrow |A_1|[/mm] = [mm]|\{\emptyset\}|=0[/mm]
Hier ist entsprechend [mm] $\{\emptyset\}$ [/mm] durch [mm] $\emptyset$ [/mm] bzw. [mm] $\{\}$ [/mm] zu ersetzen.
(Es sollte intuitiv [mm] $|\{\emptyset\}|=1$ [/mm] gelten, denn [mm] $\{\emptyset\}$ [/mm] enthält genau 1 Element, nämlich die leere Menge.)
> und
> [mm]|A_2|=|\{a\}|=1=|M|[/mm]
> [mm]\Rightarrow |M|=|A_2|\ge |A_1|\le[/mm] |M| [mm]\Rightarrow \forall[/mm]
> Teilmengen A
> von M gilt [mm]|M|\ge[/mm] |A| und alle
solchen
> A sind endlich
> Sei |M|=0
> [mm]\Rightarrow \exists[/mm] genau eine Teilmenge A von M mit
Ersetze das Wort "mit" durch "nämlich".
> [mm]A=\{\emptyset\}[/mm]
Wieder muss es [mm] $A=\emptyset$ [/mm] bzw. [mm] $A=\{\}$ [/mm] heißen.
Genauso in der folgenden Zeile:
> [mm]\Rightarrow |A|=|\{\emptyset\}|=0[/mm]
> [mm]\Rightarrow[/mm] |M|=|A|
> [mm]\Rightarrow[/mm] Für alle Teilmengen A von M gilt: [mm]|M|\ge|A|[/mm]
> und alle A sind endlich.
Du hast an sich die richtigen Ideen!
Du hast mit der Intuition der Anzahl der Elemente einer Menge gearbeitet.
Es ist gut und hilfreich, dass du diese Intuition hast.
Ziel dieser Aufgabe ist jedoch, mit der formalen Definitionen von Endlichkeit und Mächtigkeit zu arbeiten:
Warum folgt z.B. aus $|M|=1$ wirklich, dass $M$ die Gestalt [mm] $M=\{a\}$ [/mm] hat?
$|M|=1$ bedeutet, dass es eine bijektive Abbildung
[mm] $f\colon M\to\{1\}$
[/mm]
gibt.
Ich verzichte nun auf den etwas technischen Nachweis, dass tatsächlich folgt, dass $M$ die Gestalt [mm] $M=\{a\}$ [/mm] für ein Objekt $a$ hat.
Zum Fall $|M|=0$:
Eure Definition lautete ja:
Eine Menge M heißt endlich, mit 'Mächtigkeit' |M|=n, falls es eine bijektive Abbildung [mm] f:M\to\{1,...,n\} [/mm] gibt. Die leere Menge [mm] \emptyset [/mm] sei per Definition endlich, mit Mächtigkeit [mm] |\emptyset|=0
[/mm]
Das verstehe ich so, dass [mm] $n\in\IN\setminus\{0\}$ [/mm] sein soll.
Also haben alle endlichen Mengen außer der leeren Menge eine Mächtigkeit $>0$.
Somit folgt aus $|M|=0$ bereits [mm] $M=\emptyset$.
[/mm]
(Das war dir intuitiv wohl schon klar, aber ich wollte es anhand der Definition begründen.)
> Induktionsvoraussetzung:
>
> Für ein festes [mm]n\in\IN[/mm] gelte: Ist M endlich |M|=n,
> dann ist jede Teilmenge [mm]A\subset[/mm] M endlich mit [mm]|A|\le|M|[/mm]
>
> Induktionsschluss:
>
> [mm]n\to[/mm] n+1
>
> Sei nun M eine Menge mit |M|=n+1
Dann existiert also eine bijektive Abbildung
> [mm]f:M\to\{1,2,3...n,n+1\}[/mm]
>
> Sei nun [mm]A\subset[/mm] M
>
> Fall 1:
>
> [mm]A=\emptyset\Rightarrow[/mm] Dann ist |A|=0, da [mm]|\emptyset|=0.[/mm]
> Und A ist endlich da per Definition [mm]\emptyset[/mm] endlich ist.
Schön!
> Fall 2:
>
> A=M [mm]\Rightarrow[/mm] A ist endlich, da M endlich ist und
> [mm]|A|\le|M|[/mm] da |M|=|A|=n+1
Gut!
> Fall 3:
>
> [mm]A\not=\emptyset, A\not=[/mm] M
>
> Sei [mm]f:M':=M\backslash\{m\}=\{1,2,3,...,m-1,m+1,...,n,n+1}[/mm]
M muss keine Menge von Zahlen sein, $m$ muss überhaupt keine Zahl sein.
(Denke z.B. wieder an [mm] $M=\{\text{Katti1712},\text{ angela.h.b.},\text{ tobit09}\}$. [/mm]  )
> Dass die Bijektion so aussieht ist mir klar, da m fehlt,
> aber ich habe total Probleme damit, weil ich nicht weiß,
> wie ich das Beweisen soll.
> Könnt ihr mir dabei bitte noch mal helfen?
Wir haben eine bijektive Abbildung
[mm] $f\colon M\to\{1,\ldots,n+1\}$.
[/mm]
Du benötigst eine bijektive Abbildung
[mm] $g\colon M\setminus\{m\}\to\{1,\ldots,n\}$.
[/mm]
Eine solche hast du leider noch nicht gefunden.
Du musst jedem [mm] $m'\in M\setminus\{m\}$ [/mm] eine der natürlichen Zahlen von 1 bis n zuordnen (so dass jede dieser Zahlen genau einmal getroffen wird).
Wir führen eine (weitere) Fallunterscheidung durch:
Fall a): $f(m)=n+1$
Hast du in diesem Fall eine Idee für eine mögliche Wahl von $g$?
Fall b): [mm] $i:=f(m)\in\{1,\ldots,n\}$
[/mm]
Dieser Fall ist etwas komplizierter.
Da $f$ surjektiv ist, existiert ein [mm] $m^\*\in [/mm] M$ mit [mm] $f(m^\*)=n+1$.
[/mm]
Wähle nun $g$ in der Art
[mm] $g\colon M\setminus\{m\}\to\{1,\ldots,n\},\quad g(m')=\begin{cases}\ldots&\text{ für }m'\not=m^\*\\\ldots&\text{ für }m'=m^\*\end{cases}$.
[/mm]
Puh, das war jetzt eine meiner längsten Antworten, die ich hier je gegeben habe...
Viel Erfolg beim Durcharbeiten!
Viele Grüße
Tobias
|
|
|
| |
|
Hallo Tobias,
also noch mal vielen Dank, fürs korrigieren und Hilfe geben, aber ich hab trotzdem noch Probleme mit Fall b) von Fall 3... Ich kann mir leider überhaupt keine Vorstellung machen, wie so etwas aussehen soll.
Für Fall a) Ich weiß leider nicht ganz wie ich das genau aufschreiben soll):
[mm] f:M\to\{1,2,3,...,n+1\} [/mm] bij.
f(m)=n+1
n+1 wird von g nicht mehr getroffen, also muss man das m für g entfernen.
[mm] f:M\to\{1,2,3...,n+1\}
[/mm]
g: [mm] M\backslash\{m\}\to\{1,2,3...,n\}
[/mm]
da f(m)=n+1 und wir haben m aus M entfernt, wodurch n+1 nicht mehr getroffen wird.
Lieben Gruß
Katrin
|
|
|
| |
|
> Für Fall a) Ich weiß leider nicht ganz wie ich das genau
> aufschreiben soll):
Hallo,
ich sehe aber, daß Du es richtig verstanden hast.
Wir hatten
> [mm]f:M\to\{1,2,3,...,n+1\}[/mm] bij.
mit
> f(m)=n+1.
Wir definieren nun eine Funktion
g: [mm] M\setminus \{m\}\to \{1,2,3,...,n\}
[/mm]
durch
g(m'):= f(m') für alle [mm] m'\in M\setminus \{m\}.
[/mm]
Diese Funktion ist bijektiv, denn ...
(Hier solltest Du die Bijektivität, also Injektivität und Surjektivität nachweisen. Dabei nutzt Du natürlich, daß f bijektiv ist.)
Den
Fall b),
in welchem das Element m vermöge f auf eine der Zahlen 1,2,3,...,n abgebildet wird,
hat Tobias eigentlich schon vorgemacht.
Nochmal:
es sei f(m)=i mit [mm] i\in\{1,2,3,...,n}.
[/mm]
Weil f bijektiv ist, gibt es ein Element [mm] m^\* \in [/mm] M,
mit [mm] f(m^\*)=n+1.
[/mm]
(Es muß ja ein Element auf n+1 abgebildet werden wegen der Surjektivität.)
Wegen der Injektivität von f ist [mm] m^\*\not=m.
[/mm]
(Wenn wir jetzt mal einfach für eine Funktion [mm] \overline{f}:M\to \{1,2,3,...,n,n+1\} [/mm] die Funktionswerte von m und [mm] m^\* [/mm] tauschen,
also definieren
[mm] \overline{f}(m'):=f(m') [/mm] für alle [mm] m'\in M\setminus{m,m\*}
[/mm]
[mm] \overline{f}(m):=n+1
[/mm]
[mm] \overline{f}(m\*):=i,
[/mm]
so haben wir auch eine Bijektion von M nach [mm] \{1,2,3,...,n,n+1\}. [/mm] Verstanden?)
So.
Und jetzt machen wir uns eine neue, bijektive Abbildung [mm] g:M\setminus \{m\}\to \{1,2,3,...,n\}, [/mm] indem wir definieren
g(m'):=f(m') für alle [mm] m'\in M\setminus \{m, m\*\},
[/mm]
[mm] g(m\*):= [/mm] i.
Nun mußt Du noch kurz beweisen, daß diese Abbildung injektiv und surjektiv ist.
LG Angela
>
> n+1 wird von g nicht mehr getroffen, also muss man das m
> für g entfernen.
>
> [mm]f:M\to\{1,2,3...,n+1\}[/mm]
> g: [mm]M\backslash\{m\}\to\{1,2,3...,n\}[/mm]
> da f(m)=n+1 und wir haben m aus M entfernt, wodurch n+1
> nicht mehr getroffen wird.
>
> Lieben Gruß
>
> Katrin
|
|
|
| |
|
Hallo Angela,
danke für die Hinweise.
Meine Fall 3 würde jetzt so aussehen:
[mm] A\not=\emptyset [/mm] und [mm] A\not= [/mm] M
Es folgt eine weitere Fallunterscheidung
Fall 3.a): Sei f(m)=n+1
Definiere eine neue Funktion
[mm] g:M\backslash\{m\}\to\{1,2,...n\}
[/mm]
durch g(m')=f(m') [mm] \forall m'\in M\backslash\{m\}.
[/mm]
Diese Funktion g ist bijektiv, da f bijektiv.
Insbesondere ist f injektiv, d.h. [mm] \forall a,b\in [/mm] M gilt f(a)=f(b) [mm] \gdw [/mm] a=b.
Da nun g(m')=f(m') [mm] \forall m'\in M\backslash\{m\} [/mm] und f(m)=n+1 folgt
[mm] \forall a',b'\in M\backslash\{m\} [/mm] gilt [mm] g(a')=g(b')\gdw [/mm] a'=b' und g ist injektiv.
Weiterhin ist ist f surjektiv [mm] \Rightarrow \forall [/mm] i [mm] \in\{1,2,...,n+1\}
[/mm]
[mm] \existsx \in [/mm] M:f(x)=i. Da g(m')=f(m')
[mm] \forall m'\in [/mm] M [mm] \bachslash\[{m\} [/mm] und f(m)=n+1 [mm] \exists\forall i'\in\{1,2,...n\} [/mm] ein [mm] x'\inM\backslash\[{m\}, [/mm] sodass f(x')=i'
[mm] \Rightarrow [/mm] g ist surjektiv. Da g injektiv und surjektiv ist folgt g ist bijektiv.
Wir haben also eine bijektive Abbildung [mm] g=M\backslash\{m\}\to\{1,2,...n\} [/mm] gefunden
[mm] \Rightarrow M\backslash\{m\} [/mm] ist endlich mit [mm] |M\backslah\{m\}|=n [/mm] und es gilt [mm] |M\backslash\{m\}\le [/mm] |M|=n+1
Fall 3.b):
Sei f(m)=i mit [mm] i\in\{1,2,3..,n\}
[/mm]
definiere eine neue Abbildung
[mm] g:M\backslash\{m\}\to\{1,2,3..,n\} [/mm] mit g(m')=f(m') [mm] \forall m'\in M\backslash\{m,m*\}
[/mm]
und g(m*)=i
Diese Abbildung g ist injektiv da f injektiv.
Es gilt g(m')=f(m') [mm] \forall [/mm] m' [mm] \in [/mm] M [mm] \backslash \{m,m*\} [/mm]
und daher folgt [mm] \forall [/mm] a,b [mm] \in M\backslash\{m,m*\}
[/mm]
[mm] g(a)=g(b)\gdw [/mm] a=b. Weiterhin existiert genau ein Element [mm] m*\in M\{m\} [/mm] mit g(m*)=i
(meine Konstruktion von g erzwingt dies). Also ist g injektiv.
g ist surjektiv, da f surjektiv ist.
Es gilt g(m')=f(m') [mm] \forall m'\in [/mm] M [mm] \backslash\{m,m*\}
[/mm]
[mm] \Rightarrow \forall [/mm] k [mm] \in \{1,2,3,..,n\}\backslash\{i\} \exists [/mm] x [mm] \in M\backslash\{m,m*\} [/mm] sodass g(x)=k. Nach Konstruktion ist weiterhin g(m*)=i [mm] \Rightarrow \forall k'\in\{1,2,3...,n\} [/mm] exists x' [mm] \in M\backslash\{m\} [/mm] mit g(x')=k'
[mm] \Rightarrow [/mm] g ist surjektiv. Da g injektiv und surjektiv folgt g ist bijektiv.
Wieder folgt die Endlichkeit von [mm] M\backslash\{m\} [/mm] durch die gefundene bijektive Abbildung. [mm] |M\backslasch\{m\}|=n \le [/mm] |M|=n+1.
Aus den Fällen 1 bis 3 folgt die Behauptung, nämlich jede Teilmenge [mm] A\subsetM [/mm] ist endlich und [mm] |A|\le|M|
[/mm]
Lieben Gruß
Katrin
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:52 Mo 27.10.2014 | | Autor: | Katti1712 |
Ups, der obige Post sollte als Frage gesendet werden nicht als Mitteilung..
Lieben Gruß
Katrin
|
|
|
| |
|
Hallo,
> Meine Fall 3 würde jetzt so aussehen:
>
> [mm]A\not=\emptyset[/mm] und [mm]A\not=[/mm] M
Dann gibt es ein Element [mm] m\in [/mm] M, welches nicht in A ist.
A ist also Teilmenge von [mm] M\setminus \{m\}.
[/mm]
Wir zeigen nun, daß A Teilmenge einer n-elementigen Menge ist.
(Ich glaube, dieses Ziel hast Du etwas aus den Augen verloren.)
>
> Es folgt eine weitere Fallunterscheidung
>
> Fall 3.a): Sei f(m)=n+1
>
> Definiere eine neue Funktion
>
> [mm]g:M\backslash\{m\}\to\{1,2,...n\}[/mm]
>
> durch g(m')=f(m') [mm]\forall m'\in M\backslash\{m\}.[/mm]
Beh.: g ist injektiv:
Seien
> [mm] a',b'\in M\backslash\{m\}[/mm]
mit
>[mm]g(a')=g(b')\gdw[/mm]
f(a')=f(b') (nach Def. von g)
==>
> a'=b' (da f injektiv)
Also:
> g ist injektiv.
Beh.: g ist surjektiv
Sei [mm] i\in\{1,2,3,..,n\}.
[/mm]
Da f surjektiv, gibt es zu jedem [mm] i\in \{1,2,3,..,n\} [/mm] ein [mm] m_i\in [/mm] M mit
[mm] f(m_i)=i.
[/mm]
Da f(m)=n+1, sind die [mm] m_i\not=m [/mm] für alle [mm] i\in\{1,2,3,..,n\}.
[/mm]
Also
> [mm]\exists\forall i'\in\{1,2,...n\}[/mm] ein
> [mm]x'\inM\backslash\[{m\},[/mm] sodass
g(x')=
> f(x')=i'
>
> [mm]\Rightarrow[/mm] g ist surjektiv.
>Da g injektiv und surjektiv
> ist folgt g ist bijektiv.
>
> Wir haben also eine bijektive Abbildung
> [mm]g=M\backslash\{m\}\to\{1,2,...n\}[/mm] gefunden
> [mm]\Rightarrow M\backslash\{m\}[/mm] ist endlich mit
> [mm]|M\backslash\{m\}|=n[/mm]
Nun müßtest Du mal notieren, was das für A bedeutet.
An dieser Stelle kommt die Induktionsvoraussetzung zum Tragen.
> Fall 3.b):
Sei [mm] f(m)\not=n+1
[/mm]
>
Dann ist
> f(m)=i mit [mm]i\in\{1,2,3..,n\}[/mm].
Weil f surjektiv ist, gibt es ein [mm] m^\*\in M\setminus\{m\}
[/mm]
mit
[mm] f(m^\*)=n+1
[/mm]
> definiere eine neue Abbildung
> [mm]g:M\backslash\{m\}\to\{1,2,3..,n\}[/mm] mit g(m')=f(m')
> [mm]\forall m'\in M\backslash\{m,m*\}[/mm]
> und g(m*)=i
Beh:
> Diese Abbildung g ist injektiv
Seien [mm] a,b\in M\setminus \{m\} [/mm] mit
g(a)=g(b)
a. a,b sind beide [mm] \not=m^\*
[/mm]
==> ...
b. Es ist [mm] b=m^\* [/mm] und [mm] a\not=m^\*.
[/mm]
==> [mm] g(a)=g(m^\*)=i
[/mm]
==> f(a)=i=f(m)
==> a=m. Widerspruch, denn [mm] a\in M\setminus \{m\}.
[/mm]
Fall b) kann also nicht vorkommen.
> Also ist g
> injektiv.
Beh.:
> g ist surjektiv.
Sei [mm] k\in \{1,2,3...,n\}.
[/mm]
a. [mm] k\not=i
[/mm]
Da f surjektiv, gibt es ein [mm] m_k\in M\setminus\{m\} [/mm] mit
[mm] f(m_k)=k,
[/mm]
und wir haben [mm] g(m_k)=k
[/mm]
b. k=i
> Nach Konstruktion
> ist weiterhin g(m*)=i
Also ist
> g ist surjektiv.
> Da g injektiv und surjektiv
> folgt g ist bijektiv.
>
> Wieder folgt die Endlichkeit von [mm]M\backslash\{m\}[/mm] durch die
> gefundene bijektive Abbildung,
und es ist
> [mm][mm] |M\backslash\{m\}|=n
[/mm]
Damit ist A ...
> Aus den Fällen 1 bis 3 folgt die Behauptung, nämlich
> jede Teilmenge [mm]A\subset M[/mm] ist endlich und [mm]|A|\le|M|[/mm]
LG Angela
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:46 Di 28.10.2014 | | Autor: | tobit09 |
Hallo Angela!
Ein kleiner Hinweis:
Du verweist wiederholt auf die Injektivität von $f$ an Stellen, an denen sie gar nicht eingeht, z.B. hier:
> Da f surjektiv, gibt es zu jedem [mm]i\in \{1,2,3,..,n\}[/mm] ein
> [mm]m_i\in[/mm] M mit
> [mm]f(m_i)=i.[/mm]
>
> Da f injektiv ist, und f(m)=n+1, sind die [mm]m_i\not=m[/mm] für
> alle [mm]i\in\{1,2,3,..,n\}.[/mm]
Injektvität von f lässt sich charakterisieren durch
[mm] $a\not=b\Rightarrow f(a)\not=f(b)$
[/mm]
für alle [mm] $a,b\in [/mm] M$.
Die Umkehrung
[mm] $f(a)\not=f(b)\Rightarrow a\not=b$
[/mm]
hat nichts mit der Injektivität von $f$ zu tun.
Viele Grüße
Tobias
|
|
|
| |
|
> Hallo Angela!
>
>
> Ein kleiner Hinweis:
>
> Du verweist wiederholt auf die Injektivität von [mm]f[/mm] an
> Stellen, an denen sie gar nicht eingeht,
Stimmt!
Danke für den Hinweis, hab's verbessert.
LG Angela
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:48 Mi 29.10.2014 | | Autor: | Katti1712 |
Hallo Angela und Tobias,
ich habe die "Lücken" ergänzt die Angela offen gelassen hat (war ja nicht mehr viel). Und ich möchte mich bei euch für eure Hilfe bedanken!!
Ich hab es euch ja nicht grade leicht gemacht mir das zu erklären, aber wenigstens verstehe ich des jetzt. Sogar meine Tutorin hat heute gesagt, dass diese Aufgabe auf dem Übungszettel die schwerste ist und sie die Aufgabe erst ein paar mal angucken musste, um diese zu beweisen. Wie gesagt, ich bewundere euch, dass ihr eure Freizeit dafür opfert, um Leuten wie mir zu helfen!!
Wirklich vielen, vielen Dank euch beiden!!
Lieben Gruß
Katrin
|
|
|
|
