Anzahl an Abb. zw. Mengen < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Für [mm] $n,m\in\mathbb{N}$ [/mm] sei $M$ eine $m$-elementige Menge und $N$ eine $n$-elementige Menge. Beweisen Sie durch vollständige Induktion:
a) Es gibt genau [mm] $n^m$ [/mm] verschiedene Abbildungen [mm] $f:M\to [/mm] N$.
b) Es sei nun [mm] $m\le [/mm] n$. Es gibt genau [mm] $\frac{n!}{\left( n-m\right)!}$ [/mm] verschiedene injektive Abbildungen [mm] $f:M\to [/mm] N$. |
Hallo,
da ich mit Kombinatorik etwas auf Kriegsfuß stehe, hätte ich hier erstmal die erste Frage zur Teilaufgabe a):
Wie kann ich formal zeigen, dass wenn ich eine gegebene Anzahl an Abbildungen [mm] $f:M\to [/mm] N$ habe, diese Anzahl wiederum mit der Anzahl der Elemente von $N$, also $n$ multiplizieren muss, wenn ich die Anzahl der Elemente von $M$ um 1 erhöhe. Das wäre ja gerade [mm] $n^m$. [/mm]
Ich habe das bis jetzt nur "umgangssprachlich" hingeschrieben im Sinne von: Es sei [mm] $M=\left\{a_{1\le i \le m}: i\in\mathbb{N}\right\}$. [/mm] Hat man eine Anzahl von verschiedenen Abbildungen [mm] $f:M\to [/mm] N$ für ein gegebenes $m$ [mm] ($F(m):\gdw$Anzahl [/mm] verschiedener Abbildungen [mm] $f:M\to [/mm] N$), so ergeben sich bei [mm] $M\cup\left\{ a_{m+1}\right\}$ [/mm] (also ein Element mehr) bei jeder zuvor vorhandenen Abbildung $n$ Möglichkeiten das neue Element abzubilden: [mm] $F(m+1)=F(m)\cdot [/mm] n$. (Das wäre meine Begründung für den Induktionsschritt. Wie ich den Induktionsanfang formal aufschreiben soll, weiß ich ehrlich gesagt auch nicht so wirklich. Dass der richtig ist, ist ja klar, also dass ich ein Element auf $n$ verschiedene Art und Weisen auf $n$ Elemente abbilden kann.)
Dann der Induktionsschritt an sich:
nach Induktionsvoraussetzung: [mm] $F(m)=n^m$
[/mm]
[mm] $m\to [/mm] m+1$:
[mm] $F(m+1)=F(m)\cdot n=n^m\cdot n=n^{m+1}$ \qquad\Box [/mm] (hoffentlich)
Das kommt mir nur irgendwie alles nicht richtig vor. Es wäre super, wenn ihr mir da Anregungen geben könntet, wie das formaler gehen könnte.
b)
Hier habe ich ein ähnliches Problem. Wir hatten in der Vorlesung folgende Definition für Abbildungen:
Eine Abbildung [mm] $f:M\to [/mm] N$ ist definiert als Teilmenge $f$ von [mm] $M\times [/mm] N$ mit der Eigenschaft [mm] $\forall m\in M\exists!y\in [/mm] N: [mm] \left( m,n\right)\in [/mm] f$.
Und vorher das kartesische Produkt zweier Mengen $M,N$:
[mm] [i]$M\times N:=\left\{\left( m,n\right):m\in M,n\in N\right\}$ [/mm] wobei [mm] \left( m,n\right) [/mm] das geordnete Paar bezeichnet, d.h. [mm] $\left( m,n\right)=\left( m',n'\right)\gdw\left( m=m'\right)\wedge\left( n=n'\right)$[/i]
[/mm]
Kann ich dann die Menge der injektiven Abbildungen [mm] $f:M\to [/mm] N$ als "angeordnete Teilmenge" von [mm] $M\times [/mm] N$ ansehen? Wir hatten nämlich folgenden Satz:
Sei [mm] $k,n\in\mathbb{N}_0$. [/mm] Die Anzahl der $k$-elementigen Teilmengen einer $n$-elementigen Menge ist genau [mm] $\binom{n}{k}$.
[/mm]
Nun ist ja [mm] $\binom{n}{k}=\frac{n!}{k!\left( n-k\right)}=\frac{1}{k!}\cdot\frac{n!}{\left( n-k\right)}$. [/mm] Multipliziert mit $k!$ wäre ich ja dann bei der gesuchten Formel [mm] $\frac{n!}{\left( n-k\right)}$ [/mm] mit $k=m$, und hätte doch damit den Faktor der Anordnung mit drin, oder? Geht das so?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:53 So 23.10.2011 | | Autor: | Helbig |
> da ich mit Kombinatorik etwas auf Kriegsfuß stehe, hätte
Genauso wie ich! Weil in der Kombinatorik die Anzahl der Elemente einer endlichen Menge nicht so auf die Mengenlehre zurückgeführt wird, daß man
damit Beweise führen kann. Für mich habe ich daher definiert:
a) Eine Menge [mm]M[/mm] ist endlich, wenn es eine Bijektion von [mm]M[/mm] nach [mm]A_n=\{k\in\IN\mid 0\le k < n\}[/mm] gibt.
b) Die Größe [mm]|M|[/mm] einer endlichen Menge [mm]M[/mm] ist dann [mm] n [/mm].
Hierzu habe ich für mich gezeigt: Gibt es eine Bijektion von [mm]M[/mm] nach [mm]A_n[/mm] und eine nach [mm]A_m[/mm], so ist [mm]m=n[/mm].
Aber solange die Kombinatorik nicht auf solchen Definitionen gegründet wird, kann man auch keine vernünftigen Beweise führen.
Tut mir leid,
Wolfgang
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 11:52 So 23.10.2011 | | Autor: | Lustique |
> > da ich mit Kombinatorik etwas auf Kriegsfuß stehe, hätte
>
> Genauso wie ich! Weil in der Kombinatorik die Anzahl der
> Elemente einer endlichen Menge nicht so auf die Mengenlehre
> zurückgeführt wird, daß man
> damit Beweise führen kann. Für mich habe ich daher
> definiert:
> a) Eine Menge [mm]M[/mm] ist endlich, wenn es eine Bijektion von [mm]M[/mm]
> nach [mm]A_n=\{k\in\IN\mid 0\le k < n\}[/mm] gibt.
> b) Die Größe [mm]|M|[/mm] einer endlichen Menge [mm]M[/mm] ist dann [mm]n [/mm].
>
> Hierzu habe ich für mich gezeigt: Gibt es eine Bijektion
> von [mm]M[/mm] nach [mm]A_n[/mm] und eine nach [mm]A_m[/mm], so ist [mm]m=n[/mm].
>
> Aber solange die Kombinatorik nicht auf solchen
> Definitionen gegründet wird, kann man auch keine
> vernünftigen Beweise führen.
>
> Tut mir leid,
> Wolfgang
>
Kein Problem! Wenn es die entsprechenden Definitionen nicht gibt, ist das ja nicht deine Schuld, und danke erst mal für deine Antwort. :) Es ist jetzt auch eher meine Schuld, dass ich nicht noch die beiden Sachen weiter unten mit in meine Frage geschrieben habe. (habe wohl gar nicht gedacht, dass die wichtig sein könnten... Soviel zu meinem mathematischen Sachverstand. :D)
Also, in der Vorlesung hatten wir folgende Definition und folgenden Satz:
Def.:
Eine Menge $M$ heißt endlich, wenn [mm] $M\sim A_n$ [/mm] für eine der Mengen
[mm] $A:=\left\{k\in\mathbb{N}:k\le n\right\}$, [/mm] oder [mm] $M=\emptyset$ [/mm] [gilt.] (Habe ich wahrscheinlich nicht mitgeschrieben, das "gilt".)
Dann nennt man $n$ die Anzahl der Elemente von $M$ und wir schreiben [mm] $n=\# [/mm] M$ und [mm] $\#\emptyset=0$. [/mm] Andernfalls nennen wir $M$ unendlich.
Satz:
Sei [mm] $n\in\mathbb{N}$. [/mm] Die Anzahl aller bijektiven Abbildungen [mm] $f\colon A_n\to [/mm] M$ in eine $n$-elementige Menge (Permutationen/Anordnungen) beträgt $n!$
Die Definition entspricht doch dann eigentlich dem, was du geschrieben hast, oder?
Zu dem Satz hatten wir dann den Beweis:
$n=1$ ist wahr. Sei nun die Beh. für $n=k$ wahr.
Nun sei $M$ eine $(k+1)$-elementige Menge mit einer Anordnung
[mm] $f\colon A_{k+1}\to [/mm] M$.
Wir betrachten nun die $(k+1)$ verschiedenen Teilmenge[n] (Ich denke mal, dass es Teilmengen heißen muss. Ich habe da wahrscheinlich beim Abschreiben von der Tafel ein n unterschlagen.)
[mm] $M_j=M\setminus \left\{ f(j)\right\}, 1\le j\le [/mm] k+1$
Nach der Induktionsannahme besitzt jede Menge [mm] $M_j$ [/mm] $k!$ Anordnungen, weil [mm] $\# M_j=k$. [/mm] Somit gibt es insgesamt $k!(k+1)$ Anordnungen.
[mm] $\fill \Box$
[/mm]
Vielleicht habe ich auch die vollständige Induktion noch nicht richtig verstanden, aber müsste man nicht erst noch irgendwie zeigen, dass man das Ganze auch tatsächlich mit $(k+1)$ multiplizieren muss, also den Induktionsschritt irgendwie begründen? Oder ist das genau das, wo dann die entsprechenden Definitionen fehlen, die du angesprochen hast?
Wenn ich jetzt also meine "Beweise" noch auf die Def. und den Satz (Geht das mit dem Satz überhaupt? In der Aufgabe ist ja nur von injektiven Abbildungen die Rede, da [mm] $m\le [/mm] n$ und nicht $m=n$.) irgendwie zurückführen würde, könnte man sie auch tatsächlich als Beweise durchgehen lassen?
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:26 So 23.10.2011 | | Autor: | Helbig |
> Kein Problem! Wenn es die entsprechenden Definitionen nicht
> gibt, ist das ja nicht deine Schuld, und danke erst mal
> für deine Antwort. :) Es ist jetzt auch eher meine Schuld,
> dass ich nicht noch die beiden Sachen weiter unten mit in
> meine Frage geschrieben habe. (habe wohl gar nicht gedacht,
> dass die wichtig sein könnten... Soviel zu meinem
> mathematischen Sachverstand. :D)
Ja, das liegt daran, daß in den Vorlesungen die Zahl der Elemente endlicher Mengen, wenn überhaupt, mal so und mal so definiert wird. Aber Eure Definition entspricht meiner. Nur daß bei Euch die leere Menge als Sonderfall auftritt. Dies ist aber mehr kosmetisch. Man fängt sich bei solchen Definitionen in vielen Beweisen häßliche Fallunterscheidungen leer - nichtleer ein.
Bei mir ist deshalb $0$ auch eine natürliche Zahl.
Aber wie gesagt, dies ist nicht so wichtig.
Nur am Rande: Wurde in der Vorlesung auch bewiesen:
Aus [mm] $M\sim A_n$ [/mm] und [mm] $M\sim A_m$ [/mm] folgt $m=n$?
Nämlich nur dann ist [mm] $\sharp [/mm] M$ ja definiert.
>
> Also, in der Vorlesung hatten wir folgende Definition und
> folgenden Satz:
>
> Def.:
> Eine Menge [mm]M[/mm] heißt endlich, wenn [mm]M\sim A_n[/mm] für eine der
> Mengen
> [mm]A:=\left\{k\in\mathbb{N}:k\le n\right\}[/mm], oder [mm]M=\emptyset[/mm]
> [gilt.] (Habe ich wahrscheinlich nicht mitgeschrieben, das
> "gilt".)
> Dann nennt man [mm]n[/mm] die Anzahl der Elemente von [mm]M[/mm] und wir
> schreiben [mm]n=\# M[/mm] und [mm]\#\emptyset=0[/mm]. Andernfalls nennen wir
> [mm]M[/mm] unendlich.
>
>
> Satz:
> Sei [mm]n\in\mathbb{N}[/mm]. Die Anzahl aller bijektiven
> Abbildungen [mm]f\colon A_n\to M[/mm] in eine [mm]n[/mm]-elementige Menge
> (Permutationen/Anordnungen) beträgt [mm]n![/mm]
>
> Die Definition entspricht doch dann eigentlich dem, was du
> geschrieben hast, oder?
Genau!
>
> Zu dem Satz hatten wir dann den Beweis:
>
> [mm]n=1[/mm] ist wahr. Sei nun die Beh. für [mm]n=k[/mm] wahr.
> Nun sei [mm]M[/mm] eine [mm](k+1)[/mm]-elementige Menge mit einer Anordnung
> [mm]f\colon A_{k+1}\to M[/mm].
> Wir betrachten nun die [mm](k+1)[/mm]
> verschiedenen Teilmenge[n] (Ich denke mal, dass es
> Teilmengen heißen muss. Ich habe da wahrscheinlich beim
> Abschreiben von der Tafel ein n unterschlagen.)
> [mm]M_j=M\setminus \left\{ f(j)\right\}, 1\le j\le k+1[/mm]
> Nach
> der Induktionsannahme besitzt jede Menge [mm]M_j[/mm] [mm]k![/mm]
> Anordnungen, weil [mm]\# M_j=k[/mm]. Somit gibt es insgesamt [mm]k!(k+1)[/mm]
> Anordnungen.
> [mm]\fill \Box[/mm]
>
> Vielleicht habe ich auch die vollständige Induktion noch
> nicht richtig verstanden, aber müsste man nicht erst noch
> irgendwie zeigen, dass man das Ganze auch tatsächlich mit
> [mm](k+1)[/mm] multiplizieren muss, also den Induktionsschritt
> irgendwie begründen?
Genau! Das müßte man! Aber hier hebt die Vorlesung auf Intuition und nicht auf Logik ab. Laut Definition muß gezeigt werden:
Ist [mm] $\cal [/mm] B$ die Menge der Bijektionen von $M$ nach [mm] $A_n$ [/mm] (= Menge der Anordnungen der Elemente von $M$), so ist [mm] ${\cal B} \sim A_{n!}$. [/mm] Dies kann man mit Induktion beweisen, muß man aber nicht.
> Oder ist das genau das, wo dann die
> entsprechenden Definitionen fehlen, die du angesprochen
> hast?
Die Definitionen fehlen hier nicht, sondern "nur" die Begründung mit Hilfe der definierten Begriffe. Dies halte ich für verwirrender, als die Anzahl der Elemente einer endlichen Menge überhaupt nicht zu definieren und stattdessen zu verkünden, "jeder weiß ja was das ist."
>
> Wenn ich jetzt also meine "Beweise" noch auf die Def. und
> den Satz (Geht das mit dem Satz überhaupt? In der Aufgabe
> ist ja nur von injektiven Abbildungen die Rede, da [mm]m\le n[/mm]
> und nicht [mm]m=n[/mm].) irgendwie zurückführen würde, könnte
> man sie auch tatsächlich als Beweise durchgehen lassen?
Ich würde den Satz nicht dazu benutzen wollen. Hier haben wir es ja mit allen Abbildungen $M [mm] \to [/mm] N$ zu tun. Ich würde versuchen, folgendes mit Induktion nach $m$ zu beweisen: Ist [mm] ${\cal A}(m,n)$ [/mm] die Menge aller Abbildungen [mm] $A_m\to A_n$, [/mm] so ist [mm] ${\cal A}(m,n)\sim A_{n^m}$. [/mm] Im Induktionsanfang ist [mm] ${\cal A}(1, n)\sim A_n$ [/mm] zu zeigen.
Hierzu muß man eine Bijektion [mm] ${\cal A}(1, n)\to A_n$ [/mm] angeben.
Im Induktionsschritt ist eine Bijektion [mm] ${\cal A}(m+1, n)\to A_{n^{m+1}}$ [/mm] zu konstruieren. Nach Induktionsvoraussetzung ist [mm] ${\cal A}(m,n)\sim A_{n^m}$ [/mm] und nach einem anderen Satz, den ihr vielleicht auch schon hattet, ist [mm] $\sharp(M\times N)=\sharp M\cdot \sharp [/mm] N$. Damit sollte der Induktionsschritt begründet werden können.
Damit hast Du [mm] $\sharp {\cal A}=n^m$ [/mm] bewiesen. Ist nun [mm] $\sharp [/mm] M =m $ und [mm] $\sharp [/mm] N = n$, und [mm] ${\cal B}$ [/mm] die Menge aller Abbildungen von $M$ nach $N$, so ist noch
[mm] ${\cal B} \sim {\cal A}$ [/mm] zu zeigen. Und fertig!
Dies ist alles nicht trivial, steckt aber hinter den intuitiven Argumenten traditioneller Analysisvorlesungen.
In der Hoffnung, nicht total verwirrt zu haben,
Wolfgang
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:29 So 23.10.2011 | | Autor: | Lustique |
> Nur am Rande: Wurde in der Vorlesung auch bewiesen:
> Aus [mm]M\sim A_n[/mm] und [mm]M\sim A_m[/mm] folgt [mm]m=n[/mm]?
> Nämlich nur dann ist [mm]\sharp M[/mm] ja definiert.
Nein, bewiesen wurde es nicht. Bei uns stand es als Anmerkung unter der Definition "Eine Menge heißt endlich, wenn...":
Bem.:
Es ist [mm] $A_n\sim A_m\Leftrightarrow [/mm] n=m$
Damit ist die obige Zuordnung wohldefiniert.
(Mit dem Hinweis, dass das in den Präsenzübungen bewiesen werden würde, allerdings erst in denen, die ab Morgen stattfinden.)
> Ich würde den Satz nicht dazu benutzen wollen. Hier haben
> wir es ja mit allen Abbildungen [mm]M \to N[/mm] zu tun. Ich würde
> versuchen, folgendes mit Induktion nach [mm]m[/mm] zu beweisen: Ist
> [mm]{\cal A}(m,n)[/mm] die Menge aller Abbildungen [mm]A_m\to A_n[/mm], so
> ist [mm]{\cal A}(m,n)\sim A_{n^m}[/mm]. Im Induktionsanfang ist
> [mm]{\cal A}(1, n)\sim A_n[/mm] zu zeigen.
> Hierzu muß man eine Bijektion [mm]{\cal A}(1, n)\to A_n[/mm]
> angeben.
Wie könnte man denn solch eine Bijektion aufschreiben? Solch eine Abbildung müsste doch "einfach" beispielsweise [mm] $\mathcal{A}(1,1)$ [/mm] auf [mm] $1\in A_n$, $\mathcal{A}(1,2)$ [/mm] auf [mm] $2\in A_n$, [/mm] also [mm] $\mathcal{A}(1,i)$ [/mm] auf [mm] $i\in A_n$ [/mm] mit [mm] $1\le [/mm] i [mm] \le [/mm] n$ abbilden, oder? Wie macht man daraus eine Abbildung? Bijektiv wäre sie ja, da alle Elemente von [mm] $A_n$, [/mm] also $i$ getroffen werden (surjektiv), und, da ja [mm] $\mathcal{A}(1,i)=\mathcal{A}(1,i')\leftrightarrow i=i'$ mit $i,i'\in A_n$ gilt, wäre sie ja auch injektiv.
Oder wäre die Abbildung einfach $F\colon \mathcal{A}(1,n) \to A_n$ mit $F(\mathcal{A}(1,i))=i$ für $1\le i\le n$?
Einfach ein $F\colon \mathcal{A}(m,n) \to A_{n^m}$ mit $F(\mathcal{A}(j,i))=i^j$ für $1\le i\le n$ und $1\le j \le m$ zu machen, wofür es in diesem Fall ja funktionieren würde, würde ja nicht gehen, oder?
> Im Induktionsschritt ist eine Bijektion [/mm] [mm]{\cal A}(m+1, n)\to A_{n^{m+1}}[/mm]
> zu konstruieren. Nach Induktionsvoraussetzung ist [mm]{\cal A}(m,n)\sim A_{n^m}[/mm]
> und nach einem anderen Satz, den ihr vielleicht auch schon
> hattet, ist [mm]\sharp(M\times N)=\sharp M\cdot \sharp N[/mm]. Damit
> sollte der Induktionsschritt begründet werden können.
[mm] $\sharp(M\times N)=\sharp M\cdot \sharp [/mm] N$ hatten wir leider in der Vorlesung noch nicht. Kann ich das Ganze trotzdem machen, oder müsste ich dann erst [mm] $\sharp(M\times N)=\sharp M\cdot \sharp [/mm] N$ beweisen?
> Damit hast Du [mm]\sharp {\cal A}=n^m[/mm] bewiesen. Ist nun [mm]\sharp M =m[/mm]
> und [mm]\sharp N = n[/mm], und [mm]{\cal B}[/mm] die Menge aller Abbildungen
> von [mm]M[/mm] nach [mm]N[/mm], so ist noch
> [mm]{\cal B} \sim {\cal A}[/mm] zu zeigen. Und fertig!
Äh, um [mm] ${\cal B} \sim {\cal A}$ [/mm] zeigen zu können, müsste ich doch Reflexivität, Transitivität und Symmetrie zeigen, also das es sich hierbei um eine Äquivalenzrelation handelt, weil dann die Mächtigkeit von [mm] ${\cal B}$ [/mm] und [mm] ${\cal A}$ [/mm] gegeben wäre, oder? Müsste ich dann nicht zeigen, dass es wiederum zwischen beiden Mengen eine bijektive Abbildung gibt?
> Dies ist alles nicht trivial, steckt aber hinter den
> intuitiven Argumenten traditioneller Analysisvorlesungen.
>
> In der Hoffnung, nicht total verwirrt zu haben,
> Wolfgang
Ja, trivial kommt es mir zumindest nicht vor. :D Ich glaube nicht, dass ich das jetzt allzu gut durchblickt habe, ehrlich gesagt. Total verwirrt bin ich zwar nicht unbedingt, aber wahrscheinlich schon ziemlich, auch wenn ich versuche dir zu folgen. Ich glaube langsam, mir fehlt es an mathematischer Intuition. :/
Aber danke für deine Bemerkungen.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:31 So 23.10.2011 | | Autor: | Helbig |
> > ist [mm]{\cal A}(m,n)\sim A_{n^m}[/mm]. Im Induktionsanfang ist
> > [mm]{\cal A}(1, n)\sim A_n[/mm] zu zeigen.
> > Hierzu muß man eine Bijektion [mm]{\cal A}(1, n)\to A_n[/mm]
> > angeben.
>
> Wie könnte man denn solch eine Bijektion aufschreiben?
> Solch eine Abbildung müsste doch "einfach" beispielsweise
> [mm]\mathcal{A}(1,1)[/mm] auf [mm]1\in A_n[/mm], [mm]\mathcal{A}(1,2)[/mm] auf [mm]2\in A_n[/mm],
> also [mm]\mathcal{A}(1,i)[/mm] auf [mm]i\in A_n[/mm] mit [mm]1\le i \le n[/mm]
> abbilden, oder? Wie macht man daraus eine Abbildung?
Nein, wir brauchen eine Abbildung von [mm] ${\cal A}(1, [/mm] n)$ nach [mm] $A_n$, [/mm] nicht [mm] ${\cal A}(1, [/mm] i)$ nach [mm] $A_n$. [/mm] Das $n$ ist fest.
Wie sehen jetzt die Elemente von [mm] ${\cal A}(1, [/mm] n)$ aus? Dies sind Abbildungen, die das einzige Element $1$ in [mm] $A_1$ [/mm] auf eines der $n$ Elemente in [mm] $A_n$ [/mm] abbilden. Eine Bijektion ist
[mm] $\Psi\colon {\cal A}(1,n)\to A_n\; f\mapsto [/mm] f(1)$.
[mm] $\Psi$ [/mm] ist injektiv, denn ist [mm] $\Psi(f)=\Psi(g)$, [/mm] so ist [mm] $f(1)=\Psi(f)=\Psi(g)=g(1)$, [/mm] also $f=g$.
[mm] $\Psi$ [/mm] ist surjektiv, denn zu [mm] $k\in A_n$ [/mm] gibt es ein $g$ mit $g(1)=k$, und es ist [mm] $\Psi(g)=k$. [/mm] Fertig!
> > Im Induktionsschritt ist eine Bijektion [mm]{\cal A}(m+1, n)\to A_{n^{m+1}}[/mm]
> > zu konstruieren. Nach Induktionsvoraussetzung ist [mm]{\cal A}(m,n)\sim A_{n^m}[/mm]
> > und nach einem anderen Satz, den ihr vielleicht auch schon
> > hattet, ist [mm]\sharp(M\times N)=\sharp M\cdot \sharp N[/mm]. Damit
> > sollte der Induktionsschritt begründet werden können.
>
> [mm]\sharp(M\times N)=\sharp M\cdot \sharp N[/mm] hatten wir leider
> in der Vorlesung noch nicht. Kann ich das Ganze trotzdem
> machen, oder müsste ich dann erst [mm]\sharp(M\times N)=\sharp M\cdot \sharp N[/mm]
> beweisen?
Na ja, eigentlich schon. Aber vielleicht darfst Du das als offensichtlich annehmen. Ohne diese Formel wäre der Induktionsschritt unnötig schwer.
Nehmen wir mal an, das dürfen wir annehmen: Definiere eine Funktion [mm] $\Psi\colon {\cal A}(m,n)\times A_n\to{\cal A}(m+1, n),\; [/mm] (f, [mm] k)\mapsto \Psi(f, [/mm] k)$. Dabei sei [mm] $\Psi(f, [/mm] k)(j) = f(j)$ für $j [mm] \in A_m$ [/mm] und [mm] $\Psi(f, [/mm] k)(m+1) = k$. Ähnlich wie oben zeigst Du nun, daß [mm] $\Psi$ [/mm] bijektiv ist. Zusammen mit der Formel für das kartesische Produkt und der Induktionsvoraussetzung ergibt sich nun
[mm] $\sharp {\cal A}(m+1, [/mm] n) = [mm] \sharp({\cal A}(m, n)\times A_n)=\sharp{\cal A}(m,n)\cdot \sharp A_n=n^m\cdot [/mm] n = [mm] n^{m+1}$. [/mm] Fertig!
>
> > Damit hast Du [mm]\sharp {\cal A}=n^m[/mm] bewiesen. Ist nun [mm]\sharp M =m[/mm]
> > und [mm]\sharp N = n[/mm], und [mm]{\cal B}[/mm] die Menge aller Abbildungen
> > von [mm]M[/mm] nach [mm]N[/mm], so ist noch
> > [mm]{\cal B} \sim {\cal A}[/mm] zu zeigen. Und fertig!
>
> Äh, um [mm]{\cal B} \sim {\cal A}[/mm] zeigen zu können, müsste
> ich doch Reflexivität, Transitivität und Symmetrie
> zeigen, also das es sich hierbei um eine
> Äquivalenzrelation handelt, weil dann die Mächtigkeit von
> [mm]{\cal B}[/mm] und [mm]{\cal A}[/mm] gegeben wäre, oder? Müsste ich dann
> nicht zeigen, dass es wiederum zwischen beiden Mengen eine
> bijektive Abbildung gibt?
Genau das muß Du zeigen. Und ich dachte bei Mengen $M$, $N$ bedeutet [mm] $M\sim [/mm] N$,
daß es eine Bijektion zwischen diesen Mengen gibt.
Dies geht so:
Nach Voraussetzung gibt es Bijektionen
[mm] $\phi\colon M\to A_m$ [/mm] und
[mm] $\psi\colon N\to A_n$.
[/mm]
Damit definiere die Abbildung
[mm] $\Psi\colon {\cal A}(m, n)\to {\cal A}(M, N),\; f\mapsto \psi^{-1}\circ f\circ \phi$ [/mm] und zeige, daß [mm] $\Psi$ [/mm] bijektiv ist. Fertig.
Wie gesagt, einfach ist es nicht. Aber einfacher kann ich diese Formel nicht begründen.
Trotzdem wünsche ich Dir viel Spaß bei den kommenden Beweisen.
Grüße,
Wolfgang
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:34 So 23.10.2011 | | Autor: | Lustique |
> Nein, wir brauchen eine Abbildung von [mm]{\cal A}(1, n)[/mm] nach
> [mm]A_n[/mm], nicht [mm]{\cal A}(1, i)[/mm] nach [mm]A_n[/mm]. Das [mm]n[/mm] ist fest.
> Wie sehen jetzt die Elemente von [mm]{\cal A}(1, n)[/mm] aus? Dies
> sind Abbildungen, die das einzige Element [mm]1[/mm] in [mm]A_1[/mm] auf
> eines der [mm]n[/mm] Elemente in [mm]A_n[/mm] abbilden. Eine Bijektion ist
> [mm]\Psi\colon {\cal A}(1,n)\to A_n\; f\mapsto f(1)[/mm].
> [mm]\Psi[/mm] ist
> injektiv, denn ist [mm]\Psi(f)=\Psi(g)[/mm], so ist
> [mm]f(1)=\Psi(f)=\Psi(g)=g(1)[/mm], also [mm]f=g[/mm].
> [mm]\Psi[/mm] ist surjektiv, denn zu [mm]k\in A_n[/mm] gibt es ein [mm]g[/mm] mit
> [mm]g(1)=k[/mm], und es ist [mm]\Psi(g)=k[/mm]. Fertig!
Ach schei-, ich glaube ich meinte eigentlich auch was anderes und habe mich nur verschrieben. Falsch wäre es aber wahrscheinlich trotzdem gewesen. :/
Aber gut, immerhin kann ich jetzt nach ein paar Minuten Nachdenken zumindest schon mal deinen Induktionsanfang nachvollziehen.
> Na ja, eigentlich schon. Aber vielleicht darfst Du das als
> offensichtlich annehmen. Ohne diese Formel wäre der
> Induktionsschritt unnötig schwer.
> Nehmen wir mal an, das dürfen wir annehmen: Definiere
> eine Funktion [mm]\Psi\colon {\cal A}(m,n)\times A_n\to{\cal A}(m+1, n),\; (f, k)\mapsto \Psi(f, k)[/mm].
> Dabei sei [mm]\Psi(f, k)(j) = f(j)[/mm] für [mm]j \in A_m[/mm] und [mm]\Psi(f, k)(m+1) = k[/mm].
> Ähnlich wie oben zeigst Du nun, daß [mm]\Psi[/mm] bijektiv ist.
> Zusammen mit der Formel für das kartesische Produkt und
> der Induktionsvoraussetzung ergibt sich nun
> [mm]\sharp {\cal A}(m+1, n) = \sharp({\cal A}(m, n)\times A_n)=\sharp{\cal A}(m,n)\cdot \sharp A_n=n^m\cdot n = n^{m+1}[/mm].
> Fertig!
Du wirst, wenn du das Folgende liest, wahrscheinlich in Gedanken die Hände über dem Kopf zusammenschlagen, aber warum genau bildet [mm] $\Psi$ [/mm] jetzt das kartesische Produkt von [mm] ${\cal A}(m,n)$ [/mm] und [mm] $A_n$ [/mm] auf [mm] ${\cal A}(m+1, [/mm] n)$, also [mm] $\Psi\colon {\cal A}(m,n)\times A_n\to{\cal A}(m+1, [/mm] n)$, ab? Das sieht jetzt so aus, als wäre die Funktion eine andere als die beim Induktionsanfang. Ich glaube um die Schritte zu verstehen, fehlt es mir an Erfahrung im Umgang mit Abbildungen, ehrlich gesagt. Hier hast du mich nämlich schon auf halbem Weg verloren, leider.
> Genau das muß Du zeigen. Und ich dachte bei Mengen [mm]M[/mm], [mm]N[/mm]
> bedeutet [mm]M\sim N[/mm],
> daß es eine Bijektion zwischen diesen
> Mengen gibt.
> Dies geht so:
> Nach Voraussetzung gibt es Bijektionen
> [mm]\phi\colon M\to A_m[/mm] und
> [mm]\psi\colon N\to A_n[/mm].
> Damit definiere die Abbildung
> [mm]\Psi\colon {\cal A}(m, n)\to {\cal A}(M, N),\; f\mapsto \psi^{-1}\circ f\circ \phi[/mm]
> und zeige, daß [mm]\Psi[/mm] bijektiv ist. Fertig.
Es sollte bei mir übrigens heißen: "weil dann die Mächtigkeit von [mm]{\cal B}[/mm] und [mm]{\cal A}[/mm] gleich wäre" und nicht "weil dann die Mächtigkeit von [mm]{\cal B}[/mm] und [mm]{\cal A}[/mm] gegeben wäre", aber das wirst du wahrscheinlich auch so erkannt haben.
Ja, ich habe gerade noch mal in meiner Vorlesungsmitschrift nachgeguckt. Die Def. war:
Zwei Mengen $M$ und $N$ heißen gleichmächtig, wenn es eine bijektive Abbildung [mm] $f\colon M\to [/mm] N$ gibt. In diesem Fall schreiben wir [mm] $M\sim [/mm] N$
Und darunter dann die Bemerkung dazu, dass man [mm] $\sim$ [/mm] auch eine Äquivalenzrelation nennt, und vorher in der Bemerkung, dass die Relation [mm] "$\sim$" [/mm] 3 Bedingungen erfüllt (Refelxivität, Transitivität, Symmetrie).
Ich habe mir das Ganze also "in der falschen Reihenfolge" gemerkt. :D
Ok, ich habe jetzt sogar schon mehrere Minuten gebraucht, um zu verstehen, warum du die Abbildungen so definierst... (also der Weg: [mm] "$M\overset{\phi}{\rightarrow} A_m\overset{f}{\rightarrow} A_n\overset{\psi^{-1}}{\rightarrow} [/mm] N$")
Ich glaube so schnell werde ich das nicht alles beweisen können, wenn ich mich da überhaupt komplett reinfuchsen kann. Da ich leider ein kleines Zeitproblem habe (Abgabe der Aufgaben ist am Mittwoch und ich habe nur noch den Dienstagnachtmittag Zeit mich da dran zu setzen), hätte ich noch mal eine Frage: Könnte ich denn meine ja anscheinend eigentlich unvollständigen Beweise zur Not trotzdem nehmen? Also die in meiner Ausgangsfrage? Blech/Stefan meinte ja, ich hätte bei beiden Beweis(versuchen) korrekt argumentiert. Außerdem kann ich mir nicht vorstellen, dass ein solcher Aufwand für diese Aufgabe vorgesehen ist (3-Punkte-Aufgabe bei 20 Punkten insgesamt). Ich weiß, ich habe gefragt, wie ich das Ganze formaler beweisen kann, aber mittlerweile bin ich an dem Punkt, dass es mir erst mal reichen würde, wenn ich es überhaupt bewiesen hätte.
> Wie gesagt, einfach ist es nicht. Aber einfacher kann ich
> diese Formel nicht begründen.
>
> Trotzdem wünsche ich Dir viel Spaß bei den kommenden
> Beweisen.
>
> Grüße,
>
> Wolfgang
Ja, irgendwann gehts nicht mehr einfacher. Aber trotzdem Danke für deine Erklärungen. Ich habe auf jeden Fall vor, mich auch noch mal an deinen Ansatz dran zu setzen (und selbst wenn nur aus dem simplen Grund, dass ich mich nicht damit zufrieden geben will, das nicht verstanden zu haben), aber ich befürchte, dass ich das wegen Zeitmangels nicht mehr rechtzeitig vor Abgabe schaffen würde. Daher auch meine Frage, ob ich denn mit meinen Beweisen schon etwas hätte, was ich so abgeben könnte.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 01:28 Mo 24.10.2011 | | Autor: | Helbig |
> meine Frage, ob ich denn mit meinen Beweisen schon etwas
> hätte, was ich so abgeben könnte.
Ja, ich denke auch, daß dieser Beweis nicht als Übung verlangt werden kann, zumal dazu einiges an Erfahrung mit Abbildungen etc. benötigt wird. Aber traditionell ist man wohl mit Deiner Lösung zufrieden. Halte Dich an den Vorschlag von felixf, der entspricht auch am ehesten meinem Vorschlag.
Viel Erfolg,
Wolfgang
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:58 So 23.10.2011 | | Autor: | felixf |
Moin,
> > da ich mit Kombinatorik etwas auf Kriegsfuß stehe, hätte
>
> Genauso wie ich! Weil in der Kombinatorik die Anzahl der
> Elemente einer endlichen Menge nicht so auf die Mengenlehre
> zurückgeführt wird, daß man damit Beweise führen kann.
das wuerde man machen, wenn es nicht dafuer sorgen wuerde das fast alle gar nichts mehr verstehen, weil's viel zu kompliziert und technisch wird 
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:22 So 23.10.2011 | | Autor: | Blech |
Hi,
Ich seh beim besten Willen nicht, warum Du die beiden per Induktion lösen sollst. Du hast bei beiden korrekt direkt argumentiert und dann die erste etwas gequält in die Induktion gepreßt. Was für eine schwachsinnige Aufgabe.
> Wie ich den Induktionsanfang formal aufschreiben soll, weiß ich ehrlich gesagt auch nicht so wirklich.
Ist M={a} und N={b}, dann ist offensichtlicherweise f(a)=b die einzig mögliche Abbildung.
Wenn Du wirklich penibel sein willst, dann kannst Du schreiben,
[mm] $\forall\ f:M\to [/mm] N$ und [mm] $g:M\to [/mm] N$ gilt, daß
[mm] $\forall x\in [/mm] M$ (d.h. a)
$g(a)=f(a)$ (=b, zwangsläufig, da $g(a), [mm] f(a)\in N=\{b\}$).
[/mm]
ciao
Stefan
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:54 So 23.10.2011 | | Autor: | felixf |
Moin,
> Ich seh beim besten Willen nicht, warum Du die beiden per
> Induktion lösen sollst. Du hast bei beiden korrekt direkt
> argumentiert und dann die erste etwas gequält in die
> Induktion gepreßt. Was für eine schwachsinnige Aufgabe.
per Induktion geht es wesentlich sauberer als ohne.
Schreibe $M = M' [mm] \cup \{ x \}$ [/mm] mit $x [mm] \not\in [/mm] M'$; jede Abbildung $f : M [mm] \to [/mm] N$ ist eindeutig bestimmt durch [mm] $f|_{M'} [/mm] : M' [mm] \to [/mm] N$ und $n [mm] \in [/mm] N$, was man durch eine Bijektion $Abb(M', N) [mm] \times [/mm] N [mm] \to [/mm] Abb(M, N)$, $(f', n) [mm] \mapsto \begin{cases} M \to N, \\ m \mapsto f(m) & \text{falls } m \in M', \\ m \mapsto n & \text{falls } m \not\in M' \end{cases}$ [/mm] zeigen kann.
Daraus folgt $|Abb(M, N)| = |Abb(M', N) [mm] \times [/mm] N|$. Wenn man jetzt gezeigt hat, dass $|A [mm] \times [/mm] B| = |A| [mm] \times [/mm] |B|$ ist folgt also die Behauptung per Induktion.
> > Wie ich den Induktionsanfang formal aufschreiben soll,
> weiß ich ehrlich gesagt auch nicht so wirklich.
Der Induktionsanfang ist $M = [mm] \emptyset$: [/mm] es gibt genau eine Abbildung [mm] $\emptyset \to [/mm] N$, und [mm] $x^0 [/mm] = 1$ per Definition fuer jedes $x [mm] \in \IN$. [/mm] Also gilt [mm] $|Abb(\emptyset, [/mm] N)| = [mm] |N|^{|\emptyset|}$.
[/mm]
(Auch hier sieht man wieder, warum man [mm] $0^0 [/mm] := 1$ definieren sollte  )
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:08 So 23.10.2011 | | Autor: | Helbig |
>
> (Auch hier sieht man wieder, warum man [mm]0^0 := 1[/mm] definieren
> sollte )
Leider ist [mm] $0\notin \IN$ [/mm] in der VL. Im Induktionsanfang muß man daher die Behauptung für $n=1$ zeigen.
>
> LG Felix
>
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:20 Di 25.10.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
