gleichmächtige Mengen < Mengenlehre < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:59 Mi 07.11.2012 | | Autor: | heinze |
| Aufgabe | Zeige: [mm] \IN [/mm] und [mm] \INx\IN={(x,y): x,y\in \IN} [/mm] sind gleichmächtig.
Tipp: Deute die Paare [mm] (x,y)\INx\IN [/mm] als Punkte in der x-y-Ebene und versuche diese mit (1,1) beginnend abzuzählen. |
Zwei Mengen sind gleichmächtig, wenn sie die gleiche Anzahl an Elementen besitzenund endlich sind.
[mm] \IN [/mm] beinhaltet alle natürlichen Zahlen, also :
[mm] \IN={1,2,3,4,...,n}
[/mm]
[mm] \IN={1,2,3,4,...,n}
[/mm]
also erhält man die Zahlenpaare: (1,1),(1,2),(2,1),..,(n,n)
So richtig ist mir der Sinn dieser Aufgabe noch nicht klar.
LG
heinze
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:17 Mi 07.11.2012 | | Autor: | luis52 |
Moin
> Zwei Mengen sind gleichmächtig, wenn sie die gleiche
> Anzahl an Elementen besitzenund endlich sind.
Auch unendliche Mengen koennen gleichmaechtig sein, siehe unten. Das Kriterium lautet verallgemeinernd: Zwei Mengen sind gleichmächtig, wenn es eine bijektive Abbildung zwischen ihnen gibt.
>
> [mm]\IN[/mm] beinhaltet alle natürlichen Zahlen, also :$ [mm] \IN={1,2,3,4,...,n} [/mm] $
Du irrst, [mm]\IN=\{1,2,3,\dots\}[/mm] . Diese Menge ist unendlich.
>
> [mm]\IN={1,2,3,4,...,n}[/mm]
> [mm]\IN={1,2,3,4,...,n}[/mm]
>
Hier kannst du dich auf den Kopf stellen, es gibt keine Bijektion zwischen [mm] $\{(i,j)\mid i,j=1,\dots,n\}$ [/mm] und [mm] $\{1,\dots,n\}$, [/mm] sofern $n>1$ ist. Die erste Mengen hat [mm] n^2, [/mm] die zweite hat $n$ Elemente ...
vg Luis
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:06 Mi 07.11.2012 | | Autor: | heinze |
Mit bijektionen sollte hier nichts gezeigt werden.
[mm] \INx\IN [/mm] entspricht doch [mm] \IN^2, [/mm] richtig? das ist das karthesische Produkt .
Mir ist nicht klar wie ich Gleichmächtigkeit hier mit abzählen zeigen soll.
LG
heinze
|
|
|
| |
|
Unsere Texte haben sich gerade überschnitten. Lies dir zunächst meine Erklärung durch.
Eine Abbildung von [mm] \IN [/mm] in eine Menge kann man mit dem Zählen vergleichen: 1 wird abgebildet auf das erste Element, zwei auf das zweite usw.
Du musst also nur eine Anordnung der Zahlenpaare finden, aus der klar wird, dass jedes Zahlenpaar irgendwann (also nicht nach unendlich vielen) vorkommt. Du kannst also nicht sagen: zuerst kommt (0|0), dann (0|1) usw. bis [mm] (0|\infty), [/mm] dann (1|0), dann (1|1) usw. bis [mm] (1|\infty), [/mm] denn du kannst gar nicht sagen, das wievielte Glied (1|1) sein wird, weil du mit der ersten Serie gar nicht fertig wirst.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 06:05 Do 08.11.2012 | | Autor: | heinze |
Wenn ich das so betrachte ist mir das klar, Probleme bereitet es mir eine Anordnung zu finden!
Das ist mir zu Logisch um es richtig zu formulieren.
LG
heinze
|
|
|
| |
|
> Wenn ich das so betrachte ist mir das klar, Probleme
> bereitet es mir eine Anordnung zu finden!
Hallo,
das Punktgitter in der Ebene hast Du vor Augen?
Du mußt nun einen Weg durch dieses Gitter finden, so daß Du zählend an jedem Punkt vorbeikommst.
Du kannst das Gitter nicht "zeilenweise" abarbeiten, denn wenn Du den Weg (1,1),(1,2), (1,3), (1,4) usw. wählst,
kommst Du ja nier bei (2,1) an.
Du mußt also geschickter durchs Gitter wandern... Im Zickzack...
> Das ist mir zu Logisch um es richtig zu formulieren.
Schmarrn...
Wenn Du lange genug probiert hast, kannst Du Dich ja auch mal in der wikipedia vom Bildchen bei der "Cantorschen Paarungsfunktion" inspirieren lassen.
LG Angela
>
> LG
> heinze
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:24 Do 08.11.2012 | | Autor: | heinze |
Danke angela, die SEite auf Wiki hatte ich mir vorher bereits angeschaut und das ist mir klar. Klar ist mir nicht wie ich zeigen soll, dass [mm] \IN [/mm] und [mm] \INx\IN [/mm] gleichmächtig sind.
Auf wiki das bezieht sich ja auf [mm] \IN [/mm] x [mm] \IN
[/mm]
reicht es zu zeigen das gilt [mm] 2^x(2y+1) [/mm] ?
LG
heinze
|
|
|
| |
|
> Danke angela, die SEite auf Wiki hatte ich mir vorher
> bereits angeschaut und das ist mir klar.
Hallo,
mir ist nicht ganz klar, was auf der Seite Dir klar ist - aber vielleicht muß ich das auch gar nicht wissen.
> Klar ist mir nicht
> wie ich zeigen soll, dass [mm]\IN[/mm] und [mm]\IN x\IN[/mm] gleichmächtig
> sind.
>
> Auf wiki das bezieht sich ja auf [mm]\IN[/mm] x [mm]\IN[/mm]
Es wird dort vorgemacht, wie man die Elemente von [mm] \IN\times \IN [/mm] abzählen kann.
Was ist "abzählen"? Eine Bijektion in die natürlichen Zahlen.
>
>
> reicht es zu zeigen das gilt [mm]2^x(2y+1)[/mm] ?
??? Was meinst Du mit diesem freischwebenden Term?
Auch wenn es Dir nicht so gefällt: immer, wenn Du zeigen möchtest, daß irgendeine Menge M gleichmächtig zu [mm] \IN [/mm] ist, mußt Du irgendwie zeigen, daß es eine Bijektion f: [mm] M\to \IN [/mm] gibt.
Wenn Du mit
f: [mm] \IN \times\IN \to \IN\setminus\{0\}
[/mm]
[mm] f(x,y):=$2^x(2y+1)$
[/mm]
argumentieren möchtest, mußt Du die Bijektivität dieser Funktion beweisen.
LG Angela
>
> LG
> heinze
|
|
|
| |
|
Es hat keinen Sinn, dich länger zappeln zu lassen; man kommt drauf oder eben nicht.
Bilde von allen Paaren die Summe der beiden Glieder, also zu (a|b) den Wert a+b. Alle Paare, die die selbe Summe bilden, gehören zur selben "Serie".
Nun arbeitest du die Serien der Reihe nach ab, wobei du die Paare noch systematisch so anordnest, dass a steigt und b fällt:
Serie Paare
2 (1|1)
3 (1|2), (2|1)
4 (1|3), (2|2), (3|1)
5 (1|4), (2|3), (3|2), (4|1)
usw.
Wie du siehst, kommt jedes Paar irgendwann dran, keines bleibt übrig. Wenn du jetzt zu jedem Paar noch die Stelle angibst, wann es drankommt, kanst du feststellen, das jeder Zahl aus [mm] \IN [/mm] ein Paar zugeordnet wird und keines übersprungen wird, somit nicht mehr Paare als natürliche Zahlen existieren.
Beispiel: Wann kommt (47|8) dran?
Serie 2 hat 1 Element, Serie 3 2 Elemente usw.. (47|8) gehört zur Serie 47+8=55. Bis zur Serie 54 einschließlich gibt es 1+2+3+...+53 = 53*54/2=1431 Elemente.Das Paar (47|8) ist das 47. Element in der nächsten Serie und erhält damit die Nummer 1431+47=1478.
|
|
|
| |
|
Endliche Mengen gelten als gleich-mächtig, wenn sie gleich viele Elemente besitzen.
Zwei unendliche Mengen A und B gelten als gleich mächtig, wenn man eine bijektive Abbildung zwischen ihnen finden kann. Man könnte den Eindruck haben, dass a) alle unendlichen Mengen gleich mächtig sind, nämlich die Mächtigkeit "unendlich" haben, oder b) dass eine unendliche Menge, aus der man z.B. 3 Elemente entfernt, eine geringere Mächtigkeit hat als die Ausgangsmenge. Beides ist falsch.
Beispiel: Vergleiche [mm] \IN [/mm] mit Q = Menge der Quadratzahlen. Man meint, es müsse "mehr" natürliche als Quadratzahlen geben, da ja zwischen den Quadratzahlen natürliche Zahlen liegen. Stell dir vor, du schreibst jede natürliche Zahl auf eine Münze und auf die Rückseite die dazugehörige Quadratzahl. Jetzt vergisst du, dass sich unter den natürlichen zahlen ja auch die Quadratzahlen befinden, betrachtest also nur Vorder- und Rückseite jeder Münze. Dann stellst du fest: Zu jeder natürlichen Zahl gibt es genau eine Quadratzahl und umgekehrt, also gibt es von jeder Sorte gleich viel. Die Bijektion wird durch die Münze vermittelt.
Um die Gleich-Mächtigkeit von unendlichen (!) Mengen zu testen, muss man nicht immer unbedingt eine Bijektion finden. Wenn man zeigen kann, dass es von A nach B eine surjektive Abbildung gibt und von B nach A ebenfalls - ggf. eine andere - surjektive Abbildung, sind die Mengen auch gleich mächtig.
Ein Beispiel für nicht-gleichmächtige unendliche Mengen: [mm] \IN [/mm] und [mm] \IR.
[/mm]
----------------------------------------------------
Zu deinem Problem:
(x|y) [mm] \mapsto [/mm] x weist jedem Element von [mm] \IN \times \IN [/mm] eines aus [mm] \IN [/mm] zu. Damit werden alle Elemente aus [mm] \IN [/mm] "erwischt" (surjektiv), eigentlich sogar alle unendlich oft (für alle verschiedenen y, wenn x gleich bleibt). Also sind in [mm] \IN [/mm] nicht mehr Elemente als in [mm] \IN \times \IN, [/mm] eher weniger.
Jetzt musst du zeigen: Den Elementen aus [mm] \IN [/mm] kann man die Paare (x|y) so zuordnen, dass ebenfalls alle "erwischt" werden, schlimmstenfalls auch mehrfach, aber keines darf übrig bleiben. Dann ist bewiesen, dass in [mm] \IN \times \IN [/mm] nicht mehr Elemente als in [mm] \IN [/mm] sind. Damit sind dann beide Mengen gleich mächtig.
Dieser zweite Teil des Beweises verlangt einige Fantasie. Du musst nicht genau angeben, auf welches Paar z.B die Zahl 12 abgebildet wird, sondern nur klarmachen, dass kein Paar ausgelassen wird.
|
|
|
|
