Logic III 3800-L323-F
Lecture discusses the following topics. Each theorem listed below will be presented with a rigorous proof.
-0 Philosophical motivations of Godel's results: Hilbert's programme.
-1 First-order arithmetic and set theory of hereditarily finite sets.
– coding finite sets in natural numbers.
– interpretation of finitistic set theory in Peano arithmmetic.
– definition by recursion in arithmetic.
-2 Representability of recursive sets in arithmetic.
- Delta_0, Sigma_1 and Pi_1 – definable sets of natural numbers.
- representability and strong representability in an axiomatic theory. The characterisation of Delta_1 sets as sets strongly representable in Robinson's arithmetic.
-3 Limitative results
– Diagonal lemma.
– Tarski's theorem on the undefinability of truth.
– First and Second Godel's theorem.
– Godel-Lob derivability conditions. Lob's theorem. Rosser's theorem.
-4 Informations about Turing machines. Computable and computably enumerable sets. Relations with sets definable in the standard model. Recursive and primitive recursive functions.
-5 Completeness theorem for first-order logic.
-6 Nonstandard models of arithmetic and set-theory.
Type of course
Prerequisites (description)
Course coordinators
Learning outcomes
After passing the course, a student
- knows the philosophical origins of formal limitative results.
- knows the fundamental facts about the expressivity of first-order arithmetic
- knows the outlines of proofs of limitative results (menitioned in point 3 of the description of the course)
- knows the definition of a Turing machine, a computable and computably enumerable sets. Student knows the relations between computably enumerable/computable sets and Sigma_1 definable sets. Student understands the difference between primitive recursive functions and general recursive functions.
- knows the structure of a Henkin-style proof of the completeness theorem.
- understands the order type of countable nonstandard models of Peano arithmetic.
- knows what are the nonstandard elements in nonstandard models of arithmetic and set-theory.
- formulate her argumentation in a clear and precise way.
- analyze others' way of reasoning.
- carefully and patiently listen to others.
- code finite sets in natural numbers.
- define basic sets and relations in natural numbers.
- prove the existence of nonstandard models of arithmetic and set theory.
- present the structure of proofs of limitative results discussed during the lecture.
- critically asses philosophical argumentations involving the limitative results.
Bibliography
P. Hajek, P. Pudlak – Metamathematics of First-order Arithmetic, Cambridge University Press, 2017
R. Kaye – Models of Peano Arithmetic, 1991, Oxford
R. I. Soare -Turing Computability, Springer 2016
Additional information
Additional information (registration calendar, class conductors, localization and schedules of classes), might be available in the USOSweb system: