Abzählbarkeit |
09.05.2011, 21:32 | Lula90 | Auf diesen Beitrag antworten » | ||||||
Abzählbarkeit a) Abzählbare Vereinigungen von endlichen Mengen sind abzählbar. b) Abzählbare Vereinigungen von abzählbaren Mengen sind abzählbar. c) Die Menge aller endlichen Teilmengen von N ist abzählbar. Das is die Aufgabenstellung, die ich bis morgen lösen soll. Jeoch habe ich keine Ahnung, wie ich erst einmal anfangen soll. Ich weiß nicht, wie ich den Beweis hier führen soll. Kann mir jemand wenigstens einen Ansatz geben? Wie fange ich an? Mfg |
||||||||
09.05.2011, 21:41 | Mazze | Auf diesen Beitrag antworten » | ||||||
Als erstes überlegst Du dir wann eine Menge abzählbar ist. |
||||||||
09.05.2011, 21:45 | Lula90 | Auf diesen Beitrag antworten » | ||||||
abzählbar unendlich ist eine menge, wenn es eine bijektion zwischen A und (z.b.) den natürlichen zahlen gibt, d.h. wenn sie die gleiche Mächtigkeit haben oder man jeder Ziffer eine Zahl aus der menge zuordnen kann. |
||||||||
09.05.2011, 21:51 | Mazze | Auf diesen Beitrag antworten » | ||||||
So also zur Aufgabe a): Wir haben endliche Mengen , und vereinigen von diesen abzählbar viele. Sprich, gesucht ist eine Bijektion f von wir dürfen über die Ganzen natürlichen Zahlen vereinigen, da wir wissen, dass wir eine abzählbare Vereinigung betrachten. Das ist erstmal das was zu tun ist. Jetzt sind die Mengen endlich, sprich sie haben die Form : wobei die Anzahl der Elemente in Menge ist. Fangen wir mit der Menge an, Du willst eine Bijektive Abbildung haben, worauf bildest Du die Elemente von ab ? |
||||||||
09.05.2011, 21:58 | Lula90 | Auf diesen Beitrag antworten » | ||||||
na immer noch auf ? |
||||||||
09.05.2011, 21:59 | Mazze | Auf diesen Beitrag antworten » | ||||||
Ja schon , aber DU musst doch eine Abbildung finden. Du musst also ganz explizit aufschreiben was ... genau für natürliche Zahlen sein sollen. Was bietet sich da wohl an? |
||||||||
Anzeige | ||||||||
|
||||||||
09.05.2011, 22:05 | Lula90 | Auf diesen Beitrag antworten » | ||||||
Also f(1)=1, f(2)=2, ...? |
||||||||
09.05.2011, 22:07 | Mazze | Auf diesen Beitrag antworten » | ||||||
Du meinst Ja, das ist der erste Schritt. Wir erhalten also für , was ist mit ? |
||||||||
09.05.2011, 22:12 | Lula90 | Auf diesen Beitrag antworten » | ||||||
Jezt würde ich bei 2 anfangen, also damit ich wenigstens eine Bijketion habe? |
||||||||
09.05.2011, 22:13 | Mazze | Auf diesen Beitrag antworten » | ||||||
Also wenn ist, kannst Du nicht auch auf 2 setzen (nicht mehr injektiv). Aber Du hast Dir schon richtige Gedanken gemacht. Welche natürlichen Zahlen sind schon verbraucht nach dem wir die Abbildung auf definiert haben? |
||||||||
09.05.2011, 22:18 | Lula90 | Auf diesen Beitrag antworten » | ||||||
Naja , man müsste sie warscheinlich immer so zuordnen, dass sie sich nicht überschneiden, aber das geht doch nur, wenn ich weiß wie viele Mengen ich habe? Wenn ich also 5 Mengen habe, dann kann ich die Zahlen im "5er-Rhythmus" zuordnen. |
||||||||
09.05.2011, 22:21 | Mazze | Auf diesen Beitrag antworten » | ||||||
Du weißt ja nur, dass Du abzählbar viele Mengen hast von denen jede endlich ist. Sprich, zu jeder Menge gibt es eine Zahl die die Anzahl der Elemente von Menge ausdrückt. Welche natürlichen Zahlen sind also verbraucht wenn ich die Menge wie oben beschreiben abbilde? |
||||||||
09.05.2011, 22:26 | Lula90 | Auf diesen Beitrag antworten » | ||||||
Alle Zahlen Muss ich bei dann bei n+1 einfangen? Oh mann ich bin grad total verwirrt. |
||||||||
09.05.2011, 22:31 | Mazze | Auf diesen Beitrag antworten » | ||||||
Richtig! Besser formuliert : Die Zahlen 1 bis wurden verbraucht. Für ist demzufolge Das Ganze kann man in eine allgemeine Form bringen. Es sei das Element aus Menge an der Position j. Für wäre zum Beispiel . Dann ist mit eine Bijektive Abbildung beschrieben die genau unser Zählverhalten wiederspiegelt. Zeige nun, dass diese Funktion Bijektiv ist. Ich hab die Klammern um die Summe gepackt um klar zu machen, dass das j ausserhalb addiert wird. |
||||||||
09.05.2011, 22:37 | Lula90 | Auf diesen Beitrag antworten » | ||||||
wie zeige ich das jetzt |
||||||||
09.05.2011, 22:39 | Mazze | Auf diesen Beitrag antworten » | ||||||
Injektivität und Surjektivität nachweisen! Injektivität : Surjektivität : |
||||||||
09.05.2011, 22:55 | Lula90 | Auf diesen Beitrag antworten » | ||||||
ich steh auf dem schlauch. aber wir bekommen für a)-c) jeweils nur 1Punkt, also kann ich mir nicht vorstellen, dass ich das auch noch beweisen muss? |
||||||||
09.05.2011, 23:12 | Mazze | Auf diesen Beitrag antworten » | ||||||
Steht doch groß drüber bei deiner Aufgabe : Beweisen sie! Ich weiß ja nicht welche Hilfssätze ihr schon kennt. So wie wir es hier machen ist es elementar. Die beiden Eigenschaften sind aber auch nicht schwer zu beweisen : Surjektivität : Wir haben abzählbar viele endliche Mengen mit Elementen. Sprich, für jede natürliche Zahl gibt es eine Zahl mit . Damit gibt es natürlich einen Index t mit Daraus kann man dann das Urbild von k bezüglich f konstruieren. Injektivität : Es sei also Führe die Annahme zu einem Widerspruch. Daraus folgt dann sofort dass auch sein muss und die Injektivität ist gezeigt. |
||||||||
09.05.2011, 23:18 | Lula90 | Auf diesen Beitrag antworten » | ||||||
oder nicht ? oO Also ist damit a) gelöst. Ganz schön viel Aufwand für 1 Punkt. Bei b) kann ich noch nicht erkennen, wo der Unterschied zu a) ist. Klar , ich hab diesmal unendlich viele Mengen, aber wie muss ich meinen Beweis aus a) nun umändern? |
||||||||
09.05.2011, 23:27 | Mazze | Auf diesen Beitrag antworten » | ||||||
Für die Injektivität wollen wir j = l zeigen!
Wie gesagt, vielleicht hattet Ihr ja schon einige Hilfsaussagen in der Vorlesung!
Hattest Du in a auch. In a) hattest du unendlich viele endliche Mengen. In b hast du unendlich viele unendliche Mengen. Hier muss man ein wenig mehr Arbeit rein stecken. Ich würde per vollständiger Induktion über die Vereinigungsmenge argumentieren. Sprich : ist abzählbar. Der Induktionsanfang n = 1 ist trivial. Für den Induktionschritt kannst Du, wenn Du es geschickt machst, Aufgabe a) verwenden. Denn die Vereinigung zweier Abzählbarer Mengen, lässt sich als abzählbare Vereinigung endlicher Mengen darstellen . c) Überleg dir mal wie man die Mengen zählen könnte. Ich muss jetzt weg! |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|