Abzählbarkeit

Neue Frage »

Lula90 Auf diesen Beitrag antworten »
Abzählbarkeit
Beweisen Sie:
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
Mazze Auf diesen Beitrag antworten »

Als erstes überlegst Du dir wann eine Menge abzählbar ist.
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.
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 ?
Lula90 Auf diesen Beitrag antworten »

na immer noch auf ?
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?
 
 
Lula90 Auf diesen Beitrag antworten »

Also f(1)=1, f(2)=2, ...?
Mazze Auf diesen Beitrag antworten »

Du meinst



Ja, das ist der erste Schritt. Wir erhalten also für

, was ist mit



?
Lula90 Auf diesen Beitrag antworten »

Jezt würde ich bei 2 anfangen, also damit ich wenigstens eine Bijketion habe?
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?
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.
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?
Lula90 Auf diesen Beitrag antworten »

Alle Zahlen
Muss ich bei dann bei n+1 einfangen?
Oh mann ich bin grad total verwirrt.
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.
Lula90 Auf diesen Beitrag antworten »

wie zeige ich das jetzt verwirrt unglücklich
Mazze Auf diesen Beitrag antworten »

Injektivität und Surjektivität nachweisen!

Injektivität :

Surjektivität :
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?
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.
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?
Mazze Auf diesen Beitrag antworten »

Zitat:
oder nicht ? oO


Für die Injektivität wollen wir j = l zeigen!

Zitat:
Also ist damit a) gelöst. Ganz schön viel Aufwand für 1 Punkt.


Wie gesagt, vielleicht hattet Ihr ja schon einige Hilfsaussagen in der Vorlesung!

Zitat:
Klar , ich hab diesmal unendlich viele Mengen


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 Augenzwinkern .

c) Überleg dir mal wie man die Mengen zählen könnte. Ich muss jetzt weg!
Neue Frage »
Antworten »



Verwandte Themen

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