Reelle Zahlen für lange Texte

[Otmar]

Die Frage, ob es mehr reelle Zahlen als rationale Zahlen gibt, wird vom Lehrer mit ja beantwortet. Die Frage, warum das so ist, mit kurzem Schweigen und dem Versprechen, dass es in der nächsten Stunde eine Antwort gibt. Zur Vorbereitung der nächsten Stunde, sollen die Schüler folgende Aufgabe lösen:

Stellt euch unendlich lange Texte vor. Jeder Text besteht aus unendlich vielen nacheinander aufgeschriebenen Zeichen. Ein Zeichen ist ein großer oder kleiner Buchstabe, eine Ziffer ein Leerzeichen oder ein Punkt. Es gibt also genau 64 Zeichen: A...Z, a...z, 0..9, _, . Jedes Zeichen darf unabhängig von allen anderen Zeichen beliebig gewählt werden.

Findet eine Regel, die jedem Text eine und nur eine reelle Zahl zuordnet und es bei dieser Zuordnung andersrum auch für jede reelle Zahl genau einen Text gibt.

Da auch die Eltern der Schüler bei dieser Hausaufgabe nicht helfen konnten, wird die Frage hier gestellt.

edit: "und es bei dieser Zuordnung andersrum auch für jede reelle Zahl genau einen Text gibt" zugefügt.

[gp3050]

Sind nur mal ein paar spontane Gedanken.

Mehr ->

Ausgehend davon, dass jeder "Text" unendlich lange ist, muss er sich zwangsläufig irgendwann von einem anderen unterscheiden. Wenn wir nun für die Zahlen 0-9 diese Zahlen nehmen, sowie die Buchstaben auch als solche darstellen, wobei ein Buchstaber seiner Zahl, also B=2 entspricht. Diese Zahlen stellen wir nun durch ihren Binärcode da. Jedes mal, wenn ein Binärcode endet, setzen wir die Ziffer 2 für kleine Buchstaben und 3 für große. Für die Zahlen von 0-9 habe ich eine weitere Idee. Jedes mal, wenn eine Ziffernfolge in dem Text auftaucht, wird, solange nur Zahlen stehen, also z.B. 098072934 eine 4 an den Anfang, sowie eine 5 an das Ende der Zahlenfolge gesetzt. In diesem Fall also 40980729345. Der erste Punkt übernimmt die Funktion eines Kommas und wird, so wie es ist, in die Zahlenfolge gesetzt. Danach wird für jeden Punkt bwechselnd eine 6 und eine 7 gesetzt. Für die Leerzeichen wird abwechselnd eine 8 und eine 9 gesetzt.

Etwas besseres fällt mir aber auf Anhieb nicht ein. Ich überlege mir noch mal was.

[MadMac]

Eine solche Zuordnung lässt sich

Mehr ->

trivial finden, auch wenn bei meinem Vorschlag die Wahrscheinlichkeit, mit einem beliebigen Text eine Zahl bestimmter Größe zu treffen, nicht gleichverteilt ist.

Ich zerlege meine reelle Zahl in einen ganzzahligen Anteil (beliebig lang) und die Nachkommastellen (unendlich lang).

Den ganzzahligen Teil stelle ich zur Basis 63 dar, unter Verwendung der Ziffernzeichen A-Z, a-z, 0-9 und _

Dann kommt ein . als Trenner für die Nachkommastellen.

Den Rest stelle ich zur Basis 64 dar, unter Verwendung der Ziffernzeichen A-Z, a-z, 0-9, _ und .

Zweifelsohne ist die Konvertierung reelle-Zahl -> Text eindeutig.

Ebenso ist jedem Text eindeutig (der erste . ist der Trenner) eine reele Zahl zugeordnet.

Gruß,
MadMac

[Enigmemulo]

Danke für den Spoiler, ich war etwas zu schnell ... und habe auch noch einen Flüchtigkeitsfehler eingebaut, der hiermit auch korrigiert ist.

Mehr ->

Da Otmar netterweise 64 Zeichen genommen hat, ist jede Zeichenfolge trivial in eine Bitfolge verwandelbar, ich spreche im Folgenden deshalb nur von Bitfolgen.

Man nehme eine reelle Zahl x und codiere das Vorzeichen im ersten Bit, dann folgt eine Anzahl von Einsen, die dem ganzzahligen Teil von x entspricht, dann eine Null als Komma und dann die übliche Binärdarstellung des Nachkommateils. Damit wird jede Zahl eindeutig in eine Folge umgewandelt, dummerweise gibt es da noch das Problem, dass 0Periode1 dasselbe ist wie 1Periode0, die Darstellung ist umgekehrt also nicht eindeutig. Das Problem betrifft aber nur einen Teil der rationalen Zahlen, wir nehmen das Prinzip also für die Zahlen, die es nicht betrifft.

Für die anderen Zahlen lassen wir im obigen Prinzip die Codierung des Vorzeichens weg und codieren zunächst den Betrag wie gehabt und bei negativen Zahlen wird die Bitfolge invertiert. So steht Periode0 für positive Zahlen und Periode1 für negative. So bekommt jede periodische Bitfolge genau eine rationale Zahl.

Wer gut aufgepasst hat, hat natürlich bemerkt, dass es zwei Folgen gibt, die auf Null abgebildet werden, nämlich die reine Nullfolge und die reine Einsfolge. Hier wird die reine Einsfolge als überzählige in die natürlichen Zahlen gepackt wie der zusätzliche Gast in Hilberts Hotel, d.h. die reine Einsfolge ist die 0, was vorher die 0 war, wird zur 1 usw.

So haben wir eine aus praktischer Sicht völlig bescheuerte Zahlendarstellung, aber sie ist eineindeutig

[Otmar]

Bitte Spoiler, bevor es jemand sieht....

[Neuling]

Bitte Spoiler, bevor es jemand sieht....

Zu spät! - Neuling hat's grad gelesen.

[Otmar]

Der Teufel steckt hier im Detail! Und deshalb freue ich mich um so mehr über die Lösung von Enigmemulo!



Ich hatte die Idee schon woanders gesehen, aber bei dir erstmalig bis zum letzten Detail ausgefeilt. Finde, dass du deine Lösung in sehr verständlich Form einfach zu lesend für uns aufgeschrieben hast.

@gp3050

Mehr ->

Ich hatte nach deiner Antwort noch eine wichtige Ergänzung zugefügt. Sonst wäre das Rätsel zwar relativ einfach gewesen aber wenig hilfreich für die Rahmenhandlung.

@MadMac
Das ist schonmal ein Anfang, wobei ich nicht sicher bin, ob man den noch zu einer Lösung fortführen kann. Ich schreib mal auf, was mir auffiel:

Mehr ->

Du brauchst noch ne Angabe für negative Zahlen. Da sollte was gehen. Aber aufpassen, dass die 0 dann ncht doppelt da ist.

Dann kommt ein . als Trenner für die Nachkommastellen.

Es gibt auch Texte, die gar keinen . enthalten. Die liefern bei dir keine reellen Zahlen, sobald wenigstens ein Ziffernzeichen von Null verschieden ist.

Wenn **** der unendliche Rest des Textes ist und A die Ziffer Null ist, dann werden die Texte AAAB.xyz**** und B.xyz**** in die gleiche Zahl konvertiert. Nenne es mal Problem führender Nullen.

Ein weiters Problem ist, dass Periode Null und die Periode mit der größten Ziffer eine zweideutige Darstellung aller reellen Zahlen mit endlichem Nachkommateil außer 0 erlauben.

Ich selbst hab drei sehr verschiedene Lösungen. Eine davon ist der Lösung von Enigmemulo sehr ähnlich. Das was jene, die ich als Entwurf vorrätig hatte, deshalb kommt sie gleich hier:

Mehr ->

Methode Differenzcodierung

Von einem vorgegebenen Text werden die Zeichen als 6 stellige Binärzahlen darstellt und die 6 Bit Blöcke nebeneinandergeschrieben. Man erhält dann eine erste Bitfolge A = {a(1), a(2)...}

Hat die Bitfolge A nur endlich viele Bits einer Sorte (entweder Nullen oder Einsen), dann wird sie differenzcodiert. D.h. die neue Bitfolge B = {b(1), b(2), ...} entsteht aus b(i) = a(i) - a(i-1), wobei die Subtraktion modulo 2 ist und a(0) = 0 zur obigen Bitfolge A dazugenommen wird. Da es ab einer bestimmten Bitposition in A nur noch Einsen oder nur noch Nullen gibt, endet die Folge B mit unendlich vielen Nullen. Ansonsten, also wenn es in A sowohl Nullen als auch Einsen in unbegrenzter Zahl gibt, dann bleibt b(i) = a(i).

Aus der neuen Bitfolge B könnten wir jederzeit die Folge A zurückrechnen:

Denn genau dann, wenn B mit lauter Nullen endet, ist sie durch Differenzkodierung entstanden und rückwärts rekursiv berechenbar a(i) = b(i) + a(i-1) modulo 2 mit a(0) = 0. Ansonsten sind a(i)=b(i) unverändert. Deshalb ist die Zuordnung zwischen A und B eindeutig, und das obwohl B im Gegensatz zu A nicht alle möglichen Bitfolgen annehmen kann.

Die neue Folge B hat Nullen, sogar unendlich viele. Die erste davon soll B in zwei Teile trennen. Links von dieser Null stehen k Einsen (k= 0, 1, 2, ....) rechts davon eine Folge, die nicht auf lauter Einsen endet. Die rechte Folge wird als Nachkommateil R (0 <= R < 1) einer Binärzahl verwendet. Da R nicht mit Periode 1 endet, ist sowohl R < 1 als auch die Zuordnung der rechten Bitfolge zu R ist eindeutig. Das zu erreichen, war der Grund für die Differenzkodierung.

Aus der Zahl k wird der ganzzahlige Teil G gemacht. Für gerade k sei G = k/2, für ungerade k sei G = -(k+1)/2. Die reelle Zahl X sei X = G + R. Jeder Text macht eine solche Zahl wobei verschiedene Texte verschiedene Zahlen machen.

Umgekehrt geht es auch:

Jede reelle Zahl X lässt sich eindeutig zerlegen in X = G + R (mit 0 <= R < 1) und G ganzzahlig.

Ist G negativ also G < 0, dann wird k = -2G - 1 positiv und ungerade und für G >= 0 ist k = 2G eine gerade Zahl >= 0.

Nun kann man für alle i <= k das Bit b(i) = 1 setzen und wegen k >= 0 kann man b(k+1) = 0 eintragen. R lässt sich eindeutig als binärer Nachkommateil ohne Verwendung von Periode 1 darstellen und in
b(k+2), b(k+3), ... hineinschreiben.

Endet b(k) mit lauter Nullen, dann wird die komplette Folge b(k) rückwärts differnzkodiert: a(i) = b(i) + a(i-1) modulo 2 mit a(0) = 0 und sonst beibehalten. Diese Schritte kehren obige
Zuordnung "Text -> reelle Zahl" um und liefern für jede reelle Zahl X einen Folge A und damit einen Text in eindeutiger Weise.

[Otmar]

Der Vollständigkeit halber noch die beiden anderen Lösungen:

Mehr ->

reguläre Kettenbrüche:

Dazu sei hilfsweise T = {t(1), t(2), ... } = {0, -1, 1, -2, 2, -3, 3, ...} eine abzählbare Anordung der ganzen Zahlen, die weiter unten verwendet wird. A sei die Bitfolge, die sich aus dem Text ergeben hat, so wie bei der ersten Lösung.

Starten wir diesmal mit einer beliebigen reellen Zahl X und behandeln sie wie folgt:

1.) Abspalten des Ganzzahlteils G:

X = G + R mit 0 <= R < 1.

Falls G = 0 und R = 0 sind, wählen wir die Bitfolge A = {0, 0, 0, ...} mit lauter Nullen.

Falls G != 0 ist und R = 0 ist, suchen wir das k, so dass t(k) = G ist. Da t(1) = 0 war, aber G != 0 ist, ist k >= 2. Wir setzen in A nun a(k-1) = 1 und alle anderen Bits gleich Null.

falls R != 0 war, suchen wir das k, so dass t(k) = G. Diesmal ist k >= 1, da G auch 0 sein darf. Wir setzen in A alle Bits auf Null nur das Bit a(k) = 1 und fahren fort:

2.) Kettenbruchschritt:

Da 0 < R < 1 kann Q = 1/R gerechnet werden und es ist Q > 1. Wir zerlegen Q = g + r mit 0 <= r < 1 und g ganzzahlig. Wegen Q > 1 ist g >= 1. Sollte nun r = 0 sein ist sogar g >= 2.

Wenn a(l) das zuletzt gesetzte Bit in A war, sind alle Bits rechts davon noch auf 0.

Falls r = 0, also g >= 2, setzen wir in A noch das Bit a(l+g-1) und sind fertig.
Falls r > 0 war, setzen wir in A das Bit a(l+g) und fahren mit dem nächsten Kettenbruchschritt fort, wobei R = r gesetzt wird.

Für irrationale Zahlen wird das ewig so weiter gehen und für alle rationalen Zahlen irgendwann abbrechen.

Zusammengefasst kann jede Folge A so erzeugt werden. Die Nullfolge für die Zahl 0. Folgen mit einem gesetzten Bit für alle anderen ganzen Zahlen. Alle Folgen mit einer endlichen Anzahl gesetzter Bits aber mindestens 2 gesetzten Bits für rationale Zahlen (ohne ganze Zahlen) und alle anderen Folgen mit unendlich vielen gesetzen Bits sind gehören zu irrationalen Zahlen. Folgen für irrationalen Zahlen können Bits mit Wert 0 in jeder Anzahl haben oder es kann unendlich viele davon geben. Beispielsweise gehört zur Bitfolge aus lauter Einsen die Zahl
X = 0 + 1/(1+1/(1+1/(1+1/(1+1/(1+1/(......))))))
und das ist der Reziprokwert des goldenen Schnitts.

Das mehrdeutige Periodenproblem tritt bei der Kettenbruchzerlegung nicht auf. Meines Wissens ist die Kettenbruchmethode die mathematische Standardlösung für das Problem und wenn ich nicht irre wurde sie von Georg Cantor selbst verwendet.

Mehr ->

Spezielle ganze Zahlen:

A = {a(1), a(2), ....} sei wieder die Bitfolge aus dem Text.

Fall 1: A ist die Nullfolge <----> X = 0
Fall 2: In A ist genau ein Bit gesetzt und zwar sei a(k) = 1 und alle anderen 0. <----> X = -1-k
Fall 3: A ist die Folge aus lauter Einsen <----> X = -1
Fall 4: A hat wenigstens eine 0 und endet mit lauter Einsen:

A wird invertiert. Alle Nullen rechts von der letzten 1 werden weggelassen und dieser Rest wird gespiegelt. Es bleibt dann eine ganze Zahl X >= 1 in üblicher Binärdarstellung stehen (LSB rechts), die dann die reelle Zahl ist.

Fall 1..4 deckt also alle ganzen Zahlen ab.

Fall 5: Ist der Rest. A hat wenigstens 2 Einsen (wegen 1 und 2) und endet nicht in einer Folge aus lauter Einsen (wegen 2 und 3) und hat unendlich viele Nullen.

Die erste Eins trennt A in den binären Nachkommateil R (rechts davon) und eine Folge aus k Nullen links davon. k = 0, 1, 2,....

R < 1, da keine Periode aus Einsen vorliegt. R ist auch eindeutig, da keine Periode aus Einsen vorliegt. R > 0, da rechts von der ersten Eins ja noch mindestens eine zweite kommen muss.

Wenn wir jetzt die abzählbare Anordnung der ganzen Zahlen T von oben ausleihen, ist X=t(k)+R die zugehörige reelle aber nicht ganze Zahl.

Ach so, jetzt kommt die nächste Stunde. Der Lehrer sagt, dass jeder Text über die Bitfolge A auch eine beliebige Teilmenge aus den natürlichen Zahlen festlegt. Dazu werden einfach die natürlichen Zahlen. an denen das Bit gesetzt ist, in die Teilmenge gewählt werden und die anderen nicht. Und nun geht es mit dem Satz von Cantor weiter. Viel Spaß!