Abzählbarkeit von Mengen

Neue Frage »

StevenSpielburg Auf diesen Beitrag antworten »
Abzählbarkeit von Mengen
Hallo,

ich habe eine Frage zu der Abzählbarkeit von Mengen. Wir haben einige Mengen gegeben und sollen zeigen, dass diese abzählbar sind, bzw. nicht abzählbar sind.

Hier erstmal die Mengen:

Zeigen Sie...

(1)..., dass die Menge aller ungeraden natürlichen Zahlen abzählbar ist.
(2)..., dass die Menge aller geraden natürlichen Zahlen abzählbar ist.
(3)..., dass die Menge der natürlichen Zahlen abzählbar ist.
(4)..., dass die Menge abzählbar ist.
(5)..., dass die Menge abzählbar ist.

ich weiß leider nicht genau, wie genau ich dies aufschreiben muss, bzw ich das beweisen kann das diese Mengen abzählbar sind.

Bei 1,2,3 würde ich sagen, dass jeder Zahl eine natürliche Zahl zugeordnet werden kann und somit die Mengen abzählbar unendlich sind.
Die (4) haben wir schon besprochen und habe das mit Hilfe von surjektivität und injektivität bewiesen. Bei der (5) habe ich keine Idee.

Kann mir jemand helfen? Vielen Dank im voraus!!!
Mazze Auf diesen Beitrag antworten »

Zitat:
dass jeder Zahl eine natürliche Zahl zugeordnet werden kann und somit die Mengen abzählbar unendlich sind.


Das reicht nicht aus. Es muss jeder Zahl genau eine natürliche Zahl zugeordnet werden und es muss jede natürliche Zahl erreicht werden (injektiv und surjektiv).

Diese Dinge müssen natürlich Bewiesen werden. Im Allgemeinen tut man das, in dem man eine solche Bijektive Abbildung direkt angibt. Offenbar ist etwa für 1)

Es sei A die Menge der ungeraden Zahlen, dann ist

mit

eine bijektive Abbildung (was natürlich zu beweisen ist). Wenn Du das gezeigt hast, hast Du bewiesen, dass die Menge A abzählbar unendlich ist.

zu 5) Das ist etwas spezieller. Schau Dir dazu mal das Cantorsche Diagonalargument an.
StevenSpielburg Auf diesen Beitrag antworten »

Okay also muss ich versuchen, dass ich eine Bildungsvorschrift finde und dann die Bijektivität beweise..
Bei Zahlenmengen > N kann ich doch direkt sagen, dass diese nicht abzählbar sind oder?
ja (5) habe ich auch schon mal im Skript gesehen, wusste aber nicht, dass ich das damti machen kann.
Ich werds mal versuchen, vielen dank erstmal..
Mazze Auf diesen Beitrag antworten »

Zitat:
Bei Zahlenmengen > N kann ich doch direkt sagen, dass diese nicht abzählbar sind oder?


Das ergibt so erstmal keinen Sinn da man erstmal ordentlich definieren muss was "Menge A ist größer als Menge B" genau heissen soll. Und tatsächlich verwendet man dafür die Mächtigkeit.

Zitat:
Okay also muss ich versuchen, dass ich eine Bildungsvorschrift finde und dann die Bijektivität beweise..


Ja, genau so.
StevenSpielburg Auf diesen Beitrag antworten »

Okay dann bleiben wir mal kurz bei der Menge der ungeraden natürlichen Zahlen.

Als Bildungsvorschrift nehme ich diese (2n-1)
Jetzt würde ich so anfangen:

surjektiv?

rein logisch, ja, da alle Elemente der Menge getroffen werden.

injektiv?

auch ja, da alle Elemente der Menge jeweil einer Zahl zugeordnet werden können.

Jetzt fehlt mir aber der Beweis dafür!
evlt. sowas?

injektiv:
surjektiv???
StevenSpielburg Auf diesen Beitrag antworten »

kann vielleicht jemand nochmal kurz drüber schaun ob man das so machen kann?
 
 
Mazze Auf diesen Beitrag antworten »

Zitat:
rein logisch, ja, da alle Elemente der Menge getroffen werden.


