Mathematik: Der Satz von Schröder-Bernstein - explizit
Released by matroid on Sa. 19. November 2005 20:04:47 [Statistics]
Written by Martin_Infinite - 12693 x read [Outline] Printable version Printer-friendly version -  Choose language   
Mathematik

\(\begingroup\) Es wurde bereits hier ein Artikel über den Satz von Schröder-Bernstein geschrieben. Dieser besagt folgendes: Seien A,B zwei Mengen. Gibt es Injektionen A -> B und B -> A, so gibt es eine Bijektion A -> B. Oder kurz mit Kardinalzahlen: \blue abs(A) <= abs(B) <= abs(A) => abs(A) = abs(B) In dieser Form wird der Satz zumeist formuliert, und auch verwendet. Bloß wie sieht diese Bijektion denn überhaupt aus, die man aus den beiden Injektionen erhält? Das schauen wir uns hier an einigen voneinander unabhängigen Beispielen an. Dabei wird der Satz von Schröder-Bernstein also nicht als reine Existenzaussage, sondern eben als Konstruktionsvorschrift gesehen.

Der Satz allgemein Wir beweisen zunächst den Satz von Schröder-Bernstein allgemein. Es gibt dafür mehrere Möglichkeiten, allerdings wird besonders die folgende für die expliziten Bijektionen praktisch sein. Determinacy hat hier sehr anschaulich eine Vorbereitung dafür geschildert, die hier noch einmal wiedergegeben wird. Es seien A,B disjunkte Mengen und es gebe eine Injektion f : A \union B -> A. Dann gibt es eine Bijektion g : A \union B -> A, und zwar kann diese wiefolgt konstruiert werden: Die Injektion f bildet B bijektiv auf die Teilmenge f[B] von A ab. Diese wird wieder auf eine Teilmenge f[f[B]]=f^2 [B] von A abgebildet, etc. Alle diese Mengen sind disjunkt, denn f ist injektiv, und A und B sind disjunkt: Bild Es ergibt sich also eine "Spur" von Teilmengen von A. Damit kann man A \union B bijektiv auf A abbilden: Ein Element in einer solchen Teilmenge wird durch f in die nächste abgebildet, der Rest wird festgelassen. Formal setzen wir also S := B \union f[B] \union f^2 [B] \union ... = union(f^n [B] , n \in \IN_0). Dann haben wir die Bijektion g : A \union B -> A, x |-> fdef(f(x),x \in S;x,sonst) Nun seien A,B beliebige Mengen und f : A -> B, g : B -> A injektiv. Betrachte A' = g[B], B' = A\\A' . Dann sind A',B' disjunkt, und es gibt eine Injektion A = A' \union B' -> A', nämlich die Komposition g f. Aus der Vorbereitung ergibt sich dann eine Bijektion A -> A'. Weil g injektiv ist, ist A' zu B gleichmächtig. Wenn wir dies zurück\- verfolgen, erhalten wir die allgemeine Konstruktionsvorschrift nach dem Satz von Schröder\-Bernstein: \frameon\Seien f : A -> B , g : B -> A Injektionen. Definiere eine Folge von Teilmengen von A rekursiv durch X_0 = A \\ g[B] X_(n+1) = (g f)[ X_n ] und sei X ihre Vereinigung. Dann ist h : A -> B , a |-> fdef(f(a),a \in X;g^(-1)(a),sonst) \frameoff\eine Bijektion. Die Vorbereitung wird aber schon oft ausreichen: \frameon\Sind A,B disjunkt und f : A \union B -> A injektiv, so ist g : A \union B -> A , x |-> fdef(f(x),x \in S;x,sonst) \frameoff\bijektiv, wobei S := union(f^n [B], n \in \IN_0).
1. Anwendung: Intervalle Wir zeigen jetzt, dass alle Intervalle array( ) \blue intervall(a,b), intervallog(a,b), intervallgo(a,b), intervalloo(a,b) mit a < b gleichmächtig sind. Dabei können wir a = 0 und b = 1 annehmen; schließlich ist jeweils die Multiplikation mit b-a eine Bijektion. Ferner ist intervallog(0,1) ~= intervallgo(0,1) leicht einzusehen: Man kann die Punkte an 1\/2 "spiegeln", d.h. x |-> 1-x ist eine Bijektion. Es bleiben also zwei Gleichmächtigkeiten übrig. Mit dem Satz von Schröder\-Bernstein werden wir eine explitite Bijektion konstruieren. \big\1.1 \normal array( ) \blue intervall(0,1) ~= intervallgo(0,1) Wir zerlegen intervall(0,1) zunächst disjunkt in A = intervallgo(0,1) und B = {1}. Es gibt eine Injektion f: intervall(0,1)=A \union B->A, etwa x|->x\/2 . Wir können daher die Vorbereitung anwenden. Die Teilmengen von A sind dabei nur einpunktig, es gilt nämlich f^n [B]=menge(1/2^n). Die Bijektion sieht also wiefolgt aus: \red g : intervall(0,1) -> intervallgo(0,1) , x |-> fdef(1/2^(n+1),x=1/2^n für ein n \in \IN_0;x,sonst) Schauen wir uns das einmal in einem Koordinatensystem an: \geoon e(400,400) xy(0,1) replace() nolabel() name(bild1) g(1,0) print(intervall(0,1) ~= intervallgo(0,1),.7,.05) for(n,0,10,1,konst(x,power(2,-n)) konst(y,power(2,-n-1)) p(x,y)) c(white) form(*) for(n,0,10,1,konst(x,power(2,-n)) p(x,x)) \geooff array( ) geoprint(bild1) Hieran wird alternativ klar, wie diese Bijektion "funktioniert": Man geht von der identischen Funktion aus. Dabei bereitet zunächst nur die 1 Probleme, der muss man also ein anderes Bild geben. Dann muss man aber dafür sorgen, dass dieses nicht noch einmal angenommen wird, etc. \big\1.2 \normal array( ) \blue intervall(0,1) ~= intervalloo(0,1) Wir zerlegen jetzt intervall(0,1) disjunkt in A = intervalloo(0,1) und B = {0,1}. Eine Injektion A \union B -> A erhalten wir, indem das Intervall intervall(0,1) skaliert und dann entsprechend in die Mitte verschoben wird. Der Faktor 1/2 ergibt die Injektion f : A \union B -> A, x|->1/4+x/2 . Wir wenden wieder die Vorbereitung an. Die Teilmengen sind dabei zweipunktig: f^n [B] = menge(1/2 - 1/2^(n+1) , 1/2 + 1/2^(n+1)) Daraus erhalten wir die Bijektion \red g : intervall(0,1) -> intervalloo(0,1) , \red x |-> fdef(1/2+-1/2^(n+2),x=1/2+-1/2^(n+1) für ein n \in \IN_0;x,sonst) die wir uns wieder im Koordinatensystem ansehen: \geoon e(400,400) xy(0,1) replace() nolabel() name(bild1) g(1,0) print(intervall(0,1) ~= intervalloo(0,1),.7,.05) for(n,1,10,1,konst(x,0.5+power(2,-n)) konst(y,0.5+power(2,-n-1)) p(x,y) konst(x,0.5-power(2,-n)) konst(y,0.5-power(2,-n-1)) p(x,y)) c(white) form(*) for(n,1,10,1,konst(x,0.5+power(2,-n)) p(x,x) konst(x,0.5-power(2,-n)) p(x,x)) \geooff array( ) geoprint(bild1) Diese Bijektion funktioniert also ähnlich wie die aus 1.1.; am Anfang bereiten aber schon 0 und 1 Probleme, sodass "symmetrisch geschoben" werden muss. Noch ein paar Anmerkungen. Es lässt sich sogar zeigen, dass die genannten Intervalle in einem beliebigen angeordneten Körper K zu K gleichmächtig sind, siehe dazu hier. Ferner lässt sich die Bijektion zwischen den Intervallen auch anders finden, das hat Buri hier ausgeführt.
2. Anwendung: Komplemente Allgemein ist das Komplement einer endlichen Menge in einer unendlichen Menge X stets zu X gleichmächtig. Eine explizite Bijektion wird da kaum zu finden sein, weil beim Existenzbeweis das Auswahlaxiom benötigt wird. Aber in manchen Fällen geht es doch, wie z.B. bei array( ) \blue\IR \\ menge(0) ~= \IR Wir zerlegen dafür \IR disjunkt in A:= \IR \\ menge(0) und B := menge(0). Nun ist eine Injektion A \union B -> A, also \IR -> \IR \\ menge(0) gesucht. Wie oben bemerkt, ist \IR zu intervalloo(0,1) gleichmächtig, sodass man so eine Injektion schon einmal angeben kann. Die Exponentialfunktion tut's natürlich auch. Allerdings müssen wir doch, um dann die Vorbereitung anzuwenden, immer wieder die Injektion anwenden, ausgehend von 0. Eine explizite Formel dafür ergeben die obigen Injektionen \IR -> \IR \\ menge(0) nicht. Also sollten wir die gesuchte Injektion im 1. Quadranten ganz einfach gestalten, etwa linear. Was im 2. geschieht, ist für die Konstruktion dann nebensächlich, hauptsache am Ende ist es eine Injektion. Das kann man dadurch realisieren, dass die gesamte Abbildung streng monoton wachsend ist. Zum Beispiel könnte man auf folgendes kommen: f : \IR -> \IR \\ menge(0) , x |-> fdef(x+1,x>=0;2/\p arctan(x)+1,x<0) Es gilt dann f^n(0) = n, und damit erhalten wir die Bijektion \red g : \IR -> \IR \\ menge(0) , x |-> fdef(x+1,x \in \IN_0;x,sonst) Und darauf sind wir ziemlich systematisch mit dem Satz von Schröder\- Bernstein gekommen. Es geht natürlich auch ohne, erfordert aber schon etwas an Einfallsreichtum\/Erfahrung, auch so darauf zu kommen. Wir wollen das jetzt noch verallgemeinern: Sei M eine nichtleere beschränkte Teilmenge von \IR. Dann gibt es eine Bijektion array( ) \blue\IR \\ M ~= \IR Konstruktion __: Indem wir \IR gegebenfalls in sich verschieben, können wir annehmen, dass alle Elemente von M >= 0 sind. Genauer gesagt wählen wir eine untere Schranke a von M, und setzen M'=menge(m-a|m \in M). Dann ist \IR\\M -> \IR\\M' , x |-> x-a bijektiv, und alle Elemente von M' sind >= 0. Wähle ein b \in \IN_0 als obere Schranke von M. Dann ist b-a \in \IN_0 eine obere Schranke von M'. Wie bei \IR \\ menge(0) ~= \IR finden wir die folgende Injektion \IR -> \IR\\M', x |-> b-a + fdef(x+1,x>=0;2/\p arctan(x)+1,sonst) Für jedes x >= 0 gilt dann f^n(x)=n(b-a+1)+x. Daraus erhalten wir die Bijektion g': \IR -> \IR\\M', die x auf fdef(x+(b-a+1),x=n(b-a+1)+m' für ein (m',n) \in M' \times \IN_0;x,sonst) =fdef(x+(b-a+1),x=n(b-a+1)+m-a für ein (m,n) \in M \times \IN_0;x,sonst) abbildet. Zusammen mit der Bijektion \IR\/M -> \IR\/M' ergibt sich schließlich die Bijektion g : \IR -> \IR\/M, \red x |-> fdef(x+b+1,x \in S;x+a,sonst) wobei S die Menge aller rellen Zahlen der Form x=n(b-a+1)+m-a für ein (m,n) \in M \times \IN_0 ist, kurz \red S := \IN_0 (b-a+1)+M-a Beispiel__ : Wir wählen M = intervalloo(-1,1). Dann sind a = -1, b = 1 Schranken von M, und über S=intervalloo(0,2) \union intervalloo(3,5) \union intervalloo(6,8) \union intervalloo(9,11) \union .... erhalten wir die Bijektion \IR -> \IR \\ intervalloo(-1,1) , x |-> fdef(x+2,x \in S;x-1,sonst) Im Koordinatensystem sieht das wiefolgt aus: \geoon xy(-3,10) e(400,400) replace() nolabel() for(x,0,6,3,konst(a,x) konst(b,x+2) konst(c,x+4) p(a,b,p1,hide) p(b,c,p2,hide) s(p1,p2) for(x,2,8,3,konst(a,x) konst(b,x-1) konst(c,x+1) p(a,b,p1) p(c,a,p2) s(p1,p2) p(0,-1,p1) p(-3,-4,p2,hide) s(p1,p2) print(\IR ~= \IR \\ intervalloo(-1,1),6,-2.2) \geooff array( ) geoprint()
3. Anwendung: Die Abzählung der rationalen Zahlen. Hier soll es um eine explizite Abzählung der rationalen Zahlen gehen: array( ) \blue\IN ~= \IQ Dabei können wir uns freilich auf \IQ^\+, der Menge der positiven rationalen Zahlen beschränken. Ist nämlich h : \IN -> \IQ^\+ eine Abzählung von \IQ^\+ , so erhalten wir daraus eine von \IQ: 0 , h_1 , -h_1 , h_2 , -h_2 , ... Zählen wir zunächst \IN \times \IN mit dem sog. Diagonalverfahren ab: (1,1), (1,2),(2,1), (1,3),(2,2),(3,1), (1,4),(2,3),(3,2),(4,1), ... In der Reihe k stehen alle Paare (x,y) mit x+y-1=k. Dies liefert eine Bijektion g : \IN \times \IN -> \IN , (x,y) |-> x+sum(k,k=1,x+y-2)=x+(x+y-2)(x+y-1)/2 Die inverse Abbildung lässt sich nur rekursiv darstellen: g^(-1)(1)=(1,1), g^(-1)(n)=(x,y) => g^(-1)(n+1)=fdef((1,x+1),y=1;(x+1,y-1),sonst) Es gibt nun eine offensichtliche Surjektion \IN \times \IN -> \IQ^\+ . Verkettet mit g^(-1) ergibt dies eine Surjektion \IN -> \IQ^\+ . Wählt man für jede positive rationale Zahl das kleinste Urbild bez. dieser Surjektion aus, so haben wir endlich eine Injektion g' : \IQ^\+ -> \IN . Und diese bildet gekürzte__ Brüche x\/y auf g(x,y) ab. Mit der Inklusion f : \IN -> \IQ^\+ können wir jetzt den Satz von Schröder\-Bernstein anwenden. Zunächst einmal gilt für alle x \in \IN (g'f)(x)=g'(x/1)=x+(x+1-2)(x+1-1)/2=x(x+1)/2 Definiert man also X_n \subseteq \IN rekursiv durch X_0 = \IN \\ g'[ \IQ^\+ ] X_(n+1) = menge(x(x+1)/2 | x \in X_n) und X = union(X_n,n \in \IN_0), so haben wir die folgende Bijektion; h : \IN -> \IQ^\+ , x |-> fdef(x,x \in X;g^(-1)(x),sonst) Die schauen wir uns jetzt einmal an. Es gilt X_0 = menge(x+(x+y-2)(x+y-1)/2 | x,y \in \IN nicht teilerfremd array( )= menge(5,12,13,14,23,25,27,31,34,38,40,41,42,44,..) Von dieser Menge werden nun Dreieckszahlen gebildet, was beliebig oft wiederholt wird. Die nächsten beiden Mengen sehen z.B. so aus: X_1 = {15,78,91,105,...} X_2 = {120,3081,4186,...} Alle diese natürlichen Zahlen zusammen bilden die Fixpunkte unserer Bijektion h. Der Rest verläuft wie bei dem Diagonalverfahren. Schauen wir uns es nun konkret an: 1/1 , 1/2 , 2/1 , 1/3 , vec(5) , 3/1 , 1/4 , 2/3 , 3/2 , 4/1 , 1/5 , vec(12) , vec(13) , vec(14) , vec(15) , 1/6 , 2/5 , 3/4 , 4/3 , 5/2 , 6/1 , 1/7 , vec(23) , 3/5 , vec(25) , 5/3 , vec(27) , 7/1 , 1/8 , 2/7 , vec(31) , 4/5 , 5/4 , vec(34) , 7/2 , 8/1 , 1/9 , vec(38) , 3/7 , vec(40) , vec(41) , vec(42) , 7/3 , vec(44) , 9/1 , 1/10 , 2/9 , 3/8 , 4/7 , 5/6 , 6/5 , 7/4 , 8/3 , 9/2 , 10/1 , 1/11 , vec(57) , 3/9 , vec(59) , 5/7 , vec(61) , 7/5 , vec(63) , vec(64) , vec(65) , 11/1 , 1/12 , 2/11 , 3/10 , 4/9 , 5/8 , 6/7 , 7/6 , 8/5 , 9/4 , 10/3 , 11/2 , vec(78) , 1/13 , vec(80) , 3/11 , vec(82) , 5/9 , vec(84) , vec(85) , vec(86) , 9/5 , vec(88) , 11/3 , vec(90) , vec(91) , ... Hier sieht man noch einmal schön, was der Satz von Schröder\-Bernstein für eine Abzählung produziert: Der Tatsache, dass beim Diagonalverfahren Brüche doppelt vorkommen, wird durch Fixpunkte abgeholfen. Diese dürfen bei der weiteren Abzählung nicht noch einmal vorkommen, sodass sich diese "verschachteln". Zum Beispiel bedingt der Fixpunkt 5, dass am Ende der 5. Reihe nicht 5\/1 stehen kann, sondern 15 ein Fixpunkt sein muss.
Schluss Wie in der Einleitung gesagt, sollte es hier darum gehen, den Satz von Schröder-Bernstein als Konstruktionsvorschrift zu nutzen. Ich fand es ziemlich interessant, was dabei herauskommt. Zumal man auf die resultierenden Bijektionen wohl nicht so ohne weiteres kommen kann. Natürlich gehen die Anwendungen über die hier genannten hinaus. Ihr könnt aber auch einmal selbst mit dem Satz herumspielen :) Leider ist es aber oft so, dass die Bijektion aus dem Satz von Schröder-Bernstein trotz der Konstruktion nicht wirklich explizit zu bestimmen ist. Wenn man etwa eine Bijektion zwischen \wp(\IN) und \IR konstruieren möchte, ist eine Wohlordnung auf \IR oder eine Ordnung von \IQ , die durch eine Abzählung davon bestimmt ist, nötig. Vermutlich. Wenn ihr mal wieder über den Satz von Schröder-Bernstein stolpern solltet, könnt ihr einmal schauen, ob es nicht auch explizit geht ;). Zumal man manchmal auch ganz ohne den Satz auskommt.
\(\endgroup\)
Get link to this article Get link to this article  Printable version Printer-friendly version -  Choose language     Kommentare zeigen Comments  
pdfFür diesen Artikel gibt es keine pdf-Datei


