Eigenschaft von Überabzählbarkeit?

Neue Frage »

Cusquena Auf diesen Beitrag antworten »
Eigenschaft von Überabzählbarkeit?
Meine Frage:
Hi,

mir geistert eine Frage jetzt schon längere zeit im kopf herum:

Kann es eine Überabzählbare Menge geben, deren Elemente "endliche Objekte" sind?

Mit endlichen Objekten meine ich intuitiv: Es gibt eine Darstellungsform/Symbolisierung, sodass für jedes einzelne Element ein (evtl. sehr großes, aber endllich-großes) Blatt Papier existiert, worauf ich das Element aufschreiben kann.

Meine Ideen:
Ich bin mir relativ sicher, dass die Antwort auf die Frage negativ ist, mir fällt nur kein Beweis dazu ein. (oder gibt es keinen?)

Ein paar Dinge sind mir auch schon bewusst. Bildet man die Kleenesche Hülle A* einer höchstens azählbarer Menge A, so ist diese abzählbar.
Dabei ist

die Menge aller Wörter über A, d.h. aller (endlichen!!) Zeichenreihen mit Zeichen aus A.

So kann es also schonmal nicht funktionieren. Aber wie sähe es Beispielsweise mit der Menge

aus. Natürlich kann man nicht wirklich c einfach mit reellen zahlen indizieren, immerhin sind reelle Zahlen im allgemeinen irgendwie unendliche objekte, je nach Darstellung z.B. unendliche Dezimalbrüche. C ist eher eine Menge, die für jede reelle Zahl ein Zeichen bereit hält.

Ich wär sehr froh, falls mir jemand helfen kann smile
MaPalui Auf diesen Beitrag antworten »

Die Potenzmenge der natürlichen Zahlen ist überabzählbar.
Cusquena Auf diesen Beitrag antworten »

Ja, aber was macht diese Menge überabzählbar? genau die unendlichen Teilmengen! Alle endlichen Teilmengen der Natürlichen Zahlen sind Abzählbar.
Elvis Auf diesen Beitrag antworten »

Das reelle Intervall [0,1], als Teilmenge eines affinen Raums, enthält überabzählbar unendlich viele Punkte. Ein Punkt ist nach Euklid "etwas, das keine Teile hat", also ein außerordentlich endliches Objekt.
Ich hätte genau so gut von reellen Zahlen zwischen 0 und 1 reden können, aber es gibt Menschen, die reelle Zahlen mit (in gewissem Sinne "unendlichen") Dezimalzahlen verwechseln.
Finn_ Auf diesen Beitrag antworten »

Das ist eher einfach zu beantworten.

Ein Element einer Menge wird dargestellt durch eine Zeichenkette. Wenn zwei Elemente unterschiedlich sein sollen, muss die Zeichenkette notwendigerweise unterschiedlich sein. Zeichenketten lassen sich lexikographisch anordnen, wenn das Alphabet angeordnet wurde. Damit ist auf einfache Weise jeder Zeichenkette bijektiv eine natürliche Zahl zugeordnet.

Überabzählbar viele Elemente lassen sich damit nicht darstellen, denn es gibt nur abzählbar viele natürliche Zahlen.
Cusquena Auf diesen Beitrag antworten »

Danke schonmal für die Antwort!
Das Problem, warum mich die Antwort noch nicht begnügt, ist folgendes: Auch wenn die Punkte resp. reelle Zahlen endliche Objekte sind, so kann man sie trotzdem nicht auf endliche Art und Weise aufschreiben/darstellen/symbolisieren. (oder doch?)
Vielleicht präziser: wenn ich an einen Computer (Registermaschine, Turingmaschine oder sonstiges Maschinenmodell) versuche eine reelle Zahl zur Berechnung einer Funktion zu übergeben, dann ist das zum scheitern verurteilt. Im Falle der Registermaschine z.B. auch, wenn man eine beliebig lange, aber endlicher Registerbreite einbauen könnte.
 
 
Cusquena Auf diesen Beitrag antworten »