Ist das so? Was ist denn Beispielweise mit der 2? Gibt es eine ungerade natürliche Zahl n mit



? Wohl nicht. Damit ist die Abbildung nicht Surjektiv. Denk nochmal drüber nach Augenzwinkern
StevenSpielburg Auf diesen Beitrag antworten »

Ah okay das leuchtet ein, kann ich denn so die injektivität beweisen, so wie ich es oben gemacht habe?

Also folgt ja daraus, das das ganze nicht surjektiv aber injektiv ist, aber nicht bijektiv, und somit nicht abzählbar?
Mazze Auf diesen Beitrag antworten »

Zitat:
Also folgt ja daraus, das das ganze nicht surjektiv aber injektiv ist, aber nicht bijektiv, und somit nicht abzählbar?


Nein, das ist falsch. Du hast hier einen grundsätzlichen Logikfehler.

Definition abzählbar unnendlich:

Eine Menge A heißt abzählbar unendlich wenn es eine bijektive Abbildung von A in die natürlichen Zahlen gibt.

Die logische Verneinung ist :

Eine Menge A ist nicht abzählbar wenn es keine bijektive Abbildung von A in die natürlichen Zahlen gibt.


Wenn Du also für diese Abbildung gezeigt hast, dass sie nicht bijektiv ist, so folgt noch lange nicht, dass die Menge nicht abzählbar ist. Du müsstest dann für jede mögliche Abbildung beweisen , dass sie nicht bijektiv sein kann. Und wenn Du mal weiter oben schaust, hab ich dir auch schon ein Beispiel für eine bijektive Funktion von den ungeraden Zahlen in die natürlichen Zahlen geliefert.

Zitat:
Ah okay das leuchtet ein, kann ich denn so die injektivität beweisen, so wie ich es oben gemacht habe?


Deine gewählte Abbildung ist injektiv (aber nicht surjektiv wie gesagt), aber dein Beweis ist so unvollständig. Ich würde wenigstens noch einige Zwischenschritte einbauen. Aber das ist im Prinzip sowieso überflüssig, weil es diese Abbildung ja nicht macht.
StevenSpielburg Auf diesen Beitrag antworten »

Okay jetzt hast du mich total verwirrt.
Also abzählbar unendlich heißt, dass ich eine bijektive Abbildung finden muss mit den natürlichen Zahlen.
Falls ich das nicht finde, ist sie nicht abzählbar.
Okay jetzt habe ich bei dieser Abbildung ja gezeigt, dass sie nicht bijektiv ist, da die surjektivität nicht bewiesen wird. Aber wie beweise ich denn nun, dass diese Abbildung abzählbar ist?
Mazze Auf diesen Beitrag antworten »

Zitat:
Okay jetzt hast du mich total verwirrt.


In wiefern?

Zitat:
Aber wie beweise ich denn nun, dass diese Abbildung abzählbar ist?


Gar nicht, weil das keinen Sinn macht. Abzählbarkeit ist eine Eigenschaft von Mengen. (auch wenn Abbildungen streng genommen auch Mengen sind, aber das führt hier jetzt zu weit)

Nochmal : Es sei A die Menge der ungeraden natürlichen Zahlen. Die Menge A heißt abzählbar unendlich, wenn es eine Abbildung



gibt die Bijektiv ist. Du musst also nur irgendeine bijektive Abbildung finden. Wenn Du eine Abbildung findest die nicht bijektiv ist, ist das kein Gegenbeweis.

Und jetzt noch ein weiteres mal :

Ich habe dir oben schon ein Beispiel für eine bijektive Abbildung gegeben. Du musst nur noch Beweisen, dass diese Bijektiv ist.
StevenSpielburg Auf diesen Beitrag antworten »

ah okay jetzt so allmählich glaube ich...


Beobachtung: Wenn ich ungerade Zahlen für n einsetze, kommt immer eine ganze Zahl heraus. Zum Beispiel bei n=1 => f(n)=1; n=3 => f(n)=2
Wenn ich gerade Zahlen für n einsetze, kommt immer eine ungerade Zahl raus, bzw. ein Bruch. Diese sind aber nicht wichtig, da wir ja nur eine Abbilung in N haben wollen.
Somit fallen die Brüche weg und ich habe für jede ungerade Zahl ein n.

ich hoffe ich habe das einigermaßen verständlich ausgedrückt.

Surjektiv: werden alle Zahlen getroffen?
Injektiv: wird jede Zahl nur !einer! anderen Zahl zugeordnet?

Beides male ja, nur ich weiß nicht wie ich den Beweis aufstellen soll.
Mazze Auf diesen Beitrag antworten »

Zitat:
Wenn ich gerade Zahlen für n einsetze, kommt immer eine ungerade Zahl raus, bzw. ein Bruch. Diese sind aber nicht wichtig, da wir ja nur eine Abbilung in N haben wollen.


Ungünstig formuliert. Unsere Abbildung ist auf den ungeraden Zahlen definiert. Daher interessieren uns für 1) die geraden Zahlen nicht.

Zitat:
Beides male ja, nur ich weiß nicht wie ich den Beweis aufstellen soll.


Mit der Definition!

Definition injektiv. Es sei mit dann gilt für alle .

Beweis : Es sei also , das bedeutet also für unsere Abbildung in 1)



Jetzt bist Du dran!

edit: Sry, deinen Post am Anfang falsch gelesen.
StevenSpielburg Auf diesen Beitrag antworten »

schuldige aber hilf mir bitte auf die sprünge, ich kann mir unter dieser definition einfach nicht viel vorstellen verwirrt
Mazze Auf diesen Beitrag antworten »

Naja, eine Funktion f ist injektiv wenn gilt:

Wenn ist, dann folgt, dass ist.

Injektive Funktion :





Beweis :

Es sei also . Damit ist f injektiv. Trivial!

Eine interessantere Funktion:

mit

Offensichtlich ist , daher ist diese Funktion nicht injektiv auf . Genauer :

Offenbar ist aber , daher ist f nicht injektiv.

Betrachten wir jetzt aber , dann haben wir :

Sei , da ist gilt



Damit ist also f injektiv. Was wir hier sehen kann : Eine nicht injektive Funktion kann auf einer Teilmenge ihres Definitionsbereiches durchaus Injektiv sein.

Sprachlich formuliert: Eine Funktion ist Injektiv wenn jedes Zielelement höchstens einmal getroffen wird.
StevenSpielburg Auf diesen Beitrag antworten »

Zitat:




okay und was heißt das für meine aufgabe?
StevenSpielburg Auf diesen Beitrag antworten »

Zitat:




mit x1 ungleich x2, und y1 ungleich y2

ungleich
somit injektiv?
Mazze Auf diesen Beitrag antworten »

Du benutzt eine "andere" Definition von Injektiv. Die übliche vorgehensweise ist, anzunehmen dass ist und dann zu zeigen, dass dann auch gilt, denn dann ist die Funktion injektiv. Für obiges Beispiel :

Sei , dann ist also








damit ist f injektiv. Deine Definition ist nicht falsch, wenn ist so muss auch sein. Das ist äquivalent zur üblichen Definition. Das Problem hierbei ist immer, dass man mit "ungleich" argmuntiert. Der Weg wäre dann :

Es sei :





StevenSpielburg Auf diesen Beitrag antworten »

Okay gut injektiv ist verstanden. Dann vllt nochmal kurz zu surjektiv:

Ich würde jetzt so starten:

nach der Def. muss gelten f(x)=y
mit x1 ungleich x2 und y1 ungleich y2
gilt:




somit folgt surjektivität!

kann man das so machen?
Mazze Auf diesen Beitrag antworten »

Zitat:
nach der Def. muss gelten f(x)=y mit x1 ungleich x2 und y1 ungleich y2


Nein, das ist nicht die Deifnition von Surjektiv, bzw. unschön formuliert.

Definition von Surjektiv: Seien A und B (nicht leere) Mengen und , dann heißt f Surjektiv wenn es für alle ein gibt, so dass ist.

In Worten : Jedes Zielelement wird getroffen.

Damit ist dein Beweis zur Surjektivität natürlich falsch. So geht man vor :

Es sei

und sei , dann ist eine ungerade, natürliche Zahl (mach dir das klar). Dann gilt




Da eine ungerade Zahl ist, haben wir also zu y unser x gefunden (x = 2y - 1), daher ist f surjektiv. Wie kommt man auf dieses y? Bei einfachen Funktionen (wie es unsere hier ist) kann man die Gleichung



nach x umstellen. Jetzt bist Du aber mit Teil 2) dran.
StevenSpielburg Auf diesen Beitrag antworten »

Teil 2?
Mazze Auf diesen Beitrag antworten »

Du hast fünf Teilaufgaben, wir haben erst die erste erledigt.
StevenSpielburg Auf diesen Beitrag antworten »

okay gerade zahlen

f(x)=2x

injektiv:
2x=2y
x=y
somit injektiv

surjektiv
f(x)=2x -> x=y/2
f(y/2)=2*y/2 =y
somit surjektiv

somit bijektiv
Mazze Auf diesen Beitrag antworten »

Injektivität ist richtig, aber Surjektivität falsch. Offenbar ist nicht immer eine natürliche Zahl. Etwa ist für y = 3 dann . 3/2 ist keine gerade Zahl und damit kein gültiges Urbild von 3. Daher ist die Funktion



nicht surjektiv. Wenn Du die Gleichung nach x - umstellst musst Du schauen, ob der entsprechende Ausdruck auch wirklich für alle y in der Urbildmenge liegt. Bei unserem Beispiel zu Aufgabe 1) habe ich ja explizit gesagt dass

Zitat:
dann ist eine ungerade, natürliche Zahl (mach dir das klar)


gilt. Sprich, hier war für alle y ein Element der Urbildmenge. Bei Dir ist es nicht der Fall. Du musst eine andere Abbildung finden.
StevenSpielburg Auf diesen Beitrag antworten »

ah klar stimmt, mein fehler
mhh dann fällt mir keine ein

vllt x/2?
injektiv:
x/2 = y/2
x=y
somit injektiv

surjektiv:
f(x) = x/2 => x=2y
f(2y)=2y/2 = y

somit surjektiv

=> bijektiv
Mazze Auf diesen Beitrag antworten »

Zitat:
mhh dann fällt mir keine ein vllt x/2?


Nicht einfach nur raten, Eigenschaften überprüfen.

Ist für alle geraden Zahlen x definiert?

Ist diese Funktion injektiv?

Ist diese Funktion surjektiv?

Wenn ja, hast Du eine Bijektive Abbildung gefunden, wenn nein => neue Funktion finden.
StevenSpielburg Auf diesen Beitrag antworten »

Zitat:
Original von StevenSpielburg

vllt x/2
injektiv:
x/2 = y/2
x=y
somit injektiv

surjektiv:
f(x) = x/2 => x=2y
f(2y)=2y/2 = y

somit surjektiv

=> bijektiv
Mazze Auf diesen Beitrag antworten »

Der edit war aber noch nicht da vorhin Augenzwinkern .

Zitat:
injektiv: x/2 = y/2 x=y somit injektiv


In Ordnung

Zitat:
surjektiv: f(x) = x/2 => x=2y f(2y)=2y/2 = y somit surjektiv


Ist denn 2y für alle eine gerade Zahl?
StevenSpielburg Auf diesen Beitrag antworten »

okay kurz noch was grundlegendes zum verständnis

ich habe jetzt 2 mengen A,B.
mit f: A->B
In meiner Menge A bei diesem Beispiel, stehen jetzt alle geraden natürlichen Zahlen oder? und in meiner Menge B stehen alle natürlichen Zahlen.
Jetzt versuche ich eine Abbildung zu finden, die jedem Element der Menge A ein Element der Menge B zuordnet, und zwar so, dass alle Elemente der Menge B getroffen werden?

Und ich würde schon sagen, dass 2y immer eine gerade Zahl ist? Demnach müsste ich ja wenn ich x=2y dort stehen habe, alle natürlichen Zahlen für x einsetzen können und es müsste eine gerade Zahl für y rauskommen. Also wenn ich x=1 einsetze, ist y=1/2, und somit passt die Bildungsvorschrift nicht?!


