matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

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
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenDiskrete MathematikKardinalität von Potenzmengen
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Philosophie • Religion • Kunst • Musik • Sport • Pädagogik
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 ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]