Mathematics / Mathematik / Matemática

Mathematics / Mathematik / Matemática

This thread has been closed so unfortunately you can't post here any more.

Posts 1-10 of 430
  • Bernd Pfützner
    Bernd Pfützner    Premium Member   Group moderator
    The company name is only visible to registered members.
    (über)abzählbar
    Sehr geehrte Mathematik-Freunde,

    mich - einen Laien bezüglich der Mathematik - beschäftigt zur Zeit das Thema Abzählbarkeit bzw. Überabzählbarkeit. In diesem Zusammenhang stelle ich mir - und nun auch Ihnen - die Frage:

    Kann es in der Mathematik, also im Fachgebiet der Zahlen und des Zählens, überhaupt eine Menge geben, die so mächtig ist, daß man deren Elemente nicht (ab)zählen kann? Falls ja, warum?

    Ich kann mir das nämlich nicht so recht vorstellen.

    Über Ihre Anregungen würde ich mich freuen und danke Ihnen schon jetzt dafür, daß Sie Sich dabei für einen Laien verständlich ausdrücken.

    Viele Grüße

    Bernd Pfützner
    • 05 Aug 2010, 8:55 pm
  • Post visible to registered members
  • Dr. Andreas Ecker
    Dr. Andreas Ecker
    The company name is only visible to registered members.
    Re: (über)abzählbar
    Hallo,

    das stimmt schon, dass das gar nicht so einfach vorstellbar ist ...
    Im mathematischen Sinn ist eine Menge abzählbar unendlich, wenn es eine bijektive Abbildung (1-1-Abbildung) der natürlichen Zahlen (0,1,2,...) auf die Menge gibt.
    Georg Cantor hat erstmals bewiesen, dass die Menge der reellen Zahlen überabzählbar ist. Der Beweis ist ein Klassiker und beruht auf einem sogenannten Diagonalprinzip. Die Idee ist folgendermaßen: Eine reellen Zahl sind darstellbar als Vorkommazahl mit einer unendlichen Folge von Nachkommastellen (also z.B. 3,141592....). (Zu bedenken ist dabei, dass 1,0000000...=0,99999999...)
    Im Beweis beschränkt man sich auf die Zahlen zwischen 0 und 1. Angenommen es gäbe eine Abzählung (r_1, r_2, ...) dieser Zahlen, dann konstruiert man eine Zahl, die in der Aufzählung nicht enthalten sein kann wie folgt: Wenn z_n_k die k-te Nachkommastelle von r_n ist, dann definiere y_n:=z_n_n+1, wenn z_n_n<9 und 1 sonst. Dann kann die Zahl y, deren n-te Nachkommastelle y_n ist nicht in der Aufzählung enthalten sein, da sonst y ein r_i für irgendein i wäre, aber die i-te Stelle von y ist nach Definition ungleich der i-ten Stelle von r_i (also z_i_i).
    z. B.
    r_1 = 0, 1 2 4 2 4 2 7 8 ...
    r_2 = 0, 3 8 6 3 2 7 7 9 ...
    r_3 = 0, 2 5 5 4 7 5 7 6 ..
    ...
    Mit
    r_1_1 = 1
    r_2_2 = 8
    r_1_3 = 5
    ...
    Definiere
    y = 0, 2 9 6 ...

    Allgemeiner kann man definieren, dass zwei Mengen gleich groß sind, wenn es eine bijektive Abbildung zwischen den Mengen gibt. Man schreibt |N| = |M|.
    Wenn es eine injektive Abbildung von N nach M gibt (f(x)!=f(y) für x!=y, "!=" steht für ungleich), schreibt man |N|<=|M|.

    Man kann zeigen, dass für die Potenzmenge P(M) einer Menge M immer |M|<|P(M)| (also nicht gleich) gilt. Die Potenzmenge ist der Menge aller Teilmengen einer Menge, z.B.:
    M={a,b}
    P(M)={{},{a},{b},{a,b}}
    Angenommen, es gäbe eine bijektive Abbildung f: M -> P(M),
    dann betrachte man die Menge X={m in M; m ist kein Element von f(m)}.
    Nach Voraussetzung muss es ein y geben, so dass f(y)=X.
    Angenommen y läge in X, dann kann y nach Definition von X nicht in X liegen.
    Also ist y nicht in X, aber dann ist es nach Definition von X doch in X.
    Man hat also einen Widerspruch.
    Man nennt auch das eine Diagonalprinzip, das Argument ist übrigens bei der Russellschen Antinomie ganz ähnlich, aber das ist ein anderes Thema ...

    Um zu erhalten, dass Mengen immer vergleichbar sind (|N|<=|M| oder |M|<=|N|), braucht man übrigens das Auswahlaxion (Zornsches Lemma), das in manchen Mathematikerkreisen umstritten ist, da es nicht-konstruktiv ist.

    Beste Grüße,
    Andreas Ecker
    • 05 Aug 2010, 10:24 pm
  • Dr. Andreas Ecker
    Dr. Andreas Ecker
    The company name is only visible to registered members.
    Re^2: (über)abzählbar
    Hallo Herr Reusch,

    es ist wohl richtig, dass man eine diskrete Ordnung für die reellen Zahlen nicht konstruktiv angeben kann. Nimmt man aber das Auswahlaxiom an, dann gibt es eine "Wohlordnung" für die reellen Zahlen, d.h. eine Ordnung, bei der es für jede Teilmenge der reellen Zahlen ein kleinstes Element gibt. Grob vorstellen kann man sich so eine Ordnung, indem man zählt
    0,1,2,...,unendlich,unendlich + 1,..,unendlich + unendlich,..,unendlich x unendlich, ...
    Für das erste "unendlich", das hier auftaucht, schreibt man in der Mengenlehre ein kleines Omega (wohl weil es an das Unendlich-Zeichen erinnert). Die ersten Zahlen in der sind allerdings immer abzählbar, und es ist gar nicht so einfach, sich klar zu machen, dass das irgendwann überabzählbar wird.
    In der Wohlordnung hat zwar jedes Element einen Nachfolger, manche aber keinen Vorgänger (wie z.B. "unendlich").

    Grüße
    Andreas Ecker
    • 05 Aug 2010, 10:41 pm
  • Bernd Pfützner
    Bernd Pfützner    Premium Member   Group moderator
    The company name is only visible to registered members.
    Re^2: (über)abzählbar
    Lieber Herr Reusch,

    Dr. Hans Joachim Reusch schrieb:
    Wenn Sie eine Menge zählen wollen, müssen Sie in der Lage sein, die Elemente der Menge in eine Reihenfolge so zu ordnen, dass sichergestellt ist, dass zwischen zwei Elementen Ihrer Reihenfolge sich kein weiteres Ihrer Mengenelemente befindet.
    wenn ich Ihre Aussage mit Georg Cantors erstem Diagonalargument vergleiche, in welchem er die Abzählbarkeit der Menge der rationalen Zahlen bewies, dann kann diese Anforderung nicht stimmen:

    1, 1/2, 2, 3, 1/3, 1/4, 2/3, 3/2, 4, 5, 1/5, ...

    In seinem diagonalen Schema, aus dem er dann diese Reihenfolge übernahm, ist zwar ein logisches System erkennbar, aber zwischen je zwei dieser Zahlen gibt es Abstände, in denen andere rationale Zahlen liegen. Zum Beispiel zwischen 1 und 1/2 liegen 1/3, 1/4, 1/5, 2/5, etc. Diese werden zwar an anderer Stelle der Liste erwähnt, aber eine durchgängige Reihenfolge wie bei den natürlichen Zahlen ist das nicht.

    Versuche Sie dies z.B. mit den reellen Zahlen. Sie werden feststellen, dass es egal ist welche Ordnung Sie probieren, es wird immer wieder möglich sein, eine weitere reelle Zahl zwischen zwei rellen Zahlen ihrer Ordnung zu finden.
    Nehmen wir an, die Reihenfolge wäre egal (wie oben angedeutet). Dann würde es genügen, irgendeine reelle Zahl der 1 zuzuordnen, dann irgendeine andere reelle Zahl der 2, wieder eine andere reelle Zahl der 3, und so weiter. Da es keine größte natürliche Zahl gibt, reicht der Vorrat der natürlichen Zahlen aus, um für jede reelle Zahl eine natürliche Zahl zur Verfügung zu stellen.

    Was meinen Sie dazu?

    Viele Grüße

    Bernd Pfützner
    • 05 Aug 2010, 11:17 pm
  • Bernd Pfützner
    Bernd Pfützner    Premium Member   Group moderator
    The company name is only visible to registered members.
    Re^2: (über)abzählbar
    Lieber Herr Ecker,

    Dr. Andreas Ecker schrieb:
    das stimmt schon, dass das gar nicht so einfach vorstellbar ist ...
    Im mathematischen Sinn ist eine Menge abzählbar unendlich, wenn es eine bijektive Abbildung (1-1-Abbildung) der natürlichen Zahlen (0,1,2,...) auf die Menge gibt.
    das ist soweit ja klar. Aber muß dazu eine bestimmte Reihenfolge eingehalten werden?

    Georg Cantor hat erstmals bewiesen, dass die Menge der reellen Zahlen überabzählbar ist. Der Beweis ist ein Klassiker und beruht auf einem sogenannten Diagonalprinzip. Die Idee ist folgendermaßen: Eine reellen Zahl sind darstellbar als Vorkommazahl mit einer unendlichen Folge von Nachkommastellen (also z.B. 3,141592....). (Zu bedenken ist dabei, dass 1,0000000...=0,99999999...) Im Beweis beschränkt man sich auf die Zahlen zwischen 0 und 1. Angenommen es gäbe eine Abzählung (r_1, r_2, ...) dieser Zahlen, dann konstruiert man eine Zahl, die in der Aufzählung nicht enthalten sein kann wie folgt: Wenn z_n_k die k-te Nachkommastelle von r_n ist, dann definiere y_n:=z_n_n+1, wenn z_n_n<9 und 1 sonst. Dann kann die Zahl y, deren n-te Nachkommastelle y_n ist nicht in der Aufzählung enthalten sein, da sonst y ein r_i für irgendein i wäre, aber die i-te Stelle von y ist nach Definition ungleich der i-ten Stelle von r_i (also z_i_i).
    z. B.
    r_1 = 0, 1 2 4 2 4 2 7 8 ...
    r_2 = 0, 3 8 6 3 2 7 7 9 ...
    r_3 = 0, 2 5 5 4 7 5 7 6 ..
    ...
    Mit r_1_1 = 1
    r_2_2 = 8
    r_1_3 = 5
    ...
    Definiere
    y = 0, 2 9 6 ...
    Ok, aber wieviele reelle Zahlen gibt es denn, die an den ersten drei Stellen hinter dem Komma mit 296 beginnen?
    Und wieviele reelle Zahlen gibt es, die mit
    0,2960...
    0,2961...
    0,2962...
    etc.
    beginnen?
    Und wieviele reelle Zahlen gibt es, die mit
    0,29600...
    0,29601...
    0,29602...
    etc.
    0,29610...
    0,29611...
    0,29612...
    etc.
    etc.
    beginnen?
    Alle diese Zahlen müßte Cantor ja überprüfen. Und vor allem müßte er immer genau in dem Bereich weitersuchen, innerhalb dem seine Diagonalzahl liegen müßte. Denn eine reelle Zahl, die zwischen 1 und 2 liegt, kann man nicht zwischen 0 und 1 antreffen. Folglich kann man auch eine reelle Zahl, die zwischen 0,1 und 0,2 liegt, nicht zwischen 0,0 und 0,1 oder zwischen 0,2 und 0,3 antreffen. Und wenn sie zwischen 0,00 und 0,01 liegt, dann kann man sie zwischen 0,01 und 0,02 nicht finden. Und so weiter.

    Sprich, es ist von Anfang an vorprogrammiert, daß Cantor seine Diagonalzahl gar nicht finden kann, da er immer im falschen Bereich weitersucht.

    Man kann zeigen, dass für die Potenzmenge P(M) einer Menge M immer |M|<|P(M)| (also nicht gleich) gilt. Die Potenzmenge ist der Menge aller Teilmengen einer Menge, z.B.:
    M={a,b}
    P(M)={{},{a},{b},{a,b}}
    Wie soll man denn die Potenzmenge der Menge der natürlichen Zahlen bilden, wenn es doch gar keine größte natürliche Zahl gibt?

    Angenommen, es gäbe eine bijektive Abbildung f: M -> P(M),
    Sprich eine bijektive Abbildung einer Menge M auf ihre eigene Potenzmenge.

    dann betrachte man die Menge X={m in M; m ist kein Element von f(m)}.
    Das müssen Sie mir näher erklären: Was ist hier X, was ist m und was ist f(m)?

    Nach Voraussetzung muss es ein y geben, so dass f(y)=X.
    Wo kommt jetzt dieses y her? Ist das ein Element von M?

    Angenommen y läge in X, dann kann y nach Definition von X nicht in X liegen.
    Also ist y nicht in X, aber dann ist es nach Definition von X doch in X.
    Man hat also einen Widerspruch.
    Darin sehe ich eher eine unlogische Angelegenheit. Sprich, da muß vorher schon etwas falsch gewesen sein.

    Man nennt auch das eine Diagonalprinzip, das Argument ist übrigens bei der Russellschen Antinomie ganz ähnlich, aber das ist ein anderes Thema ...
    Solche Sachen lassen wir besser hier raus, sonst komme ich womöglich durcheinander.

    Um zu erhalten, dass Mengen immer vergleichbar sind (|N|<=|M| oder |M|<=|N|), braucht man übrigens das Auswahlaxion (Zornsches Lemma), das in manchen Mathematikerkreisen umstritten ist, da es nicht-konstruktiv ist.
    Ich halte es für sinnvoll, nur solche Dinge hier einzubringen, die unter Mathematikern allgemein anerkannt sind.

    Viele Grüße

    Bernd Pfützner
    • 06 Aug 2010, 12:13 am
  • Post visible to registered members
  • Karl Kemminger
    Karl Kemminger    Premium Member   Group moderator
    The company name is only visible to registered members.
    Re^3: (über)abzählbar
    Lieber Herr Pfützner,

    Sprich, es ist von Anfang an vorprogrammiert, daß Cantor seine Diagonalzahl gar nicht finden kann, da er immer im falschen Bereich weitersucht. Cantor konstruiert eben eine Zahl, die in das Schema nirgends hineinpassen kann, der Beweis ist auch in Wikipedia beschrieben:
    http://de.wikipedia.org/wiki/Cantors_zweites_Diagonalargumen...

    Angenommen y läge in X, dann kann y nach Definition von X nicht in X liegen.
    Also ist y nicht in X, aber dann ist es nach Definition von X doch in X.
    Man hat also einen Widerspruch.
     
    Darin sehe ich eher eine unlogische Angelegenheit. Sprich, da muß vorher schon etwas falsch gewesen sein.     Genau, da muß schon vorher etwas falsch gewsen sein, also die ursprüngliche Annahme falsch gewesen sein, weil alle weiteren Schritte sich logisch aus dieser Annahme abgeleitet haben. Und die Annahme war, dass die reellen Zahlen abzählbar ist. Das nennt man indirekten Beweis.

    Grüße aus Wien
    Karl Kemminger
    This post was modified on 06 Aug 2010 at 09:42 am.
    • 06 Aug 2010, 09:38 am
  • Bernd Pfützner
    Bernd Pfützner    Premium Member   Group moderator
    The company name is only visible to registered members.
    Re^4: (über)abzählbar
    Lieber Herr Kemminger,

    Karl Kemminger schrieb:
    Lieber Herr Pfützner,
     
    Sprich, es ist von Anfang an vorprogrammiert, daß Cantor seine Diagonalzahl gar nicht finden kann, da er immer im falschen Bereich weitersucht.
    Cantor konstruiert eben eine Zahl, die in das Schema nirgends hineinpassen kann, der Beweis ist auch in Wikipedia beschrieben:
    http://de.wikipedia.org/wiki/Cantors_zweites_Diagonalargumen...
    ich möchte einmal versuchen, meinen Ansatz graphisch darzustellen (was mit den Mitteln bei Xing leider etwas unvollkommen aussieht):

    Auf dem Zahlenstrahl sieht das Intervall [0, 1] so aus:

    0___0,1___0,2___0,3___0,4___0,5___0,6___0,7___0,8___0,9___1

    Nun ordnen wir die Liste, die Cantor überprüfen soll, so an, daß wir zunächst systematisch alle reellen Zahlen im Bereich 0___0,1 erfassen. Bereits in diesem Teilintervall gibt es unendlich viele reelle Zahlen, die mit 0,0... beginnen. Daraus folgt unweigerlich, daß Cantors erstes Diagonalelement seiner Diagonalzahl eine 1 sein muß, sprich seine Diagonalzahl muß sich im Teilintervall 0,1___0,2 befinden. Damit aber nicht genug, denn es gibt im ersten Teilintervall auch unendlich viele Zahlen, die mit 0,00... beginnen. Daraus folgt unweigerlich, daß Cantors zweites Diagonalelement seiner Diagonalzahl ebenfalls eine 1 sein muß, sie muß sich also im nächsten untergeordneten Teilintervall 0,11___0,12 befinden. Und selbstverständlich befinden sich auch im Teilintervall 0,000___0,001 wieder unendlich viele reelle Zahlen, so daß auch Cantors drittes Diagonalelement seiner Diagonalzahl wieder eine 1 werden muß, weshalb sich seine Diagonalzahl folglich im nächsten untergeordneten Teilintervall 0,111___0,112 befinden muß.

    Schon aus diesen wenigen systematischen Arbeitsschritten bei der Aufstellung der Liste und deren Abarbeitung nach der Cantor-Methode ist ersichtlich, daß Cantors Diagonalzahl nichts anderes als die 0,(Periode)1 werden kann.

    Da wir die 0,(Periode)1 aber bereits als Element der reellen Zahlen kennen (und sie logischerweise von Anfang an in unsere Liste aufgenommen haben), müßte Cantor sie auch finden. Aber genau das gelingt ihm nicht, da er ja unendlich mit dem Intervall 0,0___0,1 beschäftigt bleibt und sich zudem unendlich immer tiefer in dessen untergeordnete Teilintervalle verstrickt. In das Teilintervall 0,1___0,2 wird er niemals eindringen, ebenso nicht in die untergeordneten Teilintervalle 0,01___0,02 und 0,001___0,002 und 0,0001___0,0002 und so weiter.

    Wie ich schon sagte: Meiner Meinung nach ist Cantors Strategie ein perfekt angelegtes Manöver, um eine reelle Zahl, die in der Liste der reellen Zahlen enthalten ist, NICHT zu finden.

    Wie sehen Sie das?

    Angenommen y läge in X, dann kann y nach Definition von X nicht in X liegen.
    Also ist y nicht in X, aber dann ist es nach Definition von X doch in X.
    Man hat also einen Widerspruch.
     
    Darin sehe ich eher eine unlogische Angelegenheit. Sprich, da muß vorher schon etwas falsch gewesen sein.
    Genau, da muß schon vorher etwas falsch gewsen sein, also die ursprüngliche Annahme falsch gewesen sein, weil alle weiteren Schritte sich logisch aus dieser Annahme abgeleitet haben. Und die Annahme war, dass die reellen Zahlen abzählbar ist. Das nennt man indirekten Beweis.
    Dazu möchte ich erst kommen, wenn Herr Ecker auf meine Fragen geantwortet hat. Denn zuvor muß ich seinen Gedankengang verstehen lernen.

    Viele Grüße

    Bernd Pfützner
    • 06 Aug 2010, 7:47 pm
  • Katharina Schüller
    Katharina Schüller    Group moderator
    The company name is only visible to registered members.
    Re^5: (über)abzählbar
    Hallo Bernd,

    Nun ordnen wir die Liste, die Cantor überprüfen soll, so an, daß wir zunächst systematisch alle reellen Zahlen im Bereich 0___0,1 erfassen. Bereits in diesem Teilintervall gibt es unendlich viele reelle Zahlen
    Genau das macht aber der Beweis nicht. Cantor sagt, nimm irgendeine Folge aus der Menge der reellen Zahlen zwischen 0 und 1. Die Zahlen müssen auch gar nicht geordnet sein. Er zeigt mit dem Beweis, wie man eine Zahl konstruiert, die nicht in dieser Folge enthalten sein kann. Der Trick mit "irgendeine Folge" ist, dass man eben nicht bei einer bestimmten Zahl, z.B. 0,1 Periode, festhängt, und dass man am Anfang auch nicht über unendlich viele Zahlen nachdenken muss.

    Fang z.B. an mit 5 Zahlen:
    (1) 0,2356718
    (2) 0,9
    (3) 0,75
    (4) 0,3 Periode
    (5) 0,1001001001

    Die neue Zahl ist dann 0,30141. Ich habe sie konstruiert, indem ich diagonal durch die Nachkommastellen gegangen bin und dann immer 1 addiert habe. Ich könnte auch 1 subtrahieren oder 3 oder alles andere außer 0, 10, 20,... Hauptsache, meine neue Zahl unterscheidet sich von der Diagonalen der Matrix, die ich kriege, wenn ich die Nachkommastellen als Zeilenvektoren untereinander schreibe. (Man muss natürlich ggf. Nachkommastellen abschneiden oder auffüllen, damit die Matrix quadratisch wird, sonst hat sie ja keine Diagonale.)

    Da aber diese Folge beliebig gewählt sein kann, kann sie auch beliebig erweitert - und schließlich unendlich verlängert - werden. Egal welche Zahlen jedoch in welcher Reihenfolge in dieser Folge auftauchen: Cantors Methode konstruiert eine Zahl, die definitionsgemäß nicht dabei ist.

    Das siehst du spätestens dann, wenn du versuchst, in der gedanklichen Matrix von oben diese neue Zahl einzuordnen - sie hat eben an der Stelle, die auf der Diagonalen liegt, einen anderen Wert als die ursprünglich dort einsortierte Zahl, auch wenn sie mit dieser zufällig an allen anderen Stellen übereinstimmt.

    Ist es jetzt deutlicher?

    Viele Grüße
    Katharina
    • 06 Aug 2010, 10:51 pm