Mathematical Logic II - Carnegie Mellon

Basic Logic/Mathematical Logic II
21-700
Spring, 2013

J. Iovino

Content of the course

Topics to be covered include:

The completeness of first-order logic and its consequences: The method of building models from constants. Consequences of completeness: compactness and Löwenheim-Skolem theorems.
Formal number theory and computability: Axiomatic arithmetic, recursive functions, Church's Thesis, arithmetization of syntax (Gödel numbers).
Incompleteness and undecidability: The Diagonal Lemma, Gödel's Incompleteness Theorems, Church's Theorem, Tarski's Theorem on the undefinability of Truth.
Back-and-forth systems: Fraïssé's Theorem, Ehrenfeucht's games.
Extensions of First-Order Logic: Infinitary logics, Scott's isomorphism theorem, Karp's Theorem, generalized quantifiers.
Lindström's Theorems: Abstract logics and Lindström's Theorems.
Real-valued logics: Metric structures and their ultraproducts, Łukasiewicz logic and related logics.

References

M. Goldstern and H. Judah, The Incompletenes Phenomenon: A New Course in Mathematical Logic, AK Peters/CRC Press, 1998.
H.-D. Ebbinghaus, J. Flum, W. Thomas, Mathematical Logic, second edition, Springer, 1994.
H. Enderton, A Mathematical Introduction to Logic, second edition, Academic Press, 2001.
E. Mendelson, A Mathematical Introduction to Logic, fifth edition, Chapman and Hall/CRC, 2009.

Evaluation

There will be four problem sets. Each of them will have the same weight.