Second order logic I, spring 2009

Last modified by jvaanane@helsinki_fi on 2024/03/27 09:58

Second order logic I, spring 2009

Lecturer

Jouko Väänänen

Scope

5 cu.

Type

Advanced studies

Prerequisites

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.

Lectures

Wednesday 16-18 in room C124.

Exams

Bibliography

There is no course book at the moment. There are chapters on second order logic in at least the following sources:

  1. Alonzo Church, Introduction to mathematical logic. Vol. I. Princeton University Press, Princeton, N. J., 1956.
  2. Johan van Benthem, Kees Doets, Higher-order logic. Handbook of philosophical logic, Vol. 1, 189--243, Kluwer Acad. Publ., Dordrecht, 2001.
  3. Jouko Väänänen, Second-order logic and foundations of mathematics. Bull. Symbolic Logic 7 (2001), no. 4, 504--520.
  4. An online survey of second and higher order logic: http://plato.stanford.edu/entries/logic-higher-order/
  5. 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
  6. Steward Shapiro, Foundations without Foundationalism, (Clarendon press, Oxford 1991/2000).
  7. 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 jouko.vaananen@helsinki.fi.

Exercise group

Group

Day

Time

Place

Instructor

1.

Monday

16-18

B321

Jouko Väänänen

Content outline

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