Mathematik: Der von Cantor entwickelte Abzählbeweis
Released by matroid on Mo. 12. März 2001 14:41:45 [Statistics]
Written by matroid - 21115 x read [Outline] Printable version Printer-friendly version -  Choose language   
Mathematik

\(\begingroup\)\(\newcommand{\IX}{\mathbb{X}} \newcommand{\IW}{\mathbb{M}} \newcommand{\politician}[1]{\text{Ich habe die Frage nicht verstanden. #1}} \newcommand{\ba}{\begin{aligned}} \newcommand{\ea}{\end{aligned}} \newcommand{\bpm}{\begin{pmatrix}} \newcommand{\epm}{\end{pmatrix}} \newcommand{\bc}{\begin{cases}} \newcommand{\ec}{\end{cases}} \newcommand{\on}{\operatorname} \newcommand{\ds}{\displaystyle}\) Die Abzählbarkeit der Rationalen Zahlen zeigt Cantors Beweis



Ebenfalls von Cantor stammt der Beweis dafür, daß die Potenzmenge P(M) einer Menge M eine größere Mächtigkeit hat als M. Formal geschrieben: |P(M)|>|M|.
Seine Beweismethode nennt man das Cantorsche Diagonalverfahren. Man wird im folgenden sehen, warum der Name passend ist.

Erläuterung:

Zwei Mengen A und B nennt man gleichmächtig, wenn es eine Bijektion (=eineindeutige Abbildung) zwischen den beiden Mengen gibt.
Bei Mengen mit einer endlichen Zahl von Elementen ist das einfach zu sehen, z.B. sind {A,B,C} und {1,2,3} gleichmächtig. Man kann wie folgt zuordnen: 1->A, 2->B, 3->C und analog umgekehrt.
Bei Mengen mit unendlich vielen Elementen muß man eine geeignete Zuordnung angeben, um die Gleichmächtigkeit zu beweisen.
Beispiel: Eine Abbildung der natürlichen auf die ganzen Zahlen ist (z.B.):
0->0
1->-1
2->1
3->-2
4->2
5->-3
6->3
usw.

Diese Abbildung ist eindeutig und umkehrbar. Man kann für jede ganze Zahl die natürliche Zahl angeben, die auf diese ganze Zahl abgebildet wird.
Beispiel: zur ganzen Zahl 31 gehört die natürliche Zahl 62. Zur ganzen Zahl -31 gehört die natürliche Zahl 61.

Die natürliche Zahlen dienen uns gemeinhin zum Zählen von Dingen.
Indem man jeder ganzen Zahl eine natürliche Zahl zuordnet, haben wir die ganzen Zahlen also gezählt. Und wir stellen fest, daß die Menge der natürlichen Zahlen ausreicht, um die Menge der ganzen Zahlen zu zählen.
Es gibt also soviele ganze Zahlen wie natürliche Zahlen.

Für den entsprechenden Beweis, daß N und Q gleichmächtig ist, macht man es eigentlich auf die gleiche Weise, braucht aber noch den auf Cantor zurückgehenden Trick des Diagonalverfahrens.

Zurück zur Behauptung: Sei A eine Menge, dann ist |P(A)|>|A| Beweis:
Cantor hat das Gegenteil angenommen und widerlegt, also einen Widerspruchsbeweis geführt.
Wenn nämlich |P(A)|=|A|, dann gibt eine Bijektion von A nach P(A). Dann hat also jedes aeA ein Bild b in P(A). Weil P(A) die Menge der Teilmengen von A ist, ist also b eine Teilmenge von A.
Eine Teilmenge von A kann man auch charakterisieren durch eine 0-1-Folge.
Dazu stellt man sich zuerst vor, die Elemente aus A werden durchnumeriert (1,2,3, ....).
Eine bestimmte Teilmenge B von A kann dann beschrieben werden durch eine Folge aus 0 und 1. Dabei ist das i-te Glied der Folge genau dann gleich 1, wenn das Element i aus A in B ist.

Dann hat Cantor sich alle diese 0-1-Folgen untereinander geschrieben gedacht. Etwa so:

0 1 1 0 0 1 1 0 0 ...
0 0 1 0 0 1 1 0 0 ...
1 0 1 0 0 1 1 0 0 ...
0 1 1 1 0 1 1 0 0 ...
0 0 1 1 0 1 1 0 0 ...
1 0 1 1 0 1 1 0 0 ...
...
Alle diese Folgen sind verschieden, denn es sollte ja eine Bijektion zwischen A und P(A) sein.

Und nun kommt das Argument mit der Diagonalen.
Wenn man in der der ersten Folge die erste Zahl "umdreht", also aus einer 0 eine 1 macht oder aus einer 1 eine 0 und in der zweiten Folge die zweite Ziffer "umdreht" usw.... also allgemein in der n-ten Folge das n-te Element umdreht, dann betrachtet man mal nur die Diagonale (nach dem Umdrehen). Dies ist auch eine 0-1-Folge, also charakterisiert diese Folge auch eine Teilmenge von A. Und diese Folge ist verschieden von jeder anderen Folge, die man bisher hingeschrieben hatte. [Sie ist nicht gleich der ersten Folge, denn das erste Element stimmt nicht überein. Sie ist nicht gleich der 2-ten Folge, denn das zweite Element stimmt nicht überein, usw]

Da ist also eine Folge (sprich eine Teilmenge von A) gefunden worden, die nicht Bild eines aeA ist. Folglich war die Annahme, es könnte eine Bijektion zwischen A und P(A) geben falsch. Das mit der Bijektion hatte man aber aus der Annahme abgeleitet, daß |P(A)|=|A|.
Ergo: diese Annahme ist widerlegt.

Das Diagonalargument verwendet Cantor häufig. Es gibt es sogar in zwei Unterarten, nämlich Cantors Erstes Diagonalargument und Cantors Zweites Diagonalargument.

Das Zweite Diagonalargument habe wir oben bereits beim Beweis von |P(A)|>|A| in der Anwendung gesehen.
Ebenfalls mit dem Zweiten Diagonalargument beweist man, daß die Menge der reellen Zahlen überabzählbar ist.

Mit dem Ersten Diagonalargument bewies Cantor Ende des 19. Jahrhunderts, daß die Menge der rationalen Zahlen abzählbar unendlich ist.
Interessierte finden hier das Prinzip auf einer Seite der Uni Oldenburg unter Unendliche Mengen und Cantors Diagonalargumente

\(\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 :: Kardinalzahlen :
Der von Cantor entwickelte Abzählbeweis [von matroid]  
Die Abzählbarkeit der Rationalen Zahlen zeigt Cantors Beweis
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
 
Aufrufzähler 21115
 
Aufrufstatistik des Artikels
Insgesamt 1508 externe Seitenaufrufe zwischen 2012.01 und 2021.09 [Anzeigen]
DomainAnzahlProz
https://google.com211.4%1.4 %
http://matheraum.de24816.4%16.4 %
https://google.de25917.2%17.2 %
http://google.de79652.8%52.8 %
http://google.nl412.7%2.7 %
http://google.lu231.5%1.5 %
https://www.mathe-online.at261.7%1.7 %
https://duckduckgo.com100.7%0.7 %
https://www.ecosia.org100.7%0.7 %
https://www.bing.com140.9%0.9 %
http://google.ch40.3%0.3 %
http://google.com40.3%0.3 %
http://www.matheraum.de30.2%0.2 %
http://vorhilfe.de20.1%0.1 %
http://philo-welt.de20.1%0.1 %
https://www.startpage.com20.1%0.1 %
http://google.at20.1%0.1 %
http://www.bing.com151%1 %
http://suche.t-online.de20.1%0.1 %
https://cse.google.com10.1%0.1 %
https://bing.com10.1%0.1 %
http://www.search.ask.com20.1%0.1 %
https://www.qwant.com10.1%0.1 %
http://www.searchmobileonline.com10.1%0.1 %
http://de.yhs4.search.yahoo.com10.1%0.1 %
http://search.conduit.com30.2%0.2 %
http://r.duckduckgo.com10.1%0.1 %
http://www.holasearch.com10.1%0.1 %
https://de.search.yahoo.com10.1%0.1 %
http://suche.web.de20.1%0.1 %
http://search.softonic.com10.1%0.1 %
http://nortonsafe.search.ask.com10.1%0.1 %
https://ch.search.yahoo.com10.1%0.1 %
http://start.mysearchdial.com10.1%0.1 %
https://startpage.com10.1%0.1 %
http://www.philo-welt.de10.1%0.1 %
http://www.ecosia.org10.1%0.1 %
http://suche.aol.de10.1%0.1 %
http://de.search.yahoo.com10.1%0.1 %

Häufige Aufrufer in früheren Monaten
Insgesamt 1443 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
2012-2016 (244x)http://matheraum.de/forum/ueberabzaehlbarkeit/t26376
2020-2021 (210x)https://google.de/
2013-2017 (193x)http://google.de/url?sa=t&rct=j&q=
2012-2013 (74x)http://google.de/url?sa=t&rct=j&q=satz von cantor potenzmenge
201211-11 (67x)http://google.de/url?sa=t&rct=j&q=z abzählbar unendlich beweis
201411-11 (66x)http://google.de/url?sa=t&rct=j&q=2. cantorsches diagonalverfahren
201311-11 (43x)http://google.de/url?sa=t&rct=j&q=diagonalargument von cantor 0,1folge
201410-10 (41x)http://google.nl/url?sa=t&rct=j&q=
201210-10 (39x)http://google.de/webhp?source=search_app
201204-04 (36x)http://google.de/url?sa=t&rct=j&q=zweites diagonalargument folgen 0 1
201202-02 (31x)http://google.de/url?sa=t&rct=j&q=q mit cantor abzählen
202102-06 (30x)https://google.de
201207-07 (24x)http://google.de/url?sa=t&rct=j&q=potenzmenge beweis cantor
201203-03 (23x)http://google.lu/url?sa=t&rct=j&q=cantors erstes diagonalargument
201301-03 (23x)http://google.de/url?sa=t&rct=j&q=diagonal verfahren nach cantor
201405-05 (21x)http://google.de/url?sa=t&rct=j&q=cantors erstes diagonalargument
202007-07 (19x)https://google.de/search?q=erstes diagonalverfahren
2020-2021 (18x)https://google.com/
201505-05 (16x)http://google.de/url?sa=t&rct=j&q=diagonal trick folgen cantor
201502-02 (16x)http://google.de/url?sa=t&source=web&cd=14&ved=0CEIQFjAN
201205-05 (14x)http://google.de/url?sa=t&rct=j&q=www.hasipage.de
201201-01 (14x)http://google.de/url?sa=t&rct=j&q=folgen abzählbar unendlich beweis
2020-2021 (13x)https://www.mathe-online.at/materialien/matroid/files/vi/vi.html
201206-06 (13x)http://google.de/url?sa=t&rct=j&q=widerspruchsbeweis cantor
201306-06 (12x)http://google.de/url?sa=t&rct=j&q=cantors diagonalargument
201501-01 (12x)http://google.de/url?sa=t&source=web&cd=14&ved=0CEMQFjAN
201209-09 (11x)http://google.de/url?sa=t&rct=j&q=mächtigkeit potenzmenge beweis
2020-2021 (10x)https://duckduckgo.com/
201208-08 (9x)http://google.de/url?sa=t&rct=j&q=rationale zahlen pyramide natürliche zah...
201407-07 (9x)http://google.de/url?sa=t&source=web&cd=2&ved=0CCUQFjAB
2020-2021 (9x)https://www.ecosia.org/
2020-2021 (8x)https://www.mathe-online.at/
201601-01 (8x)http://google.de/url?sa=t&source=web&cd=8&rct=j&q=cantorsches diagonalverfahr...
201308-08 (8x)http://google.de/url?sa=t&rct=j&q=n x n abzählbar
201506-06 (8x)http://google.de/url?sa=t&rct=j&q=2. diagonalverfahren
2020-2021 (8x)https://www.bing.com/
201512-12 (7x)http://google.de/url?sa=t&source=web&cd=7&rct=j&q=cantorsches diagonalverfahr...
2016-2017 (6x)http://google.de/
202005-05 (5x)https://www.bing.com/search?q=matroids matheplanet
2020-2021 (5x)https://www.mathe-online.at
201511-11 (4x)http://google.de/url?sa=t&source=web&cd=8&rct=j&q=cantors zweites diagonal ar...
2015-2017 (4x)http://google.ch/url?sa=t&rct=j&q=
201803-06 (4x)http://google.com/
201605-05 (4x)http://google.de/url?sa=t&rct=j&q=kantors diagonale
201307-07 (4x)http://google.de/url?sa=t&rct=j&q=cantorsches diagonalverfahren vollständi...

[Top of page]

"Mathematik: Der von Cantor entwickelte Abzählbeweis" | 9 Comments
The authors of the comments are responsible for the content.

Re: Der von Cantor entwickelte Abzählbeweis
von: Ex_Mitglied_40174 am: Di. 31. Dezember 2002 17:02:47
\(\begingroup\)Der Schritt
"die Elemente aus A werden durchnumeriert (1,2,3, ....)"
setzt doch aber voraus, dass die Menge A abzählbar unendlich ist, womit der
Beweis nur für abzählbare unendliche Mengen A gültig wäre, oder?

mfg
Torsten\(\endgroup\)
 

Re: Der von Cantor entwickelte Abzählbeweis
von: Ex_Mitglied_40174 am: So. 15. Juni 2003 02:06:09
\(\begingroup\)Hier der einzig wahre und vollständige Beweis dieses geilen Satzes...

http://www.hasipage.de/svc.pdf\(\endgroup\)
 

Re: Der von Cantor entwickelte Abzählbeweis
von: Martin_Infinite am: Fr. 24. Oktober 2003 00:49:50
\(\begingroup\)Ich habe unter "rationale Zahlen" etwas über's Thema geschrieben.

Gruß
Martin\(\endgroup\)
 

Re: Der von Cantor entwickelte Abzählbeweis
von: Ueli am: Sa. 03. Januar 2004 15:58:41
\(\begingroup\)Einmal eine andere Ansicht:

Cantors Beweis ist sicher sehr einleuchtend, doch ich glaube seine Argumentation ist falsch.

Betrachtet man das Diagonalverfahren wie oben mit Dualzahlen. Schreibt man nun Listen auf: zunächst mit allen n-stelligen Dualzahlen, so sieht man, dass es für alle n-stelligen Zahlen (2 hoch n) Einträge gibt in der Liste. Bildet man nun die Diagonalzahl und bildet bitweise das Komplement, so hat man sehr wohl eine Zahl, die wiederum in der Liste steht. Sie wird einfach nicht von der Diagonalen erfasst.

Für wachsendes n verschlechtert sich die Situation sogar zunehmend. Die Liste wird viel tiefer als breit.
Nun kann man argumentieren, dass die Liste unendlich lange Elemente enthält und das Argument dann wieder fängt.

Dazu zwei Einwände:
1. Ein Argument, dass für alle endlichen Listen nicht funktioniert sollte gemäss vollständiger Induktion auch für unendliche Listen nicht funktionieren.
2. Auch wenn die Diagonale im Unendlichen doch noch alle Elemente erwischt, wird die Komplementbildung dort nichts bewirken, da diese Stellen bei einer reellen Zahl keinen Beitrag mehr bringen.

Es ist für mich daher auch nicht verwunderlich, dass die Kontinuumshypothese nicht beweisbar und nicht widerlegbar ist: Sie sagt gar nichts aus.

Gruss Ueli\(\endgroup\)
 

Re: Der von Cantor entwickelte Abzählbeweis
von: Fabi am: So. 04. Januar 2004 16:53:17
\(\begingroup\)@Ueli:

1. Den Induktionsbeweis will ich sehen.
Sowohl ANzahl der Zeilen als auch Anzahl der Splaten sidn abzählbar unendlich, also gleichmächtig.

2. Es gibt bei einer reellen Zahl keine unendlichen Stellen, die keinen Beitrag liefern.

Gruß
Fabi \(\endgroup\)
 

Re: Der von Cantor entwickelte Abzählbeweis
von: manfred am: Mi. 07. Januar 2004 18:29:13
\(\begingroup\)Hallo Fabi,

.. aber was ist mit dem Einwand von Anonimous ganz oben ? Cantors Diagonalargumente sind doch nicht mehr anwendbar für den Beweis, daß
I P(M) I > I M I
ist falls M selbst schon überabzählbar groß ist.

Gruß

Manfred\(\endgroup\)
 

Re: Der von Cantor entwickelte Abzählbeweis
von: Fabi am: Mi. 07. Januar 2004 22:18:52
\(\begingroup\)Das beweist man ja mit dem Diagonalargument garnicht, sondern man beweist, dass R überabzählbar ist. Für |P(M)| > |M|
braucht man einen anderen Beweis.


\(\endgroup\)
 

Re: Der von Cantor entwickelte Abzählbeweis
von: manfred am: Do. 08. Januar 2004 10:47:07
\(\begingroup\)... das sehe ich ja auch so. Aber im obigen Artikel steht schon im ersten Absatz:

"...die Potenzmenge P(M) einer Menge M eine größere Mächtigkeit hat als M. Formal geschrieben: |P(M)|>|M|.
Seine Beweismethode nennt man das Cantorsche Diagonalverfahren...."

und weiter unten wird die Beweismethode eingehend beschrieben, beginnend mit:

"Zurück zur Behauptung: Sei A eine Menge, dann ist |P(A)|>|A| Beweis:
Cantor hat das Gegenteil angenommen und widerlegt, also einen Widerspruchsbeweis geführt..."

Der Widerspruch wird dann unter Verwendung des Diagonalarguments herbeigeführt.

Daß dies nicht zulässig ist für überabzählbare A, darüber sind wir uns offensichtlich einig - aber kennst du einen anderen Beweis für |P(A)|>|A| ?

Grüße

Manfred






\(\endgroup\)
 

Re: Der von Cantor entwickelte Abzählbeweis
von: manfred am: Mo. 12. Januar 2004 11:31:00
\(\begingroup\)... also ich glaub ich habs.

Der in diesem Kommentar angeführte Beweis für die Behauptung, die Potenzmenge einer Menge A ist immer mächtiger als A selbst:

|P(A)| > |A|

ist nur anwendbar für höchstens abzählbare A denn es wird vorausgesetzt (Zitat):

...eine bestimmte Teilmenge B von A kann dann beschrieben werden durch eine Folge aus 0 und 1.

...und das ist sicher falsch für überabzählbare Mengen A.

Ich denke, ich habe den allgemeinen Beweis Cantors gefunden, der ebenfalls die Annahme der Existenz einer Bijektion von A nach P(A) zum Widerspruch führt:

Sei f diese Bijektion - dann konstruiert man die Menge aller Elemente a aus A, die nicht Element von ihrer Bildmenge f(a) sind. Diese Menge nennen wir X. Da dies eine Teilmenge von A ist, muss es ein x e A geben, welches durch die Bijektion f auf X abgebildet wird – also:

f(x) = X

Dieses x ist entweder in X enthalten oder nicht – aber beide Annahmen führen zum Widerspruch:

Wenn x e X, dann entsteht der Widerspruch durch die Konstruktionsvorschrift von X – das war die Menge aller Elemente aus A, die gerade nicht Element von f(a) sind also ist x nicht e X.

Wenn x nicht e X, dann entsteht ebenfalls ein Widerspruch – denn weil x nicht e f(x) = X würde wegen der Konstruktionsvorschrift für X folgen, dass x e X.

(@ Ueli: deine Einwände sind m.E. durch diese Art des Beweises entkräftet – oder ?)

Die Überlegung, die hinter diesem Beweis steckt, ist übrigens die gleiche, die das Paradoxon vom Barbier von Sevilla auflöst. Dieser behauptete nämlich, er rasiere alle Männer von Sevilla, die sich nicht selbst rasieren.

Frage: rasiert er sich nun selbst oder nicht ?

Antwort: weder noch – er lügt !

Manfred
\(\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]