Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Potenzmenge überabzählbar

Potenzmenge überabzählbar

Universität / Fachhochschule

Sonstiges

Tags: Cantor, surjektivität

dummtrottel aktiv_icon

15:02 Uhr, 25.11.2009

Satz

1.8 :

Cantor

Sei A eine beliebige Menge und

2^{A} = {X : X \subseteq A}

ihre Potenzmenge. Dann existiert keine Surjektion

f : A \to 2^{A}

. Insbesondere ist

2^{A}

überabzahlbar.

Beweis:
Ein Widerspruchsbeweis. Angenommen

f : A \to 2^{A}

ist surjektiv. Setze

D := {a \in A : a! \in f {a)}

.

Weil

f

surjektiv ist, existiert ein

a_{0} \in A

mit

f (a_{0}) = D

. Aber nach der Definition
von

D

gilt:

a_{0} \in D \Leftrightarrow a_{0}! \in f (a_{0}) = D,

ein Widerspruch.
Wäre

2^{ℕ}

abzählbar, so gäbe es eine Bijektion

ℕ \to 2^{ℕ},

aber - wie wir bereits gezeigt haben - gibt es nicht einmal eine Surjektion.

Frage:

[1

. Wie lautet die Formeleditoreingabe für "nicht Element von"? Es ist weder "!el", wie in der Hilfe beschrieben, noch "!in", wie ich erwartet hätte.

]

2. Gibt es irgendwo eine Erklärung für Doofe zu diesem Beweis (insbesondere zur Menge

D :

Was steckt dahinter?Wie kommt man darauf)? Vielleicht ein Beispiel?

[3

. Muß sowas ein "guter" Mathematiker im ersten Anlauf verstehen, oder ist es "normal", daß man sich damit etwas schwertut bzw. besteht die Möglichkeit, daß es noch irgendwann klick macht, auch wenn man das Gefühl hat, gar nichts zu verstehen?

]

Viele Grüße und danke schon mal!

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

Doener aktiv_icon

15:23 Uhr, 25.11.2009

zu 3: mathe is alles nur übungssache... erinnerst dich noch wie damals in der grundschule das multiplizieren schwer fiel?
zu

1 : k . a

.
zu 2: bsp: menge:

{a, b, c}

potenzmenge:

{{}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}

wir müssten jetzt jedem element der ersten ein element der zweiten zuordnen können...(injektiv oder surjektiv weiß net mehr genau welches das war)

dummtrottel aktiv_icon

15:34 Uhr, 25.11.2009

zu3: Hm. Tja, leider hab ichs so schwer nicht in Erinnerung wie das hier...

zu2: Ja, so hätte ich es mir selber auch klar gemacht. Es gibt also "logischerweise" mehr Teilmengen als Elemente der Originalmenge. Nur kann ich leider die Brücke zum formalen Beweis nicht schlagen. Insbesondere zur Menge D.

Wenn ich es richtig verstehe, wird dort ja behauptet, daß es eine Menge von Elementen gibt / geben muß, deren Abbildung das Element selber nicht enthält.

a)

Ist das wirklich die Aussage?

b)

Warum muß das gelten? Weil schon für

A = {1}

gilt:

2^{A} = {{}, {1}}

? Oder auf welche Voraussetzung beruft man sich hier mit D?

hagman aktiv_icon

15:38 Uhr, 25.11.2009

Zu 1:

a \

notin

M \to a \notin M

Wie kommt man auf D? Vor Cantor ist ja auch keiner darauf gekommen. Aber jetzt ist das ein Standardtol, das auch Gödel nutzte

. .

dummtrottel aktiv_icon

15:45 Uhr, 25.11.2009

"Vor Cantor ist ja auch keiner darauf gekommen."

Gut, dann muß ich vielleicht auch nicht verlangen, daß ich selber draufkomme ;-)

Aber nochmal:

a)

Wird dort behauptet, daß es mindestens eine Abbildung (=Teilmenge) gibt, die das zugeordnete Urbild-Element nicht enthält? Stimmt mein Verständnis oder wird etwas ganz anderes gesagt?

b)

Ist die Leere Menge die Begründung dafür, daß man

D

so aufstellen kann oder welche Berechtigung gibt es für diese Behauptung sonst?

Danke und Grüße

g-bigo aktiv_icon

21:44 Uhr, 15.05.2013

Überabzählbarkeit der Potenzmenge der natürlichen Zahlen.

