Abzählbarkeit von Teilmengen

Neue Frage »

Patho Auf diesen Beitrag antworten »
Abzählbarkeit von Teilmengen
Folgende Aufgabe:

Wir wissen aus der Vorlesung dass ,d.h die Menge aller Teilmengen von überabzählbar ist.

Wir wollen nun zeigen dass ,d.h die Menge aller endlichen Teilmengen, dagegen abzählbar ist. Weisen sie dazu die Existenz einer Bijektion zwischen und nach, indem Sie zeigen, wie man die Elemente aus sortieren kann.

Ich weiss nicht recht wie ich das angehen muss. Mir scheint klar zu sein dass dies stimmen muss, wenn abzählbar ist, ist auch jede Teilmenge davon abzählbar. Soll ich jetzt die Bijektion einfach mit einer Zuordnung aufzeichnen im Sinne von:

1 ->
2 ->
3 ->
4 ->
...
HAL 9000 Auf diesen Beitrag antworten »

Deinen Ausführungen nach nehme ich an, dass bei dir ist, d.h., die 0 nicht zu gehört.

In dem Fall ist mit eine passende bijektive Abbildung.

P.S.: Bei würde man das zu abändern. Augenzwinkern
Patho Auf diesen Beitrag antworten »

Oh nein, mir ist mal wieder der übliche Fehler passiert. Die 0 gehört bei der Definition die wir verwenden dazu.

Leider verstehe ich deine Lösung noch nicht, wir haben aber auch noch nie Summennotation im Kontext von Funktionen verwendet
HAL 9000 Auf diesen Beitrag antworten »

Was gibt es daran nicht zu verstehen? ist eine endliche Menge natürlicher Zahlen, und es wird über diejenigen summiert, aus denen eben besteht. unglücklich

Also:

{} -> 0
{0} -> 1
{1} -> 2
{0,1} -> 3
{2} -> 4
{0,2} -> 5
{1,2} -> 6
{0,1,2} -> 7
{3} -> 8

usw.
Patho Auf diesen Beitrag antworten »

Ok Danke, so blicke ich durch. Ich habe nicht verstanden wo die 2 herkommt (bzw was sie bedeutet) bei
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Patho
Ich habe nicht verstanden wo die 2 herkommt (bzw was sie bedeutet) bei

Und ich hatte immer gedacht, diese Zahl lernt man bereits in der Grundschule. Augenzwinkern
 
 
Leopold Auf diesen Beitrag antworten »

Man könnte sich auch das folgende Vorgehen vorstellen: Man schreibt die natürlichen Zahlen in einer Liste auf: 0,1,2,3,4,5,6,7,... Ist nun eine endliche Menge der natürlichen Zahlen gegeben, so schreibt man unter jede Zahl der Liste eine 1, wenn sie zu gehört, und eine 0, wenn sie nicht zu gehört. Da endlich ist, gibt es in der 0-1-Folge eine letzte 1. Die Nullen danach läßt man weg. So gehört zu jeder Menge ein Binärcode endlicher Länge, der mit einer 1 endet. Um auch die leere Menge zu berücksichtigen, ordnet man ihr den uneigentlichen Code 0 zu. Er ist der einzige, der nicht mit einer 1 endet. Seine Länge sei 0.

Beispiele

1) Zu gehört

2) Zu gehört

3) Umgekehrt kann man auch zu jedem solchen Binärcode die Menge angeben: Welches gehört zu ?

Damit ist eine Bijektion zwischen den endlichen Mengen und den beschriebenen Binärcodes gegeben. Und diese kann man abzählen, indem man zuerst alle Codes der Länge 0, dann der Länge 1, dann der Länge 2 und so weiter hinschreibt:

0
1
01,11
001,011,101,111
0001,0011,0101,0111,1001,1011,1101,1111
...


Und wenn man sich das einmal genauer überlegt, ist das im wesentlichen dieselbe Idee wie bei HAL.
Finn_ Auf diesen Beitrag antworten »

Skizze zur Zusammenführung. Es steht in eins-zu-eins-Beziehung zu ihrer Indikatorfunktion die die natürlichen Zahlen als Definitionsbereich hat, also ein Folge ist, und somit als formale Potenzreihe



kodiert werden kann. Betrachten wir nun allgemein



Sofern für alle gilt und eine endliche Nichtnullstellenmenge besitzt, ist die Little-Endian-Darstellung von im Stellenwertsystem zur Basis

Weil es sich bei um eine Binärfolge handelt, per Prämisse mit endlicher Nichtnullstellenmenge, darf man die Basis wählen, womit die durch



definierte Abbildung eine injektive ist. Zudem ist surjektiv, denn zu jeder Binärdarstellung existiert ein denn per Prämisse ist eine beliebige endliche Teilmenge der natürlichen Zahlen.
Neue Frage »
Antworten »



Verwandte Themen

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