Abzählbarkeit

Neue Frage »

Furius Auf diesen Beitrag antworten »
Abzählbarkeit
Meine Frage:
Man zeige:

Die Menge aller n-elementigen Teilmengen von N (natürliche Zahlen) ist für jedes n element N abzählbar.


Meine Ideen:
Naja es handelt sich doch um die Potenzmenge von N oder?

Aber wie stelle ich das nun an? Es gitl laut skript, das die Natürlichen zahlen abzählbar sind weil es eine Identische abbildung

N -> N
n-> n gibt

das gilt dann doch auch für jede Teilmenge... Somit auch für die ganze Potenzmenge oder?
Nur wie schreibe ich das Mathematisch auf?
JdPL Auf diesen Beitrag antworten »

Achtung: Die Potenzmenge von N ist überabzählbar.

Um Abzählbarkeit einer Menge M zu beweisen würde ich zwei Funktionen f1, f2 verwenden mit:
f1: M -> N ist surjektiv
f2: M -> N ist injektiv

(Alternativ könnte man eine Bijektion finden)
f2 stellt wahrscheinlich das größere Problem dar. Als Beispiel für n=2 hilft hier:
http://de.wikipedia.org/wiki/Abzählbarkeit
http://de.wikipedia.org/wiki/Cantorsche_Paarungsfunktion
danach würde ich mit Induktion über n arbeiten und die Paarungsfunktion mehrfach ausführen.
Furius Auf diesen Beitrag antworten »

Hö? Aber laut aufgabenstellung soll ich doch zeigen, das diese Menge da oben abzählbar ist.

Ist das nicht die Potenzmenge dann?!
JdPL Auf diesen Beitrag antworten »

Nein, die Potenzmenge ist die Menge aller Teilmengen von N.

Du sollst nur die Menge aller Teilmengen von N betrachten, die genau n Elemente besitzt.
Furius Auf diesen Beitrag antworten »

Achso okay :P les mir das gerade durch bei Wikipedia..

gibt noch ne aufgabe b):

Die Menge aller endlichlen Teilmengen von N ist abzählbar.

Da kann ich das doch genauso machen fast oder?
JdPL Auf diesen Beitrag antworten »

Hattet ihr schon, dass die Vereinigung von endlich vielen abzählbaren Mengen, wieder eine abzählbare Menge ist?

Wenn ja, bist du nach a fast fertig, wenn nein, bietet es sich glaube ich an, diesen Satz zu beweisen.
 
 
Furius Auf diesen Beitrag antworten »

Jap steht so im Skrip drin Big Laugh

versteh den Cantorsche Paarungsfunktion nicht ganz.. Bei der definition ist das i dort die imaginäre zahl?

Die tabelle versteh ich soweit :P Das würde doch auch als beweis reichen oder?
JdPL Auf diesen Beitrag antworten »

i ist bei der Summe nur eine Zählvariable; ich hatte bei einer ähnlichen Aufgabe die alternative mit:
2^x (2y+1) benutzt, da ich diese deutlich einfacher fand.

Die Paarungsfunktion macht leider nicht genau das, was du möchtest (sondern eigentlich sogar etwas zuviel);
Die Paarungsfunktion weist nämlich Tupeln wie (1,1), (2,2), ... auch einen Wert zu; in deiner Menge sind diese Tupel leider nicht enthalten.
Furius Auf diesen Beitrag antworten »

Warum nicht? Also wenn ich zum Beispiel die Menge aller 2 Elementigen Teilmengen von N betrachte ist doch (1,1) enthalten oder??

Und wenn ich das nach dem Satz mache, das die Vereinigung abzählbar ist reicht das dann, wenn ich argumentiere, dass meine größte Teilmenge mit n Elementen doch N selber ist oder? Somit ist diese Teilmenge abzählbar.. somit auch alle kleineren Teilmengen.. und nun ist ja nachdem satz wenn ich endlich viele abzählbare Teilmengen Vereinige die Gesamtmenge wieder abzählbar.
JdPL Auf diesen Beitrag antworten »

