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.

#### Consultations:

After each lecture, via email or, if you will have more questions at the same time, via zoom (at a time arranged by email).
Do not hesitate to write frequently and ask even short and simple questions.
I will also start each lecture by answering questions about previous lectures.
Zoom ID: 396 697 4589, https://lfp-cuni.zoom.us/j/3966974589
Password: I will send you the password by email. After you join the zoom meeting you will find yourself in a waiting room - this is just a precaution to avoid unwanted visitors. For the same reason please join each meeting under your *full real name*.

### 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:

Topics of the three exam questions are essentially covered in van den Dries's notes parts of chapters 2 and 3 (question 1), in Sipser's book parts of chapters 3 and 4 (question 2), both listed below.
While the notions and facts used in our treatment of question (3) via Sigma^0_1-completeness of a finite fragment of PA and by the formalization of the halting problem are in most texts below, in none of them it is organized and presented the way we do it. Here several short notes I wrote - see the lecture page - may be useful.

[The pdfs of the books are meant for study purposes and not for a further distribution.]

### 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.

• M.Sipser, Introduction to the theory of computation, 2nd ed., Thomson, 2006.