# Second order logic I, spring 2009

### Lecturer

### 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:

- 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 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