# LOG110 Logical theory, 15 credits

## LOG110: Logical theory, 15 credits

The course starts with a comprehensive presentation of syntax, semantics and proof systems for propositional logic; and continues with classical first-order predicate logic. Detailed proofs of the completeness theorems for both propositional and predicate logic are included. Basic results, such as the compactness theorem and Löwenheim-Skolem's theorem, together with more advanced results and concepts, for example, model completeness, form the model theoretical part of the course.
As examples of other logics, second-order and intuitionistic logic are presented together with completeness results. Basic proof theory is introduced and lead up to a proof of normalisation for natural deduction, both for classical and intuitionistic logic. Gödel's incompleteness theorems and basic recursion theory are also included.

### Literature

The course is based on van Dalen: Logic and structure 5th edition.

### Course plan

Please see the module for part 1 and part 2 for the plan.

### Learning outcomes

On successful completion of the course the student will be able to:

Knowledge and understanding

• describe and demonstrate an understanding of basic model theory and proof theory including completeness theorems, for propositional logic, first-order logic, intuitionistic logic, and second-order logic.
• describe the relationship between intuitionistic and classical logic from both a model theoretic and proof theoretic perspective.
• describe the relationship between second-order logic, first-order logic, and propositional logic.
• describe and discuss Gödel's first and second incompleteness results as well as Gödel-Rosser's theorem.

Competence and skills

• formulate and present proofs of the most important results in the course including completeness, incompleteness and normalisation theorems, as well as of lemmas used in the proofs.
• apply methods and results of the course in independent problem-solving.

Judgement and approach

• critically discuss, analyse and evaluate the results in the course as well as their applications.