Anzahl der Abbildungen A --> B

22.10.2010, 18:45

kleene-miss

Anzahl der Abbildungen A --> B

Meine Frage:
Hallo smile

Wir haben auf unserem Übungsblatt folgende Aufgabe:

Die Mengen A und B seien durch A={alpha, beta, gamma} und b={a,b,c,d,e} definiert.
(a) Wie viele Abbildungen A --> B und wie viele Abbildungen B --> A gibt es?

aber wie kann ich des denn beweisen? weil die Profs wollen ja immer alles bewisen haben.

Kann mir da jemand helfen?

Gleiches bei der Teilaufgabe (c) Wie viele injektive Abbildungen A-->B und wie vele surjektive Abbildungen B-->A gibt es?

aber wie beweis ich des?

Danke schonmal für eure Antworten!!

Grüßle Nadine

Meine Ideen:
(a) Etz is es ja logisch und auch von den stohastischen Formeln die ma in der Schule lernt klar ersichtlich dass es bei A-->B 5^3 Möglichkeiten hat und bei B-->A 3^5

(c) da hab ich 60 und 150

22.10.2010, 19:53

Elvis

Auf diesen Beitrag antworten »

Die Aufgabe a) ist bewiesen, wenn du bewiesen hast, dass die Anzahl der Abbildungen von $\begin{eqnarray*} X \end{eqnarray*}$ nach $\begin{eqnarray*} Y \end{eqnarray*}$ gleich $\begin{eqnarray*} |Y|^{|X|} \end{eqnarray*}$ ist.
Für endliche Mengen schlage ich einen Beweis mittels vollständiger Induktion vor.

Wie kommst du auf 60 und 150 ??? Bitte, bitte einen Beweis. Augenzwinkern

22.10.2010, 19:57

kleene-miss

Auf diesen Beitrag antworten »

Zitat:

Original von Elvis
Die Aufgabe a) ist bewiesen, wenn du bewiesen hast, dass die Anzahl der Abbildungen von $\begin{eqnarray*} X \end{eqnarray*}$ nach $\begin{eqnarray*} Y \end{eqnarray*}$ gleich $\begin{eqnarray*} |Y|^{|X|} \end{eqnarray*}$ ist.
Für endliche Mengen schlage ich einen Beweis mittels vollständiger Induktion vor.

Wie kommst du auf 60 und 150 ??? Bitte, bitte einen Beweis. Augenzwinkern

ja ich weiß schon, dass die Anzahl der Abbildungen von $\begin{eqnarray*} X \end{eqnarray*}$ nach $\begin{eqnarray*} Y \end{eqnarray*}$ gleich $\begin{eqnarray*} |Y|^{|X|} \end{eqnarray*}$ ist. Und dass ich genau des beweisen muss. aber wie setz ich da an? ich hab da echt keinerlei Vorstellung, wie ich da anfangen muss!