Arbeitsgruppe Alexandria Dieser Artikel ist im Verzeichnis der Arbeitsgruppe Alexandria eingetragen:
: Mathematik :: Abbildungen :: Mengenlehre :: Reine Mathematik :
Der Satz von Schröder-Bernstein - explizit [von Martin_Infinite]  
Es wurde bereits hier ein Artikel über den Satz von Schröder-Bernstein geschrieben. Dieser besagt folgendes: Gibt es Injektionen A -> B, B -> A, so gibt es eine Bijektion A -> B.
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
 
Aufrufzähler 12693
 
Aufrufstatistik des Artikels
Insgesamt 1556 externe Seitenaufrufe zwischen 2012.01 und 2022.05 [Anzeigen]
DomainAnzahlProz
https://matheplanet.com130.8%0.8 %
https://google.com835.3%5.3 %
https://google.de45028.9%28.9 %
https://de.wikipedia.org10.1%0.1 %
http://google.de66042.4%42.4 %
http://math.stackexchange.com1127.2%7.2 %
http://de.wikipedia.org865.5%5.5 %
https://www.bing.com382.4%2.4 %
http://google.gr201.3%1.3 %
https://google.lu181.2%1.2 %
https://duckduckgo.com120.8%0.8 %
https://www.ecosia.org100.6%0.6 %
http://google.fr60.4%0.4 %
http://google.com50.3%0.3 %
http://de.m.wikipedia.org40.3%0.3 %
https://de.m.wikipedia.org60.4%0.4 %
https://www.startpage.com30.2%0.2 %
http://de.academic.ru20.1%0.1 %
https://startpage.com20.1%0.1 %
https://search.becovi.com20.1%0.1 %
http://deacademic.com30.2%0.2 %
http://wuerstchenundbier.com20.1%0.1 %
http://google.at10.1%0.1 %
http://search.conduit.com20.1%0.1 %
http://yandex.ru40.3%0.3 %
http://r.duckduckgo.com10.1%0.1 %
https://www.linuxmint.com10.1%0.1 %
http://www.search.ask.com10.1%0.1 %
https://deref-gmx.net10.1%0.1 %
http://archive.is10.1%0.1 %
http://suche.t-online.de20.1%0.1 %
http://de.dbpedia.org10.1%0.1 %
http://images.google.de10.1%0.1 %
http://www.ecosia.org10.1%0.1 %
http://search.comcast.net10.1%0.1 %