Ich finde es in so einem Fall immer hilfreich sich "kleine" Beispiele anzusehen:
P({0,1}) = {{}, {0}, {1}, {0,1}} (zu beachten ist, dass {0,0} und {1,1} nicht in der Potenzmenge enthalten sind)

Und die größte Menge mit n Elementen darf nicht die Menge der Menge N sein (diese würde auch übrigens nur ein Element enthalten).

Ich merke gerade, dass du für die b) sogar brauchst, dass eine abzählbare Vereinigung abzählbarer Mengen abzählbar ist.

Mit diesem Satz kannst du dann feststellen, dass die Menge aller endlichlen Teilmengen von N abzählbar ist, da du für jedes n in N eine Menge genau eine Menge hast (also abzählbar viele Mengen) und du für jede der Mengen die Abzählbarkeit bewiesen hast.

Aber den Unterschied zwischen der Menge aller endlichlen Teilmengen von N und der Potenzmenge von N (die überabzählbar ist) kann ich dir leider nicht sagen.
Furius Auf diesen Beitrag antworten »

Hö? hast du mir doch vorhin gesagt..

Habe die aufgabe jetzt so verstanden das ich mir ein n aus N wähle, und dann alle Teilmengen betrachte die n Elemente haben oder?

Also z.B n=2, dann betrachte ich alle 2 Elementigen Teilmengen oder? Also z.B {{1,1},{1,2}...,{100,657}

oder? Und dann kann ich doch das Cantorsche Paarungsprinzip anwenden für n=2 bzw. für n=3 einmal mehr und so weiter.

Damit weise ich dann jedem meiner 2 Elementenigen tupel genau eine Zahl zu, habe also eine Abbildung die surjektiv ist, da jedes getroffen wird und injektiv weil ich eben jedem tupel nur eine Zahl zuweise.

Also so habe ich die a jetzt verstanden..
Furius Auf diesen Beitrag antworten »

Und b erscheint mir irgendwie Trivial.. weil ich habe endlich Teilmenge.. das heißt doch immer abzählbar oder? Da muss man doch nichts beweisen?
Und dann eben die Vereinigung davon laut unserem satz der bei uns 6.1 ist ist die Vereinigung wieder abzählbar.

Allersdings steht da: "Die vereinigung abzählbarer vieler abzählbarer Mengen ist abzählbar".

Sind denn meine endlichen Teilmengen abzählbar viele?
JdPL Auf diesen Beitrag antworten »

Es stimmt auch fast, allerdings sind die von dir betrachteten Mengen alle Teilmengen der Potenzmenge und enthalten innerhalb des Tupels keine Zahl mehrfach.
Deswegen würde ich auch, wenn ihr bereits wisst, dass euch eine injektive und eine surjektive Funktion statt einer bijektiven Funktion, als Abzählbarkeitsargument ausreichen, auch zwei Funktionen verwenden.
Als injektive Funktion kannst du dann die Paarungsfunktion nehmen, und den Definitionsbereich verkleinern (das macht nur die Surjektivität kaputt).

edit: du hast keine endlichen Teilmengen, sondern abzählbar viele abzählbare Mengen (und ja, mit a ist b sehr einfach).
edit2: endliche Mengen sind nicht abzählbar
Furius Auf diesen Beitrag antworten »

Wenn injektivität und surjektivität gilt dann ist die Funktion doch auch immer bijektiv oder? Hatten das so definiert.

Mhh.. Die paarungsfunktion versteh ich nicht ganz weil wir Pi noch nicht hatten so Definiert.. also wie er auf die Summe kommt :-/
Furius Auf diesen Beitrag antworten »

Soo hab jetzt n Ansatz:

Also ich habe das erstmal für n=2 gemacht.

Dann besteht meine Teilmenge P aus {a1,a2 | a1,a2 element N a1 ungleich a2}

Dann ist zu zeigen, das es eine Bijektive Abbildung gibt:

f: P -> H
(a1,a2) -> 10^(a1) + 10^(a2)

Somit erhalte ich eine Bijektive Abbildung da jedem Tupel genau eine Zahl zugeordnet wird ist sie injektiv. Surjektiv auch, da alle getroffen werden oder?

Das kann man nun auf n=3..... n=n erweitern jeweils.

Zur aufgabe b) habe ich dann:

Da "Die vereinigung abzählbarer vieler abzählbarer Mengen ist abzählbar" gilt:

Wenn ich alle n elementigen Teilmengen von N vereinige erhalte ich somit die Menge aller endlich Teilmengen von N. Da alle n elementigen Teilmengen abzählbar sind, ist die vereinigung abzählbar, somit ist b) bewiesen.
JdPL Auf diesen Beitrag antworten »

Wie du gesagt hast, sollte das Erweitern auf höhere n nicht das Problem sein;

Allerdings solltet ihr wissen, dass bei dem Abzählbarkeitsbeweis eine injektive Funktion und eine surjektive Funktion die bijektive ersätzen können.

Ich weiß nicht, was deine Menge H ist, aber falls du N gemeint hast ist die Funktion zwar injektiv (weil die Reihenfolge von a1, a2 keine Rolle spielt), aber du erhältst mit keinem Tupel den Wert 3 (nur ein Beispiel).

eine surjektive Funktion zu finden sollte aber auch kein Problem sein, da die Menge der Tupel "gefühlt" viel größer ist als N.
Furius Auf diesen Beitrag antworten »

Meine Funktion H ist einfach nur die Menge auf die es abgebildet wird.

Sie enhält ja alle 10er potenzen angefangen bei n =1 also ein tupel aus einem Element.

Dann werden ja alle 10er Potenzen getroffen die es gibt.

Wenn mein Tupel aus zwei Elementen besteht werden doch auch alle Elemente meiner Menge H getroffen welche dann:

10^a1 + 10 ^a2 ist.. also das kleinste Elemente wäre 110.. das Größte wäre 10^n + 10^n-1.

Damit habe ich doch dann eine Bijektive abbildung oder?
Gastmathematiker Auf diesen Beitrag antworten »

Zitat:
Original von JdPL
Ich finde es in so einem Fall immer hilfreich sich "kleine" Beispiele anzusehen:
P({0,1}) = {{}, {0}, {1}, {0,1}} (zu beachten ist, dass {0,0} und {1,1} nicht in der Potenzmenge enthalten sind)


Bevor sich das ein Anfänger so merkt. Natürlich ist {1,1} und {0,0} in P({0,1}) = {{}, {0}, {1}, {0,1}} enthalten. Denn {1,1}={1} und {0,0}={0}. Aber diese Mengen sind damit natürlich einelementig.
JdPL Auf diesen Beitrag antworten »

(H hat übrigens kein größtes Element)

Du brauchst leider keine Bijektion auf eine beliebige Menge, sondern auf eine Menge, die sicher abzählbar ist.

Habt ihr vielleicht folgenden Satz gelernt:
Sei A eine unendliche Menge, phi: A -> N eine surjektive Funktion.
Dann gilt A ist abzählbar.

Wenn ja, bist du mit diesem Satz fertig, wenn du feststellst, dass H eine Teilmenge von N ist.
Wenn nein:
Wenn du H so gewählt hast, dass deine Funktion surjektiv ist (also genau die Bildmenge der selben Funktion von A nach N), hast du, wie du richtig erkannt hast, eine Bijektion von A nach H.
Nun musst du zeigen, dass H abzählbar ist, also dass es eine Bijektion von H nach N gibt. (Dann hast du durch Verkettung auch eine Bijektion von A nach N)
Im Prinzip muss man feststellen, dass man die Elemente von H aufsteigend durchnummerieren kann, wenn du weißt, dass du das darfst, bist du fertig.

Beim 3-Tupel kannst du dann benutzen: Es existiert eine Bijektion von (a1,a2,a3) auf ein (a1, x).
Auf (a1, x) kannst du im Prinzip deine Funktion nochmal anwenden.
Es kann hier allerdings gelten: x = a3.
Du musst also noch kurz zeigen, dass das deine Funktion nicht kaputtmacht.

Analog geht das dann für größere n.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »