Second order logic I, spring 2009
The course assumes knowledge of Gödel's Completeness and Incompleteness Theorems for predicate (i.e. first order) logic. Also knowledge of basic naive and axiomatic set theory is needed.
Wednesday 16-18 in room C124.
There is no course book at the moment. There are chapters on second order logic in at least the following sources:
- Alonzo Church, Introduction to mathematical logic. Vol. I. Princeton University Press, Princeton, N. J., 1956.
- Johan van Benthem, Kees Doets, Higher-order logic. Handbook of philosophical logic, Vol. 1, 189--243, Kluwer Acad. Publ., Dordrecht, 2001.
- Jouko Väänänen, Second-order logic and foundations of mathematics. Bull. Symbolic Logic 7 (2001), no. 4, 504--520.
- An online survey of second and higher order logic: http://plato.stanford.edu/entries/logic-higher-order/
- Maria Manzano: Extensions of first order logic, Cambridge University Press http://books.google.com/books?id=GYSZ0AdppgMC&dq=maria+manzano+extensions+of+first+order+logic&printsec=frontcover&source=bn&hl=en&ei=9waTSfGHN9it-gbwhICjCw&sa=X&oi=book_result&resnum=5&ct=result#PPA170,M1
- Steward Shapiro, Foundations without Foundationalism, (Clarendon press, Oxford 1991/2000).
- Daniel Leivant, Higher order logic, in: Handbook of Logic in Artificial Intelligence and Logic Programming: Deduction methodologies Dov M. Gabbay, Christopher John Hogger, John Alan Robinson (eds.) Oxford University Press, 1994.
Registration at the first lecture
To ask about the course and to be included in the course mailing-list write to the lecturer firstname.lastname@example.org.
1. Definition of SO, syntax and semantics. A categorical axiomatization of number theory. Non-axiomatizability of SO.
2. Sigma^1_n and Pi^1_n classes. Definitions of infinity and countability. A categorical axiomatization of the continuum, reals.
3. Well-ordering, Continuum Hypothesis, finiteness. The concept of a general model.
4. More about general models. Semantic game, model existence game, consistency property.
5. A proof of the Model Existence Theorem.
6. A proof of the completeness theorem. A proof of the uniqueness of arithmetic in general models.
7. Second order arithmetic.
8. Model theory
9. Set theory
10. More set theory