Kardinalität von Potenzmengen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Zeige, dass |A| < [mm] |\mathcal{P}(A)|. [/mm] |
Ich wollte wissen, ob meine Lösung formal richtig ist.
Es habe A genau n [mm] \in \IN [/mm] Elemente.
Dann hat A eine Mächtugkeit von n und [mm] \mathcal{P}(A) [/mm] eine Mächtigkeit von [mm] 2^{n}.
[/mm]
Also n < [mm] 2^{n}, [/mm] was für alle n [mm] \in \IN [/mm] erfüllt ist.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:54 Sa 16.01.2016 | | Autor: | Reynir |
Hi,
es kommt darauf an, was dein A ist, wenn es nicht endlich ist, wird die Aussage so nicht gehen, weil die Aussage für endliche Mengen gilt.
Viele Grüße,
Reynir
|
|
|
| |
|
Warum?
Egal wie viele Elemente die Menge A hat, die Ungleichung ist doch für beliebig große n erfüllt
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:19 Sa 16.01.2016 | | Autor: | Reynir |
Hi,
das stimmt, aber eben für ein bestimmtes n und nicht für [mm] $\infty$, [/mm] du kannst für das Intervall $[0,1]$ keine Kardinalität der Potenzmenge angeben. Du wirst mir sicher zustimmen, dass bei [mm] $\infty<2^{\infty}$ [/mm] die Relation nicht so viel Sinn macht, oder?
Viele Grüße,
Reynir
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:24 So 17.01.2016 | | Autor: | Reynir |
Überlege dir, dass für eine beliebige Menge A gilt, dass jedes Element x aus A eine Teilemenge [mm] ($\{x\}$) [/mm] davon ist. Zudem sind A selbst und die leere Menge Teilmengen nach Definition, was selbst für [mm] $A=\{x\}$ [/mm] impiziert
$|A|<|P(A)|$.
Viele Grüße,
Reynir
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:42 So 17.01.2016 | | Autor: | Gonozal_IX |
Hiho,
> Überlege dir, dass für eine beliebige Menge A gilt, dass
> jedes Element x aus A eine Teilemenge ([mm]\{x\}[/mm]) davon ist.
> Zudem sind A selbst und die leere Menge Teilmengen nach
> Definition, was selbst für [mm]A=\{x\}[/mm] impiziert
> [mm]|A|<|P(A)|[/mm].
Ja, für $[mm]A=\{x\}[/mm]$ funktioniert das, weil A dann endlich ist.
Du wurdest bereits darauf hingewiesen, dass deine Argumentation für $|A| = [mm] \infty$ [/mm] falsch ist!
Du behauptest nämlich: Weil $|A| [mm] \le [/mm] |P(A)|$ und es von der Anzahl mindestens 2 Elemente mehr in $P(A)$ als in A gibt, gilt $|A| < |P(A)|$
Und das ist schlichtweg Blödsinn, denn: [mm] $\infty [/mm] + 2 = [mm] \infty$
[/mm]
Nach deiner Theorie wäre die Kardinalitäten von [mm] $\IN$ [/mm] und [mm] $\IZ$ [/mm] verschieden, denn schließlich gilt [mm] $\IN \subseteq \IZ$ [/mm] und $-1 [mm] \in \IZ$ [/mm] aber $-1 [mm] \not\in \IN$
[/mm]
Aber es gilt [mm] $|\IN| [/mm] = [mm] |\IZ|$
[/mm]
Gruß,
Gono
> Viele Grüße,
> Reynir
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:14 So 17.01.2016 | | Autor: | Reynir |
Hi,
also ich wurde auf nichts hingewiesen. ;) Und meine Anmerkung sollte lediglich eine - wenn auch nicht ganz korrekte - Vorstellung zu der von Fred angedeuteten Relation liefern. Ich habe mit keinem Wort sagen wollen, dass das die Aufgabe löst.
Viele Grüße,
Reynir
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 09:27 So 17.01.2016 | | Autor: | fred97 |
Fall 1: A = [mm] \emptyset. [/mm] Dann dürfte die Behauptung klar sein.
Fall 2: A [mm] \ne \emptyset.
[/mm]
Betrachte [mm] $M:=\{\{x\}: x \in A\} \subseteq \mathcal{P}(A)|. [/mm] $
Dann haben wir $|A|= |M|. $. Somit ist $|A| [mm] \le |\mathcal{P}(A)|. [/mm] $
Wäre nun $|A| = [mm] |\mathcal{P}(A)|, [/mm] $ so gäbe es eine Bijektion $f:A [mm] \to \mathcal{P}(A)$.
[/mm]
Zeige: keine(!) Abbildung $f:A [mm] \to \mathcal{P}(A)$ [/mm] ist surjektiv !
FRED
|
|
|
| |
|
Dass die Behauptung für unendliche Mengen ebenfalls gilt, hat erst um 1850 der Mathematiker Cantor - der Begründer der Mengenlehre - herausgefunden.
Bei unendlichen Mengen folgt aus A [mm] \subset [/mm] B und A [mm] \ne [/mm] B noch lange nicht |A|<|B|. So ist z.B. 2 [mm] \IZ [/mm] (die Menge der geraden Zahlen) [mm] \subset \IZ [/mm] und ungleich, aber trotzdem sind beide gleich mächtig, denn wenn du jede ganze Zahl verdoppelst erhältst du die geraden Zahlen, und wenn du diese durch 2 dividierst wieder die ganzen Zahlen, also gibt es in beiden Mengen gleich viele Elemente.
Vergleichst du A und $ [mm] \mathcal{P}(A) [/mm] $ miteinander, so bleiben in $ [mm] \mathcal{P}(A) [/mm] $ immer Mengen übrig, für die du in A kein Urbild hast.
BEWEIS:
Annahme: Zu jedem Element aus $ [mm] \mathcal{P}(A) [/mm] $ - also jeder Teilmenge von A - gibt es ein x aus A, das dessen Urbild ist. Dabei wurde jedem x aus A genau eine solche Teilmenge zugeordnet.
Ein paar dieser Zuordnungen erfasse ich nun mal tabellarisch, um besser argumentieren zu können. Ich habe sie durchnummeriert, aber tatsächlich müssen sie sich gar nicht nummerieren lassen, z.B. wenn die Menge A überabzählbar ist.
[mm] x_1 \mapsto A_1= \{3,4,5,r,t,x_1,n,20\}
[/mm]
[mm] x_2 \mapsto A_2= \{34,44,r,t,x_1,n,66\}
[/mm]
7 [mm] \mapsto A_3= [/mm] {5,6,7}
4 [mm] \mapsto A_4= [/mm] {3,5,9}
...
Wobei [mm] x_1, x_2,3,4,5,6,7,9,r,t,n,20,34,44,66,... \in [/mm] A sind.
Auf diese Weise könnten wir zu jedem Element von A (links) die zugehörige Menge [mm] A_i [/mm] hinschreiben. Jetzt stellen wir uns vor, dass die Tabelle komplett ist (auch wenn man sie bei unendlich vielen Elementen nicht hinschreiben kann). Wir sehen dann, dass [mm] A_1 [/mm] genau das Element [mm] x_1 [/mm] enthält, das seinem Urbild entspricht. Bei [mm] A_2 [/mm] ist das nicht der Fall, es enthält [mm] x_2 [/mm] nicht. [mm] A_3 [/mm] wiederum enthält sein Urbild 7, [mm] A_4 [/mm] sein Urbild 4 aber nicht.
Wir gehen nun die linke Spalte durch und notieren alle Elemente aus A, die nicht(!) in ihrer Zielmenge [mm] A_i [/mm] liegen.
In unserem Beispiel wären das [mm] x_2 [/mm] und 4 (und die, die noch in der Tabelle folgen). Die Menge dieser Urbilder bildet ebenfalls eine Untermenge U von A, U = [mm] \{x_2, 4,...\}. [/mm] Dabei kann U auch die leere Menge sein.
Die Menge U suchen wir nun rechts in der Tabelle, sie muss ja schon da sein - aber wir werden sie nicht finden, weil sie eben nicht erfasst werden kann! (Beweis s.u.) Obwohl jedem Element aus A eine Untermenge [mm] A_i [/mm] zugeordnet wurde, ist U nicht dabei. Und deshalb gibt es mehr Untermengen von A als Elemente aus A, denn die sind links alle vorhanden.
Warum fehlt nun U?
Wir nehmen an, dass U in der Tabelle vorkommt als
x [mm] \mapsto [/mm] U.
Frage: Ist x [mm] \in [/mm] U oder nicht?
Wäre x [mm] \in [/mm] U, so hätten wir, als wir links die Elemente von U zusammengesucht hätten, x nicht nehmen dürfen, weil ja nur die Elemente für U genommen werden, die nicht in ihrer eigenen Bildmenge liegen. Wäre x also in U, so hätten wir es nicht in U packen dürfen, also wäre es nicht drin - Widerspruch!
Wäre x nicht in U, so hätten wir x nehmen und es in U hineinpacken müssen - also wäre es doch in U - Widerspruch. Wie sollte das gehen? Die einzige mögliche Lösung aus diesem Dilemma ist, dass x auf irgendeine andere Menge abgebildet ist und U in unserer Tabelle rechts fehlt.
Diese Überlegung gilt für endliche, unendlich abzählbare und unendlich überabzählbare Mengen und zeigt, dass die Potenzmengen von Mengen immer mächtiger als die Mengen selber sind. Die Unendlichkeit von [mm] \IR [/mm] ist also "größer" als die von [mm] \IN [/mm] oder [mm] \IZ, [/mm] die von $ [mm] \mathcal{P}(\IR) [/mm] $"größer" als die von [mm] \IR.
[/mm]
|
|
|
|
