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.