Aufrufer der letzten 5 Tage im Einzelnen
Insgesamt 44 Aufrufe in den letzten 5 Tagen. [Anzeigen]
DatumAufrufer-URL
2022.05.22 16:35viewtopic.php?topic=152237
2022.05.01-2022.05.21 (43x)https://google.com/

Häufige Aufrufer in früheren Monaten
Insgesamt 1422 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
2020-2022 (359x)https://google.de/
2013-2016 (278x)http://google.de/url?sa=t&rct=j&q=
2012-2018 (103x)http://math.stackexchange.com/questions/9274/isomorphism-between-0-1-to-0-1
201206-12 (96x)http://google.de/url?sa=t&rct=j&q=schröder-bernstein
2012-2017 (81x)http://de.wikipedia.org/wiki/Cantor-Bernstein-Schröder-Theorem
201311-11 (69x)http://google.de/url?sa=t&rct=j&q=cantor-bernstein-schröder-satz
202103-05 (59x)https://google.de
201201-05 (51x)http://google.de/url?sa=t&rct=j&q=schröder-bernstein beweis
2020-2021 (40x)https://google.com/
2020-2022 (38x)https://www.bing.com/
201204-04 (20x)http://google.gr/url?sa=t&rct=j&q=
201210-10 (18x)http://google.de/url?sa=t&rct=j&q=konstruieren sie explizite bijektion
202110-10 (18x)https://google.lu/
201305-05 (16x)http://google.de/url?sa=t&rct=j&q=satz von schröder bernstein martin_infin...
201304-04 (14x)http://google.de/url?sa=t&rct=j&q=schröder bernstein
201303-03 (13x)http://google.de/url?sa=t&rct=j&q=trichotomie beweis dedekind
202008-08 (12x)https://google.de/url?sa=t
201501-01 (12x)http://google.de/url?sa=t&rct=j&q=dedekind cantor bernstein beweis
2020-2022 (11x)https://duckduckgo.com/
201202-02 (11x)http://google.de/url?sa=t&source=web&cd=3&ved=0CDIQFjAC
201203-03 (10x)http://google.de/url?sa=t&rct=j&q=schröder mathematik
201510-10 (10x)http://google.de/url?sa=t&source=web&cd=2&rct=j&q=satz von bernstein beweis
201306-06 (8x)http://google.de/url?sa=t&rct=j&q=satz von schröder-bernstein beweis
201302-02 (8x)http://google.de/url?sa=t&rct=j&q=trichotomie äquivalent auswahlaxiom
2013-2017 (8x)http://math.stackexchange.com/questions/9274/isomorphism-between-0-1-to-0-1/9...
2020-2021 (8x)https://www.ecosia.org/
2016-2017 (7x)http://google.de/
201505-05 (6x)http://google.de/url?sa=t&rct=j&q=einfachster beweis des bernstein und cantor...
201502-02 (6x)http://google.fr/url?sa=t&rct=j&q=
201301-01 (6x)http://google.de/url?sa=t&rct=j&q=satz von schröder-bernstein aufgaben
201803-10 (5x)http://google.com/
201307-07 (5x)http://google.de/url?sa=t&rct=j&q=cantor-bernstein-schröder-satz beweis
201403-03 (4x)http://google.de/url?sa=t&rct=j&q=schroeder bernstein
201209-09 (4x)http://google.de/url?sa=t&rct=j&q=schröder mathe
201202-12 (4x)http://de.m.wikipedia.org/wiki/Cantor-Bernstein-Schröder-Theorem
2020-2022 (4x)https://de.m.wikipedia.org/