Cantors Widerspruchsbeweis in allen Ehren, aber was ist mit folgender Zuordnung:

1 \to

2 \to {1}

3 \to {2}

4 \to {1, 2}

5 \to {3}

6 \to {1, 3}

7 \to {2, 3}

8 \to {1, 2, 3}

9 \to {4}

. .

.

Nach

2^{n}

kommt als nächstes die einelementige Menge, die nur die natürliche Zahl

(n + 1)

enthält, dann alle noch nicht erfassten Teilmengen, geordnet nach

(a)

Anzahl der Elemente,

(b)

erstem Element

(c)

zweitem Element
usw. usf.

IMHO ist dies sogar eine bijektive Zuordnung zwischen

N

und

2^{N} -

jeder natürlichen Zahl ist genau eine Teilmenge zugeordnet, und es gibt keine Teilmenge von

N,

die ich mit dieser Zuordnung nicht erfasse.

Natürlich wächst die linke Seite dieser Zuordnung verdammt rasch (halt mit

2^{N}

gegenüber dem größten Element in den bis dato erfassten Teilmengen), aber das ist ja kein Hinderungsgrund. Bzgl. der naiven Vorstellung, dass es 'viel mehr' rationale Zahlen als natürliche Zahlen gibt, stellt sich ja auch heraus, dass man zwar

u . U

. ganz schön lange zählen muss, um bei einer gegebenen rationalen Zahl anzukommen, dass man sie aber in jedem Fall mit einem vorgegebenen Abzählalgorithmus erreichen kann, es somit eine surjektive Abbildung zwischen

N

und

Q

gibt - oder halt in Mächtigkeiten formuliert:

| N | = | Q |

Natürlich ist das hier nur der Beginn eines versuchten Induktionsbeweises; ich bin mir aber ziemlich sicher, dass man ihn mit endlicher Mühe sauber ausformuliert bekommt: Wenn ich von

A (n)

(Menge aller Teilmengen mit größtem Element

n)

A (n + 1)

gehe, kommen halt

2^{n + 1} - 2^{n}

neue Teilmengen dazu, die man sauber zuordnen muss; kein Problem mit obiger Sortierung.

Damit hätte man dann also den Widerspruchsbeweis von Cantor, gemäß dem

| N | < | 2^{N} | = | P (N) |,

und im Gegensatz dazu einen Induktionsbeweis, gemäß dem es eine bijektive Abbildung zwischen

N

und

2^{N}

gibt, nach dem also

| N | = | 2^{N} |

.

Wo steckt der Wurm? Oder ist das tatsächlich mal wieder eines der wenigen konkreten Beispiele für den Gödelschen Unvollständigkeitssatz, in diesem Fall sogar in der 'katastrophaleren' Ausprägung, dass gleichzeitig eine Aussage und ihr Gegenteil aus vorhandenen Axiomen und Sätzen abgeleitet werden kann?

Bzgl. der Kontinuumshypothese

-

in der einfachsten Formulierung soweit ich es verstanden habe also die Aussage

| 2^{N} | = | R | -

hat sich ja bereits herausgestellt, dass sowohl ihre Gültigkeit als auch ihre Nichtgültigkeit mit den gängigen Axiomen der ZFS-Mengenlehre vereinbar ist.

Einziger Punkt, der mir einfällt, sind die Mengen, die die Menge der leeren Menge (und verallgemeinert mehr als einelementige Teilmengen) als Teilmengen enthalten, also:

{

Ø}

{

{Ø},

1}

{

{Ø}, {{Ø},

1},

{

{{Ø}, {{Ø},

1},

{

{Ø}, {{Ø},

1}, 1}

. .

.
- damit erhalte ich natürlich bereits auf der leeren Menge Ø und der 1 eine abzählbare Unendlichkeit. Aber zum einen widerspricht dies eigentlich der ansonsten üblichen

2^{n} -

Aussage - bis zum (endlichen)

n

hätte ich so halt nicht

2^{n},

sondern bereits abzählbar unendlich viele Teilmengen. Zum zweiten wird der Abzählalgorithmus zwar komplizierter, aber ähnlich wie bei der Abzählung von

Q

sollte es möglich sein, eine Art 'Abzähl-Spirale' zu konstruieren.

Bin für jeden Tipp dankbar.

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

1095100

684797

	Status: nicht eingeloggt	Noch nicht registriert?