Argumente zum binären Baum

17/04/2009 - 18:06 von WM | Report spam
These: Der unendliche binàre Baum besitzt nur abzàhlbar viele Pfade.

0.
/ \
0 1
/ \ / \
0 10 1
...

PRO

A) Konstruieren den binàren Baum beginnend mit einem "Baum", der nur
aus einem einzigen Pfad p_0 = 0.000... 0 besteht:

0,
|
0
|
0
|
0
...

Füge sàmtlich Pfade hinzu, die mit unendlich vielen Nullen enden.
Jeder noch zu konstruierende Pfadendabschnitt beginnt an einem Knoten
des Pfades p_0 oder an einem Knoten eines anderen bereits
konstruierten Pfades. Der Baum ist vollstàndig konstruierbar, da eine
Konstruktionsvorschrift gegeben werden kann. Zum Beispiel
(abschließende Nullen werden unterdrückt)

0,1
0,01
0,11
...

Der auf diese Weise konstruierte Baum enthàlt alle Knoten (es sind
abzàhlbar viele). Jeder Knoten wurde bei der Konstruktion benutzt, um
einen Pfadendabschnitt anzubringen. Der Baum enthàlt also abzàhlbar
viele Pfade. Der Baum enthàlt alle Pfade, wenn man davon ausgehen
kann, dass Pfade allein durch Knoten definiert werden. Zum Beispiel
ist jeder Knoten des Pfades 0,010101... vorhanden.


B) Der binàre Baum besteht ausschließlich aus Elementarzellen der Form

|
o
/ \

(außer der Wurzel). In jede Elementarzelle làuft eine Linie ein und
zwei unterscheidbare Linien laufen heraus.
Die Anzahl der herauslaufenden Linien minus Anzahl der einlaufenden
Linien minus Anzahl der Knoten ist:
2 - 1 - 1 = 0.
Die Anzahl der Knoten ist abzàhlbar. Die Anzahl der Linien ist daher
auch abzàhlbar, wenn sie nicht größer als die der Knoten ist, wenn
also die Summe über alle Elementarzellen
SUM[n = 1 --> oo] 0 = 0
oder wenigstens
SUM[n = 1 --> oo] 0 =< aleph_0
ist.
Die Anzahl der Linienunterscheidungen ist abzàhlbar.
Die Anzahl der Linien beschrànkt die Anzahl der Pfade.

C) Betrachte alle Knoten nebeneinander aufgereiht. Diese Reihe
begrenzt die Anzahl unterscheidbarer Pfade auf aleph_0. Es gibt keinen
weiteren Knoten zur Unterscheidung weiterer Pfade.

CONTRA

V. Pratt:
http://www.cs.nyu.edu/pipermail/fom...13493.html

Im finiten Fall eines Baums der Höhe h laufen durch jeden Knoten, der
den Abstand d vom Wurzelknoten besitzt, 2^(h-d) Pfade. Mit
zunehmendem h laufen durch jeden Knoten in eine exponentiell
ansteigende Anzahl von Pfaden. Im Grenzfall sind das 2^N Pfade pro
Knoten. Man mag argumentieren, dass auch die Anzahl der Knoten sich
mit jedem Niveau verdoppelt. So haben wir zu fragen, ob dieses
Wachstum der Knotenanzahl stark genug ist, die Anzahl der durch einen
Knoten laufenden Pfade zu aufzuwiegen. Im Grenzfall ist jeder Pfad auf
N Knoten verteilt, aber das làsst 2^N/N Pfade pro Knoten, und das kann
nicht N sein, weil N^2 abzàhlbar ist und 2^N nicht.
_______________________________________
Man kann mit drei Knoten 6 unterscheidbare Pfade bilden, nàmlich abc,
acb, bac, bca, cab, cba. Doch dazu muss man die Knoten geschickt
kombinieren. Im binàren Baum ist das nicht möglich. n unterscheidbare
Pfade unterscheiden sich durch mindestens n Knoten. aleph_1 Pfade kann
man nicht mit alep_0 Knoten unterscheiden.
_________________________________________

V. Pratt:
http://www.cs.nyu.edu/pipermail/fom...13493.html

Für Bàume der Höhe h finden wir eine Kardinalitàtslücke, nàmlich 2^h -
1 Knoten gegenüber 2^h Pfaden. Warum sollte der Übergang zum Grenzfall
diese Lücke schließen?
_______________________________________
Dann lassen wir den Baum doch mit einem Vorwurzelknoten beginnen:
o
|
o
/ \
...
und schon ist die Lücke weg. Ansonsten, gutes Argument: Warum sollte
beim Übergang zum Grenzfall eine Lücke entstehen, wenn vorher keine da
ist?
___________________________________________

D.C. Ullrich
http://groups.google.com/group/sci....ing=d&

Du sagst immer wieder:

"Diese Prozedur, selbst wenn unendlich oft angewandt, kann nur das
Resultat 0 ergeben, das heißt eine abzàhlbare Anzahl von Linien.

aber das ist einfach nicht wahr.
_______________________________________
Dies bezieht sich auf Argument B, das in meinen Augen ein àußerst
mathematisches ist. Die Akzeptanz einer überabzàhlbaren Anzahl von
Pfaden erfordert demnach die Akzeptanz von
SUM[n = 1 --> oo] 0 > aleph_0
_________________________________________

Virgil
http://groups.google.com/group/sci....ing=d&
Du behauptest durch das Konstruieren von unendlich vielen Pfaden mit
nur endlich vielen Einsen pro Pfad alle Pfad konstruiert zu haben,
auch die mit unendlich vielen Einsen. Das ist falsch.
__________________________________________
Welcher Pfad fehlt denn im nach A oder B konstruierten Baum?
_____________________________________________
Calvin Ostrum
http://groups.google.com/group/sci....ing=d&

[Wenn der Baum nach Beendigiung der Konstruktion alle Knoten enthàlt,
dann enthàlt er auch alle Pfade.]

Richtig. Du hast explizit nur eine abzàhlbare Anzahl von Pfaden
hinzugefügt, aber eine überabzàhlbare Anzahl haben sich am Ende
eingeschlichen, weil von jedem der klàglich abzàhlbar vielen explizit
eingefügten eine Kante [Verbindung zwischen zwei Knoten] beigetragen
hat.
______________________________________________
Eine überabzàhlbare Menge unterschiedlicher Pfade kann durch abzàhlbar
viele Schritte entstehen?
___________________________________________

So viel zu den Argumenten für und gegen den binàren Baum. Es tut mir
wirklich Leid, dass ich kein einziges (für mich) nachvollziehbares
Gegenargument bringen konnte. Ich habe noch keines gesehen, würde mich
aber freuen, wenn eines kàme.

Das Hauptargument, das alle Mengenlehrer überzeugt, there are 2^N
paths and N nodes weil das aus Cantors Beweis folgt, ist für mich
nicht stichhaltig, weil 1) Cantors Beweis keiner ist, wenn man
zwischen potentiell und aktual unendlich unterscheiden kann, und weil
2) selbst wenn Cantors Argument richtig wàre, die Logik auf
unendlichen Mengen (offenbar) versagt.

"... classical logic was abstracted from the mathematics of finite
sets and their subsets Forgetful of this limited origin, one
afterwards mistook that logic for something above and prior to all
mathematics, and finally applied it, without justification, to the
mathematics of infinite sets. ... As Brouwer pointed out this is a
fallacy, the Fall and Original sin of set theory even if no paradoxes
result from it." [Hermann Weyl]

Gruß, WM
 

Lesen sie die antworten

#1 Thomas Plehn
17/04/2009 - 19:51 | Warnen spam
Hallo,

ist das nicht àquivalent zu der Aussage, dass es nur abzàhlbar viele reelle
Zahlen gàbe? Ich denke die Lehrmeinung ist hier allgemein bekannt
(Cantorsches Diagonalargument), dennoch fàllt es mir schwer zu erkennen,
welche Argumentationen fehlerhaft sind und welche nicht und werde deshalb
auf die Urteilskraft von professionellen Mathematikern vertrauen.

Gruß
Thomas

"WM" schrieb im Newsbeitrag
news:
These: Der unendliche binàre Baum besitzt nur abzàhlbar viele Pfade.

0.
/ \
0 1
/ \ / \
0 10 1
...

PRO

Ähnliche fragen