[Top of page]

"Mathematik: Der Satz von Schröder-Bernstein - explizit" | 13 Comments
The authors of the comments are responsible for the content.

Re: Der Satz von Schröder-Bernstein - explizit
von: nakamura am: So. 20. November 2005 01:04:44
\(\begingroup\)\(\endgroup\)
 

Re: Der Satz von Schröder-Bernstein - explizit
von: Martin_Infinite am: So. 20. November 2005 02:22:53
\(\begingroup\)Hi, das betrifft ja nichtwirklich das Thema, und wurde daher nicht ausgeführt. Kann man aber mal tun ;) \blue\Sei X eine unendliche Menge, und T eine endliche Teilmenge von X. \blue\Dann sind X und X\\T gleichmächtig. Beweis(plan). Sei E(X) die Menge aller endlichen Teilmengen von X. Für jedes Y \in E(X) ist dann X \\ Y != \0, sodass wir \(mit dem Auswahlaxiom\) eine Abbildung f : E(X) -> X mit f(Y) \in X\\Y für alle Y \in E(X) erhalten. (Wie die aussieht, ist eine andere Frage) Definiere g : \IN_0 -> E(X) rekursiv durch g(0) = T und g(n+1) =g(n) \union menge(f(g(n))) Jetzt schreiben wir T = menge(t_1 , ... , t_n). Leicht einzusehen ist, dass h : \IN -> X , i |-> fdef(t_i,i<=n;f(g(i-n)),i>n) eine Injektion mit h[ menge(1,...,n) ]=T ist. Und damit ist \a : X -> X\\T , x|-> fdef(h(i+n),x=h(i);x,sonst) eine Bijektion. array( ) \bigbox Beachte, dass man nur ein solches h braucht, um \a zu konstruieren, und es im Allgemeinen nur mit dem Auswahlaxiom "gefunden" werden kann. Aber bei bei X = \IR geht es auch ohne: Ist nämlich T = menge(t_1 , ... , t_n) eine endliche Teilmenge von \IR, die o.E. zu \IN disjunkt ist \(ansonsten verschieben\) so ist h : \IN -> \IR , i |-> fdef(t_i,i<=n;i,sonst) eine Injektion mit h[ menge(1,...,n) ]=T. Daraus ergibt sich die Bijektion \a : \IR -> \IR \\ T , x |-> fdef(h(i+n),x=h(i);x,sonst) = fdef(i+n,x=t_i für ein i \in \IN_<=n;x+n,x \in \IN_>n;x,sonst) Einfacher geht es mit \b : \IR -> \IR \\ T , x |-> fdef(i,x=t_i für ein i \in \IN_<=n;x+n,x \in \IN;x,sonst) Jeweils besteht die Idee darin, \IN um die Länge der jeweiligen Teilmenge "weiterzuschieben". Gruß Martin\(\endgroup\)
 

