Anzahl Abbildungen Beweisen

16.11.2015, 06:53

Ruben765

Anzahl Abbildungen Beweisen

Meine Frage:
Hallo Leute, ich hab folgende Aufgabe bei der ich nicht weiter weiß:
Ich hab eine Menge X mit n Elementen und eine Menge Y mit m Elementen, nun soll ich mit vollständiger Induktion zeigen wie viele verschiedene Abbildungen es von X nach Y gibt, dabei soll m gegeben uns fest sein.

Wie genau soll ich das Beweisen? Ich kann mir das ganze irgendwie nicht vorstellen und weiß auch nicht wie ich das mathematische Begründen soll, dass es für alle n gilt ... könnt ihr mir da weiterhelfen?

Meine Ideen:
Ansatz: Erstmal hab ich mir Abbildungen mit 1-1 1-2 2-1 3-3 und 2-3 Elementen aufgemalt und bin auf $\begin{eqnarray*} m^{n} \end{eqnarray*}$ ist die Anzahl der möglichen Abbildungen gekommen.
Induktionsanfang: Wenn die Abbildende Menge nur ein Element enthält, hat $\begin{eqnarray*} X\Rightarrow Y \end{eqnarray*}$ genau so viele Abbildungen wie es m Elemente gibt
$\begin{eqnarray*} m^n=m^1=m \end{eqnarray*}$

Induktionsschritt: nun müssen wir zeigen, dass wenn wir die Abbildende Menge X um 1 Element vergrößern, $\begin{eqnarray*} m^{n+1} \end{eqnarray*}$ gilt

16.11.2015, 09:07

Elvis

Auf diesen Beitrag antworten »

Ja, das ist so, weil auch das m+1-te Element n mögliche Bilder hat. Mache eine Induktion über m, und halte n fest. Übrigens heißt X Definitionsbereich und Y Wertebereich.

16.11.2015, 15:46

Ruben765

Auf diesen Beitrag antworten »

Was genau bringt mir die Induktion über m, wenn m als fest angenommen wird? das macht dann doch keinen Sinn.

Ich hab keinerlei Ansatz wie ich das logisch begründen soll, dass für jedes weitere n (also n+1)
die Formel gelten soll....
nehmen wir an $\begin{eqnarray*} m^n \end{eqnarray*}$ = Anzahl der Abbildungen stimmt
bilden wir jetzt $\begin{eqnarray*} m^{n+1} \end{eqnarray*}$ erhöht sich die Anzahl der Abbildungen auf $\begin{eqnarray*} m^n*m \end{eqnarray*}$ aber wie kann ich dieses letzte mal m Begründen? woher kommt das bzw,was steck dahinter?

16.11.2015, 17:14

Elvis

Auf diesen Beitrag antworten »

Ich schlage vor : Induktion über $\begin{eqnarray*} m \end{eqnarray*}$ bei festem $\begin{eqnarray*} n \end{eqnarray*}$ . Das macht Sinn.
Du antwortest : Induktion über $\begin{eqnarray*} m \end{eqnarray*}$ bei festem $\begin{eqnarray*} m \end{eqnarray*}$ . Das macht keinen Sinn.
Meine Antwort auf Deine Antwort: stimmt, das macht keinen Sinn.

16.11.2015, 17:40

Ruben765

Auf diesen Beitrag antworten »

Du schlägst Induktion über m vor ,laut der Aufgabenstellung ist aber m fest und gegeben, falls du das nochmal nachlesen möchtest.

16.11.2015, 17:58

Elvis

Auf diesen Beitrag antworten »

Wenn ich nachlese, ist $\begin{eqnarray*} n \end{eqnarray*}$ die feste Anzahl der Elemente von $\begin{eqnarray*} X \end{eqnarray*}$ und $\begin{eqnarray*} m \end{eqnarray*}$ die feste Anzahl der Elemente von $\begin{eqnarray*} Y \end{eqnarray*}$ . So gesehen kann man gar keine Induktion machen. Big Laugh

Ich gebe zu dass ich beide Mengen miteinander verwechselt habe. Tut mir leid. als Entschädigung in der Induktion nach $\begin{eqnarray*} n \end{eqnarray*}$ bei festem $\begin{eqnarray*} m \end{eqnarray*}$ jetzt der Induktionsschritt:

Induktionsannahme: $\begin{eqnarray*} |X|=n, |Y|=m, |Abb(X,Y)|=m^n \end{eqnarray*}$
Induktionsschritt: $\begin{eqnarray*} |X\cup \{x\}|=n+1 \end{eqnarray*}$ , die Elemente von $\begin{eqnarray*} X \end{eqnarray*}$ werden nach Ind.Ann. durch $\begin{eqnarray*} m^n \end{eqnarray*}$ Abbildungen nach $\begin{eqnarray*} Y \end{eqnarray*}$ abgebildet, das neue Element $\begin{eqnarray*} x \end{eqnarray*}$ kann auf $\begin{eqnarray*} m \end{eqnarray*}$ Elemente aus $\begin{eqnarray*} Y \end{eqnarray*}$ abgebildet werden, also ergeben sich $\begin{eqnarray*} m^n*m=m^{n+1} \end{eqnarray*}$ Abbildungen. Somit ist $\begin{eqnarray*} |Abb(X\cup \{x\},Y)|=m^{n+1} \end{eqnarray*}$ .

(Uff, das war eine schwere Geburt.)

16.11.2015, 18:35

Ruben765

Auf diesen Beitrag antworten »

Zitat:

neue Element $\begin{eqnarray*} x \end{eqnarray*}$ kann auf $\begin{eqnarray*} m \end{eqnarray*}$ Elemente aus $\begin{eqnarray*} Y \end{eqnarray*}$ abgebildet werden

Genau das hat mir gefehlt. Dadurch, dass ich mir Mengen aufgemalt habe und die immer mit Pfeilen(Abbildung) verbunden habe um einen Zusammenhang zusehen, hatte ich immer ein festes n und ein festes m.
Also im Endeffekt wenn ich die Menge X um ein Element erweitere, kann das neue auf jedes einzelne Element von Y abbilden.

Super, vielen Dank smile

16.11.2015, 18:38

Elvis

Auf diesen Beitrag antworten »

Genau so. Die für X möglichen Abbildungen bleiben in der Induktionsannahme erhalten und werden mit m Abbildungen des neuen Elements zu Abbildungen der vergrößerten Menge vervielfacht.

Neue Frage »

Antworten »

Anzahl Abbildungen Beweisen

Verwandte Themen