Stern Mathematik: Der Satz von Schroeder-Bernstein
Released by matroid on Di. 10. Juni 2003 20:49:34 [Statistics]
Written by Plex_Inphinity - 6701 x read [Outline] Printable version Printer-friendly version -  Choose language   
Mathematik

\(\begingroup\)  
Ich möchte in diesem Artikel einen Beweis des Satzes von Schroeder-Bernstein vorstellen, den ich für sehr schön halte.
Der Beweis ist dem BUCH der Beweise entnommen und stammt ursprünglich von Andrei Zelevinsky.

\big\darkblue Satz von Schroeder-Bernstein:

\blue\boxon Wenn jede von zwei Mengen M und N injektiv in die jeweils
andere abgebildet werden kann, dann existiert eine Bijektion
von M auf N, das heißt, es gilt dann \|M\|=\|N\|\..
\boxoff


\big Beweis__:

Seien f:M->N und g:N->M Injektionen.

Die Idee des Beweises besteht darin, eine Bijektion \phi:M->N aus f
und der Umkehrabbildung g^(-1) von g zu konstruieren.
Dazu bedient man sich erst der Injektivität von f, indem man eine
bestimmte Teilmenge A \subset M ausmacht und diese injektiv auf f(A)
abbildet.
Damit \phi auch surjektiv ist, also jedes Element von N getroffen wird,
braucht man aber noch eine Teilmenge von M , die injektiv auf N\\f(A)
abgebildet wird, denn f ist nicht notwendigerweise surjektiv, d.h. es
gilt nicht immer f(A) = N.
Hierzu bedient man sich g, indem man über g zurück nach N geht und so
die Teilmenge g(N\\f(A))\subset\M erhält. \stress (siehe  Skizze 1)

\phi ließe sich dann folgendermaßen definieren:

\phi(x) := fdef(f(x),x\el A;g^(-1)(x),x\el g(N\\f(A)))

Jedoch gibt es dabei noch ein Problem, denn damit \phi:M->N auch
wirklich eine wohldefinierte Funktion ist, muss gelten:
1. A \cut g(N\\f(A)) = \0
und
2. A \union g(N\\f(A)) = M
Mit anderen Worten: A und g(N\\f(A)) müssen eine Partition von M sein.
\stress (siehe Skizze 2)
Skizze 1
Bild

Skizze 2
Bild

define(S,schnitt(A_i))
define(SF,schnitt(f(A_i)))

\Unsere Aufgabe besteht nun also darin ein solches A\subset\M zu finden,
das 1 und 2 erfüllt.

Hierzu definieren wir eine Funktion auf der Potenzmenge von M.

F: Pot(M) -> Pot(M) durch

F(A) := M\\g(N\\f(A))

Anhand der Skizzen 1 und 2 kann man sich leicht klarmachen, dass für
eine Menge A_0 , die 1 und 2 erfüllt F(A_0)=A_0 gelten muss und
umgekehrt.
Gesucht ist also letztendlich ein Fixpunkt der Funktion F.

Um zu beweisen, dass ein solcher Fixpunkt tatsächlich existiert,
brauchen wir aber zunächst ein kleines Lemma.

Lemma__:
Sei A_1, A_2, A_3, ... eine Familie von Teilmengen von M, dann gilt:

F(schnitt(A_i,i >= 1)) = schnitt(F(A_i),i >=i)

Beweis__:
Zunächst beachte man, dass
i. f(schnitt(A_i)) = schnitt(f(A_i)) gilt, da f injektiv ist.
Der Beweis ist einfach.
ii. g(vereinigung(A_i)) = vereinigung(g(A_i))  für jede Abbildung g gilt.
Dies läßt sich ebenso einfach beweisen.

