Abzählbarkeit von Mengen |
28.01.2013, 12:23 | StevenSpielburg | Auf diesen Beitrag antworten » | ||||||||||
Abzählbarkeit von Mengen 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!!! |
||||||||||||
28.01.2013, 12:32 | Mazze | Auf diesen Beitrag antworten » | ||||||||||
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. |
||||||||||||
28.01.2013, 12:54 | 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.. |
||||||||||||
28.01.2013, 12:56 | Mazze | Auf diesen Beitrag antworten » | ||||||||||
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.
Ja, genau so. |
||||||||||||
28.01.2013, 17:00 | 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??? |
||||||||||||
29.01.2013, 12:32 | StevenSpielburg | Auf diesen Beitrag antworten » | ||||||||||
kann vielleicht jemand nochmal kurz drüber schaun ob man das so machen kann? |
||||||||||||
Anzeige | ||||||||||||
|
||||||||||||
29.01.2013, 12:41 | Mazze | Auf diesen Beitrag antworten » | ||||||||||
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 |
||||||||||||
29.01.2013, 21:23 | 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? |
||||||||||||
29.01.2013, 22:02 | Mazze | Auf diesen Beitrag antworten » | ||||||||||
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.
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. |
||||||||||||
30.01.2013, 10:38 | 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? |
||||||||||||
30.01.2013, 10:53 | Mazze | Auf diesen Beitrag antworten » | ||||||||||
In wiefern?
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. |
||||||||||||
30.01.2013, 12:08 | 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. |
||||||||||||
30.01.2013, 12:28 | Mazze | Auf diesen Beitrag antworten » | ||||||||||
Ungünstig formuliert. Unsere Abbildung ist auf den ungeraden Zahlen definiert. Daher interessieren uns für 1) die geraden Zahlen nicht.
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. |
||||||||||||
30.01.2013, 13:36 | StevenSpielburg | Auf diesen Beitrag antworten » | ||||||||||
schuldige aber hilf mir bitte auf die sprünge, ich kann mir unter dieser definition einfach nicht viel vorstellen |
||||||||||||
30.01.2013, 13:50 | 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. |
||||||||||||
30.01.2013, 15:33 | StevenSpielburg | Auf diesen Beitrag antworten » | ||||||||||
okay und was heißt das für meine aufgabe? |
||||||||||||
30.01.2013, 15:36 | StevenSpielburg | Auf diesen Beitrag antworten » | ||||||||||
mit x1 ungleich x2, und y1 ungleich y2 ungleich somit injektiv? |
||||||||||||
30.01.2013, 15:41 | 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 : |
||||||||||||
01.02.2013, 12:35 | 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? |
||||||||||||
01.02.2013, 12:45 | Mazze | Auf diesen Beitrag antworten » | ||||||||||
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. |
||||||||||||
01.02.2013, 13:09 | StevenSpielburg | Auf diesen Beitrag antworten » | ||||||||||
Teil 2? |
||||||||||||
01.02.2013, 13:10 | Mazze | Auf diesen Beitrag antworten » | ||||||||||
Du hast fünf Teilaufgaben, wir haben erst die erste erledigt. |
||||||||||||
01.02.2013, 13:28 | 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 |
||||||||||||
01.02.2013, 13:34 | 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
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. |
||||||||||||
01.02.2013, 14:13 | 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 |
||||||||||||
01.02.2013, 14:18 | Mazze | Auf diesen Beitrag antworten » | ||||||||||
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. |
||||||||||||
01.02.2013, 14:22 | StevenSpielburg | Auf diesen Beitrag antworten » | ||||||||||
|
||||||||||||
01.02.2013, 14:26 | Mazze | Auf diesen Beitrag antworten » | ||||||||||
Der edit war aber noch nicht da vorhin .
In Ordnung
Ist denn 2y für alle eine gerade Zahl? |
||||||||||||
01.02.2013, 14:32 | 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. |
||||||||||||
01.02.2013, 14:40 | Mazze | Auf diesen Beitrag antworten » | ||||||||||
Richtig , A ist die Definitionsmenge oder auch Urbildmenge.
Ja, B nennt man Wertebereich oder Bildmenge.
Das wäre nur die Surjektivität, Du willst auch , dass jedem Element aus A höchstens ein Element aus B zugeordnet wird.
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 . 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.
1 ist keine gerade Zahl und damit nicht relevant für die Betrachtung der Urbildmenge. |
||||||||||||
01.02.2013, 14:44 | 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? |
||||||||||||
01.02.2013, 14:47 | Mazze | Auf diesen Beitrag antworten » | ||||||||||
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. |
||||||||||||
01.02.2013, 14:54 | 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 |
||||||||||||
01.02.2013, 14:57 | Mazze | Auf diesen Beitrag antworten » | ||||||||||
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. |
||||||||||||
01.02.2013, 15:24 | StevenSpielburg | Auf diesen Beitrag antworten » | ||||||||||
okay zu 4. hab ich schon die lösung. wie kann ich 5. beweisen? |
||||||||||||
01.02.2013, 15:25 | Mazze | Auf diesen Beitrag antworten » | ||||||||||
Hab ich weiter oben schon erwähnt. Das Cantorsche Diagonalargument wird dir hier helfen. |
||||||||||||
01.02.2013, 16:20 | StevenSpielburg | Auf diesen Beitrag antworten » | ||||||||||
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! |
||||||||||||
01.02.2013, 22:53 | Mazze | Auf diesen Beitrag antworten » | ||||||||||
Schreibe es doch ordentlich mathematisch auf. Du willst also eine Funktion wobei A die ungeraden Zahlen sind betrachten mit . Diese Funktion ist bijektiv, richtig!
Du nimmst nicht einfach irgendwelche Elemente aus M, Du nimmst zwei Bilder von Element aus N unter f. Und diese liegen in M.
Die 2 ist keine ungerade Zahl und damit kein Gegenbeispiel zur Surjektivität. Du solltest schon genau schauen woher Du deine Elemente nimmst. |
||||||||||||
01.02.2013, 23:22 | 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? |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
Die Neuesten » |
|