Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Beweis: Menge aller endlichen Teilmengen von X

Beweis: Menge aller endlichen Teilmengen von X

Universität / Fachhochschule

Sonstiges

Funktionentheorie

Tags: Abzählbarkeit, Funktionentheorie, Mengenlehre

feflo aktiv_icon

18:13 Uhr, 15.10.2017

Hallo, ich hab Mühe dies zu beweisen:

Sei

X

eine abzählbar unendliche Menge und

P_{f} (X) = {Y \in P ∣ ∣ Y ∣ < \infty}

die Menge aller endlichen Teilmengen von

X

. Zeigen Sie, dass

P_{f} (X)

abzählbar unendlich ist.

Ist dieses erstes Beweis korrekt?
Sei

f : P_{f} (N) \to N, f (n_{1}, . . ., n_{k}) \mapsto \sum_{i = 1}^{k} 2^{n_{i}}

eine Abbildung. Da diese bijektiv ist, folgt, dass

f : N \to P_{f} (N)

surjektiv ist.

□

Eine alternative Lösung die ich online gefunden habe, jedoch nicht komplett verstehe ist folgende:
Sei

N \to P_{f} (N), n \mapsto {n}

eine injektive Abbildung.
Dann sei

P_{f} (N) \to N, {n_{1} < n_{2} < . . . < n_{k}} \mapsto Π_{i = 1}^{k} p_{i}^{n_{i}}

eine injektive Abbildung, wobei

(p_{i})_{i \in N} = (2, 3, 5, 7, 11, . . .)

die Folge der Primzahlen in

N

sei. Dann gibt es auch eine bijektive Abbildung zwischen den beiden Mengen.

□

Nun bei diesem Beweis verstehe ich folgendes Dinge nicht.

E r s t e n s

: Wozu braucht man die erste Abbildung überhaupt: wenn die Zweite injektiv ist, dann folgt schon eine Surjektion von

N

nach

P_{f} (N)

Z w e i t e n s

: Was genau bedeutet denn

{n_{1} < n_{2} < . . . < n_{k}}

? Wozu braucht man die "<"?

Dankä!

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

Hierzu passend bei OnlineMathe:

Online-Übungen (Übungsaufgaben) bei unterricht.de:

Mengenlehre

tobit aktiv_icon

00:06 Uhr, 17.10.2017

Hallo feflo!

Beide Beweise behandeln den Spezialfall

X = ℕ

.
Genau genommen ist dann noch der allgemeine Fall darauf zurückzuführen.

Zu zeigen sind:
i)

P_{f} (X)

ist abzählbar
ii)

P_{f} (X)

ist unendlich.

Der erste Beweisidee ist korrekt, wenn man die 0 zu den natürlichen Zahlen zählt.

Die Bijektivität der Abbildung f zeigt i) und ii).

Die Notation der Abbildung f ist nicht ganz korrekt:
Insbesondere muss

n_{1}, \dots, n_{k}

paarweise verschieden vorausgesetzt werden.

Dann muss man sich kurz die Wohldefiniertheit von f klarmachen, da die Darstellung einer Menge

M \in P_{f} (ℕ)

in der Form

M = {n_{1}, \dots, n_{k}}

nicht eindeutig bestimmt ist.

Beide Probleme mit der Abbildung f lassen sich durch folgende einfachere Notation umschiffen:

f : P_{f} (ℕ) \to ℕ

definieren wir durch

f (M) := \sum_{m \in M} 2^{m}

.

Die Bijektivität von f erscheint mir gar nicht so einfach sauber zu begründen zu sein.
Ich würde hier wohl u.a. mit der Existenz und Eindeutigkeit der 2-adischen Darstellung natürlicher Zahlen argumentieren.

Zum zweiten Beweis:

Die angegebene injektive Abbildung

ℕ \to P_{f} (ℕ)

wird genutzt, um ii) zu zeigen.

In der Tat folgt aus der Existenz einer injektiven Abbildung

P_{f} (ℕ) \to ℕ

unter Berücksichtigung von

P_{f} (ℕ) \neq \emptyset

die Existenz einer surjektiven Abbildung

ℕ \to P_{f} (ℕ)

und damit i).

{n1<n2<...<nk} soll wohl eine Kurzschreibweise für die Menge

{n_{1}, n_{2}, \dots, n_{k}}

sein unter dem Zusatzbedingung

n_{1} < n_{2} < \dots < n_{k}

.
Jede endliche Teilmenge der natürlichen Zahlen lässt sich eindeutig in der Form

{n_{1}, n_{2}, \dots, n_{k}}

mit

n_{1} < n_{2} < \dots < n_{k}

schreiben, so dass die angegebene Abbildung

P_{f} (ℕ) \to ℕ

wohldefiniert ist.

Viele Grüße
Tobias

tobit aktiv_icon

00:26 Uhr, 17.10.2017

Eine andere Beweisidee, die direkt den allgemeinen Fall und nicht nur den Spezialfall

X = ℕ

behandelt, ist folgende:

