Zur Seitennavigation oder mit Tastenkombination für den accesskey-Taste und Taste 1 
Zum Seiteninhalt oder mit Tastenkombination für den accesskey und Taste 2 

ONLINE im WS 2020/21: Logik und Beweisbarkeit - Einzelansicht

  • Funktionen:
Grunddaten
Veranstaltungsart Vorlesung/Übung Langtext
Veranstaltungsnummer 9718 Kurztext FMI-IN0082
Semester WS 2020 SWS 5
Teilnehmer 1. Platzvergabe 20 Max. Teilnehmer 2. Platzvergabe 30
Rhythmus Jedes 2. Semester Studienjahr
Credits für IB und SPZ
E-Learning
Hyperlink
Weitere Links
Informationen, Skript, Folien, Übungsblätter https://users.fmi.uni-jena.de/~mundhenk/LB.html
Sprache Deutsch
Belegungsfrist Zur Zeit keine Belegung möglich
Abmeldefristen
Nach Zulassung ist eine Abmeldung nur durch den Dozenten möglich.

Nach Zulassung ist eine Abmeldung auch durch den Teilnehmer möglich.

Nach Zulassung ist eine Abmeldung nur durch den Dozenten möglich.
Termine Gruppe: 1-Gruppe iCalendar Export für Outlook
  Tag Zeit Rhythmus Dauer Raum Lehrperson (Zuständigkeit) Status Bemerkung fällt aus am Max. Teilnehmer 2. Platzvergabe
Einzeltermine anzeigen Di. 14:00 bis 16:00 w. 03.11.2020 bis
09.02.2021
    findet statt  
Einzeltermine anzeigen Do. 14:00 bis 16:00 w. 05.11.2020 bis
11.02.2021
    findet statt  
Gruppe 1-Gruppe:



Zugeordnete Person
Zugeordnete Person Zuständigkeit
Mundhenk, Martin, Universitätsprofessor, Dr. verantwortlich
Zuordnung zu Einrichtungen
Fakultät für Mathematik und Informatik
Theoretische Informatik
Inhalt
Kommentar

Kann man alle wahren arithmetischen Aussagen (z.B.(?): es gibt unendlich viele Primzahlzwillinge) formal beweisen?
Kurt Gödel hat mit seinen Unvollständigkeitssätzen gezeigt, dass das nicht geht.
In dieser Vorlesung werden wir uns ansehen, was geht und was nicht geht, und warum es so ist.

Wir beginnen mit dem einfachen Fall der Aussagenlogik, gehen dann über die variablenfreie Arithmetik zur ∑1-Arithmetik (das ist der Teil der Arithmetik ohne unbeschränkte Allquantoren).Für diese Logiken werden wir Vollständigkeitssätze für entsprechende Beweissysteme zeigen.

Damit haben wir gesehen, was geht. Weiter geht's mit dem, was nicht geht. Dafür brauchen wir als Fundament etwas Berechenbarkeitstheorie und verbinden dann – etwas verblüffend – die Begriffe Berechnung und Beweis. Auf diesem Fundament ist der Beweis des Gödelschen Unvollständigkeitssatzes recht einfach.

Zum Abschluss werden wir noch in die Original-Arbeit von Gödel schauen und sehen, was er anders gemacht hat.

Literatur
  • Gödel, K.: Über formal unentscheidbare Sätze der Pricipia Mathematica und verwandter Systeme I. Monatshefte der Mathematik und Physik, 38: 173-198, 1931.
  • van Dalen, D.: Logic and Structure. Springer Verlag, 2004.
  • Smith, P.: An Introduction to Gödel's Theorems. Cambridge University Press, 2013.
  • Cutland, N.J.: Computability. Cambridge University Press, 1980.
  • Wolf, R.S.: A Tour Through Mathematical Logic. The Mathematical Association of America, 2005.
Lerninhalte
  • Formale Aussagenlogik und formale Arithmetik
  • Formales Beweisen mittels Natürlichem Schließen
  • Vollständigkeitssatz für Natürliches Schließen in der Aussagenlogik
  • Vollständigkeitssatz für Natürliches Schließen mit den Robinson-Axiomen in der ∑1-Arithmetik
  • Berechenbarkeitstheorie: entscheidbare und semi-entscheidbare Mengen
  • Semi-entscheidbare Mengen sind genau die durch ∑1-Formeln beschriebenen Mengen
  • Unvollständigkeitssätze von Gödel
Strukturbaum
Keine Einordnung ins Vorlesungsverzeichnis vorhanden. Veranstaltung ist aus dem Semester WS 2020 , Aktuelles Semester: SoSe 2024

Impressum | Datenschutzerklärung