2.0 VU Mathematische Logik 2 (185.255, WS 2007/08)

This lecture will be presented in English (unless all participants are fluent in German)

Lecturer: Christian Fermüller

NOTE:

• The final lecture on January 22, 2008 will focus (somewhat informally) on Ehrenfeucht-Fraisse games and related matter. Suggestions for additional topics to comment on briefly are welcome. (Email to C. Fermüller.)
• Links to addtional material on Kant's chirality theorem and on first order geometry (Tarski's axiomatization of it) have been added below (immeditately after the lecture slides).

(Regular) Place and Time:

Tuesday, 10:00 (sharp) until about 12:00
Seminarraum E1852
Favoritenstraße 9 / Stiege 1 / 3rd floor (yellow zone)

Important information:

• (If you you haven't done so yet) please REGISTER for this course at TUWIS++
• First lecture: Tuesday, October 9, 10:00 (sharp)
  
• Concerning the TEXTBOOK (see also below):
  
  • Five copies of this book are now available at the Lehrbuchsammlung of the main TU library.

Contents:

In accordance with the current Studienplan der Magisterstudien aus Informatik some (or even all) of the following slightly advanced topics in mathematical logic will be presented:

• Syntax and semantics of classical first order logic (with identity)
• Elements of model theory: expressibility, canonicity, ...
• Löwenheim-Skolem theorem
• Compactness theorem
• Undecidabilty of first order logic
• Craig's Interpolation Theorem
• Beth's Definability Theorem
• Elements elementary geometry as a first order theory
• Monadic logic, dyadic logic, Horn logic
• Elements of formal set theory
• An overview over more advanced topics with hints on further relevant logic courses

Prerequisites:

It is assumed that participants have mastered the elementary concepts of propostional and first-order logic as presented, e.g., in the basic lectures Theoretische Informatik und Logik (or Theoretische Informatik 1 and Theoretische Informatik 2, or Mathematische Logik, alter Studienplan).

It is not necessary (but helpful) do have participated in Mathematische Logik 1.

TEST YOURSELF whether you are fit for this course:
You should be able to prove without handwaving (and preferably without consulting any book or notes) that (forall x) (exists y) P(x,y) is a logical consequence of (exists x) (forall y) P(y,x), but that the converse does not hold. In particular you should be able to present a formal definition of the (logical) consequence relation.

Course material:

A main source will be the excellent text book:

• Computability and Logic von George S. Boolos, John P. Burgess und Richard C. Jeffrey
  (See also: Errata page)
  This book is now also available as eBook from Cambridge University Press.

Five copies of this book are now also available at the Lehrbuchsammlung of the main TU library.

In addition:

• Copies of some relevant sections of the book will be prepared on demand.

Lecture slides:

• First unit (1-19) [4 in 1, PDF]
• Second unit (20-25) [4 in 1, PDF]
• Third unit (26-32) [4 in 1, PDF]
• Fourth unit (33-43) [4 in 1, PDF]
• Fifth unit (44-63) [4 in 1, PDF]
• Sixth unit (64-67) [4 in 1, PDF]
• Seventh unit (68-80) [4 in 1, PDF]
• Eighth unit (81-88) [4 in 1, PDF]

Additional information (links)

• Background information on [BBJ], problem 20.3 (Kant's chirality theorem) can be found in lecture notes of Oliver Pooley (Oxford)
• For additional information about Euclidean geometry as a first-order theory of classical logic see Wikipedia entry on "Tarski's axioms"

Exercises:

• Exercises 1-12 [2 in 1, PDF]
• Exercises 13-22 [2 in 1, PDF]
• Exercises 23-30 [2 in 1, PDF]
• Exercises 31-40 [2 in 1, PDF]

Selected solutions to exercises:

Selected solutions, worked out by the course participants will be posted here

Please include your name, the statement of the problem and the `excercise number' as well as (where applicable) the reference to the `problem number' in your solution, which should be in PDF.

For those working with LaTeX (recommended!) the site 'Latex for Logicians' might be useful.

• Exercises 2/3/4/5 [4 pages, PDF] (Tamas Schmidt)
• Exercise 26 (12.12) [1 page, PDF] (Martin Berlakovich)
• Exercise 32 (12.16) [1 page, PDF] (Harry Snow)

Organisation / Assessment:

As an integrated, essential part of the lecture, students will regularly be assigned exercises during the course and are expected to present solutions in written and/or oral form.

Regular, successful participation (in particular in the exercise part) will suffice to pass the course. (No additional examination will be required. However participants that cannot participate regularly, may take an examination.)

Informationen zur Anrechenbarkeit:

Diese Lehrveranstaltung ist Wahlfach im Magisterstudium Computational Intelligence (Bereich "Diskrete Mathematik und Logik").

C.Fermüller