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.
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
(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.
M.Sipser,
Introduction to the theory of computation,
2nd ed., Thomson, 2006.
For Godel's theorems specifically see also
this list of literature.