Entry requirements

60 credits in mathematics. Participation in Algebra II or Set Theory.

Learning outcomes

On completion of the course, the student should be able to:

• explain essential concepts from the course such as consistency, completeness, categoricity, cardinality, (primitive) recursivity, recursive enumerability, elementary equivalence/substructure;
• formulate essential results from the course such as the soundness theorem, the model existence theorem, the completeness theorem, the compactness theorem, conditions which are equivalent to the axiom of choice, the Löwenheim-Skolem theorems, Vaught's criterion for completeness, characterisations of recursively enumerable sets, Rice's theorem, Gödel's incompleteness theorem;
• use concepts, methods and results from the course to solve problems concerning the concepts of consistency, completeness, categoricity, cardinality, recursivity, recursive enumerability, elementary equivalence/substructure;
• describe the fundamental features in the proofs of more important theorems.

Content

The formal language of first order logic (FOL) is introduced as well as its semantics, i.e. how statements in FOL are interpreted as true/false in mathematical structures (e.g. graphs or groups). A formal proof system for FOL is described, and the concept of consistency is introduced. A strong relationship between formal provability and logical consequence for structures is proved, the so-called soundness theorem and the completeness theorem. The model existence theorem is an important ingredient in the proof. The most used axioms within set theory, denoted ZF(C), can be expressed with FOL. The concepts ordinal, cardinal and cardinality are introduced as well as fundamental arithmetical rules for cardinals. Statements that are equivalent to the axiom of choice are dealt with.

The course deals with basic model theory, i.e. the study of the structures (models) that satisfy a set of axioms that can be expressed with FOL and relations between such structures such as elementary equivalence and (elementary) substructure. The compactness theorem and the Löwenheim-Skolem theorems are proved, from which follows that if an enumerable set of axioms in FOL has an infinite model, then it has as well a model of each infinite cardinality. The concepts 'complete' and 'categorical' set of axioms are treated, as is Vaught's criterion for completeness. A criterion, the Ehrenfeucht-Fraïssé game, to decide if two structures satisfy the same statements within first order logic, is considered.

An introduction is given to recursion theory, i.e. the study of computably (partial) functions and computably enumerable sets, and examples and criteria for algorithmically unsolvable problems are given. Further, FOL is used to prove Gödel's incompleteness theorem which says that the basic axioms for addition and multiplication on the natural numbers, together with all instances of the induction axioms that can be formulated in FOL, do not constitute a complete set of axioms; i.e. there are arithmetic statements which can not formally be proved or disproved from these axioms.

Instruction

Lectures and possibly exercise classes.

Assessment

Written examination at the end of the course (4 credits). Compulsory written assignments during the course (6 credits).

If there are special reasons for doing so, an examiner may make an exception from the method of assessment indicated and allow a student to be assessed by another method. An example of special reasons might be a certificate regarding special pedagogical support from the disability coordinator of the university.

Other directives

The course can not be included in a degree together with Logic II.