Und auf die Zahlen komm ich folgendermaßen:
5⋅4⋅3=60 oder 5!/2!=60
und
35-(3+(4 aus 5)⋅3⋅2+(3 aus 5)⋅3⋅2)=150
(also: alle möglichekeiten -( (Alle Möglichkeiten dass a,b,c,d,e auf einen gr. Buchstaben fallen)+(Alle Möglchkeiten dass vier der Buchstaben auf einen gr. BUchstaben fallen und der 5 Buchstabe dann auf einen der übrigen gr. BUchstaben) +( alle Mögl. dass 3 Buchstaben auf einen gr. Buchstaben fallen und dann die 2 übrigen Buchstaben auf einen der beiden gr. BUchstaben fallen)

22.10.2010, 20:01

kleene-miss

Auf diesen Beitrag antworten »

Zitat:

5⋅4⋅3=60 oder 5!/2!=60
und
35-(3+(4 aus 5)⋅3⋅2+(3 aus 5)⋅3⋅2)=150

so sollte des natürlich net dastehen^^
nochmal:

5*4*3=60 oder 5!/2!=60
und
3^5 - ( 3 + (4 aus 5)*3*2 + (3 aus 5)*3*2) = 150

22.10.2010, 20:02

Elvis

Auf diesen Beitrag antworten »

Bei vollständiger Induktion fängt man immer mit dem Induktionsanfang an.

22.10.2010, 20:25

kleene-miss

Auf diesen Beitrag antworten »

d.h.?^^

23.10.2010, 11:21

Elvis

Auf diesen Beitrag antworten »

$\begin{eqnarray*} |X|=1\Rightarrow |X\to Y|=|Y|=|Y|^1=|Y|^{|X|} \end{eqnarray*}$

Möchtest du nur Fragen stellen, oder fängst du gelegentlich an zu denken ?

23.10.2010, 12:33

René Gruber

Auf diesen Beitrag antworten »

Nun mal nicht gleich so aggressiv:

In der Aufgabenstellung ist nichts zu lesen vom Beweis einer allgemeinen Aussage A(n), die man vielleicht mit irgendeinem Induktionsbeweis erledigen könnte bzw. müsste. Sondern es sind konkrete Mengen vorgegeben, und die geforderte Anzahl der Abbildungen kann man mit bekannten kombinatorischen Anzahlformeln (hier: Variationen mit sowie ohne Zurücklegen) direkt bestimmen. Es ist also nicht nötig, Fragestellern irgendwas aufzudrängen, was hier gar nicht gebraucht wird.

Und wenn auch die Lesbarkeit des Formelaufschriebs anfänglich ziemlich misslungen war, so sind die Rechnungen von kleene-miss ja als durchaus richtig einzuschätzen.

Bei der Anzahl der surjektiven Abbildungen $\begin{eqnarray*} B \to A \end{eqnarray*}$ würde ich lediglich noch einen für beliiebige endliche $\begin{eqnarray*} A,B \end{eqnarray*}$ besser verallgemeinerbaren Weg vorschlagen, nämlich über die Siebformel:

$\begin{eqnarray*} 3^5 - \binom{3}{1}\cdot 2^5 + \binom{3}{2}\cdot 1^5 = 243 - 96 + 3 = 150 \end{eqnarray*}$

23.10.2010, 13:48

kleene-miss

Auf diesen Beitrag antworten »

Zitat:

Original von René Gruber
Nun mal nicht gleich so aggressiv:

In der Aufgabenstellung ist nichts zu lesen vom Beweis einer allgemeinen Aussage A(n), die man vielleicht mit irgendeinem Induktionsbeweis erledigen könnte bzw. müsste. Sondern es sind konkrete Mengen vorgegeben, und die geforderte Anzahl der Abbildungen kann man mit bekannten kombinatorischen Anzahlformeln (hier: Variationen mit sowie ohne Zurücklegen) direkt bestimmen. Es ist also nicht nötig, Fragestellern irgendwas aufzudrängen, was hier gar nicht gebraucht wird.

Und wenn auch die Lesbarkeit des Formelaufschriebs anfänglich ziemlich misslungen war, so sind die Rechnungen von kleene-miss ja als durchaus richtig einzuschätzen.

Bei der Anzahl der surjektiven Abbildungen $\begin{eqnarray*} B \to A \end{eqnarray*}$ würde ich lediglich noch einen für beliiebige endliche $\begin{eqnarray*} A,B \end{eqnarray*}$ besser verallgemeinerbaren Weg vorschlagen, nämlich über die Siebformel:

$\begin{eqnarray*} 3^5 - \binom{3}{1}\cdot 2^5 + \binom{3}{2}\cdot 1^5 = 243 - 96 + 3 = 150 \end{eqnarray*}$

super vielen Dank smile

wir ham des damals in der Schule alles total komisch und verwirrend gmacht daher hatte ich davon nicht so wirklich ne ahnung und habs mir halt logisch überlegt Augenzwinkern

aber die formel is super smile

danke

05.12.2020, 15:11

tewmp

Auf diesen Beitrag antworten »

Allgemeiner Fall
Ich habe diese Aufgabe in meinem Studium als Hausübung bekommen mit dem Unterschied, dass wir die Formel für den Algemeinfall beweisen sollen. Könnten sie das auch zeigen oder einen Ansatz geben smile

05.12.2020, 18:08

Elvis

Auf diesen Beitrag antworten »

Behauptung: $\begin{eqnarray*} |Y^X|=|Y|^{|X|} \end{eqnarray*}$
Beweis durch vollständige Induktion nach $\begin{eqnarray*} n=|X| \end{eqnarray*}$
Induktionsanfang $\begin{eqnarray*} n=1 \end{eqnarray*}$ : Jedem $\begin{eqnarray*} x\in X \end{eqnarray*}$ wird genau ein $\begin{eqnarray*} y\in Y \end{eqnarray*}$ zugeordnet. Da in $\begin{eqnarray*} X \end{eqnarray*}$ genau ein Element liegt, wird diesem genau ein Element aus $\begin{eqnarray*} Y \end{eqnarray*}$ zugeordnet. Das sind $\begin{eqnarray*} |Y| \end{eqnarray*}$ paarweise verschiedene Abbildungen. Also $\begin{eqnarray*} |Y^X|=|Y|=|Y|^1=|Y|^{|X|} \end{eqnarray*}$
Induktionsschluss von $\begin{eqnarray*} n \end{eqnarray*}$ auf $\begin{eqnarray*} n+1 \end{eqnarray*}$ : Wähle ein $\begin{eqnarray*} x_0\in X \end{eqnarray*}$ fest, dann hat $\begin{eqnarray*} X\backslash \{x_0\} \end{eqnarray*}$ genau $\begin{eqnarray*} n \end{eqnarray*}$ Elemente. Nach Induktionsvoraussetzung gibt es genau $\begin{eqnarray*} |Y|^n \end{eqnarray*}$ paarweise verschiedene Abbildungen $\begin{eqnarray*} X\backslash \{x_0\}\to Y \end{eqnarray*}$ , diese ergänzen wir durch die $\begin{eqnarray*} |Y| \end{eqnarray*}$ Zuordnungen $\begin{eqnarray*} \{x_0\}\to Y \end{eqnarray*}$ (vgl. Induktionsanfang) zu $\begin{eqnarray*} |Y|^n\cdot |Y|=|Y|^{n+1}=|Y|^{|X|} \end{eqnarray*}$ paarweise verschiednen Abbildungen $\begin{eqnarray*} X\to Y \end{eqnarray*}$ .
qed

Hinweis: Für nichtendliche Mengen versuche dasselbe mit transfiniter Induktion, mein Gefühl sagt mir, dass das aufgrund des Wohlordnungssatzes möglich sein sollte, ohne Gewähr. Bei bedarf nachlesen bei Oliver Deiser, Einführung in die Mengenlehre.

Neue Frage »

Antworten »

Anzahl der Abbildungen A --> B

Verwandte Themen