@Finn:
Das ist genau das, was ich zu Anfangs mit der Kleeneschen Hülle meinte! (Die lexikographische Anordnung der Wörter/Zeichenketten ist eine Möglichkeit, die Abzählbarkeit zu zeigen.)
Aber was passiert, wenn man die Zeichen selber (aus denen die Wörter bestehen) aus einer überabzählbaren Menge schöpft? Also es ist klar was dann passiert. die Frage ist eher ob das möglich ist.
Finn_ Auf diesen Beitrag antworten »

Wenn das Alphabet überabzählbar ist, lässt sich einfach jedem Element bijektiv ein Zeichen zuordnen. Das wird wohl nicht gemeint sein.

Bleibt noch der Fall übrig, bei dem das Alphabet abzählbar unendlich ist.
Finn_ Auf diesen Beitrag antworten »

Jedes Zeichen aus dem Alphabet bekommt nun bijektiv eine natürliche Zahl zugeordnet. Die Zeichketten sind dann endliche Tupel natürlicher Zahlen.

Zu bestimmen ist also die Mächtigkeit von

bzw.

Das kartesische Produkt von abzählbaren ist nach dem ersten Diagonalargument abzählbar. Die endliche Vereinigung von abzählbaren Mengen ist nach dem Reißverschlussargument offenbar auch abzählbar.
Finn_ Auf diesen Beitrag antworten »

Ach so, die Tupel können ja beliebig lang werden. Aber die Vereinigung von abzählbar vielen abzählbaren Mengen ist nach ACC immer noch abzählbar.
Cusquena Auf diesen Beitrag antworten »

Was meinst du mit "Wenn das Alphabet überabzählbar ist, lässt sich einfach jedem Element bijektiv ein Zeichen zuordnen." ?

Meinst du jedem Element des Alphabets eine reelle Zahl? Doch, so ist das gemeint. Die Menge aller Wörter über einem solchen überabzählbaren Alphabet trivialerweise überabzählbar. Das meinte ich mit "es ist klar was dann passiert. Sorry, war nicht so eindeutig wie ich es geschrieben hab.

Zum abzählbaren Alphabet: das habe ich auch bereits im ersten Post geschrieben: auch dann ist die Menge aller Wörter abzählbar.
Finn_ Auf diesen Beitrag antworten »

Zitat:
Was meinst du mit "Wenn das Alphabet überabzählbar ist, lässt sich einfach jedem Element bijektiv ein Zeichen zuordnen." ?

Ich meinte, es gibt eine Bijektion zwischen einer überabzählbaren Menge (mit Mächtigkeit ) und dem Alphabet aus überabzählbar (wieder die selbe Mächtigkeit) vielen unterschiedlichen Zeichen.

Zitat:
Zum abzählbaren Alphabet: das habe ich auch bereits im ersten Post geschrieben: auch dann ist die Menge aller Wörter abzählbar.

Dann scheint die Frage doch beantwortet zu sein.

Selbst wenn man abzählbar viele unterschiedliche Zeichen zu Verfügung hätte, lässt sich nicht gleichzeitig jedem Element aus etc. eine endliche darstellende Zeichenkette zuordnen.
Cusquena Auf diesen Beitrag antworten »

Zitat:

Ich meinte, es gibt eine Bijektion zwischen einer überabzählbaren Menge (mit Mächtigkeit ) und dem Alphabet aus überabzählbar (wieder die selbe Mächtigkeit) vielen unterschiedlichen Zeichen.

Ok, also genau so wie ich meinte dass ich es verstanden hab.

Zitat:

Dann scheint die Frage doch beantwortet zu sein.


Hä? aber nein! Das heißt das alles was du geschrieben hast bereits im Eingangspost stand Big Laugh


Zitat:

Selbst wenn man abzählbar viele unterschiedliche Zeichen zu Verfügung hätte, lässt sich nicht gleichzeitig jedem Element aus etc. eine endliche darstellende Zeichenkette zuordnen.


Das wäre leicht, das ganze muss natürlich auch noch injektiv sein. Aber wahrscheinlich meintest du das so. Aber wie gesagt, das ist genau das was im Eingangspost stand. Die Frage ist, ob es möglich wäre, dass überabzählbar viele Zeichen zur Verfügung stehen!
Finn_ Auf diesen Beitrag antworten »

