Entry requirements

60 credit points Mathematics/Computer science including Algebra II, Logic and Proof Techniques I

Learning outcomes

In order to pass the course (grade 3) the student should

be able to give an account of important concepts in recursion theory and model theory;

understand the concept of incompleteness and be able to give an account of Gödel's incompleteness theorem;

be able to exemplify and interpret important concepts in specific cases;

be able to formulate important results and theorems covered by the course and describe the main features of the proofs of important theorems;

use the theory, methods and techniques of the course to solve mathematical problems;

present mathematical arguments to others.

Content

Elementary recursion theory: primitive recursive functions and partial recursive functions, properties of recursive and recursively enumerable sets, the s-m-n theorem, the second recursion theorem and a little about the arithmetical hierarchy and relative computability.

Strength of first order theories. Models for theories, Tarski semantics, the completeness and compactness theorems. Gödel's incompleteness theorems.

Model theory: isomorphism, substructure, elementary equivalence and elementary substructure, the Löwenheim-Skolem theorems, Ehrenfeucht-Fraïssé games, model completeness, complete theories, algebraic applications, non-standard analysis.

Instruction

Lectures and problem solving sessions.

Assessment

Written and, possibly, oral examination at the end of the course. Moreover, compulsory assignments may be given during the course.