Re: Der Satz von Schröder-Bernstein - explizit
von: FlorianM am: So. 20. November 2005 15:27:55
\(\begingroup\)Ich finde den Artikel auch für Leute, die sich mit dem Thema nicht so viel beschäftigen, absolut verständlich geschrieben. Danke.\(\endgroup\)
 

Re: Der Satz von Schröder-Bernstein - explizit
von: Gonzbert am: So. 20. November 2005 18:20:56
\(\begingroup\)Hi Maddin! Sehr schöner Artikel! Interessantes Thema und sehr gut (=anschaulich aber dennoch nicht oberflächlich) rübergebracht. Übrigens hatten wir mal auf dem 2. Übungsblatt in Linearer Algebra die Aufgabe eine Bijektion IR\{0} -> \IR zu finden. Jetzt rate mal, wieviele Leute Schröder-Bernstein benutzt haben! 😉 Viele Grüße\(\endgroup\)
 

Re: Der Satz von Schröder-Bernstein - explizit
von: Martin_Infinite am: So. 20. November 2005 18:27:25
\(\begingroup\)Hi Gonzo & Florian, danke! @Gonzo: Diese Aufgabe, eine Bijektion R \ {0} -> R zu finden, wird wohl öfters gestellt. Die Bijektion, die dann in der Musterlösung steht, erhält man aber auch mit dem Satz von Schröder-Bernstein - das wollte ich zeigen, Es geht aber auch mit den Überlegungen aus dem letzten Kommentar. Oder habe ich dich missverstanden, und alle haben den Satz verwendet? *g* Gruß Martin\(\endgroup\)
 

