Ich danke der ÖMG dafür, daß sie mich eingeladen hat, über meine Forschung vorzutragen. Ich möchte dieses vorgegebene Thema aber ein bißchen abändern und auch Resultate von anderen erwähnen, und gleichzeitig auch die Gelegenheit ergreifen, über ein Thema zu sprechen, das mir sehr am Herzen liegt, nämlich die Lage der Logik innerhald der Mathematik.
Leider habe ich die Erfahrung gemacht, daß die Logik oft als ein Gebiet angesehen wird, das erstens außerhalb der eigentlichen Mathematik liegt, und zweitens ihr Sinn hauptsächlich im Philosophieren über das ausgeschlosse Dritte liegt, oder daß das Wesen der Logik darin besteht, mit möglichst formalistischen Ableitungen Dingen zu beweisen, die bereits aus dem gesunden Menschenverstand folgen.
Diese Einstellung ist nicht neu, ich habe da ein Zitat ausgegraben, das schon etwa 200 Jahre alt ist,
und wahrscheinlich kann man auch noch älteres finden.
[Die eingestreuten hyperlinks sind Verweise auf die Overheadfolien, die ich während des Vortrags verwendet habe. Je nach Inhalt sind sie als Textfiles, html-files, oder dvi/postscript verfügbar. Alle Overheadfolien sind auch zusammen in
Format verfügbar.)Wenn ich im Folgenden von ``Logik'' spreche, meine ich das immer als Abkürzung für ``Mathematische Logik''. Ich brauche mich also von diesem Goethe-Zitat nicht angesprochen fühlen, weil es ja nur von Philosophen handelt.
Ich habe dann noch ein jüngeres Zitat, auch schon 100 Jahre alt, von einem Mathematiklehrer:
Wie gesagt, im Folgenden ist ``Logik'' Abkürzung für mathematische Logik. Was Mathematische Logik genau ist, möchte ich hier nicht defineren -- als erste Approximation können wir sagen, mathematische Logik ist das, was im Zentralblatt oder in den math Reviews unter ``03'' geführt wird:
Eine mögliche Definition der Logik
Die Beispiele, die ich bringen werde, sind all aus dem Gebiet der Mengenlehre, 03E -- das hat keinen tiefen philosophischen Sinn, sondern liegt daran, daß der größte Teil meiner mathematischen Arbeit eben diesem Gebiet zuzuordnen ist.)
Die Mengenlehre wird ja leider schon in der Schule sehr stiefmütterlich behandelt -- also vielleicht ist das ja jetzt anders, aber zu meiner Zeit, ich bin Maturajahrgang 1981, bestand Mengenlehre in der Schule darin, zusätzlich zu ``x=3'' eben auch noch die Lösungsmenge anzugeben: ``L={3}''
Sie wissen natürlich, daß Mengenlehre viel mehr ist...
Wie schon im Titel angedeutet, möchte ich mich mit dem Verhältnis zwischen Logik und dem Rest der Mathematik befassen. Der Titel faßt eine Einstellung zusammen, die ich bei vielen Mathematikern, auch Logikern angetroffen habe, nämlich die, daß Logik irgendwie außerhalb der ``normalen'' Mathematik steht. Jetzt möchte ich mich selbst aber nicht als ``abnormalen'' Mathematiker bezeichnen, daher muß ich den Titel es Vortrags ändern:
``Naiv'' nenne ich die Mathematik außerhalb der Logik deshalb, weil sie nicht (wie die Logik es tut) über sich selbst reflektiert -- ihre Definitionen und Sätze befassen sich zum Beispiel mit Funktionen oder Vektorräumen oder irgendwelchen anderen Objekten und Strukturen, aber nicht mit Sätzen und Definitionen selbst.
Keinesfalls möchte ich hier mißerstanden werden, und ich möchte ``naiv'' nicht als Herabsetzung verstehen. Beachten Sie, daß ich nur von naiver Mathematik spreche, und nicht irgendwelchen Mathematikern unterstelle, naiv zu sein. (Obwohl es solche natürlich gibt)
Ich möchte also in meinem Vortrag ein paar Beispiele für Wechselwirkungen zwischen Logik und ``naiver''Mathematik bringen, mit dem Ziel, sie zu überzeugen, daß es eigentlich keine klare Grenze gibt, weil insbesondere logische Methoden und Resultate auf ganz naive Fragestellungen anwendbar sind.
Ich werde drei Beispiele bringen. Im ersten (welches nicht von mir ist) wird ein Satz aus der naiven Mathematik durch einen Satz movitivert, der aus der Logik kommt, im zweiten und dritten beantwortet die Logik -- zumindest teilweise -- eine Frage aus der naiven Mathematik, bzw weist darauf hin, wie man die Frage besser stellen könnte.
Um ihnen die Übersicht zu erleichtern, werde ich auf den folgenden Folien Farben verwenden -- mit grün kennzeichne ich Abschnitte aus der naiven Mathematik, mit rot den ``logischen'' Teil, aber gegen Ende werden die beiden Farben ineinanderschwimmen.
b(P) := min{ #A : A Teilmenge von P, A unbeschränkt in P}
Dieses Symbol #A bedeutet ``Kardinalität'' von A. Sie kennen sicher alle diesen grundlegeneden Begriff aus der Mengenlehre -- zwei Mengen haben die gleiche Kardinalität, wir sagen auch: ``sind gleichmächtig'', wenn es eine Bijektion zwischen ihnen gibt. Eine Menge A ist mächtiger als eine Menge B, wenn sich B in A injektiv einbetten läßt, und strikt mächtiger, wenn zwar A mächtiger als B ist, aber nicht umgekehrt.
Das ergibt eine Quasihalbordung zwischen allen Mengen, und man kann zeigen, daß man nach Ausfaktorisieren der Gleichmächtigkeit sogar eine Wohlordung bekommt, also eine lineeare Ordnung, in der jede nichtleere Teilmenge ein kleinstes Element hat. All dies sage ich nur deshalb, um dieses ``min'' zu rechtfertigen.
Machen wir gleich ein nichttriviales Beispiel:
Folie zur Maß und Kategorie, Teil 1:
b(N) is die Antwort auf die Frage: Wieviele Nullmengen muß man vereinigen, um eine Menge von positivem äußeren Maß zu bekommen?
Offensichtlich ist aleph_0 < b(N) , und b(N) ist höchstens gleich der Kardinalität des Kontinuums, 2^{aleph_0}.
Die Frage nach der Größe von Kardinalität b(N) möchte ich zumindest für die Dauer dieses Vortrags der Logik, genauer der Mengenlehre zuordnen.
[[Formal würde ich den Begriff der Kardinalität der naiven Mathematik zuordnen, aber ``soziologisch'' gehört er (meiner Meinung nach da nicht hinein -- aber ich kenne genügend viele Mathematiker, für die Kardinalitat bei
endlich, abzaehlbar ueberabzählbar
aufhoert. ]]
b(M) ist natürlich auch überabzählbar.
Wiederum entstammt M der naiven Mathematik, und b(M) eher nicht.
Eine typisch mengentheoretische Fragestellung ist nun die folgende:
Es wäre aber nicht nur unfair, sondern auch ein Fehler, wie ich im im folgenden demonstrieren möchte.
In den frühen 80ern hat nun Bartoszynski den folgenden Satz bewiesen:
b(N) <= b(M)
[also: ``b(N) ist höchstens gleich b(M)'']
So weit, so logisch. Was hat das mit naiver Mathematik zu tun?
Folie zur Maß und Kategorie, Teil 2:
Ein trivialer Fall ist, der, daß P ein Faktor von Q ist. Wenn Q von der Form P * R ist, dann ist natürlich b(P) <= b(Q), weil jede unbeschränkte Menge in P sofort eine unbeschränkte Menge in Q liefert.
Wie funktioniert das? Es gibt eine Abbildung e (``Einbettung''), die P in Q abbildet, und jede unbeschränkte Mengen von P auf eine unbeschränkte Menge von Q abbildet. Wenn A Teilmenge von P , und e[A] in Q durch ein q beschränkt ist, dann ist gibt es pi(q) (``Projektion''), welches A beschränkt. Dadurch motiviert, defineren wir folgendes:
Seien (P,< ) und (Q,<) Halbordnungen. P < Q bedeutet:
Es gibt Funktionen e, pi:
e: P -> Q
P <- Q: pi
sodaß gilt:
Wenn e(p) <= q , dann p <= \pi(q).
Natürlich gilt: Wenn P < Q, dann b(P) <= b(Q).
N < M
und die Funktionen e und pi sind kanonisch definierbar.
Der Beweis ist einfach eine Übersetzung des Satzes von Bartoszynski.
Mit anderen Worten: Eine Methode, die ursprünglich in der mathematischen Logik angewendet wurde, hat sich als naiv anwendbar entpuppt.
Unter andrem lernen wir auch folgende Lektion: Wenn wir einfach die Kontinuumshypothese als normal angenommen hätten, hätten wir nie das Resultat von Bartoszynski und vielleicht auch nicht das von Fremlin bekommen. Also:
Warnung des Vortragenden:
Die Anwendung der
Kontinuumshypothese
kann das Erkennen von Zusammenhängen
behindern!
Folie zur Verbandstheorie:
p(x,y) = ((x + a) . b) + (x + y)
ein Polynom.
Es ist eine grundlegende Frage in der universellen Algebra, das Verhalten von Polynomen zu verstehen. Wenn der Verband zum Beispiel distributiv ist, dann können wir Polynome in einer Art Normalform darstellen, so wie über kommutativen Ringen.
Gibt es solche Verbände? Im Endlichen ja, und diese sind auch gut untersucht.
Es bleibt also noch die folgende Frage:
Die naive Mathematik hat bisher kein Ergebnis geliefert. Das ist natürlich eine Untertreibung, es gibt viele Resultate, die alle sagen: Wenn ein Verband so-und-so ist, dann ist er nicht o.p.c. Zum Beispiel können Sie sich zu Fuß überlegen, daß etwa eine lineare Ordnung sicher nicht opc ist, weil die Polynome alle ganz triviale Operationen sind. Allgemeiner kann man zeigen, daß ein opc Verband einfach sein muß, also keine nichttrivialen homomorphen Bilder haben darf, insbesondere nicht distributiv, etc.
Ich möchte hierfür den Begriff des Logikers als ``Bitspalters'' prägen, weil ich hier sozusagen ein Bit an Information noch einmal in zwei Teile aufgespalten habe. Sie können das entweder als mächtiges Werkzeug, wie die Atomspaltung sehen, oder, wenn es Ihnen nicht gefällt, als Variation des Haarspalters.
Sie denken jetzt vielleicht, daß so eine Spaltung unsinnig ist, denn wenn man die eine Frage mit ``ja'' beantworten kann, dann ist die Antwort auf die andere natürlich ``nein''. Die Umkehrung gilt aber nicht --- es ist durchaus vorstellbar, daß die Antwort auf beide Fragen ``nein'' ist.
Man kann nämlich zeigen, daß die Kardinalität eines unendlichen opc Verbandes eine unerrreichbare Kardinalzahl sein muß. Aus der Existenz eine so großen Kardinalzahl folgt aber die Widerspruchsfreiheit der üblichen Mengenlehre, und seit Gödel wissen wir, daß sich diese nicht in der üblichen Mengenlehre beweisen läßt.
Ich habe über dieses Resultat bei eine Algebra-Konferenz vorgetragen, und habe naiverweise --- sie sehen, auch ein Logiker kann naiv sein -- ich habe also erwartet, daß die Algebraiker aufschrecken werden und sagen: ``Aha, wir werden jetzt also alle Mengenlehre lernen, weil wir das für Probleme in der Algebra brauchen.'' Statt dessen hat man mir gesagt: ``Na ja, die Sache ist für uns erledigt, jetzt ist es Ihr Problem...''
Das war nun insofern kein gutes Beispiel, weil ja hier die Logik zwar einen Fortschritt, aber keine Lösung geliefert hat.
Über Gleichverteilung haben Sie ja vielleicht schon einiges in anderen Vorträgen gehört, aber ich möchte noch einmal die wichtisten Definitionen bringen:
Es ging um folgendes Problem: Sie wissen vielleicht, was eine ``normale'' Zahl ist: Das ist eine reelle Zahl, in deren Dezimaldarstellung nicht nur alle Ziffern in gewissem Sinn ``gleich oft'' vorkommen, sondern auch alle Ziffernpaare, alle Zifferntripel, etc. Ich spreche im Folgenden nur von Normalität zur Basis 10.
Formal macht man das so:
1. Folie zur Gleichverteilung:
Nachdem wir uns sowieso nur für die Nachkommastellen interessieren, ersetzen wir eine Zahl einfach durch eine unendliche Ziffernfolge, und statt ``normal'' sagt man dann üblicherweise ``gleichverteilt''.
Ich arbeite hier mit der Basis 10, wenn es Ihnen lieber ist, können sie alles durch die Basis 2 ersetzen.
Sie sehen hier auf dieser Folie die Definition der Gleichverteilung -- man schaut sich die ersten N Elemente der Folge an, jede Ziffer sollte ungefähr N Zehntel mal vorkommen, man mißt die Abweichung davon und läßt N gegen unendlich gehen. Nach dem Gesetz der großen Zahlen sind fast alle Folgen gleichverteilt. (``fast alle'' im Sinne des Produktmaßes auf dem Folgenraum, oder im Sinne des Lebesguemaßes auf den reellen Zahlen bzw im Einheitsintervall.)
Wenn wir statt einzelnen Ziffern k-Tupel von aufeinanderfolgenden Ziffern betrachten, bekommen wir den Begriff der k-Gleichverteilung. Wiederum sind fast alle Folgen k-gleichverteilt
Wieder können wir die Diskrepanz jedes Anfangsabschnittes messen, und eine Folge ist genau dann k-gleichverteilt, wenn diese k-diskrepanz gegen 0 geht.
Man sieht leicht, daß das nur für sehr langsam wachsende Funktionen s sinnvoll ist. s muß schwächer wachsen als der Logarithmus. (Logarithmus zur Basis 10, oder wenn Sie mit 0,1-Folgen arbeiten: Zur Basis 2.)
(log N - log log N - s(N)) divergiert gegen unendlich
und mit Hilfe von zwar naiver aber doch ziemlich tiefliegender und komplizierter Mathematik -- erzeugende Funktionen, Residuen, und so weiter, kann man folgenden nichttrivialen Satz beweisen:
Fast alle Folgen sind s-gleichverteilt
genau dann, wenn:
s ist eine langsame Folge
2. Folie zur Gleichverteilung:
Jetzt haben wir also für jedes langsame s eine Menge vom Maß 1. Wir können jetzt den Durchschnitt über alle diese Mengen bilden, und eine Folge super-gleichverteilt nennen, wenn sie für alle langsamen s s(N)-gleichverteilt ist.Es ergibt sich also die folgende Frage:
Vorhin, nachdem wir gezeigt hatten, daß für jedes k fast alle Folgen k-gleichverteilt sind, hatten wir es leicht, wir haben einfach den Durchscnitt dieser abzählbar vielen 1-Mengen gebilet, und noch immer hatten wir eine 1-menge.
Beachten Sie, daß das hier aber ein überabzählbarer Durchschnitt ist, der auch nicht durch einen abzählbaren Durchschnitt ersetzt werden kann.
Antwort auf die Frage gibt der folgende
Sei N^N die Menge aller Funktionen
von den natuerlichen Zahlen in sich selbst.
(Diese Menge ist durch die punktweise Ordnung halbgeordnet)
Sei (B_f: f in N^N) eine Borel-Familie von Nullmengen.
Wenn diese Familie monoton ist,
(also aus
f < g
die Beziehung
B_f Teilmenge von B_g
folgt)
dann ist die Vereinigung aller B_f
noch immer eine Nullmenge.
Hier sehen wir, daß
eine überabzählbare Vereininigung von Lebesgue-Nullmengen unter
gewissen Umständen wirder eine Lebesgue-Nullmenge liefert. Der
Korollar folgt dann durch triviale Umformungen.
So wie er da steht, gehört der Satz sicher zur naiven Mathematik, also was hat das mit meinem Vortragstitel zu tun? Nun ja, der erste Beweis, den ich für diesen Satz gefunden habe, war rein mengentheoretischer Natur. Ich kann natürlich in so einem Vortrag keine Beweise bringen, außerdem habe ich keine Zeit mehr, ich lege also nur rasch die letzte Folie auf
3. Folie zur Gleichverteilung:
wo der vollständige Beweis des Satzes dasteht, genau so, wie ich ihn veröffentlicht habe (mit ein paar Änderungen, um die Notation anzupassen). Ohne den Beweis jetzt im Detail druchzugehen, sehen Sie hier, daß an mehreren Stellen Logik eingesetzt wird, und zwar schwere Geschütze, daß aber der ganze Beweis von der Struktur her recht einfach ist.
ENDE
Dieser Vortrag kann auf meiner homepage im World-Wide-Web gefunden werden, unter
http://info.tuwien.ac.at/goldstern/
an der Technischen Universität Wien.
Kommentare zum Vortrag können an goldstern@tuwien.ac.at geschickt werden.