Abzählbarkeit von Teilmengen |
09.01.2022, 16:34 | Patho | Auf diesen Beitrag antworten » | ||
Abzählbarkeit von Teilmengen 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 -> ... |
||||
09.01.2022, 16:42 | 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. |
||||
09.01.2022, 17:09 | 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 |
||||
09.01.2022, 17:13 | 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. Also: {} -> 0 {0} -> 1 {1} -> 2 {0,1} -> 3 {2} -> 4 {0,2} -> 5 {1,2} -> 6 {0,1,2} -> 7 {3} -> 8 usw. |
||||
09.01.2022, 17:19 | Patho | Auf diesen Beitrag antworten » | ||
Ok Danke, so blicke ich durch. Ich habe nicht verstanden wo die 2 herkommt (bzw was sie bedeutet) bei |
||||
09.01.2022, 17:35 | HAL 9000 | Auf diesen Beitrag antworten » | ||
Und ich hatte immer gedacht, diese Zahl lernt man bereits in der Grundschule. |
||||
Anzeige | ||||
|
||||
09.01.2022, 17:43 | 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. |
||||
09.01.2022, 20:08 | 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. |
|
Verwandte Themen
Die Beliebtesten » |
Die Größten » |
|
Die Neuesten » |
|