Nun haben wir
\align
F(\S) = M\\(g(N\\f(\S)
= M\\g(N\\ schnitt(f(A_i)))  , nach i.
= M\\g(vereinigung(N\\f(A_i))) , de Morgans Gesetz
= M\\(vereinigung(g(N\\f(A_i)))) , nach ii.
= schnitt(M\\g(N\\f(A_i))) , de Morgans Gesetz
= schnitt(F(A_i))
\stopalign

q.e.d.



Betrachte nun die folgende Kette von Teilmengen:

M \supersetequal F(M) \supersetequal F^2(M) \supersetequal F^3(M) ...

und definiere A_0 als den Durchschnitt aller Mengen in der Kette, also

\align
A_0 = M \cut F(M) \cut F^2(M) \cut F^3(M)
= \schnitt(F^i(M),i >= 0)

\stopalign

Mit obigem Lemma folgt nun:
\align
F(A_0) = F(\schnitt(F^i(M),i >= 0))
= \schnitt(F(F^i(M)),i >= 0)
= \schnitt(F^i(M),i >= 1)
= F(M) \cut F^2(M) \cut F^3(M) ...
= A_0
\stopalign

Also ist A_0 ein Fixpunkt von F und A_0 erfüllt somit 1 und 2.

Durch
\phi(x) := fdef(f(x),x\el A_0;g^(-1)(x),x\el g(N\\A_0))= fdef(f(x),x \el A_0;g^(-1)(x),x \notel A_0)
wird also eine Bijektion zwischen M und N definiert, was den
Satz von Schroeder-Bernstein beweist.



Ich wünsche allen Besuchern und Bewohnern des Matheplaneten einen schönen Sommer,

Plex Inphinity
\(\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:
: Interessierte Studenten :: Mengenlehre :: Reine Mathematik :: Mathematik :: Axiomatische Mengenlehre :
Der Satz von Schroeder-Bernstein [von Plex_Inphinity]  
Ich möchte in diesem Artikel einen Beweis des Satzes von Schroeder-Bernstein vorstellen, den ich für sehr schön halte.
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
 
Aufrufzähler 6701
 
Aufrufstatistik des Artikels
Insgesamt 475 externe Seitenaufrufe zwischen 2012.01 und 2021.08 [Anzeigen]
DomainAnzahlProz
http://google.de32768.8%68.8 %
http://www.onlinemathe.de5712%12 %
https://www.bing.com428.8%8.8 %
https://duckduckgo.com132.7%2.7 %
https://www.ecosia.org153.2%3.2 %
https://google.com51.1%1.1 %
http://google.com61.3%1.3 %
https://metager.de20.4%0.4 %
http://ecosia.org20.4%0.4 %
http://www.bing.com10.2%0.2 %
http://google.at10.2%0.2 %
http://www.mathproject.de10.2%0.2 %
http://suche.gmx.net10.2%0.2 %
http://search.conduit.com10.2%0.2 %
https://google.de10.2%0.2 %

Häufige Aufrufer in früheren Monaten
Insgesamt 450 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
2013-2017 (115x)http://google.de/url?sa=t&rct=j&q=
2012-2017 (57x)http://www.onlinemathe.de/forum/Satz-von-Schroeder-Bernstein
201201-11 (52x)http://google.de/url?sa=t&rct=j&q=schröder-bernstein beweis
2020-2021 (36x)https://www.bing.com/
201411-11 (34x)http://google.de/url?sa=t&source=web&cd=5&ved=0CCsQFjAE
201305-05 (22x)http://google.de/url?sa=t&rct=j&q=satz von cantor bernstein beweis
2012-2013 (15x)http://google.de/url?sa=t&rct=j&q=schröder bernstein beweis
2012-2014 (15x)http://google.de/url?sa=t&rct=j&q=schröder bernstein
201306-06 (13x)http://google.de/url?sa=t&rct=j&q=schröder bernstein sche satz beweis
2012-2013 (13x)http://google.de/url?sa=t&rct=j&q=satz von schröder-bernstein beweis
2020-2021 (12x)https://duckduckgo.com/
2020-2021 (11x)https://www.ecosia.org/
202006-06 (6x)https://www.bing.com/search?q=schröder bernstein theorem beweis
201206-06 (6x)http://google.de/url?sa=t&rct=j&q=sei g eine gruppe und g el g man definiert ...
2016-2017 (6x)http://google.de/
201304-04 (5x)http://google.de/url?sa=t&rct=j&q=satz von bernstein integral
201301-01 (5x)http://google.de/url?sa=t&rct=j&q=satz von schröder-bernstein aufgaben
201203-07 (5x)http://google.de/url?sa=t&rct=j&q=schröder-bernstein
2020-2021 (5x)https://google.com/
201403-03 (5x)http://google.de/url?sa=t&rct=j&q=schroeder bernstein
201210-10 (4x)http://google.de/url?sa=t&rct=j&q=injektiv schnitt vom bild
202101-05 (4x)https://www.ecosia.org
2015-2018 (4x)http://google.com/ie

[Top of page]

"Stern Mathematik: Der Satz von Schroeder-Bernstein" | 3 Comments
The authors of the comments are responsible for the content.

Re: Der Satz von Schroeder-Bernstein
von: matroid am: Di. 10. Juni 2003 22:31:10
\(\begingroup\)Hi Plex,

das ist total schön, die Lösung ist der Fixpunkt einer Abbildung!

Und eigentlich ist ja alles klar, wenn man nur erst diese Idee hätte gehabt haben können.

Wie naheliegend ist denn die Idee dazu?

Ich kritzele gerade ein Beispiel, nur um etwas mehr zu verstehen.

f: \IN -> \IN definiert als f(n)=2n
und g: \IN -> \IN definiert als g(n)=3n.

Beide Abbildungen sind injektiv.

Ich bilde für A=menge(1,2,3) das Bild F(A).
\align
F(menge(1,2,3))=\IN \\ g(\IN \\ menge(2,4,6))
=\IN \\(3\IN \\ menge(6,12,18))
= alle nicht durch 3 teilbaren zuzüglich 6, 12, 18

Toll, was Zelevinsky da gesehen hat.

Danke für diesen Artikel.

Gruß
Matroid\(\endgroup\)
 

Re: Der Satz von Schroeder-Bernstein
von: Ex_Mitglied_40174 am: Mi. 11. Juni 2003 17:01:29
\(\begingroup\)Wenn ich das Beispiel richtig verstehe, dann steht links eine Menge aus 3 Elementen F({1,2,3}], rechts hingegen eine unendliche Menge.
Wo liegt mein Problem?\(\endgroup\)
 

Re: Der Satz von Schroeder-Bernstein
von: Martin_Infinite am: Mi. 30. März 2005 13:20:01
\(\begingroup\)Hi, es gibt auch eine Verallgemeinerung: \darkblue\(A \subseteq B \subseteq C \and abs(C)<=abs(A)) => abs(B)=abs(C) Beweis. Sei f : C -> A injektiv und D := C\\B. Definiere g : \IN -> V rekursiv durch g(0) = D und g(n+1)=f[g(n)]. Setze D^- := union(g(n),n \in \IN) und definiere h : C->B durch x -> fdef(f(x),x \in D^-;x,sonst). Um zu sehen, dasss h surjektiv ist, sei b \in B beliebig. Für b \notin D^- ist schon f(b)=b. Sei also b \in D^-. Wegen b \notin D gibt es dann ein n \in \IN mit b \in f[g(n)], also b=f(x) für ein x \in g(n) \subseteq D^-, sodass b=h(x) ist. Für die Injektivität nehme man sich x,y \in C mit h(x)=h(y). array(Für x\in D^-\,) y \notin D^- gibt es ein n \in \IN mit x \in g(n) und es folgt der Widerspruch y=h(y)=h(x)=f(x) \in f[g(n)]=g(n+1) \subseteq D^-. Also ist x,y \notin D^- oder x,y \in D^-, woraus mit der Injektivität von f sofort x=y array(folgt. array( ) \bigbox) Daraus folgt dann abs(A)<=abs(B)<=abs(A) => abs(A)=abs(B), denn wenn f : A -> B und g : B -> A injektiv sind, dann gilt (gf)[A] \subseteq g[B] \subseteq A und abs(A)=abs((gf)[A]), also abs(B)=abs(g[B])=abs(A) nach dem oben Bewiesenen. Gruß Martin\(\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-2021 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]