Gibt es einen Beweis für die Collatz-Vermutung ("3n+1-Problem")? Ist es überhaupt möglich, einen solchen Beweis zu führen, und falls ja, wie sähe er wohl aus?
Ich selbst bin fanatischer Anhänger der 1977 von ===> Edward Nelson entwickelten ===> Nonstandard Analysis ( NSA ; IST ) Lehrbuch von ===> Alain Robert, erschienen bei Wiley; neueste Ausgabe bei Amazon. Für ein seriöses Mathe Lehrbuch bringt Robert eine Menge witziger Karikaturen …
" I have to admit there are Nonstandard black holes … "
Nelson selber hat immer wieder betont, dass selbst die genialsten Mathematiker seine Syntax zu stammeln anfangen wie kleine Kinder ihre Muttersprache ( Das soll aber nicht heißen, dass es sich nicht lohne, sprechen zu lernen. )
Ich kann ihm da nur Recht geben; sein Original Paper ist die wohl einzige Veröffentlichung, die es unternimmt, den häufigsten Denkfehlern und Missverständnissen des Lesers entgegen zu treten. Z.B. ein Schweizer Prof führte im Telefongespräch mit mir aus, er habe Gerüchte weise vernommen, die Nelsontheorie sehe Mengen wie |N und |R als endlich an. als ich ihm heftig widersprach, meinte er entschuldigend, das sei ja nur ein Gerücht …
Du magst hieraus ganz deutlich ersehen, dass alle immer auf den armen Nelson einprügeln, ohne wirklich Ahnung zu haben.
Einmal präsentierte ich in einem Forum den Schattensatz; da geht es um eine ganz bestimmte eindeutige Zerlegung. Man kommt aus dem Staunen einfach nicht heraus; bumms hatte ich schon wieder einen Kommentar
" Wieso? Wenn ich ein x gegeben habe, dann gibt es doch unendlich viele Zerlegungen x = y + z … " Das ist das, was ich meine. Es scheint furchtbar schwer zu sein zuzuhören.
Könnte ja sein, dass du noch nie davon gehört hast. Oder du bedarfst noch Nachhilfe; dann bin ich mit Vergnügen dein Nachhilfelehrer.
Nelson ist ja stolz wie Oskar, dass er den Begriff des Inf(initesimalen) rehabilitiert hat, von dem noch das ( leider fossile ) Fischerlexikon bemerkte
" Inf hat in der Analysis nichts zu suchen, weil sich dieser Begriff nicht Sinn voll axiomatisieren lässt. "
Ich entstamme ja einem Welt_Elektronikkonzern; mein Chef kannte den zynischen Spruch
" Wollen Sie damit gesagt haben, dass man es nicht kann oder nur, dass Sie es nicht können? "
In Hörfunkbeiträgen wird ja immer wieder der Verdacht geäußert, die ===> Goldbachvermutung könne sich eines Tages als unentscheidbar im ===> Gödelschen Sinne heraus stellen. Für derlei Befürchtungen habe ich nur ein müdes Grinsen übrig … Und urplötzlich kommt Nelsons Theorie ein eminentes Gewicht zu in der Zahlentheorie. Nelson selber beruft sich ja immer auf den Witz
" Der kürzeste Umweg zur reellen Analysis führt immer noch über die komplexe Ebene … "
Analog nämlich führt die Einführung des Prädikats " Standard " Vereinfachungen herbei. Mit Collatz habe ich übrigens lange gehadert; hier liegen die Dinge doch etwas komplizierter.
Gödel sagt ja, ein Beweis sei ein Assemblerprogramm, das auf einer CPU läuft und das, beginnend bei den Voraussetzungen so wie Axiomen und anerkannten Theoremen, auf Stop geht und ausdruckt, die Behauptung ist bewiesen bzw. widerlegt. Nur sollte man auch sehen; nicht jedes Programm ist kompatibel mit jeder Wortlänge. Auf der anderen Seite empfiehlt es sich nicht zu behaupten, bestimmte Beweise seien undurchführbar bloß weil die erforderlichen Prozessoren niemals gefertigt werden. Wenn |N wirklich eine unendl. Menge ist, dann gibt es zu Mindest ideell zu jedem noch so großen n0 einen Prozessor, desse größte darsellbare Zahl n0 ist. Auch dann noch, wenn n0 Nonstandard. Und auf einem solchen Nonstandardrechner schreibe ich dir ganz fix ein Programm, welches den Collatz für jedes konkrete ( Standard ) n entscheidet. Meine Antwort, siehe Radio Eriwan; " Im Prinzip ja "
PROGRAMM Einzel_Wert
INPUT , " Welche Zahl ist genehm? _ " , n
co_laz := n
FOR index = 1 TO n0
IF co_laz MOD 2 = 0 THEN
co_laz := co_laz/2
ELSE IF co_laz = 1 THEN
STOP " Kollatz bewiesen nach " , index , " Schritten "
ELSE
co_laz := 3 * co_laz + 1
ON_ERROR = OVERFLOW THEN EXIT_LOOP
END_IF
NEXT index
PRINT " Herzlichen Glückwunsch zum Hauptgewinn; Sie haben soeben eine Zahl geraten, die den guten Onkel Collatz tief kränkt … "
Beweis nach endlich vielen Schritten? Wie kann das sein? Dahinter steht das Transferaxiom, das " T " in Nelsons " IST " und bei Weitem das wichtigste seiner drei Axiome.
" Wenn ein Standardproblem überhaupt eine Lösung hat, so immer auch eine Standardlösung. "
Genau so, wie man Vektoren immer z.B. durch Fettdruck kennzeichnet, wollen wir in Zukunft alle Variablen fett drucken, deren Wertebereich auf Standard eingeschränkt ist. Genau den Transferschluss, der meinem Programm zu Grunde liegt, will ich jetzt formalisieren. Collatz ist doch weiter nichts als eine ( endliche oder unendliche ) Folge < c >_ n ( wobei n dein Seed, deine Inputzahl sein soll. )
(E) c | < c > = < c >_ n ===> (E) c | < c > = < c >_ n ( 1 )
In ( 1 ) ist c der Transferparameter; wir wollen beweisen, dass c Standard. Transfer ist immer der Schluss von Allgemein auf Standard. In den Ausdruck geht aber als zusätzlicher freier Parameter ( ZFP ) dieses n ein; in unserem Programm hatten wir uns bewusst auf Standard n beschränkt. Diese Forderung an den / die ZFP ist hinreichend, aber nicht notwendig für den korrekten Transferschluss.
Der große Streitpunkt hinter Mc Collatz ist doch; ist c^ - 1 endlich oder unendlich? Auch c ^ -1 ist Standard; das folgt diesmal durch trivialen Transfer. Du hast aber gelernt:
" Eine Menge besteht ausschließlich aus Standardelementen <===> Sie ist Standard endlich. "
Dann muss der größte Wert von index, für den sie mit c ( index ) = 1 abbricht, auch Standard sein. Das selbe ließe sich noch einfacher sagen. Aus Transfer folgt: Das Maximum einer Standardmenge ist selbst wieder Standard. In jedem Falle erreichst du die Abbruchbed. noch für einen " manierlichen " Standardwert von index.
Natürlich macht die Kurve c ( index ) beliebig viele Ausreißer und Überschwinger; so lange aber noch etwas zu erwarten bleibt, bleiben auch die Standard. Berühmtes Lemma
y = f ( x ) ist Standard ( 2 )
Die Errorbed. habe ich nur aufgenommen, um dem Fall co_laz > n0 vorzubeugen.
Erster Einwand; n0 liegt jenseits des " Ereignishorizontes " Derartige Maschinen können wir nie bauen. Doch hier rettet uns Transfer. Sei P ( n ) das programm, das Collatz ( n ) entscheidet:
(E) P ( n ) ===> (E) P ( n ) ( 3a )
In ( 3a ) machen wir den Transfer über das Programm P . Und dann betrachten wir L , die Anzahl Assemblerschritte in dem Coding von P .
(E) L ( P ) ===> (E) L ( P ) ( 3b )
Und unter allen Codings muss es schließlich das eindeutig kürzeste geben; wir sind jetzt also schon so weit, dass wir Einzelabfragen der Form Collatz ( 4 711 ) , Collatz ( Wow ) oder Collatz ( Turm ) beantworten können. Irgendein schlauer Bursche schrieb hier mal, Gödel erlaube eine Abschätzung, wie groß ein Programm mindestens sein muss, das eine bestimmte Aufgabe bewältigt. Was ich suche, sind natürlich obere Schranken über seinen Komplexitätsgrad. Es ist mal wie immer in der Mathematik; ich vermag nur mit einer Existenzaussage zu dienen. Konkrete Angaben sind mir nicht bekannt.
Aber eigentlich sind wir ja auf etwas ganz anderes aus. Wir haben gezeigt, dass wir die Frage für alle Standard n beantworten können. Das schreit doch förmlich nach Transfer. Das obige Programm Einzel_Wert kürze ich ab als P
(E) P (V) n | P ( n ) ===> ( 4a )
( ? ) ===> (V) n | P ( n ) ( 4b )
( 4b ) ist aber offensichtlich falsch. Eine solche obere Schranke wie n0 existiert ja für Collatz gerade nicht. What is sere loose? Das ist ein schönes Beispiel für verbotenen Transfer. Die beiden Quantoren können wir doch wie zwei Schleifen ansehen; der Existenzquantor bildet die äußere Schleife mit P als Parameter so wie der Allquantor die innere mit n . Der Transfer geht über den Parameter der inneren Schleife; und vom Standpunkt der inneren Schleife aus gesehen ist P ein ZFP . Diesmal ist P aber nicht Standard. Widerspruchsbeweis durch Transfer; wäre P ein Standardprogramm, so würde folgen n0 = Standard.
Oder stell es dir so vor; der Allquantor konstituiert ein Unterprogramm; und der Parameter P wird diesem übergeben. Übergabeparameter sind freie Parameter. Ein beliebter Test; unter der inneren Schleife sagst du z.B. Q statt P :
(E) P (V) n | Q ( n ) ( 4c )
( 4c ) ist deshalb unsinnig, weil P und Q individuelle Namen sind
" Was ist bitte Q , und in welchem Verhältnis steht es zu P? "
Drehen wir doch einfach die Reihenfolge der Quantoren um; das Wort Transfer kam ja daher, dass es sich um die Übertragung von Standard auf Allgemein handelt:
(V) n (E) P = P ( n ) ===> (V) n (E) ( … ) ( 5a )
Stellen wir uns zwei ineinander geschachtelte Schleifen in einem Programm vor. P ist ein bloß lokaler Parameter der inneren Schleife, der in der äußeren gar nicht mehr definiert ist; der Transfer erstreckt sich über die gesamte innere Schleife ( und nicht nur deren Inhalt wie in ( 4a ) ) P als funktion von n ist diesmal ein gebundener Parameter; die Werte gebundener Parameter intressieren für Transfer gar nicht. Der Test auf gebundene Parameter ist immer, dass du statt P genau so gut etwas anderes sagen kannst, z.b. Q
(V) n (E) Q = Q ( n ) ( 5b )
P ist nicht der Name von irgendetwas; das sieht man gerade daran, dass man diese Variable auswechseln kann.
Bei Lichte besehen ist ja ( 5a ) was wir erwartet haben. Wir sind ausgegangen von einem Programm, welches individuelle n eingelesen und gelöst hat. Und jetzt haben wir eben die Verallgemeinerung, dass es für beliebige, auch Nonstandard n so ein Programm gibt.
Noch einmal müssen wir in die Trickkiste greifen; jene Subroutine, die individuell für jedes n entscheidet, ob Collatz ( n ) wahr ist oder nicht, möge Co_latz heißen. Und wenn wir eben wissen wollen, ob Collatz für alle Zahlen gilt; du ahnst es sicher schon
PROGRAMM Alle_Werte
FOR index = 1 TO n0
IF NOT Co_laz ( index ) THEN
STOP " Hurra !!! Collatz widerlegt für n = " , index
END_IF
NEXT index
PRINT " Erwartungsgemäß gilt Collatz für alle Zahlen "
Jetzt habe ich aber noch ein ganz spezielles Anliegen. Nur falls du selber auf die Idee kommen solltest. Könnte man nicht das obige HP " Einzel_Wert " zur Subroutine abspecken? Alle Stop_und Printanweisungen nimmst du quasi heraus und ersetzt sie durch Return. Ich stelle mir das jetzt so vor:
PROGRAMM Break
index = 1
DO WHILE Stan_dard ( index )
CALL Einzel_Wert ( index; co_laz )
IF co_laz > 1 THEN
STOP " Äätsch bäätsch; Colatz widerlegt für n = " , index
END_IF
index = index + 1
END_DO
PRINT " Colatz bewiesen
Warum so etwas nicht funktioniert? als Beispiel für nicht berechenbare Aufgabenstellungen findest du in dem Kultbuch " GEB " von ===> Douglas Hofstädter den fleißigen Biber, eine der Art selbstkinsistente verschnörkelte Aufgabe, dass ich sie mir einfach nicbt einzhuprägen vermochte. Wie immer geht in der NSA alles ganz einfach. Es gibt keine Subroutine, die entscheidet, ob eine ( beliebige ) Zahl Standard ist.
PROGRAMM Gödel
index = 1
DO WHILE Stan_dard ( index )
index = index + 1
END_DO
PRINT " Die kleinste Nonstandardzahl ist " , index
Bekanntlich gibt es keine kleinste Nonstandardzahl. Deshalb kann es keine derartige Abfrage geben.
In Wiki fand ich dazu übrigens eine hoch spannende theoretische Erwägung; schau mal unter dem Stichwort ===> transfinite Induktion.
Den Induktionsbeweis stellt man sich immer als eine Kettenreaktion von unendlich vielen Dominosteinen vor, die einer nach dem anderen umfallen; im ZDF Studio haben die das echt mal aufgebaut. Erinnern wir uns doch an Gödel, dann gibt es keine unendlichen Beweise. Wenn wir uns vergegenwärtigen, was wir effektiv tun, so enthält ein Induktionsbeweis genau wie jeder andere Beweis nur ein endliches Coding.
Wiki sagt aber jetzt, jenes geschraubt klingende fünfte Peanoaxiom ist äquivalent zu der Aussage: ( |N , < ) ist wohl geordnet.
Meine Nomenklatur; die ( nicht leeren ) Teilmengen U von |N bezeichne ich als dessen Urnen und die Elemente k € U als ihre Kugeln. Dann heißt " wohl geordnet " :
" Jede Urne enthält eine ( eindeutige ) niedrigste oder kleinste Kugel. "
An sich ist das auch sehr abstrakt; denn es stellt ein Urteil dar über ( überabzählbar ) viele Urnen. Wer weiß schon so genau, was im Reich der Riesenzahlen gilt? Aber es gilt allemal plausibler als das Gesetz der Induktion.
Und jetzt beweise ich dir die Induktion über die Wohlordnung. Angenommen für das Prädikat P hast du den Induktionsbeweis erbracht
(V) n | P ( n ) ===> P ( n + 1 ) ( 6a )
Widerspruchsbeweis; angenommen es gebe doch eine Urne G , " G " wie Gegenbeispiele. Wegen der Wohlordnung besitzt G ein kleinstes n0
P ( n0 - 1 ) ^ nicht P ( n0 ) ( 6b )
Wegen ( 6a ) muss aber gelten
P ( n0 - 1 ) ===> P ( n0 ) ; Widerspruch ( 6c )
Ich erwähne dies, weil ja die Nonstandard Zahlen gerade kein kleinstes besitzen, wie wir obeb gesehen haben.
n Nonstandard ===> n - 1 Nonstandard ( 6d )
Man redet sich da immer raus, so etwas wie die " Menge " der Nonstandard Zahlen gibt es nicht. Vom Standpunkt Alfred Tarskis ist die Nelsontheorie aus Sicht der ZFC eine Metasprache; wäre Standard eiin Mengen bildendes Prädikat, so wäre ja auf dem Niveau der ZFC entscheidbar, ob es das prädikat Standard gibt oder nicht.