Re: Der Satz von Schröder-Bernstein - explizit
von: Gonzbert am: So. 20. November 2005 18:41:11
\(\begingroup\)Ja, maddin, jeder hat geschrieben "Trivial mit Schröder-Bernstein." 😉\(\endgroup\)
 

Re: Der Satz von Schröder-Bernstein - explizit
von: Cerebus am: Mo. 21. November 2005 11:17:51
\(\begingroup\) Sehr schön! Übrigens ist die Aussage, dass eine unendliche Menge gleichmächtig zu einer echten Teilmenge ist, equivalent dazu, dass diese unendliche Menge eine abzählbar unendliche Teilmenge hat. In der Anwendung sollte das immer der Fall sein. Statt in Anwendung 2 könnten wir einfach so vorgehen: Wir partitionieren \IR in \IN und \IR-\IN. Für \IN bekommen wir leicht eine Bijektion in eine echte Teilmenge die zusammen mit der Identität auf \IR-\IN eine Bijektion des \IR mit einer echten Teilmenge liefert. Für Intervalle können wir ähnlich verfahren. Als abzählbare Teilmenge von [a,b] bietet sich zum Beispiel {a+((b-a)/n):n\el\ \IN} an. lg. Michael Edit: P.S.: Eine Beinahe-Bijektion zwischen \IR und \wp(\IN) liefert es wenn wir reelle Zahlen in Binärdarstellung mit Indikatorfunktionen auf \IN identifizieren. Vielleicht lässt sich daraus eine echte Bijektion machen.\(\endgroup\)
 

