Bijektion auf Teilmengen von N

25.10.2009, 17:14

IfindU

Auf diesen Beitrag antworten »

Bijektion auf Teilmengen von N

Hallo zusammen,

ich hab in Analysis folgende Übungsaufgabe bekommen:
Man zeige: Die Menge $\begin{eqnarray*} \epsilon(\mathbb N) := \{A \subset \mathbb N | A \text{ endlich oder } \mathbb N \backslash A \text{ endlich}\} \end{eqnarray*}$ ist abzählbar, die Menge $\begin{eqnarray*} P(\mathbb N) := \{ A \subset \mathbb N \} \end{eqnarray*}$ aller Teilmengen von $\begin{eqnarray*} \mathbb N \end{eqnarray*}$ dagegen nicht.

Hinweis:
Zu einer eventuellen Bijektion $\begin{eqnarray*} f : \mathbb N \rightarrow P(\mathbb N) \end{eqnarray*}$ betrachte man die Menge $\begin{eqnarray*} A := \{n \in \mathbb N | n \notin f(n)\} \end{eqnarray*}$

Meine Überlegung war: ich zeige, dass $\begin{eqnarray*} \mathbb N \rightarrow \epsilon \end{eqnarray*}$ bijektiv ist, in dem ich zeige, dass $\begin{eqnarray*} \mathbb N \rightarrow A \end{eqnarray*}$ bijektiv ist, da N ohne A für ein unendliches A wieder A' ergibt und sich damit analog verhält.
Ist die Idee bis dahin richtig?

Danke fürs Lesen.

25.10.2009, 17:29

Duedi

Auf diesen Beitrag antworten »

Verstehe ich dich im letzten Abschnitt richtig, wenn du meinst, dass für eine unendliche Menge $\begin{eqnarray*} A\subset \mathbb N \end{eqnarray*}$ die Menge
$\begin{eqnarray*} \mathbb N\setminus A \end{eqnarray*}$ endlich ist?

25.10.2009, 17:34

IfindU

Auf diesen Beitrag antworten »

In der Aufgabe ist ja vorgegeben, dass A entweder endlich sein muss oder N\A endlich sein muss. Oder versteh ich dich da falsch?

25.10.2009, 17:39

Duedi

Auf diesen Beitrag antworten »

Achso, du gehst schon gleich von der Aufgabe aus. Ich dachte, das wäre ein genereller Ansatz Big Laugh

Big Laugh

(Ansonsten gäbe es das Gegenbeispiel $\begin{eqnarray*} A=\{n\in\mathbb N|~n\text{ gerade}\} \end{eqnarray*}$ )
Hm, dürft ihr denn nicht verwenden, dass eine Teilmenge einer abzählbaren Menge ebenfalls abzählbar ist? (denn $\begin{eqnarray*} \varepsilon(\mathbb N) \end{eqnarray*}$ ist ja eine Teilmenge von $\begin{eqnarray*} \mathbb N \end{eqnarray*}$ )

EDIT: Huuuuch, falsch gelesen. Ich markiere mit rot den Fehler. Ich mache mir gleich nochmal Gedanken darüber.

25.10.2009, 17:45

Julian@mb

Auf diesen Beitrag antworten »

Hallo!

Ich bin auch bei dir in Ana. Hier mein Ansatz:

Grundsätzlich hab ich das Problem wie du auch erstmal auf endliche Mengen reduziert. Ich zeige, dass N^n (n € N\{0}) abzählbar ist und konstruiere eine surjektive Abbildung von N auf die Menge der n-elementigen Teilmengen von N.

Den Rest kannst du dir denken.

Edit: Verbessert.

25.10.2009, 17:56

Duedi

Auf diesen Beitrag antworten »

OK, ich hab eine Idee.
Versuche es mal so:
Wie du und auch Julian richtig gesagt haben, genügt es, endliche Mengen zu betrachten. Die Aufgabenstellung ist also nichts anderes als:
Ist die Menge aller endlichen Teilmengen in $\begin{eqnarray*} \mathbb N \end{eqnarray*}$ abzählbar?
Mein Ansatz wäre folgendermaßen:
Du hast eine endliche Menge $\begin{eqnarray*} A=(a_1,\cdots a_\nu) \end{eqnarray*}$
Jetzt brauchst du eine eineindeutige Abbildung $\begin{eqnarray*} A\mapsto n\in \mathbb N \end{eqnarray*}$

Anzeige

25.10.2009, 18:00

Julian@mb

Auf diesen Beitrag antworten »

Ich hab oben noch etwas in rot eingefügt.

25.10.2009, 18:05

IfindU

Auf diesen Beitrag antworten »

Danke euch beiden, ich verdau das erstmal in Ruhe bevor ich mich überstürzt irgendwo reinwerfe.

25.10.2009, 18:07

papahuhn

Auf diesen Beitrag antworten »

Edit: Sollte genauer lesen ...

25.10.2009, 18:08

Duedi

Auf diesen Beitrag antworten »

Ja, das habe ich leider erst gemerkt, als mein Beitrag schon raus war. Konnte den Fehler nur noch zur Warnung einröten Big Laugh

Big Laugh

EDIT: Der Sinn dessen, was hier steht, ist jetzt verloren (bezog sich auf papahuhns Äußerung zu meinem Fehlschluss in meinem Thread oben)

25.10.2009, 19:22

IfindU

Auf diesen Beitrag antworten »

Irgendwas am folgenden Gedankengang ist falsch, weil P(N) abzählbar wäre, ich komm aber nicht drauf was es sein könnte.

Wir haben gezeigt dass $\begin{eqnarray*} \mathbb N \times \mathbb N \rightarrow \mathbb N \end{eqnarray*}$ eine bijektive Abbildung ist.
Außerdem, dass falls A und B abzählbar sind, dann A x B abzählbar ist. (So stehts zumindest im Skript)

Nun dachte ich das führt zu einer Erweiterung, so dass $\begin{eqnarray*} \mathbb N \times \mathbb N \times \dots \times \mathbb N \rightarrow \mathbb N \end{eqnarray*}$ abzählbar ist.

Aber das müsste auch für unendliche Mengen stimmen - wo hab ich Mist gebaut?

25.10.2009, 19:29

Duedi

Auf diesen Beitrag antworten »

Der Schritt ins Unendliche ist leider nicht möglich. Du kannst zwar immer noch eins dazuzählen, bist dabei aber immer noch im Endlichen.
Mit anderen Worten: Für jede beliebige Zahl $\begin{eqnarray*} n\in\mathbb N \end{eqnarray*}$ ist $\begin{eqnarray*} \mathbb N^n \end{eqnarray*}$ abzählbar, " $\begin{eqnarray*} \mathbb N^\infty \end{eqnarray*}$ " (Die "" beachten, das darf man so nicht schreiben Augenzwinkern

Augenzwinkern

) jedoch nicht.

25.10.2009, 19:49

IfindU

Auf diesen Beitrag antworten »

Okay, könnte ich aber für endliche Mengen so argumentieren. Die einzige surjektive Abbildung die mir einfallen würde, jeder endlichen Menge die Anzahl der Elemente zuzuordnen.
Könnte ich das machen und so gegen P(N) argumentieren?

25.10.2009, 19:53

Julian@mb

Auf diesen Beitrag antworten »

Zitat:

Original von IfindU
Die einzige surjektive Abbildung die mir einfallen würde, jeder endlichen Menge die Anzahl der Elemente zuzuordnen.

Was soll dieser Satz bedeuten?

25.10.2009, 20:11

Duedi

Auf diesen Beitrag antworten »

Das wäre keine Bijektion, und die brauchst du, damit du einen Isomorphismus hast. Versuchs mal so, dass du für jede k-te natürliche Zahl, die vorkommt, $\begin{eqnarray*} 10^k \end{eqnarray*}$ addierst. Ein Beispiel:
$\begin{eqnarray*} A=\{1,3,4,7\}\mapsto 10^1+10^3+10^4+10^7 = 10011010 \end{eqnarray*}$

25.10.2009, 20:25

IfindU

Auf diesen Beitrag antworten »

Danke für die Antwort, darauf wär ich wohl nie gekommen.

Edit:
Hätte noch eine Frage, da das sehr kompliziert wird beim Aufschreiben (z.b. die 0 zu integrieren); wir haben: Sei A eine unendliche Menge und f : N -> A surjektiv. Dann gibt es auch eine bijektive Abbildung g: N -> A (d.h., dann ist a abzählbar) als bewiesenes Lemma stehen. Könnte man dann nicht doch den Weg über die Anzahl der Elemente gehen?

26.10.2009, 12:39

Julian@mb

Auf diesen Beitrag antworten »

Vorbemerkung:
M_n ist die Menge der Teilmengen von N mit n Elementen (n > 0)
M ist die Menge der nichtleeren Teilmengen von N.

Du hast a_n: N -> N^n bijektiv
Damit konstruierst du leicht:
b_n: N -> M_n surjektiv
und erhältst:
c_n: N -> M_n bijektiv.
Jetzt gibt es
d: N -> N* x N bijektiv
womit man
e: N -> M bijektiv
und ganz leicht auch
f: N -> M u {{}} bijektiv
konstruiert.
Damit erhält man sofort:
g: N -> e(N) bijektiv

Somit ist e(N) abzählbar.

26.10.2009, 18:33

Duedi

Auf diesen Beitrag antworten »

IfindU:
Die reine Existenz einer derartigen Abbildung ist dann zwar gesichert, wie sie aber dann genau aussieht, weißt du nicht. Außerdem geht die Abbildung, die einer Menge ihre Elementanzahl zuordnet, in die falsche Richtung, nämlich A->N. Dein Lemma fordert N->A.

26.10.2009, 18:37

IfindU

Auf diesen Beitrag antworten »

Okay, danke euch beiden, werd mich noch mal intensiv dem Thema auseinandersetzen.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »