Mathematische Logik - Website of Alexander Bors · 2017. 3. 7. · Mathematische Logik kann als Teilgebiet der Mathematik angesehen werden, wie z.B. auch Algebra oder Analysis. Untersuchungsobjekt

1

Einführung Geschichtlicher Überblick

Mathematische LogikVorlesung 1

Alexander Bors

2. März 2017

A. Bors Logik

2


Überblick

1 Einführung: Administratives und Motivation

2 Geschichtlicher Überblick (Quelle: Hoffmann, pp. 13–66)Zu Cantors WerkZu Freges WerkHilberts Rede auf dem zweiten internationalenMathematikerkongress

A. Bors Logik

3


Administratives

Die Lehrveranstaltung ist eine VP und gliedert sich in zweiTeile:

1 einen Vorlesungsteil, abgehalten von Alexander Bors,donnerstags, 13:30–15:00 Uhr, HS 414, sowie

2 einen Übungsteil, abgehalten von Markus Hittmeir, montags,17:00-17:45 Uhr, HS 414.

Achtung: Nächsten Montag, 6.3.2017, wird die eineLV-Einheit noch zur Vorlesung verwendet.

Als VP ist die gesamte Lehrveranstaltung prüfungsimmanent,d.h., es besteht Anwesenheitspflicht sowohl im Vorlesungs-als auch im Übungsteil.

A. Bors Logik

4


Administratives cont.

Notwendige Bedingungen, um eine positive Note erhalten zukönnen, sind:

Anwesenheit von mindestens 80% in der LV,mindestens eine Tafelleistung im Übungsteil sowieein positives Resultat (mehr als 50%) in der Vorlesungsklausuram Semesterende.

Sind diese Minimalvoraussetzungen erfüllt, so errechnet sichdie Note aus zwei Teilen mit gleicher Gewichtung:

der besten Tafelleistung im Übungsteil sowiedem Ergebnis der Klausur.

Zur Übung: Es wird keine Kreuzliste geben. DieStudierenden, die eine Aufgabe präsentieren wollen, meldensich freiwillig, wobei bei mehreren “InteressentInnen” für eineAufgabe jenen, die noch am wenigsten oft an der Tafel waren,der Vorzug gegeben wird.

A. Bors Logik

5


Literatur zur Vorlesung

Dirk W. Hoffmann, Grenzen der Mathematik. Eine Reisedurch die Kerngebiete der mathematischen Logik, Berlin(Springer), 2. Aufl. 2013. Ein konzeptuell und graphischwirklich wunderschön gestaltetes Buch, das u.a. die in derVorlesung behandelten Themen mit viel Motivation behandelt.

Kenneth Kunen, Set Theory, London (College Publications),2011. Eines der großen Standard-Lehrbücher für alle, dietiefer in die Mengenlehre eintauchen und vor allem Beweisefür bekannte Unabhängigkeitsresultate (wie etwa dieUnabhängigkeit der Kontinuumshypothese über ZFC)verstehen wollen.

A. Bors Logik

6


Literatur zur Vorlesung cont.

Martin Ziegler, Vorlesung über Mathematische Logik,Vorlesungs-Skriptum, Freiburg, 1997–2007, online verfügbarunter http://home.mathematik.uni-freiburg.de/ziegler/skripte/logik.pdf. Sehr kompaktes und in sichabgeschlossenes Vorlesungs-Skriptum, in dem Beweise zulogischen Grundresultaten im Detail nachgelesen werdenkönnen.

A. Bors Logik

http://home.mathematik.uni-freiburg.de/ziegler/skripte/logik.pdfhttp://home.mathematik.uni-freiburg.de/ziegler/skripte/logik.pdf

7


Motivation: Was ist Logik?

Unterschiedliche Bedeutungen des Wortes “Logik” (nachWikipedia):

Schlussfolgerungslehre bzw. Denklehre (wie z.B. beiAristoteles),

Lehre allgemeiner Gesetze bzw. empfohlener Verhaltensweisenin einem bestimmten Bereich (“Logik des Handelns”, “Logikder Dichtung”),

umgangssprachlich oft bezogen auf Formen des Handelns(Pragmatik),

symbolische/mathematische Logik, um die es in dieserVorlesung geht.

A. Bors Logik

8


Motivation: Was ist Logik? cont.

Mathematische Logik kann als Teilgebiet der Mathematikangesehen werden, wie z.B. auch Algebra oder Analysis.

Untersuchungsobjekt der (mathematischen) Logik ist dieMathematik selbst (bzw. allgemeiner formaleAbleitungskalküle).

Ein paar interessante Fragen zur Motivation:

Was ist eigentlich ein (mathematischer) Beweis?Was ist eine mathematische Aussage?Wann ist eine mathematische Aussage “wahr”?“Kann man das überhaupt lösen?!” (ein fleißiger Student, malwieder an einer äußerst schweren Übungsaufgabe verzweifelnd)

A. Bors Logik

9


Motivation: Was ist Logik? cont.

Um diese und ähnliche Fragen mit mathematischen Methodenbearbeiten zu können, müssen erst einige Konzepteformalisiert werden, denn nur exakte formale Begriffe lassensich mathematisch untersuchen.

Diese Formalisierungs-Schritte werden wir in Kapitel 2durchführen. Grob gesagt geht es darum, Mathematik für dieformalen Überlegungen als ein “Spiel mit Zeichenketten”aufzufassen (philosophisch gesehen ist das der formalistischeZugang zur Mathematik), und dieses Spiel lässt sich gutformal untersuchen.

Zuvor geben wir aber (für einen interessanten und etwassanfteren Einstieg) in Kapitel 1 einen geschichtlichenÜberblick über jene grundlegenden Resultate dermathematischen Logik, die auch direkt die Mathematik selbstbetreffen.

A. Bors Logik

10

Einführung Geschichtlicher Überblick Cantor Frege Hilbert

Fouriers Vermutung

Den Stein ins Rollen brachte interessanterweise folgendeVermutung aus der Analysis:

Vermutung 1.1.1 (Fourier, 1822)

Jede Funktion f : R→ R lässt sich in eine trigonometrische Reihe(heute würden wir dazu eher Fourier-Reihe sagen) entwickeln.

Wir wissen heute, dass Vermutung 1.1.1 falsch ist.

U.a. arbeitete auch der deutsche Mathematiker Georg Cantor(1845–1918) an einem Beweis von Fouriers Vermutung.

Cantor wusste, dass die Vermutung für stetige f bereits“bewiesen” war (man sollte mit dem Wort vorsichtig sein, daes damals noch kein formales Fundament der Mathematik gabund manche der “Beweise” von damals nach heutigenMaßstäben unzureichend sind).

A. Bors Logik

11


Cantors Vorgehensweise und unendliche Mengen

Cantor betrachtete die Menge M(f ) der Unstetigkeitsstellenvon f .

Er konnte die Behauptung von stetigen f auf jene, bei denenM(f ) endlich ist, verallgemeinern. Sein Ziel: DieVoraussetzungen noch weiter abzuschwächen.

Aber der Fall mit unendlichem M(f ) machte ihm Probleme.Er konnte die Entwickelbarkeit immer nur zeigen, wenn dieMenge M(f ) gewisse strukturelle Eigenschaften erfüllte.Letztlich konnte er natürlich die (falsche) Vermutung nichtbeweisen, aber er entwickelte durch die Arbeit an demProblem ein tieferes Verständnis für unendlicheZahlenmengen, was letztlich 1874 zu einer Publikation mitdem Titel “Über eine Eigenschaft des Inbegriffes aller reellenalgebraischen Zahlen” führte.

A. Bors Logik

12


Cantors Paper (1874)

Das von Cantor intendierte Hauptresultat des Papers war dieAbzählbarkeit der Menge der reellen algebraischen Zahlen. Dazuführte er in der heutigen Mengenlehre grundlegende Konzepte ein:

Definition 1.1.2

Es seien M1 und M2 Mengen.

1 Wir sagen, M1 und M2 sind gleichmächtig, geschrieben|M1| = |M2|, falls es eine Bijektion M1 → M2 gibt.

2 Wir sagen, M1 sei höchstens so mächtig wie M2, geschrieben|M1| ≤ |M2|, falls es eine Injektion M1 → M2 gibt.

3 M1 heißt

abzählbar, falls |M1| ≤ |N|,abzählbar unendlich, falls |M1| = |N| undüberabzählbar, falls es nicht abzählbar ist.

A. Bors Logik

13


Überabzählbarkeit von R

Außerdem bewies Cantor in dem Paper aus 1874 folgendenberühmten Satz:

Satz 1.1.3

Die Menge R der reellen Zahlen ist überabzählbar.

Wir besprechen hier nicht den Beweis aus dem Paper (der auf demIntervallschachtelungsprinzip beruht, sh. Übung 1), sondern einenanderen Beweis, den Cantor drei Jahre später gab. Dieser ist,durch die Verwendung der berühmten “Diagonalmethode”,wegbereitend geworden.

A. Bors Logik

14


Überabzählbarkeit von R cont.

Wir brauchen zuerst folgendes

Lemma 1.1.4

Es seien X und Y Mengen, X nichtleer, und es existiere eineInjektion X → Y (d.h., es gilt |X | ≤ |Y |). Dann existiert auch eineSurjektion Y → X .

Beweis

Fixiere eine Injektion f : X → Y sowie ein Element x0 ∈ X .Betrachtet als Funktion X → f [X ] ist f bijektiv, sodass auff [X ] ⊆ Y die Umkehrabbildung f −1 wohldefiniert ist. Definiere

g : Y → X durch g(y) :=

{f −1(y), wenn y ∈ f [X ],x0, sonst.

. g ist

surjektiv, denn für jedes x ∈ X gilt: g(f (x)) = f −1(f (x)) = x .

A. Bors Logik

15



Beweis von Satz 1.1.3 (Cantors zweiter Überabzählbarkeitsbeweis,1877)

Indirekt. Angenommen, R wäre abzählbar, also |R| ≤ |N|.Nach Lemma 1.1.4 gibt es dann eine Surjektion N→ R, d.h.,wir können alle reellen Zahlen in der Form x0, x1, . . . aufzählen.

Daraus erhalten wir auch eine Aufzählung ω0, ω1, . . . allerZahlen aus dem halboffenen Intervall [0, 1), indem wir in derursprünglichen Liste die Einträge, die nicht in dem Intervallliegen, streichen.

Es sei ωi = 0, ζi ,1ζi ,2 · · · jene Dezimalentwicklung von ωi , beider nicht fast alle Ziffern gleich 9 sind.

A. Bors Logik

16



Beweis von Satz 1.1.3 cont.

Wir wollen eine Zahl ξ = 0, ζ1ζ2 · · · definieren, welche nicht inder Liste ω1, ω2, . . . vorkommt.

Dazu definieren wir die Ziffern ζj , j ∈ N+, von ξ so, dass jedeeinzelne die Gleichheit von ξ mit einem der ωi “sabotiert”(und natürlich letztlich alle solchen Gleichheiten sabotiertsind).

Eine mögliche Definition dafür: ζj :=

{0, wenn ζj−1,j 6= 0,1, wenn ζj−1,j = 0.

.

Dann sabotiert die j-te Ziffer ζj von ξ, dass ξ = ωj , und dasfür jedes j .

A. Bors Logik

17


Bemerkungen zu Cantors zweitem

Überabzählbarkeitsbeweis

Die Bezeichnung “Diagonalargument” kommt von folgenderAnschauung: Man stelle sich die Ziffernentwicklungen derωi = 0, ζi ,1ζi ,2 · · · untereinandergeschrieben. Dadurchentsteht eine unendliche Matrix (ζi ,j)i∈N,j∈N+ . Bei derDefinition von ζj wurden die “Sabotageakte” entlang derDiagonalen dieser Matrix durchgeführt.

Es ist aber eigentlich nicht wichtig, sie genau entlang derDiagonalen durchzuführen. Für manche Beweise kann das“Sabotageverfahren” sogar nicht entlang der Diagonalendurchgeführt werden und muss adaptiert werden (sh. Übung2).

Die Diagonalmethode ist ein sehr nützliches Werkzeug undwird uns im Laufe der Vorlesung noch öfter begegnen. Eineweitere Anwendung sehen wir gleich.

A. Bors Logik

18


Der Satz von Cantor

Folgender berühmter Satz stammt ebenfalls von Cantor, und seinBeweis verwendet ebenfalls die Diagonalmethode:

Satz 1.1.5 (Cantor)

Es sei M eine beliebige Menge. Dann gibt es keine SurjektionM → P(M), wobei P(M) die Potenzmenge von M bezeichnet,d.h., die Menge aller Teilmengen von M.

Beweis

Wir zeigen, dass keine Funktion f : M → P(M) surjektiv seinkann. Setze dazu Tf := {x ∈ M | x /∈ f (x)}. Wir zeigen, dassTf /∈ f [M]. Andernfalls schreibe Tf = f (x0). Nun gilt nachDefinition x0 ∈ Tf ⇔ x0 /∈ f (x0) = Tf , ein Widerspruch.

A. Bors Logik

19


Bemerkungen zum Satz von Cantor

Auf den ersten Blick ist vielleicht nicht klar, warum derangeführte Beweis ein Diagonalargument ist. Beachte, dasswir Tf so definiert haben, dass für jedes einzelne x ∈ M gilt:Tf verhält sich bezüglich der Frage, ob x ein Elementvon ihm ist genau anders herum als f (x). Das sind lautereinzelne “Sabotageakte”, die zusammengenommenverhindern, dass Tf irgendein Funktionswert von f ist.

Anschaulich bedeutet der Satz von Cantor, dass P(M) stetsstrikt größere Mächtigkeit besitzt als M. Wir halten allerdingsfest, dass wir bis dato noch gar nicht definiert haben, was die“Mächtigkeit” einer Menge ist, und es wird auch noch einigeZeit dauern, bis wir das können.

A. Bors Logik

20


Der Satz von Cantor-Schröder-Bernstein

Zumindest können wir schon einmal folgenden Satz beweisen, derheuristisch besagt, dass die “Mächtigkeiten von Mengen” aufnatürliche Weise geordnet sind. Er wurde 1887 von Cantorvermutet und konnte erst 1897 unabhängig voneinander von FelixBernstein und Ernst Schröder bewiesen werden.

Satz 1.1.6 (Cantor-Schröder-Bernstein)

Es seien X und Y Mengen, sodass es Injektionen f : X → Y undg : Y → X gibt (d.h., sodass |X | ≤ |Y | und |Y | ≤ |X |). Danngibt es eine Bijektion X → Y (d.h., es gilt |X | = |Y |).

A. Bors Logik

21


Zum Beweis des Satzes von Cantor-Schröder-Bernstein

Im Beweis werden wir folgendes Hilfskonzept verwenden:

Definition 1.1.7

Es seien X und Y Mengen, f : X → Y und g : Y → XInjektionen, x ∈ X .

1 Wir definieren die f -g -Urbilderfolge von x als die (wegen derInjektivität eindeutig bestimmte) längste endliche oderunendliche Folge (z0, z1, z2, . . .) sodass gilt: z2i ∈ X undz2i+1 ∈ Y für i ∈ N, z0 = x sowie g(z2i+1) = z2i undf (z2i+2) = z2i+1 für i ∈ N.

2 Der f -g -Typ von x , notiert typef ,g (x), ist die Länge derf -g -Urbilderfolge von x , und somit ein Element vonN+ ∪ {∞}.

A. Bors Logik

22


f -g -Typen: zwei Beispiele

1 Es sei zunächst X = Y = N, f : x 7→ x + 1, g : y 7→ 2y .x = 3 liegt nicht im Bild von g , hat also gar kein Urbild unterg , sodass die f -g -Urbildfolge von x bereits bei x abbricht. Esfolgt: typef ,g (3) = 1.Für x = 4 sieht die Urbildfolge so aus: (4, 2, 1). Es ist alsotypef ,g (4) = 3.

2 Nun sei X = Y = Z, f = g sei dieVorzeichenwechsel-Funktion t 7→ −t. Dann folgt für jedesx ∈ X = Z, dass die f -g -Urbildfolge von x wie folgt aussieht:(x ,−x , x ,−x , . . .). Sie bricht also nicht ab, und somit gilttypef ,g (x) =∞ für alle x ∈ X .

A. Bors Logik

23


f -g -Typen: ein Lemma

Lemma 1.1.8

Es seien X und Y Mengen, f : X → Y , g : Y → X Injektionen,x ∈ X . Dann gilt:

1 typeg ,f (f (x)) = typef ,g (x) + 1 (wobei ∞+ 1 :=∞).2 Ist x ∈ g [Y ], so gilt typeg ,f (g−1(x)) = typef ,g (x)− 1 (wobei∞− 1 :=∞).

Beweis

Zu Punkt 1: Offenbar ist die g -f -Urbildfolge von f (x) gleich(f (x), x , z1, z2, . . .), wobei die zi die entsprechenden Einträgeaus der f -g -Urbildfolge von x sind.

Zu Punkt 2: Folgt aus Punkt 1 durch Vertauschung derRollen von X und Y (beachte, dass x = g(g−1(x))).

A. Bors Logik

24


Bijektivität und Umkehrfunktionen

Wir erinnern zudem an folgendes elementare mengentheoretischeLemma:

Lemma 1.1.9

Es seien X und Y Mengen, α : X → Y . Folgende Aussagen sindäquivalent:

α ist bijektiv.

α besitzt eine Umkehrfunktion, d.h., eine Funktionβ : Y → X , sodass α ◦ β = idY und β ◦ α = idX .

A. Bors Logik

25


Beweis des Satzes von Cantor-Schröder-Bernstein

Beweis von Satz 1.1.6

Wir werden Funktionen α : X → Y und β : Y → X definierenund zeigen, dass diese zueinander invers sind.

α und β sind wie folgt definiert:

α(x) :=

{f (x), wenn typef ,g (x) ∈ (2N + 1) ∪ {∞},g−1(x), wenn typef ,g (x) ∈ 2N+,

,

β(y) :=

{g(y), wenn typeg ,f (y) ∈ 2N + 1,f −1(y), wenn typeg ,f (y) ∈ 2N+ ∪ {∞}

.

Wir werden hier nur verifizieren, dass β ◦ α = idX gilt, da derNachweis von α ◦ β = idY analog geht.

A. Bors Logik

26


Beweis des Satzes von Cantor-Schröder-Bernstein cont.

Beweis von Satz 1.1.6 cont.

Es sei also x ∈ X . Fallunterscheidung:Fall 1: typef ,g (x) ∈ (2N + 1) ∪ {∞}. Dann folgt nach Lemma1.1.8, dass typeg ,f (f (x)) = typef ,g (x) + 1 ∈ 2N+ ∪ {∞}. Esfolgt: (β ◦ α)(x) = β(α(x)) = β(f (x)) = f −1(f (x)) = x , waszu zeigen war.Fall 2: typef ,g (x) ∈ 2N+. Dann folgt nach Lemma 1.1.8, dasstypeg ,f (g

−1(x)) = typef ,g (x)− 1 ∈ 2N + 1. Somit folgt:(β ◦ α)(x) = β(α(x)) = β(g−1(x)) = g(g−1(x)) = x , was zuzeigen war.

A. Bors Logik

27


Eine Anwendung: Die Mächtigkeit von RDas folgende Korollar kann als eine Verstärkung von Satz 1.1.3gesehen werden.

Korollar 1.1.10

Es gilt: |R| = |P(N)|. Insbesondere (nach Lemma 1.1.4 und Satz1.1.5) ist R überabzählbar.

Beweis

Wir zeigen zuerst, dass |R| = | [0, 1] | mit dem Satz vonCantor-Schröder-Bernstein. Dass | [0, 1] | ≤ |R|, ist trivial.Umgekehrt prüft man leicht nach, dass die FunktionR→ [0, 1/3] ∪ [2/3, 1] ⊆ [0, 1], welche∑∞

i=−∞ bi10i 7→ 13(b010

−1 +∑∞

i=1 (b−i10−2i + bi10

−2i−1))und −

∑∞i=−∞ bi10

i 7→13(b010

−1 +∑∞

i=1 (b−i10−2i + bi10

−2i−1)) + 23 abbildet,injektiv ist.

A. Bors Logik

28


Eine Anwendung: Die Mächtigkeit von R cont.

Beweis von Korollar 1.1.10 cont.

Wir bezeichnen mit {0, 1}N die Menge aller Folgen (an)n∈Nmit Einträgen aus {0, 1} (sh. auch Übung 3). Man sieht leicht,dass die Abbildung P(N)→ {0, 1}N, welche M ⊆ N abbildet

auf die Folge (an,M)n∈N mit an,M :=

{1, wenn n ∈ M,0, wenn n /∈ M,

eine

Bijektion ist. Somit gilt auch |P(N)| = |{0, 1}N|.Gemäß dieser Vorüberlegungen genügt es nun, zu zeigen, dass| [0, 1] | = |{0, 1}N|. Dies werden wir ebenfalls mit dem Satzvon Cantor-Schröder-Bernstein bewerkstelligen.

A. Bors Logik

29


Eine Anwendung: Die Mächtigkeit von R cont.

Beweis von Korollar 1.1.10 cont.

Indem wir zu jedem Element x ∈ [0, 1) jene Binärentwicklungx =

∑∞i=1 ξi2

−i betrachten, wo nicht fast alle der ξi gleich 1sind, erhalten wir eine Injektion [0, 1)→ {0, 1}N,x 7→ (ξi+1)i∈N, und durch das Hinzufügen derAbbildungsinformation 1 7→ (1)i∈N erhalten wir sogar eineInjektion [0, 1]→ {0, 1}N.Außerdem prüft man leicht nach, dass die Abbildung{0, 1}N → [0, 1] , (ai )i∈N 7→

∑∞i=0 ai2

−2i−1 eine Injektion ist.Damit sind wir fertig nach dem Satz vonCantor-Schröder-Bernstein.

A. Bors Logik

30


Abschließende Bemerkungen zu Cantors Werk

Wir wissen nun, dass N eine Teilmenge von R mit echtkleinerer Mächtigkeit ist. Cantor vermutete, dass es keineMächtigkeiten zwischen jener von N und jener von R gibt:

Vermutung 1.1.11 (Kontinuumshypothese, Cantor, 1878)

Es sei X eine Menge mit N ⊆ X ⊆ R. Dann gilt entweder|X | = |N| oder |X | = |R|.

Erst in den 1960er-Jahren (dank der Arbeit von Kurt Gödelund Paul Cohen) sollte sich herausstellen, dass dieseVermutung eine erstaunliche Eigenschaft besitzt: Man kannsie weder beweisen noch widerlegen; solche mathematischenAussagen nennt man unabhängig. Wir werden das im Laufeder Vorlesung noch präzisieren.

A. Bors Logik

31


Abschließende Bemerkungen zu Cantors Werk cont.

Cantors Resultate stießen zu seinen Lebzeiten oft aufAblehnung; wahrscheinlich einer der wichtigsten Gründe,warum er so viel mit Depressionen zu kämpfen hatte. DieseAblehnung hatte vorwiegend philosophische Gründe, da vieleMathematikerInnen damals aktuale Unendlichkeit (d.h., das“Herumhantieren” mit unendlichen Mengen alsabgeschlossene Gebilde) ablehnten. Viele empfanden gewisseEigenschaften unendlicher Mengen (z.B., dass unendlicheMengen echte Teilmengen mit der gleichen Mächtigkeitbesitzen) als befremdlich und sahen dies als Grund, lediglichdie potentielle Unendlichkeit (das Arbeiten mit Begriffen,welche zwar nicht nur endlich viele Objekte beinhalten (wiez.B. “natürliche Zahl”), aber ohne die Gesamtheit dieserObjekte als eigenständiges Objekt anzusehen) zu akzeptieren.

A. Bors Logik

32


Überblick über Freges Werk

Grunddaten: Gottlob Frege (1848-1925), deutscherMathematiker und Philosoph.

Er begründete eine neue philosophische Denkrichtung, denLogizismus: Die Logik soll die Basis für alles sein;insbesondere ist die Mathematik nur ein Teil der Logik undnicht umgekehrt, und die gesamte Mathematik soll auf einlogisches Fundament gestellt werden.

1879: Publikation der Begriffsschrift, seines wichtigstenWerkes.

Schaffung der symbolischen Logik,Entwicklung einer künstlichen Sprache, stark genug, um diegesamte Mathematik zu formalisieren.

A. Bors Logik

33


Überblick über Freges Werk cont.

Abgrenzung zum Werk von George Boole (1815-1864):

Boole hatte die Aussagenlogik geschaffen, welche einesymbolische Beschreibung der Zusammenhänge zwischenelementaren Aussagen ermöglichte. Die elementaren Aussagenselbst wurden aber nicht eingehend formalisiert, sondernlediglich durch Variablen, die einen der Werte 0 (falsch) oder 1(wahr) annehmen können, repräsentiert.Freges Ansatz war stark genug, um die Struktur derElementaraussagen selbst zu formalisieren.Im Prinzip kann man die von Frege erschaffene Sprache alsPrädikatenlogik bezeichnen, aber seine Notation warzweidimensional und sehr unhandlich.

A. Bors Logik

34


Überblick über Freges Werk cont.

1884: Publikation der Grundlagen der Arithmetik.

rein umgangssprachliche Abhandlung (im Gegensatz zurBegriffsschrift)Versuch, den Zahlenbegriff formal zu definieren

1893 und 1903: Publikation der Grundgesetze der Arithmetik,zweibändig.

Zusammenhang zwischen Zahl- und Mengenbegriff (zurFormalisierung)

A. Bors Logik

35


Zu Hilbert

David Hilbert (1862-1943), deutscher Mathematiker.

zahlreiche bedeutende Beiträge zu verschiedenen Gebieten derMathematik, zum Beispiel:

Algebraische Geometrie: Hilbertscher Nullstellensatz:Maximale Ideale in K [X1, . . . ,Xn], K ein algebraischabgeschlossener Körper, “entsprechen Punkten”, d.h., sind vonder Form (X1 − a1, . . . ,Xn − an) für einen “Punkt”(a1, . . . , an) ∈ K n.Algebraische Zahlentheorie: Zahlbericht, 1897:Zusammenfassung von Werken von Kummer, Kronecker undDedekind mit eigenen Ideen. Enthält das als “Hilberts Satz90” bekannte Resultat über die Struktur zyklischerGalois-Erweiterungen.Geometrie: Grundlagen der Geometrie, 1899: Präsentationeines vollständigen Axiomensystems für die euklidischeGeometrie (und Beweis der Eindeutigkeit bis auf Isomorphie).

A. Bors Logik

36


Hilberts Rede

6.-12. August 1900: zweiter internationalerMathematikerkongress in Paris

8. August 1900: Hilbert hält seine berühmte Rede auf demKongress.

Präsentation von 23 Problemen, die er für die Mathematik deskommenden Jahrhunderts als bedeutend erachtete.

1. Problem: Klärung der Kontinuumshypothese

2. Problem: Beweis der Widerspruchsfreiheit derPeano-Arithmetik (eines von Giuseppe Peano 1889publizierten Axiomensystems für die Ordnungsstruktur dernatürlichen Zahlen)

10. Problem: Entscheidungsalgorithmus für die Lösbarkeit vondiophantischen Gleichungen.

A. Bors Logik

37


Zum zweiten Hilbertschen Problem

Hilbert war ein Verfechter des zu Beginn erwähntenmathematischen Formalismus: Mathematische Axiomemachen Aussagen über Beziehungen zwischen Objekten voneiner formalen Natur, und MathematikerInnen leiten ausdiesen weitere formale Aussagen mittels zulässigerSchlussregeln ab.

Philosophische Fragestellungen wie das “wahre Wesen” derbesprochenen Objekte (z.B.: “Was ist die Zahl 0 eigentlichwirklich?”) haben im Formalismus keine Bedeutung.

Beispiel: Hilberts Axiomatisierung der euklidischen Geometrie:“Man kann statt ‘Punkten, Geraden und Ebenen’ jederzeitauch ‘Tische, Stühle und Bierseidel’ sagen.”

A. Bors Logik

38


Zum zweiten Hilbertschen Problem cont.

In seinen Grundlagen der Geometrie gab Hilbert auch einenrelativen Widerspruchfreiheitsbeweis: Wenn die Axiome derPeano-Arithmetik widerspruchsfrei ist, so sind es auch seineAxiome für die euklidische Geometrie.

Für die Peano-Arithmetik wollte Hilbert aber einen absolutenWiderspruchfreiheitsbeweis.

1931 publizierte schließlich Kurt Gödel seine berühmten zweiUnvollständigkeitssätze, auf die wir noch ausführlich zusprechen kommen werden. Der zweite davon zeigtinsbesondere, dass dieser Plan von Hilbert zum Scheiternverurteilt ist.

A. Bors Logik

39


Zum zehnten Hilbertschen Problem

Eine diophantische Gleichung ist eine Gleichung der FormP = 0, wobei P ∈ Z[X1, . . . ,Xn], also ein Polynom in denVariablen X1, . . . ,Xn und mit ganzzahligen Koeffizienten, ist.

Hilbert wollte einen Algorithmus, um für ein gegebenessolches Polynom P zu entscheiden, ob die entsprechendediophantische Gleichung lösbar ist, d.h., ob P eine Nullstelle(x1, . . . , xn) ∈ Zn besitzt.Problem: Es gab damals noch keine mathematisch exakteDefinition von “Algorithmus”. Diese sollte erst in den1930er-Jahren durch Alan Turing erfolgen.

Schließlich konnte 1970 der russische Mathematiker YuriMatiyasevich beweisen, dass es einenEntscheidungsalgorithmus wie von Hilbert gewünscht nichtgeben kann.

A. Bors Logik

Einführung: Administratives und MotivationGeschichtlicher Überblick (Quelle: Hoffmann, pp. 13–66)Zu Cantors WerkZu Freges WerkHilberts Rede auf dem zweiten internationalen Mathematikerkongress

Documents

Mathematische Logik - Website of Alexander Bors · 2017. 3. 7. · Mathematische Logik kann als Teilgebiet der Mathematik angesehen werden, wie z.B. auch Algebra oder Analysis. Untersuchungsobjekt