Seien M und N endliche Mengen mit m = |M| und n = |N|. Wie viele Funktionen gibt es von M x N nach P(M)?

Question

Aufgabe:

Seien M und N endliche Mengen mit m = |M| und n = |N|. Wie viele Funktionen gibt es von M x N nach P(M)?

Problem/Ansatz:

Ich verstehe hier überhaupt nicht, was ich machen muss. Laut Produktregel gilt ja: |M x N| = |M| * |N|.

Bei dieser Aufgabe hier weiß ich aber überhaupt nicht, was ich tun soll.

P(M) Wäre die Potenzmene von M. (P(M) := { X | X ⊆ M} die Potenzmenge von M).

Laut Definition bzw. Beispiel aus einem Buch gilt:

Falls M = {1,2} und N = {a,b,c}, so gilt:

M x N = {(1,a), (1,b), (1,c), (2,a), (2,b), (2,c)}

und P(M) = {∅, {1}, {2}, {1,2}},

was mir auch einleuchtet.

Aber laut Aufgabenstellung gibt es ja dieses Mal keine zugewiesenen Werte. Das heißt, ich würde das Ganze dann so beantworten:

Es gibt so viele Funktionen, soviel gemeinsame Elemente es jeweils in den Mengen M und N gibt, sowie zusätzlich eben noch die zusammengesetzten (wie m Beispiel in P(M) mit {1,2} und eben die leere Menge.

Answer 1

Es gibt \(\left|B\right|^{\left|A\right|}\) Funktionen von \(A\) nach \(B\), weil jedes \(a\in A\) auf eines von \(|B|\) Elementen abgebildet werden kann.

Seien M und N endliche Mengen mit m = |M| und n = |N|. Wie viele Funktionen gibt es von M x N nach P(M)?

Stelle \(|M \times N|\) und \(|P(M)|\) mittels \(m\) und \(n\) dar und setze in obige Formel ein.

Comments

Hi, ich bins nochmal.

Also wenn |M x N| = |M| * |N| gilt, dann folgt ja,

da |M| = m und |N| = n:

|M x N| = |M| * |N| = m * n.

Wie geht es dann aber weiter?

also würde m * n auf P(M) abgebildet werden,

wobei P(M) = P(m) ?

---

Es gibt \(\left|B\right|^{\left|A\right|}\) Funktionen von \(A\) nach \(B\)

Einsetzten von \(M\times N\) für \(A\) und \(P(M)\) für \(B\) ergibt:

(1)        Es gibt \(\left|P(M)\right|^{\left|M\times N\right|}\) Funktionen
             von \(M\times N\) nach \(P(M)\).

|M x N| = |M| * |N| = m * n.

Einsetzen in (1) ergibt:

(2)        Es gibt \(\left|P(M)\right|^{m\cdot n}\) Funktionen
             von \(M\times N\) nach \(P(M)\).

Stelle \(|P(M)|\) mittels \(m\) und \(n\) dar und setze in (2) ein.

---

Wie stelle ich |P(M)| mittels m und n dar? Das wäre ja dann |P(M)| = |P(m)| oder nicht? Und das setze ich dann ein, und dann?

---

Wie stelle ich |P(M)| mittels m und n dar?

Irgendwo in deinen Unterlagen müsste stehen, wie man aus der Mächtigkeit \(m\) der Menge \(M\) die Mächtigkeit der Potenzemenge von \(M\) bestimmt.

|P(M)| = |P(m)|

Was ist P(m)?

---

Naja, |M| ist doch = m.

---

Was ist P(m)?

---

Das weiß ich ja leider nicht.

Aber wenn ich die Potenzmenge von M bestimmen möchte, muss sie doch endlich sein.

Das hat glaube ich etwas mit der Unendlichkeit und Kardinalität zu tun. So richtig etwas dazu finde ich aber leider nicht im Skript.

---

Es ist \(|P(A)| = 2^{|A|}\) für jede Menge \(A\).

---

Dieser Sachverhalt wurde hier gestern erörtert.

---

Ok. Dann gibt es 2^{|M| (hoch: m*n)} Funktionen von M x N nach P(M).

Das wars dann? oder muss ich noch was weiter rechnen/zeigen?

---

Du musst noch weiter rechnen.

2^{|M| (hoch: m*n)}

Ich kenne diese Notation nicht.