Man benutzt die Tatsache, dass abzählbare Vereinigungen abzählbarer Mengen wieder abzählbar sind und kommt so ohne explizite zahlentheoretische Rechnungen wie Additionen oder Multiplikationen aus.

Man zeigt ii) mittels der injektiven Abbildung

X \to P_{f} (X)

definiert durch

x \mapsto {x}

.

Um i) zu zeigen, genügt es zu zeigen, dass für jedes

n \in ℕ_{0}

die Menge

P_{n} (X) := {Y \in P (X) ∣ ∣ Y ∣ = n}

abzählbar ist:
Denn dann ist auch

P_{f} (X) = ⋃_{n \in ℕ_{0}} P_{n} (X)

als abzählbare Vereinigung abzählbarer Mengen selbst wieder abzählbar.

Die Abzählbarkeit der Mengen

P_{n} (X)

lässt sich durch Induktion nach n beweisen:
Der Induktionsschritt lässt sich dabei z.B. folgendermaßen bewerkstelligen:

Es ist

P_{n + 1} (X) = ⋃_{x \in X} P_{n + 1, x} (X)

mit

P_{n + 1, x} (X) := {Y \in P_{n + 1} ∣ x \in Y} = {Z \cup {x} ∣ Z \in P_{n} (X), x \notin Z}

.
Unter Benutzung der Induktionsvoraussetzung zeigt man die Abzählbarkeit der Mengen

P_{n + 1, x} (X)

, weswegen auch

P_{n + 1} (X)

als abzählbare Vereinigung abzählbarer Mengen selbst wieder abzählbar ist.

feflo aktiv_icon

09:27 Uhr, 17.10.2017

Vielen Dank tobit!

Noch zwei kleine Fragen:

Wäre das Problem der eindeutigkeit der Menge

M = {n_{1}, . . ., n_{k}}

also geklärt, wenn man die als

M = {n_{1} < n_{2} < . . . n_{k}}

schreiben würde?

Ich mag deine Beweisidee, aber ich verstehe nicht wirklich den Teil mit dem Induktionsschritt (ich hab noch ein bisschen Mühe mit solchen Beweisen)... Könntest du mir das vielleicht nochmals in Worte erklären?

Danke nommals :-D)

tobit aktiv_icon

18:53 Uhr, 17.10.2017

" Wäre das Problem der eindeutigkeit der Menge M={n1,...,nk} also geklärt, wenn man die als M={n1<n2<...nk} schreiben würde? "

Sofern der/die Leser(in) / Korrigierende diese Schreibweise akzeptiert, ja.

Zu meinem Induktionsschritt:

Wir nehmen also an, dass

P_{n} (X)

abzählbar ist.
Zeigen müssen wir, dass auch

P_{n + 1} (X)

abzählbar ist.

Dazu genügt es,

P_{n + 1} (X)

als abzählbare Vereinigung abzählbarer Mengen darzustellen.

Ich wähle dazu folgende Darstellung:

P_{n + 1} (X) = ⋃_{x \in X} P_{n + 1, x} (X)

(*),

wobei

P_{n + 1, x} (X) := {Y \in P_{n + 1} (X) ∣ x \in Y}

.

Wenn ich also (*) sowie die Abzählbarkeit der Mengen

P_{n + 1, x} (X)

für alle

x \in X

nachgewiesen habe, folgt wie gewünscht die Abzählbarkeit von

P_{n + 1} (X)

.

Zum Nachweis von (*):

Es genügt, nacheinander
(a)

P_{n + 1} (X) \supseteq ⋃_{x \in X} P_{n + 1, x} (X)

und
(b)

P_{n + 1} (X) \subseteq ⋃_{x \in X} P_{n + 1, x} (X)

nachzuweisen.

(a) folgt im Wesentlichen aus der Definition der Mengen

P_{n + 1, x} (X)

.

Zu (b):
Sei

Y \in P_{n + 1} (X)

.
Dann ist

∣ Y ∣ = n + 1 \geq 0 + 1 \geq 1

und damit enthält

Y

mindestens ein Element

x_{0} \in Y

.
Es folgt

Y \in P_{n + 1, x_{0}} (X)

und damit insbesondere

Y \in ⋃_{x \in X} P_{n + 1, x} (X)

.

Zum Nachweis der Abzählbarkeit der Mengen

P_{n + 1, x} (X)

:

Es gilt

P_{n + 1, x} (X) = {Z \cup {x} ∣ Z \in P_{n} (X), x \notin Z} \subseteq {Z \cup {x} ∣ P_{n} (X)}

.
Die rechte Seite ist abzählbar, da nach Induktionsvoraussetzung

P_{n} (X)

abzählbar ist, und somit ist auch

P_{n + 1, x} (X)

als Teilmenge einer abzählbaren Menge wieder abzählbar.

Man könnte sicherlich manches noch detaillierter ausführen.
Bei Bedarf frage bitte zu den entsprechenden Stellen nach.

1390891

1390499

	Status: nicht eingeloggt	Noch nicht registriert?