www.vorhilfe.de
- Förderverein -
Der Förderverein.

Gemeinnütziger Verein zur Finanzierung des Projekts Vorhilfe.de.
Hallo Gast!einloggen | registrieren ]
Startseite · Mitglieder · Impressum
Forenbaum
^ Forenbaum
Status VH e.V.
  Status Vereinsforum

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Suchen
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Diskrete Mathematik" - Kardinalität von Potenzmengen
Kardinalität von Potenzmengen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Diskrete Mathematik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Kardinalität von Potenzmengen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 10:05 Sa 16.01.2016
Autor: SinistresFlagellum

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.

        
Bezug
Kardinalität von Potenzmengen: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                
Bezug
Kardinalität von Potenzmengen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 20:55 Sa 16.01.2016
Autor: SinistresFlagellum

Warum?

Egal wie viele Elemente die Menge A hat, die Ungleichung ist doch für beliebig große n erfüllt

Bezug
                        
Bezug
Kardinalität von Potenzmengen: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                                
Bezug
Kardinalität von Potenzmengen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
                                        
Bezug
Kardinalität von Potenzmengen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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


Bezug
                                                
Bezug
Kardinalität von Potenzmengen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
        
Bezug
Kardinalität von Potenzmengen: Antwort
Status: (Antwort) fertig Status 
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


Bezug
        
Bezug
Kardinalität von Potenzmengen: Cantor hat's gesagt
Status: (Antwort) fertig Status 
Datum: 17:44 So 17.01.2016
Autor: HJKweseleit

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]

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Diskrete Mathematik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
ev.vorhilfe.de
[ Startseite | Mitglieder | Impressum ]