LOG110 Logical theory, 15 credits

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. 

Schedule

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.

See the course syllabus for more information. 

Course summary:

Date Details