Re: Der Satz von Schröder-Bernstein - explizit
von: Martin_Infinite am: Mo. 21. November 2005 13:24:27
\(\begingroup\)Hi Michael, ja, solche Alternativen wollte ich mit dem Schlussatz angesprochen haben *g*. Die sind m.E. auch besser, bloß darum sollte es hier nicht gehen. Die Idee mit der Binärdarstellung hat mir schon Gockel verraten, daher auch dieser Thread. Das wird schon irgendwie klappen, dauert nur noch ein wenig ;) Gruß Martin\(\endgroup\)
 

Re: Der Satz von Schröder-Bernstein - explizit
von: wasseralm am: Mo. 28. November 2005 20:38:37
\(\begingroup\)Hallo Martin, ein schöner Artikel! Auch die Graphik gefällt mir gut. Eine Frage an alle: Weiß jemand, wie die Namensgebung für den Satz zustandegekommen ist? Ich kannte ihn auch als "Satz von Schröder-Bernstein", in der Wikipedia steht "Satz von Cantor-Bernstein-Schröder". O. Deiser in seinem Buch "Einführung in die Mengenlehre" spricht konsequent von dem "Satz von Cantor-Bernstein" und schreibt, dass der Satz von Cantor vermutet und von Bernstein bewiesen wurde. Gruß von Helmut\(\endgroup\)
 

