 |
 |
 |
 |
 |
 |
Startseite » Forum » Gleichmächtig
Gleichmächtig
Universität / Fachhochschule
Tags: Lineare Algebra
 
|
anonymous 13:40 Uhr, 08.12.2005  |
|
|---|---|
|
Folgende Aufgaben kann ich nicht lösen: Welche der folgenden Mengen sind gleichmächtig? Begründung! A und A, falls A eine beliebige menge ist A und AxA, falls A eine endliche menge ist AxB und BxA, falls A und B beliebige mengen sind N und NxA, falls A eine endliche Menge ist (N= natürliche Zahlen) N und NxN N und NxNxN Wer hilft ganz schnell??!! |
|
| |
 |
|
|
Hallo, du musst jeweils eine Bijektion von der einen Menge in die andere finden. Eine Bijektion ist eine Funktion, die jedem Punkt in der einen Menge genau einen Punkt in der anderen Menge zuordnet. Dabei darf kein Punkt in der zweiten Menge uebrig gelassen werden. Es ist klar, dass wenn du zwei Mengen hast und du jedem Element aus einer der beiden Mengen genau ein Element in der jeweils anderen Menge zuordnest, sie dann gleich viele Elemente enthalten muessen (was das auch immer heissen mag, wenn die Mengen unendlich gross sind). Ich werde dir jetzt nicht jeden Fall begruenden, aber zumindest sagen, welche Mengen gleichmaechtig sind. Bei denen, die es nicht sind, ist es manchmal gar nicht so einfach zu zeigen, dass es keine Bijektion gibt. A und A - gleichmaechtig (natuerlich!). Bijektion: Identitaet A und AxA, A endlich - nicht gleichmaechtig AxB und BxA - gleichmaechtig. Bijektion: (x,y)-->(y,x) N und NxA, A endlich - gleichmaechtig, aber komme auf die Schnelle nicht auf die Bijektion (aufmalen waere einfacher). N und NxN - gleichmaechtig... die Bijektion dafuer ist sehr leicht graphisch darzustellen, aber recht bloed aufzuschreiben. N und NxNxN - gleichmaechtig Das folgt aus dem vorigen. Du kannst NxN eindeutig auf N abbilden und damit auch NxNxN auf NxN. Aber NxN ist gleichmaechtig wie N (auch nach dem vorigen). Anmerkungen: es mag zuerst merkwuerdig erscheinen, dass NxN dieselbe Maechtigkeit wie N hat, aber man darf nicht vergessen, dass die Mengen unendlich sind. Da versagt manchmal die intuitive Anschauung. Bei den endlichen Mengen bin ich davon ausgegangen, dass es sich um die Zahlen 0 bis x handelt, wobei x+1 die Zahl der Elemente in dieser endlichen Menge ist. Das kann man immer annehmen, denn schliesslich kann man die Elemente in einer solchen Menge ja einfach so nummerieren. Cheers, Alex |
|
anonymous 14:03 Uhr, 08.12.2005 |
|
|
ich kann aber doch nicht einfach nur sagen, die Abbildungen sind bijektiv, muss ich Injektivität u. Surjektivität jeweils beweisen und wie mach ich das mit unkonkreten mengen? |
|
anonymous 14:06 Uhr, 08.12.2005 |
|
| ich kann aber doch nicht einfach nur sagen, die Abbildungen sind bijektiv, muss ich Injektivität u. Surjektivität jeweils beweisen und wie mach ich das mit unkonkreten mengen | |
|
|
|
|
Also N ist nicht unkonkret und die anderen Mengen sind endlich und da kannst du immer sagen, dass wenn dir jemand die Menge vor die Nase legt, du einfach eine Funktion zu den Zahlen {0, ..., x} definierst, indem du ganz stumpfsinnig aufschreibst f(Element 1 der Menge) = 0 ... f(Element x der Menge) = x-1 Fuer eine endliche Menge ist das ein endlicher Vorgang, der eine sauber defnierte Funktion hervorbringt. Und diese Funktion ist auch eine Bijektion, was direkt aus der Definition folgt. Und jetzt brauchst du dir nur noch Bijektionen auf die Menge {0, ..., x-1} ueberlegen. Denn es gilt das fuer zwei Bijektionen f und g zum einen f^(-1) und f(g(x)) auch Bijektionen sind. Wenn du also eine Bijektion von deiner Ausgangsmenge nach {0, ..., x-1} findest (ich nenne sie g(x)), dann gilt, dass g(f^(-1)(x)) eine Bijektion in die unkonkrete Menge ist. Cheers, Alex |
|
|
|
|
|
Sorry, in der letzten Zeile muss es f^(-1)(g(x)) heissen. (Erst nach {0, ..., x-1}, dann zurueck in die unkonkrete Menge) |
|
|
|
|
|
Fuer ein Bsp fuehre ich es ausfuehrlich vor. N und NxA, A endlich, sind gleichmaechtig. Beweis: A hat endlich viele Elemente. Nennen wir die Anzahl der Elemente in A: x. Nun schreiben wir alle Elemente aus A untereinander und rechts daneben die Zahlen 0 bis x-1. Sei f: A --> {0, ..., x-1}. Und sei die gerade erstellte Tabelle die Abbildungsvorschrift von f, derart, dass f(x) = Eintrag, der in der Spalte rechts daneben steht. Es ist einsichtig, dass das eine Funktion ist, denn da jedes Element aus A genau einmal in der linken Spalte auftaucht und in der Spalte rechts genau ein Wert steht, ist die Def. einer Fkt. erfuellt. Weiterhin ist f eine Bijektion, denn in der Spalte rechts tauchen alle Werte der Definitionsmenge genau einmal auf. Sei nun g: NxA --> N definiert durch (n, a) --> n*x+f(a). Ich gehe davon aus, dass N die 0 enthaelt. (Falls du wirklich N ohne 0 meinst, musst du f auf {1,...,x} abbilden und g bildet dann (n, a) auf (n-1)*x+f(a).) Die Behauptung ist, dass g bijektiv ist. g ist injektiv, denn sei (n1, a1) und (n2, a2) ungleiche Elemente aus NxA und nehmen wir an, dass n1*x+f(a1)=n2*x+f(a2) ist. Wenn a1 und a2 ungleich sind, so koennen wir auf beiden Seiten das f(...) subtrahieren und durch x teilen. Dann kriegen wir n1 = n2. Aber das ist ein Widerspruch zu der Annahme, dass die Elemente ungleich sind. Nun nehmen wir an, dass a1 = a2. Aber dann muss n1 ungleich n2 sein. Das bedeutet dann, dass f(a1) = f(a2) waere, aber weil f ja eine Bijektion ist, folgt daraus, dass a1 = a2 waere, was auch ein Widerspruch zur Annahme ist. Folglich sind die Bilder zweier Elemente unter g nur gleich, wenn die Elemente gleich sind. Und zwei verschiedene Elemente werden auch auf zwei verschiedene Elemente abgebildet. Daher ist f injektiv. g ist surjektiv. Sei n Element aus N. Und sei m die kleinste natuerlich Zahl, so dass m*x <= n ist. Sei a Element aus A, so dass f(a) := n-m*x (das ist kleiner x und kann daher gefunden werden!). Dann ist g((m, a)) = m*x+f(a) = m*x+n-m*x = n. Also hat jedes Element in N ein Element in der Urmenge, das auf es abbildet. Daher ist g surjektiv. Das beweist, dass g bijektiv ist. Cheers, Alex |
|
|
|
|
| Ein kleiner Fehler ist drin. In der letzten Zeile des ersten Absatzes des Beweises muss es heissen: "...tauchen alle Werte der Wertemenge genau einmal auf." | |
anonymous 22:51 Uhr, 08.12.2005 |
|
|
Tagchen Eva! A und A, falls A eine beliebige menge ist Für A=leere Menge ist die leere Abbildung eine Bijektion (da gibt es nix zu zeigen). Ist A nicht leer, so wähle die Identität f(x)=x. Das ist injektiv: Sind x,y aus A mit f(x)=f(y), so folgt damit und per Definitionem von f, dass x=f(x)=f(y)=y, also x=y. Also ist f injektiv! Ist y aus A vorgegeben, so wählen wir x:=y, was dann aus A ist. Dann gilt f(x)=f(y)=y, also ist f surjektiv! f ist also bijektiv! A und AxA, falls A eine endliche menge ist Wähle zum Beispiel A={1,2}. Dann ist AxA={(1,1),(1,2),(2,1),(2,2)}. Gäbe es eine surjektive Abbildung von A nach AxA, so müßte auch A 4 Elemente haben. A hat aber nur 2! AxB und BxA, falls A und B beliebige mengen sind Das wird gehen, denn: AxB={(a,b): a aus A, b aus B}. Definiere f: AxB -> BxA durch f((a,b)):=(b,a) und rechne die Bijektivität nach! N und NxA, falls A eine endliche Menge ist (N= natürliche Zahlen) Da kann man sich eine Abzählung überlegen, siehe nächste Aufgabe! N und NxA sind also dann gleichmächtig (z.B. nummerierst du die Elemente (sagen wir mal, A habe k Stück) von 1 bis k durch, und betrachtest die Abbildung f: NxA -> N, definiert durch f((n,a)):=n+Nummer(a) und zeigst die Bejektivität!) N und NxN sind gleichmächtig. Dazu siehe das Kantorsche Diagonalisierungsverfahren bzw. die Abzählung von Q! N und NxNxN wird dann auch gleichmächtig sein. Einfacher begründen ließe sich das z.B. so: NxNxN= Vereinigung (über alle i aus N) {(a,b,i): a,b aus N}=Vereinigung (über alle i aus N) NxNx{i} und weil NxN nach dem Kantorschen Diagonalisierungsverfahren abzählbar ist, ist NxNxN als abzählbare Vereinigung über eine abzählbare Menge abzählbar! Gruß, Weißnix |
|
|
Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.
|
456663
456655