Syllabus and literature for lectures on

## "Mathematical logic", Jan Krajicek

Course code: NMAG331. The course will be given in English if there is a student not speaking Czech or Slovak enrolled.

### Exam questions.

Student logic seminar.

What it is "a mathematical statement" and what does it mean that it is "true"? What it is "a mathematical structure or a mathematical object" and what does it mean when we say that it "exists"? What it is "a proof" and can we prove all true statements and disprove all false ones?
Mathematical logic offers a certain insight into these questions and the course will present some relevant basic concepts and results. Attending the introductory course is recommended but it is not a formal requirement: anybody willing to study seriously will be able to follow the course.

### Syllabus:

• A brief review of basics of propositional and first-order logic, including elements of model theory.

• The completeness theorem.

• Turing machines, the universal machine, the undecidability of the halting problem.

• Peano arithmetic PA, formalization of syntax in PA.

• Godel's theorems.

## Literature:

The topics of the exam questions are essentially covered in van den Dries's notes (parts of chapters 2-4) and in Mendelson's book (parts of chapters 3 and 5) listed below. For our treatment of question (5) via Sigma^0_1-completeness of a finite fragment of PA and by the formalization of the halting problem notes of Cook and Pitassi may be useful.

### For basics of logic

• L. van den Dries, Lecture notes on mathematical logic, (ps file)

• V.Svejdar, Logika: neuplnost, slozitost a nutnost , Academia, Praha, 2002.

### For computability, undecidability and Godel's theorems

• H.D.Ebinghaus, J.Flum, W.Thomas: Mathematical Logic, Springer-Verlag 1984 ISBN 0-387-90895-1

• E.Mendelson: Introduction to Mathematical Logic; D.Van Nostrand Company, INC., Princeton, New Jersey, Toronto, New York, London 1964 (fourth edition 1977 Chapman & Hall ISBN 412 80830 7)

• J.R.Shoenfield: Mathematical logic; Addison-Wesley Publishing Company, London . Don Mills, Ontario, 1967.