Das Kalenderblatt 111111

10/11/2011 - 08:05 von WM | Report spam
Das Kalenderblatt 111111

Eine Bijektion im herkömmlichen Sinne zwischen den Knoten und den
unendlichen Pfaden des Binàren Baums existiert in der Tat nicht -
schon weil unendliche Pfade gar nicht vorhanden sind. Die Ziffernfolge
einer reellen Zahl enthàlt Ziffern nur an natürlichen Indizes. Sie
erstreckt sich aber weiter als alle natürlichen Indizes. Und da omega
keinen Vorgànger besitzt, existieren nicht einmal alle natürlichen
Indizes selbst. In diesem Punkte hatte ich zuweilen fahrlàssig
formuliert, was zu brechtigter Kritik Anlass gab:

Wann entfernen Sie den peinlichen "Beweis", dass es eine Bijektion
zwischen den Knoten und den Pfaden eines vollstàndigen binàren Baums
gàbe? Welche Nummer hat der Pfad 111111111111111111111111111111 in
Ihrer Bijektion?
[Horst Kraemer, "Cantors Diagonalbeweis widerlegt", de.sci.mathematik,
5. 6. 2005]

Um aber die Abschàtzung zu verdeutlichen, griff ich auf eine schon
früher (s. KB111107) erwogene Idee zurück: Ich machte einen Schnitt
(Schulden, nicht Dedekind) und verdoppelte die Knotenanzahl:

Bleiben wir bei der ursprünglich gewàhlten Bezeichnung Pfad statt
Pfadbündel. Es gibt keine ununterscheidbaren Pfade, d.h. zwei
(verschiedene) Pfade unterscheiden sich in mindestens einem Knoten
einer Ebene.
Nun erzeugen wir eine Surjektion der Knoten (Separationsstellen)
auf die Pfade. Dazu wird die Anzahl der Knoten verdoppelt. Ein
Grundelement des Baumes sieht folgendermaßen aus:

|
Ba Bb
/ \

Jedem Pfad, der nach links verzweigt, wird der Knoten Ba zugeordnet,
jedem Pfad, der nach rechts verzweigt, wird der Knoten Bb zugeordnet.
Verzweigt einer der Pfade abermals, so wird seinen Kindern wieder
jeweils ein Knoten der Verzweigungsstelle zugeordnet. Zusammen mit dem
gemeinsamen Knoten von oben tràgt nun jeder Kindpfad 3/2 Knoten.
Verzweigt ein Kindpfad abermals, so wird jedem Enkelpfad wieder
jeweils ein Knoten der Verzweigungsstelle zugeordnet. Zusammen mit dem
Erbe von oben tràgt nun jeder Enkelpfad 7/4 Knoten. Ich behaupte
nicht, daß jeder Pfad immer wieder verzweigt. Ist dieser Fall jedoch
gegeben, dann tràgt jeder der Pfade in der Ebene n mehr als einen und
weniger als 2 Knoten. Das kann leicht berechnet werden, solange die
Knoten durch natürliche Zahlen numeriert werden. Unter 1 kann die
Knotenzahl nie sinken. Daher liegt eine Surjektion der Knoten in die
Pfade vor.
[WM, "B-Baum", de.sci.mathematik, 8. 6. 2005]

Für unendliche Pfade erhàlt man genau 2 Knoten pro Pfad. Werden die
Doppelknoten wieder halbiert, so zeigt auch dieses Argument: Es gibt
genaus so viele Pfade wie Knoten. Wie ich erst viel spàter erfuhr, ist
die Methode bereits seit langem (1949) bekannt (s. KB111025,
Ungleichung von Kraft, hier im Original:
http://dspace.mit.edu/handle/1721.1/12390
).

CC: Der Knoten darf und kann nur auf einen Pfad abgebildet werden,
es unterscheiden sich aber mehrere in diesem Knoten von P. Damit ist
diese Konstruktion nicht eindeutig. Die Wahl eines beliebigen Pfades
wàre möglich, aber es fehlt die Begründung, warum dadurch alle Pfade
erreicht werden sollen.
WM: Meine Konstruktionsvorschrift ereicht aber alle Pfade, da
keiner von einem Pfad, auf den schon ein Knoten abgebildet wurde,
abzweigen kann, ohne daß ein Knoten auf ihn selbst abgebildet wird.
CC: Ich bestàtige gerne, dass Ihre Beschreibung sich als
Konstruktion einer Surjektion auf diese Menge interpretieren làsst.
Nur ist das nicht die Menge der Pfade im Baum - es gibt in dieser
Menge kein einziges einelementiges Pfadbündel.
WM: Macht nichts. Dann brauchen wir darauf auch keinen Knoten
abzubilden.
CC: Wenn in Ihrem Axiomensystem keine Binàrdarstellung von 1/3
existiert, ist das kein Widerspruch innerhalb irgendeines anderen
Axiomensystems.
CC: Es gibt keine Kante in P, die in keinem anderen Pfad auftaucht.
{{Ganz genau so ergeht es der Cantorschen Diagonalzahl. Es gibt keine
Ziffer, die eine abschließende Beurteilung ihrer Abwesenheit in der
Liste ermöglicht. Auch diese Ziffernfolge individualisiert sich
niemals, sondern beschreibt stets ein Intervall.}} Falls Sie das
bestreiten, geben Sie bitte die Kante in dem zur 0 gehörigen Pfad mit
dieser Eigenschaft an. {{Nein, ich bestreite das nicht. Ich bestreite
lediglich, dass man einen Pfad ohne Zielkante definieren,
identifizieren, individualisieren kann, wenn er keine endliche
Definition besitzt.}}
[Christopher Creutzig, "B-Baum", de.sci.mathematik, 11.-14. 6. 2005]

RK: Kannst du bitte eine Regel angeben, *welchem* dieser Pfade der
Knoten A nun zugeordnet wird?
WM: Ich sehe nicht, warum es eine solche Regel geben muß. Denn es
ist bekannt, daß kein Pfad von einem anderen abweichen kann, ohne daß
dies in einem Knoten passiert.
RK: Ich hab die Existenz von 0.001001001... behauptet, das ist 1/7,
wenn ich mich nicht tàusche. 1/7 wird doch wohl noch existieren, oder
nicht? [...] weil aus diesen Bündeln eben niemals (an keiner Stelle n)
ein einzelner Pfad wird, folgt daraus eben keine Surjektion.
[Rade Kutil, "B-Baum", de.sci.mathematik, 13. 6. 2005]

Die Überabzàhlbarkeit nicht existierender Pfade anhand einer
Nummerierung dieser Pfade zu widerlegen, ist wohl ausgeschlossen. So
gesehen war Cantors Trick wirklich eine Meisterleistung.

Gruß, WM
 

Lesen sie die antworten

#1 Michael Klemm
10/11/2011 - 08:08 | Warnen spam
WM wrote:

Eine Bijektion im herkömmlichen Sinne zwischen den Knoten und den
unendlichen Pfaden des Binàren Baums existiert in der Tat nicht -
schon weil unendliche Pfade gar nicht vorhanden sind.



Falsch, die Identitàt auf der leeren Menge ist eine Bijektion.

Gruß
Michael

Ähnliche fragen