Kurzer Nachtrag:
Also bei den ungerade Zahlen, hatte wir ja auch x=2y-1 dort stehen
Wenn ich nun 1,2,3,4,...,n für y einsetze, kommt für x immer eine ungerade Zahl raus.
Genau so wäre es ja auch hier bei den gerade Zahlen
Wir haben x=2y dort stehen
Wenn ich nun 1,2,3,4,...n, für y einsetze, bekomme ich immer eine gerade Zahl für x raus.
Somit müsste es ja doch passen.
Mazze Auf diesen Beitrag antworten »

Zitat:
In meiner Menge A bei diesem Beispiel, stehen jetzt alle geraden natürlichen Zahlen oder?


Richtig , A ist die Definitionsmenge oder auch Urbildmenge.

Zitat:
und in meiner Menge B stehen alle natürlichen Zahlen.


Ja, B nennt man Wertebereich oder Bildmenge.


Zitat:
Jetzt versuche ich eine Abbildung zu finden, die jedem Element der Menge A ein Element der Menge B zuordnet, und zwar so, dass alle Elemente der Menge B getroffen werden?


Das wäre nur die Surjektivität, Du willst auch , dass jedem Element aus A höchstens ein Element aus B zugeordnet wird.


Zitat:
Und ich würde schon sagen, dass 2y immer eine gerade Zahl ist?


Ja , natürlich. Eine Zahl ist gerade, wenn sie ohne Rest durch 2 Teilbar ist. Offenbar ist 2y immer ohne Rest durch 2 teilbar ist. Du musst aber explizit auch nachweisen, dass dein gefundenes Urbild für y auch wirklich zur Urbildmenge gehört (was in unserm Fall die geraden zahlen sind). Denn sonst würde es dir nichts bringen Augenzwinkern .

Du kannst nicht davon ausgehen, dass nach dem Umstellen die Zahl wirklich in der Urbildmenge liegt. Du hast das ja oben mit den 2/3 gesehen. Man muss das schon ordentlich nachweisen.

Zitat:
Also wenn ich x=1 einsetze, ist y=1/2, und somit passt die Bildungsvorschrift nicht?!


1 ist keine gerade Zahl und damit nicht relevant für die Betrachtung der Urbildmenge.
StevenSpielburg Auf diesen Beitrag antworten »

okay also ist meine surjektivität richtig? oder fehlt noch etwas zum vollständigen beweis?
reicht das nicht, dass x=2y ist und somit immer eine gerade Zahl herauskommt?
Mazze Auf diesen Beitrag antworten »

Zitat:
reicht das nicht, dass x=2y ist und somit immer eine gerade Zahl herauskommt?


Du hast mich noch nicht ganz verstanden. Du hast korrekt umgeformt zu . Aber wer sagt uns denn dass wirklich im Definitionsbereich liegt? Das müssen wir dazu sagen. Du hast es doch oben bei deiner falschen Funktion gesehen. Da hat 3/2 nicht zum Definitionsbereich gehört. Hier ist es aber richtig und damit die Surjektivität richtig.
StevenSpielburg Auf diesen Beitrag antworten »

okay also reicht dann ein satz den ich dazu schreiben muss und fertig?

weiter mit der abzählbarkeit von n.
wenn ich das so mache, wie wir das bei den anderen beiden aufgaben auch schongemacht habe, würde ich einfach sagen f(n)=n.

injektiv: f(x)=f(y)
x=y
somit injektiv

surjektiv: f:A->B für jedes yeA existiert ein xeB mit f(x)=y
f(x)=x -> x=y
somit surjektiv

->bijektiv
Mazze Auf diesen Beitrag antworten »

Zitat:
okay also reicht dann ein satz den ich dazu schreiben muss und fertig?


Bei diesen einfachen Beispielen reicht es. Man kann Beispiele finden wo das Argument über die zugehörig zur Urbildmenge äußerst komplex werden kann.

Ansonsten kannst Du deinem Beweis für 3) so lassen.
StevenSpielburg Auf diesen Beitrag antworten »

okay zu 4. hab ich schon die lösung.
wie kann ich 5. beweisen?
Mazze Auf diesen Beitrag antworten »

Hab ich weiter oben schon erwähnt. Das Cantorsche Diagonalargument wird dir hier helfen.
StevenSpielburg Auf diesen Beitrag antworten »

Zitat:
Original von Mazze
Zitat:
rein logisch, ja, da alle Elemente der Menge getroffen werden.


Ist das so? Was ist denn Beispielweise mit der 2? Gibt es eine ungerade natürliche Zahl n mit



? Wohl nicht. Damit ist die Abbildung nicht Surjektiv. Denk nochmal drüber nach Augenzwinkern


nochmal kurze frage dazu, bin jetzt gerade etwas verwirrt gewesen.
wenn das n jetzt mein neN ist, also 1,2,3,4,5,...
und mein f(n) wäre 1,3,5,7,9,...
müsste die abbildung 2n-1 doch eine bijektive abbilung sein oder?
da
2x-1=2y-1
x=y

und
f(x)=2x-1
x=(y+1)/2
f((y+1)/2)=2*(y+1)/2-1 =y

ich versuche meine frage mal selber zu beantworten:
nach der def. Es sei f: M->N eine Abb heißt injektiv wenn:
für alle x1,x2eM gild x1!=x2 => f(x1)!=f(x2)
heißt surjektiv wenn:
für jedes yeN ein xeM existiert mit f(x)=y

Auf dieses Beispiel bezogen: M ist die Menge meiner ungerade nat. Zahlen, N ist die Menge aller natürlichen Zahlen.
Bei injektiv, nehme ich also elemente aus M und setze diese gleich und gucke, ob sie gleich bzw. ungleich sind( je nach vorgehensweise), dies würde ja für diesen Fall zustimmen.
Bei surjektiv, nehme ich ein Element aus N (mein y) und ein Element aus M (mein x)
Dann hätte ich: f(x)=2x-1=y
Jetzt versuche ich mit meinem Element aus M (dem x) jedes Element aus der Menge N (das y) zu treffen. angenommen, wir wollen die 2 aus N treffen. also y=2
--> 2x-1=2 Es gibt keine ungerade natürliche Zahl aus xeM die diese Gleichung erfüllt.
Somit nicht surjektiv????
ich hoffe das stimmt so!
Mazze Auf diesen Beitrag antworten »

Zitat:
wenn das n jetzt mein neN ist, also 1,2,3,4,5,... und mein f(n) wäre 1,3,5,7,9,...


Schreibe es doch ordentlich mathematisch auf. Du willst also eine Funktion

wobei A die ungeraden Zahlen sind betrachten mit .

Diese Funktion ist bijektiv, richtig!

Zitat:
Bei injektiv, nehme ich also elemente aus M und setze diese gleich und gucke, ob sie gleich bzw. ungleich sind( je nach vorgehensweise), dies würde ja für diesen Fall zustimmen.


Du nimmst nicht einfach irgendwelche Elemente aus M, Du nimmst zwei Bilder von Element aus N unter f. Und diese liegen in M.

Zitat:
wir wollen die 2 aus N treffen. also y=2


Die 2 ist keine ungerade Zahl und damit kein Gegenbeispiel zur Surjektivität. Du solltest schon genau schauen woher Du deine Elemente nimmst.
StevenSpielburg Auf diesen Beitrag antworten »

Okay dann nochmal konkret für mein Beispiel.

ich habe eine Menge M der ungeraden natürlichen Zahlen gegeben und ich soll zeigen, dass diese Menge M abzählbar ist, also bijektiv ist.

Also suche ich eine Abbildung dieser Art
f:N->M wobei M die ungeraden Zahlen sind.

f(n)=2n-1

ich kann also alle Elemente der Menge N einsetzen
und bekomme Elemente der Menge M heraus.

Jetzt muss ich noch die Bijektivität beweisen.

injektiv?
mit f(x1)=f(x2) und x1=x2
2x1-1=2x2-1
x1=x2
also injektiv

surjektiv?
yeM und xeN
f(x)=2x-1
x=(y+1)/2
Somit kann ich für y ungerade natürliche Zahlen einsetzen und bekomme
immer ein Element aus N heraus.
somit surjektiv

daraus folgt dann bijektiv?


Falls diese Argumentation zutrifft, warum genau war dann meine Abbildung die ich vorher schon geschrieben habe mit 2n-1 falsch?
Evtl. Antwort: Weil die Abbildung vo A->N ging?
Neue Frage »
Antworten »



Verwandte Themen

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