Syllabus and literature for lectures on
Course code: NMAG331. The course will be given in English if there
is a student not speaking Czech or Slovak enrolled.
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.

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

(see also this
list of literature)

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.

For Godel's theorems specifically see also
this list of literature.