Zitat:
Die Frage ist, ob es möglich wäre, dass überabzählbar viele Zeichen zur Verfügung stehen!

Das wäre nur möglich, wenn sich das Blatt Papier unendlich vergrößern ließe um diese vielen Zeichen unterscheiden zu können. Jedes Element könnte dann auch als Punkt in einer Streckenskala angegeben werden, die man sich unter einem »Mikroskop« anschauen müsste, um diesen Punkt immer weiter und weiter aufzulösen.

Andernfalls müssten die Zeichen aus Teilsymbolen aufgebaut sein. Man kann sich dabei auch eine Matrix von Pixeln vorstellen. Ohne weiteres enstehen hierbei zunächst auch nur endlich viele Zeichen. Hat man abzählbar viele Pixelfarben, kommen auch nur abzählbar viele Zeichen bei raus.
Finn_ Auf diesen Beitrag antworten »

Auf freche Weise lässt sich das Problem auch so charakterisieren:

Das Blatt Papier ist ein gigantischer monochromer Bildpuffer. Alle Bildzeilen lassen sich nun hintereinanderlegen. Darin kann ein n-Tupel von {0,1} gespeichert werden. Das ermöglicht aber nur , also endlich viele unterschiedliche Elemente.

Das Blatt muss entweder unendlich groß sein, oder eine unendlich feine Auflösung besitzen, um überabzählbar viele Elemente zu ermöglichen. Anders geht es nicht. Das unendlich fein ist wie gesagt damit gleichbedeutend, dass sich in einem virtuellen Pixel überabzählbar unendlich viele Zustände kodieren lassen.
Cusquena Auf diesen Beitrag antworten »

Danke auf jeden Fall schon mal für die bisherigen Gedanken dazu.
Ich habe mir auch schon versucht mir das auf unformale Weise klarzumachen. Unter anderem daher auch die Vermutung, dass die Antwort auf die Frage Negativ sei. Aber ein wirklich schlagendes Argument habe ich bisher nicht gefunden und sehe ich ehrlich gesagt auch noch nicht bei dem was du geschrieben hast.
Ich glaube eine Sache hattest du falsch verstanden (vielleicht auch nicht, dann hab ich das von dir nicht verstanden Big Laugh )
Es geht nicht darum, alle Elemente auf einem beliebig-, aber endlich großem Blatt Papier darzustellen. Es geht darum, jedes einzelne Element auf einem eigenen Blatt Papier unterzubringen. Es kann so viele Blätter wie nötig geben. (Es müssen auf jeden Fall überabzählbar viele sein)
Jetzt könnte man sagen: Nagut, dann nehmen wir einfach überabzählbar viele endlich-große Blätter und schreiben auf jedes ein Symbol. Aber geht das? Wenn wir es mit den reellen Zahlen versuchen würden, würden wir scheitern. Denn egal für welche Darstellungsart wir uns entscheiden, z.B. die Dezimalbruchdarstellung, werden wir nicht in der Lage sein, z.B. aufzuschreiben.
Cusquena Auf diesen Beitrag antworten »

Gleiches gilt auch für alle Potenzmengen abzählbar unendlicher Mengen.
Finn_ Auf diesen Beitrag antworten »

Zitat:
Es geht darum, jedes einzelne Element auf einem eigenen Blatt Papier unterzubringen.

Davon ging ich aus, muss dann aber irgendwie durcheinander gekommen sein. Die einzelnen Argumente bleiben davon jedoch unberührt:
  1. Zur Darstellung eines Elements wird abzählbar unendlich viel Speicher benötigt (z.B. unendliche Dezimalbruchdarstellung).
  2. Das Blatt Papier lässt sich durch einen endlich großen monochromen Bildpuffer modellieren. Da passt aber nur endlich viel Information rein.
Cusquena Auf diesen Beitrag antworten »

Zitat:

  1. Zur Darstellung eines Elements wird abzählbar unendlich viel Speicher benötigt (z.B. unendliche Dezimalbruchdarstellung).


Dass das für reelle Zahlen so ist, ist schon klar, hatte ich ja auch geschrieben...
Meine eigentliche Frage ist immernoch die gleiche: Wieso kann es keine andere überabzählbare Menge geben, für die das nicht gilt?
Finn_ Auf diesen Beitrag antworten »

Zitat:
Meine eigentliche Frage ist immernoch die gleiche: Wieso kann es keine andere überabzählbare Menge geben, für die das nicht gilt?

Zwischen zwei Mengen mit der Mächtigkeit des Kontinuums gibt es nach Definition eine Bijektion. Die Bijektion benennt die Elemente nur um.
Elvis Auf diesen Beitrag antworten »

Was spricht gegen meine Darstellung überabzaehlbar vieler Objekte, nämlich der reellen Zahlen zwischen 0 und 1, durch Punkte eines Intervalls? Wer sagt denn, dass eine reelle Zahl durch eine Zeichenkette dargestellt werden muss?
Cusquena Auf diesen Beitrag antworten »

Jop. Aber impliziert das, dass es auch für jede andere Menge, deren Mächtigkeit mindestens so groß wie die des Kontinuums ist, keine endliche Darstellung ihrer Elemente gibt?
Cusquena Auf diesen Beitrag antworten »

Der letzte Post war noch an Finn gerichtet.

@ Elvis:
Zitat:
Original von Elvis
Wer sagt denn, dass eine reelle Zahl durch eine Zeichenkette dargestellt werden muss?


Niemand. Aber wie würdest du eine reelle Zahl an ein Maschinenmodell übergeben, wenn nicht durch eine Zeichenkette?
Elvis Auf diesen Beitrag antworten »

Über eine Darstellung für eine Maschine habe ich nicht nachgedacht. In deinem ersten Beitrag hast du nach der Darstellung auf einem Blatt Papier gesprochen, und das klappt mit dem Intervall ganz gut.
Cusquena Auf diesen Beitrag antworten »

Da hast du recht, für mich war das das gleiche. Dann tauschen wir das aus zu:

Mit endlichen Objekten meine ich intuitiv: Es gibt eine Dastellungsart/Symbolisierung, so dass jedes einzelne Element exakt an ein Maschinenmodell übergeben werden kann.

