Induktionsbeweis mit Mengen

Wissenschaft Physik
1

Hallo!

Ich habe Probleme mit folgender Aufgabe:

Es seien M eine m-elementige und N eine n-elementige Menge, wobei m>0. Zeigen Sie, dass es m^n (m hoch n) verschiedene Abbildungen von N in M gibt.
Hinweis: Vollständige Induktion über n. Es gibt genau eine Abbildung von der leeren Menge in die Menge M. (warum?)

Ok. Klar, dass es genau eine Abbildung von der leeren Menge in die Menge m gibt. m hoch Anzahl der Elemente=m hoch 0=1.

Aber wie komm ich jetzt von da zu meinem Induktionsanfang?
Oder gilt: m hoch n=n+1? (Kann ich mir eigentlich nicht vorstellen und das klappt auch nicht, wenn ich es anhand von Beispielmengen zeigen will).

Also mal als Beispiel wähle ich für die Menge m={1,2,3} und für n={2,3}. Laut Behauptung gibt es also m hoch n Abbildungen das wären hier 3 hoch 2 = 9 Abbildungen von N in M. Das wären doch dann die Abbildungen:
(2,1),(2,2),(2,3),(3,1),(3,2),(3,3) = m hoch n = 3 hoch 2 = 6 Abbildungen, oder?
Wähle ich jetzt n als die leere Menge, also n={} und wähle m weiterhin mit m={1,2,3}. Dann gibt es also m hoch n = 3 hoch 0 = 1 Abbildung.
Und wie lautet die? Ich soll doch dann {} in {1,2,3} abbilden. Das ergibt doch dann wieder {}. Und das müßte genau diese eine Abbildung sein.

Aber weiter kam ich mit meinen Überlegungen noch nicht und frage mich immer noch, wie ich von m hoch n mit n=0 also m hoch n=1 auf meine weiter komme, bzw. was ich damit anstellen soll, um meine Induktion weiterzuführen.

Genau da liegt jetzt mein Problem.

Wer kann mir da helfen?
Gruß, Ralf

2

hi,

Es seien M eine m-elementige und N eine n-elementige Menge,
wobei m>0. Zeigen Sie, dass es m^n (m hoch n) verschiedene
Abbildungen von N in M gibt.
Hinweis: Vollständige Induktion über n. Es gibt genau eine
Abbildung von der leeren Menge in die Menge M. (warum?)

Ok. Klar, dass es genau eine Abbildung von der leeren Menge in
die Menge m gibt. m hoch Anzahl der Elemente=m hoch 0=1.

Aber wie komm ich jetzt von da zu meinem Induktionsanfang?
Oder gilt: m hoch n=n+1? (Kann ich mir eigentlich nicht
vorstellen und das klappt auch nicht, wenn ich es anhand von
Beispielmengen zeigen will).

du meinst induktionsschritt. induktionsanfang hast du schon.

geh also davon aus, dass zwischen der menge N und der menge M m^n abbildungen existieren.
nun erweiterst du die menge N um ein element zur menge N’. N’ hat dann n+1 elemente.
nun kannst du jede funktion f: N -> M auf m arten zu einer funktion
f: N’ -> M erweitern, nämlich indem du dem zusätzlichen element einen der m werte aus M zuordnest.

d.h. du bekommst zu jeder funktion f: N -> M m erweiterungen. das sind dann m^n * m = m^(n+1) funktionen. und das sind sicher alle, denn eingeschränkt auf N muss jede schon vorher in den m^n enthalten gewesen sein.

hth
m.

3

hi,

und nun noch zum beispiel …

Also mal als Beispiel wähle ich für die Menge m={1,2,3} und
für n={2,3}. Laut Behauptung gibt es also m hoch n Abbildungen
das wären hier 3 hoch 2 = 9 Abbildungen von N in M. Das wären
doch dann die Abbildungen:
(2,1),(2,2),(2,3),(3,1),(3,2),(3,3) = m hoch n = 3 hoch 2 = 6
Abbildungen, oder?

3 hoch 2 ist 9, nicht 6. und deine zahlenpaare sind noch keine abbildungen. eine abbildung ist im wesentlich eine menge von zahlenpaaren, in denen in der ersten komponente alle elemente von N jeweils genau einmal vorkommen.

nimm besser N = {a,b}
die abbildungen sind dann:
1: (a,1), (b,1)
2: (a,1), (b,2)
3: (a,1), (b,3)
4: (a,2), (b,1)
5: (a,2), (b,2)
6: (a,2), (b,3)
7: (a,3), (b,1)
8: (a,3), (b,2)
9: (a,3), (b,3)

Wähle ich jetzt N als die leere Menge, also N={} und wähle M
weiterhin mit M={1,2,3}. Dann gibt es also m hoch n = 3 hoch 0
= 1 Abbildung.
Und wie lautet die? Ich soll doch dann {} in {1,2,3} abbilden.
Das ergibt doch dann wieder {}. Und das müßte genau diese eine
Abbildung sein.

naja: wenn N leer ist, ist auch die menge der paare aus N x M leer. und das ist die eine funktion. (funktion ist genau genommen das tripel aus (N, M, G), wobei G (der „graph“) die menge der paare ist. ist N = {}, dann gibts eben ({}, M, {}) als die eine funktion.

wenn dir das zu unheimlich ist, mach den induktionsanfang für eine einelementige menge N. da gibts genau m mögliche funktionen: du kannst dem einen ding in N auf m verschiedene weisen dinge aus M zuordnen. anzahl also m = m^1.

hth
m.