Re: Der Satz von Schröder-Bernstein - explizit
von: Cerebus am: Fr. 17. Februar 2006 21:03:00
\(\begingroup\)Also historisch scheint das so ausgesehen zu haben: Cantor argumentierte, dass der Satz aus der Trichotomie der Kardinalzahlen folgt, die er später beweisen wollte. Tat er allerdings nie. So oder so, die Trichotomie der Kardinalzahlen ist äquivalent zum Auswahlaxiom, das für diesen Satz nicht notwendig ist. Der Satz wurde 1887 erstmals von Richard Dedekind bewiesen. Der Beweise wurde jedoch erst 1932 in Dedekinds gesammelten Werken publiziert. 1896 und 1898 publizierte Ernst Schröder einen "Beweis", der jedoch fehlerhaft war, wie A. Korselt 1911 bemerkte. Der erste korrekte und publizierte Beweis kam von Felix Bernstein und steht in einem 1898 herausgekommenen Buch von Emile Borel. Quelle \(\endgroup\)
 

Re: Der Satz von Schröder-Bernstein - explizit
von: Martin_Infinite am: Di. 08. September 2015 10:07:36
\(\begingroup\)Der Artikel Betrachtungen zum Satz von Bernstein (2004) von Markus Meiringer geht ebenfalls auf die konkrete Konstruktion von Bijektionen mit dem Satz von Schröder-Bernstein ein.\(\endgroup\)
 

Re: Der Satz von Schröder-Bernstein - explizit
von: Martin_Infinite am: Di. 03. November 2015 10:19:55
\(\begingroup\)In einem neuen Artikel gehe ich auf einen kategoriellen Satz von Schröder-Bernstein ein.\(\endgroup\)
 

Re: Der Satz von Schröder-Bernstein - explizit
von: Ex_Mitglied_43997 am: Di. 03. November 2015 17:22:53
\(\begingroup\)\(\endgroup\)
 

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]