(Ich glaube eigentlich ist da nicht wirklich ein Unterschied. Denn wie willst du [latex] \frac{\sqrt{2}}{2} \in [0,1] [latex/] auf einem Blatt Papier eindeutig darstellen? Abgesehen von der Zeichenkette [latex] \frac{\sqrt{2}}{2} [latex/]. Das ist m. E. nur, jenachdem wie man es will, eine Zeichenkette oder eine Funktion, nicht der der "wirkliche Wert".
Finn_ Auf diesen Beitrag antworten »

Zitat:
Original von Cusquena
Jop. Aber impliziert das, dass es auch für jede andere Menge, deren Mächtigkeit mindestens so groß wie die des Kontinuums ist, keine endliche Darstellung ihrer Elemente gibt?

Die Zeichenketten lassen sich binär kodieren. Die der Länge sind endliche Tupel aus . Die Menge aller endlichen Binärfolgen ist

Die abzählbare Vereinigung von endlichen Mengen ist abzählbar. Daher ist

Wenn die Menge gleichmächtig zu ist, dann ist auch

Es gibt also keine Injektion . D.h. es kann unmöglich jedem Element von eine unterschiedliche endliche Binärfolge zugeordnet werden.
Cusquena Auf diesen Beitrag antworten »

Mist, ich sollte mich registrieren, dann könnte ich editieren und den Latexquark korrigieren. bzw. war natürlich gemeint.

Was du da gemacht hast Finn, ist alle Wörter über dem 2-elementigen Alphabet {0, 1} zu bilden. D.h. {0,1}* in der Notation meines ersten Postes. Wie wir schon ein paar mal festgehalten hatten, ist selbst bei einem abzählbar unendlichen Alphabet (z.B ) die Menge aller Wörter über diesem nur Abzählbar unendlich.
Die Frage ist nach wie vor, ob es ein überabzählbares Alphabet geben kann.
Finn_ Auf diesen Beitrag antworten »

Zitat:
Die Frage ist nach wie vor, ob es ein überabzählbares Alphabet geben kann.

Ja natürlich kann es ein solches Alphabet geben. Das ist aber eine philosophische Frage.

Aber gemogelt ist es dann schon, weil das Überabzählbare in das Alphabet eingeimpft wurde.

Genau so ist es mit einem reellen Intervall. Da ist das Überabzählbare schon drin. Jeder Punkt darin ist zwar endlich, aber es wird abzählbar unendlich viel Information benötigt um ihn zu charakterisieren. Es geht ja nicht um den Punkt selbst, sondern um die Beziehung des Punktes zu den anderen Punkten.

Da wird eine endliche Darstellung gefordert, aber dann doch das Unendliche hineingemogelt.
Elvis Auf diesen Beitrag antworten »

Das ist nicht gemogelt. Eine Menge heißt unendlich, wenn es eine Bijektion zwischen und einer echten Teilmenge gibt. Also ist wegen unendlich. Ein reelles Intervall passt problemlos auf einen Papierschnipsel, und alle Elemente, also alle reellen Zahlen des Intervalls, sind als Punkte dargestellt.

In den endlichen Arbeitsspeicher einer Maschine, in der Zahlen als Bitfolgen abgelegt werden, passen nur endlich viele Zahlen. Von abzählbaren oder überabzählbaren Mengen kann in solchen Maschinen nicht die Rede sein.

Wir sind selbstverständlich nicht in der Lage, jeden einzelnen von überabzählbar vielen Punkten zu benennen. Das gelingt uns nicht einmal bei den abzählbar vielen natürlichen Zahlen. In London war ich einstmals Augen- und Ohrenzeuge eines Kunstprojekts, in dessen Verlauf in einem Glascontainer auf einem öffentlichen Platz natürliche Zahlen fortlaufend vorgelesen wurden - ich habe das Ende nicht abgewartet ...
Cusquena Auf diesen Beitrag antworten »

@Finn
Zitat:

Das ist aber eine philosophische Frage.

Ich denke auch schon seit längerem darüber nach und mehr und mehr festigt sich auch bei mir, dass das eine philosophische Frage ist. Wobei ich aber eher in die andere Richtung gehen würde und denke, dass es das nicht gibt! Big Laugh

Ich habe jetzt ein Argument gefunden, was mich halbwegs zufrieden stellt. Falls es dich, Elvis oder sonst jemanden interessiert:
Wir haben ja gesehen, dass sich solch eine Überabzählbare Menge, deren einzelne Elemente auf endliche Art und Weise exakt darstellen lassen, nicht durch Kombination von Symbolen entstehen kann, welche aus einer höchstens abzählbaren Symbolmenge geschöpft werden. Folglich muss die gewünschte Menge selbst eine Symbolmenge sein, und zwar eine überabzählbare. Kann so etwas existieren? (Ich denke im folgenden ähnlich wie Turing es tat um seine Turingmaschine zu entwerfen, falls das jemand kennt)
Angenommen, ein Mensch setzt sich hin und schreibt (paarweise verschiedene) Symbole auf. Dieser Mensch ist mit ewigem Leben gesegnet und schreibt bis in alle Ewigkeit weiter Symbole auf. Er könnte diesen Prozess auch automatisieren, so dass er viel schneller neue Symbole aufschreibt.
Das Problem bei der Sache ist: Egal nach wie langer Zeit man nachschaut, wieviele Symbole bereits geschrieben wurden, sind es nur endlich viele. Man könnte jetzt definieren als die Menge an Symbolen, die nach i Minuten/Jahren/Millisekunden geschrieben wurden. Dann ist aber auch nur Abzählbar.
(Ich hab "Symbol" nicht immer einheitlich benutzt. In dem oben hab ich "Symbol" als Begriff für eine art elementares/atomares Zeichen verwendet.)

Vielleicht ist das auch alles Quatsch was ich da gerade geschrieben hab Big Laugh


@ Elvis:
Ich glaube du hast die Frage nicht verstanden. Ich Zitiere nochmal was ich vor einigen Posts geschrieben hab: Es geht nicht darum, alle Elemente auf einem beliebig-, aber endlich großem Blatt Papier darzustellen. Es geht darum, jedes einzelne Element auf einem eigenen Blatt Papier unterzubringen. Es kann so viele Blätter wie nötig geben. (Es müssen auf jeden Fall überabzählbar viele sein)
Jetzt könnte man sagen: Nagut, dann nehmen wir einfach überabzählbar viele endlich-große Blätter und schreiben auf jedes ein Symbol. Aber geht das? Wenn wir es mit den reellen Zahlen versuchen würden, würden wir scheitern. Denn egal für welche Darstellungsart wir uns entscheiden, z.B. die Dezimalbruchdarstellung, werden wir nicht in der Lage sein, z.B. aufzuschreiben.

natürlich kann man auf einem endlich großen Blatt Papier nicht unendlich (ob über- oder nur abzählbar) viele Elemente aufschreiben...
Elvis Auf diesen Beitrag antworten »

Nach dem Wohlordnungssatz kann man jede Menge wohlordnen. Schreibe die reellen Zahlen in der Reihenfolge ihrer Wohlordnung auf überabzaehlbar viele Blätter und du bist fertig. Restproblem, es gibt eine Wohlordnung, aber man hat keine, und man hat nicht genug Blätter in einem endlichen Universum.
Finn_ Auf diesen Beitrag antworten »

Zitat:
Angenommen, ein Mensch setzt sich hin und schreibt (paarweise verschiedene) Symbole auf. Dieser Mensch ist mit ewigem Leben gesegnet und schreibt bis in alle Ewigkeit weiter Symbole auf. Er könnte diesen Prozess auch automatisieren, so dass er viel schneller neue Symbole aufschreibt.
Das Problem bei der Sache ist: Egal nach wie langer Zeit man nachschaut, wieviele Symbole bereits geschrieben wurden, sind es nur endlich viele.

Um abzählbar unendlich viele Operationen in einer endlichen Zeit zu bewerkstelligen, wird eine Zenomaschine herangezogen, die braucht mit jeder nachfolgenden Operation nur noch halb so viel Zeit. Die Maschine hat natürlich auch wie eine Turing-Maschine abzählbar unendlich viel Speicher.
Cusquena Auf diesen Beitrag antworten »

Zitat:
Original von Elvis
Nach dem Wohlordnungssatz kann man jede Menge wohlordnen. Schreibe die reellen Zahlen in der Reihenfolge ihrer Wohlordnung auf überabzaehlbar viele Blätter und du bist fertig. Restproblem, es gibt eine Wohlordnung, aber man hat keine, und man hat nicht genug Blätter in einem endlichen Universum.


Ok, und wie schreibst du Wurzel 2 auf das Blatt?


@finn
Hui, cool Maschine, schau ich mir mal an! Ich wollte nur nochmal sagen, dass ich nicht meinte, dass in endlicher Zeit abzählbar unendlich viele Operationen bewerkstelligt werden. Da steht ja auch "Egal nach wie langer Zeit man nachschaut, wieviele Symbole bereits geschrieben wurden, sind es nur endlich viele." Wenn man den Limes betrachtet, d.h. , so ist A nur abzählbar.
Elvis Auf diesen Beitrag antworten »

Option 1: Jedes Blatt hat überabzählbar viele Dezimalstellen, dann lasse ich die reellen Zahlen als Dezimalzahlen schreiben.
Option 2: Wurzel aus 2 schreibe ich als .
Option 3: Alle rationalen Zahlen lasse ich als Brüche schreiben (z.B. , alle algebraischen Zahlen lasse ich als Nullstellen ihres Minimalpolynoms schreiben (z.B. ). Nachtrag: Transzendente Zahlen werden durch ihren Index in der Wohlordnung dargestellt (bin mir nicht sicher, ob das so geht).
Cusquena Auf diesen Beitrag antworten »

Zitat:
Original von Elvis
Option 1: Jedes Blatt hat überabzählbar viele Dezimalstellen, dann lasse ich die reellen Zahlen als Dezimalzahlen schreiben.

Abzählbar viele Dezimalstellen würden reichen. Aber es geht ja explitzit um die Darstellung mit endlich großen Blättern.
Zitat:

Option 2: Wurzel aus 2 schreibe ich als .
Option 3: Alle rationalen Zahlen lasse ich als Brüche schreiben (z.B. , alle algebraischen Zahlen lasse ich als Nullstellen ihres Minimalpolynoms schreiben (z.B. ).

Ob Man das als Darstellung ok ist oder nicht, dafür kenn ich mich zu wenig aus. Ist so eine Nullstelle berechenbar? falls nicht, wär das natürlich unpraktisch. Aber auch wenn nicht, ist es trotzdem irgendwie eine endliche Darstellung. Wie auch immer, das ist eigentlich auch egal, denn das eigentliche Problem sind denke ich die Transzendenten Zahlen.
Zitat:

Nachtrag: Transzendente Zahlen werden durch ihren Index in der Wohlordnung dargestellt (bin mir nicht sicher, ob das so geht).


Welchen Index in der Wohlordnung? einfach per Wohlordnung durchnummerieren (t1, t2, t3,...) geht nicht. Dann gäbe es ja eine Bijektion zu . Aber es sind gerade die transzendenten Zahlen, welche überabzählbar machen.
Elvis Auf diesen Beitrag antworten »

Die Wohlordnung der reellen Zahlen kann nicht nur über die natürlichen Zahlen gehen, denn die reellen Zahlen sind nicht abzählbar. Die Indizes der Wohlordnung sind . Wer weiß genau, wo das Ende ist und was ich in dieser Indexfolge noch aufschreiben müsste ? Ich weiß nur, dass es ein Ende gibt, und das Ende ist die Kardinalität von .
zweiundvierzig Auf diesen Beitrag antworten »
RE: Eigenschaft von Überabzählbarkeit?
Zitat:
Original von Cusquena
Kann es eine Überabzählbare Menge geben, deren Elemente "endliche Objekte" sind?

Die klassisch berechenbaren reellen Zahlen (die auch gewisse transzendente Zahlen umfassen) sind abzählbar. Also sind fast alle reellen Zahlen unberechenbar.

Betrachtet man andere Modelle (z.B. Blum-Shub-Smale-Maschinen), dann gibt es auch überabzählbare Mengen, die berechenbar sind, vgl. Blum, Shub, Smale: On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines.

Zur informellen Darstellung einer BSS-Maschine siehe S. 5. Insbesondere kann eine BSS-Maschine im unterschied zu einer Turingmaschine beliebige reelle Zahlen speichern.
Cusquena Auf diesen Beitrag antworten »

Sorry, war lange weg.

@Elvis: Ok, damit hast du das Problem auf die Frage verschoben, ob diese "Indizes der Wohlordnung" endlich darstellbar sind smile

@zweiundvierzig: Von diesen Maschinen wusste ich noch nichts, danke für den Hinweis! smile Muss ich mir (wenn man denn mal irgendwann zeit für sowas findet) mal anschauen. Allerdings sehe ich nicht ganz, was das mit der eigentlichen Frage zu tun hat. Oder sollte es das gar nicht, sondern einfach ein Hinweis auf diesen "Bereich der Berechenbarkeitstheorie" sein?
zweiundvierzig Auf diesen Beitrag antworten »

Zitat:
Original von Cusquena
Allerdings sehe ich nicht ganz, was das mit der eigentlichen Frage zu tun hat.

Ich habe die Frage gelesen als (verwandt zu der) Frage nach der Existenz überabzählbarer berechenbarer Mengen.
Cusquena Auf diesen Beitrag antworten »

@Zweiundvierzig: ups, ich seh den Zusammenhang Big Laugh An diese Maschinen kann man ja beliebige reelle Zahlen übergeben und diese kann sie speichern...
Aber wird das "Problem" dabei einfach umgangen indem man einfach definiert, dass sie in einer Art Speicherzelle eine bel. reelle Zahl aufnehmen kann?
Die Sache bei den herkömmlichen Maschinenmodellen ist ja, dass man sie theoretisch auch in die Praxis umsetzen könnte (zumindest die deterministischen), bzw. die rekursiven Funktionen usw. einfach als Mensch nachvollziehen kann. Das ginge ja evtl. bei einer BSSM nicht. Oder?
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »