Ist A gleichmächtig zum kartesischen Produkt M x M?
A := {f | f : {0, 1} → M Abbildung}
M ist eine Menge
2 Antworten
Versuche eine Bijektion zwischen den beiden Mengen zu konstruieren.
Wenn es eine existiert, dann sind die Menge. Gleichmächti.
Na überkege doch, wie du eine Abbildung von A nach MxM definieren könntest.
Ich kann eine Funktion k(x) = f(0) und f(1) aufstellen und dann?
Ich habe keine Ahnung, was du mit
Ich kann eine Funktion k(x) = f(0) und f(1) aufstellen
Meinst.
Kannst du bitte ordentlich aufschreiben, von wo nach wo k abbildet und wie deine Funktionsvorschrift lautet?
Allgemein gilt: Die Menge aller Abbildungen von A nach B hat |B|^|A| viele Elemente. Deshalb schreibt man die Menge auch als B^A.
In deinem Fall also |M|^2 viele.
Das ist auch die Mächtigkeit von MxM.
Oder anders erklärt:
Die 1 und die 0 dürfen jeweils nur auf genau ein Element auf M abgebildet werden. Wie viele Möglichkeiten gibt es 2 Elemente aus M auszuwählen? => |M|*|M| = |M|^2
Hier eine Erklärung:
Jedes Element aus A wird auf genau ein Element aus B abgebildet.
Hat A nur 1 Element, gibt es also genau so viele Möglichkeiten Funktionen zu bilden, wie B Elemente hat. Nämlich jeweils die Abbildung von dem einen Element aus A auf eines der Elemente aus B. Also |B| Möglichkeiten.
Hast du 2 Elemente in A, hast du für das erste Element wieder die gleichen |B| Möglichkeiten. Für jede dieser |B| Möglichkeiten hast du aber nochmal |B| Möglichkeiten das zweite Element abzubilden. Also |B| mal |B| viele Möglichkeiten insgesamt.
(Falls das nicht offensichtlich ist, stell dir vor du schreibst alle Möglichkeiten für das erste Element zeilenweise auf - |B| Zeilen - und dann zu jeder dieser Elemente alle Möglichkeiten das 2. Element abzubilden - also nochmal alle Elemente aus B pro Zeile. Dann hast du |B| Zeilen mit |B| Elementen. Also eine |B|x|B| Matrix und jedes Feld steht für eine Mögliche Abbildung)
Für 3 Elemente hast du für jede der |B| * |B| Möglichkeiten nochmal |B| Möglichkeiten das 3. abzubilden. Also |B|^3. Spätestens hier sollte auffallen, dass man also immer |B|^|A| viele Möglichleiten hat.
Das ist so natürlich kein Beweis für deine Frage, nur eine Erklärung. Möchtest du es beweisen, solltest du wie Jangler geschrieben hat eine Bijektion aufstellen. Oder nach dem Schema wie ich es allgemeiner beschrieben habe, vollständige Induktion.
Wie gehe ich da vor?