Expressibility and Incompleteness

The course is included in the degree programme H2LOG Logic, Master's programme and can also be given as a freestanding course.

Admission to the course requires Logic and completeness (LOG112) or equivalent. In addition, language proficiency equivalent to English 6 is required.

The course explores the phenomena of completeness and expressive adequacy in formal logic through three primary routes: intuitionistic logic, second order logic, and the Gödel incompleteness theorems.

Intuitionistic logic derives from a reading of the logical connectives as constructions rather than functions on truth values. Proof systems and Kripke semantics are presented, and proven sound and complete.

Second order logic expands first order logic by quantification over sets of objects. The increased expressivity offers different readings of `completeness' which are discussed in this course.

Gödel's incompleteness theorems encompass two theorems due to Kurt Gödel on the limitations of formal reasoning. They are regarded by many logicians as the most signifcant results in the history of logic and had a transformation effect on the development of the field. The course presents and proves the incompleteness theorems and other limiting results, and examines a number of important corollaries and applications.

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

Knowledge and understanding

• describe and demonstrate an understanding of the elementary model and proof theory of intuitionistic logic and second-order logic,
• explain, via central theorems, the relationship between intuitionistic logic and classical logic,
• describe the relationship between second order logic and first order logic,

Competence and skills

• formulate and present proofs of the most important results in the course, including Gödel's first incompleteness theorem and Gödel-Rosser's theorem, as well as dependent lemmas,
• apply methods and results of the course in independent problem-solving,

Judgement and approach

• compare and evaluate the differences between intuitionistic and classical logic from model theoretic and proof theoretic perspectives,
• compare and evaluate the differences between first and second order logic from the perspective of expressivity,
• critically discuss, analyse and evaluate the results in the course as well as their applications.

Teaching is given in the form of lectures, seminars, exercises, individual assignments and group assignments.

Language of instruction: English

The course is assessed individually in written form. In addition to the final written examinations, there may also be up to four compulsory homework assignments during the course.

The grading teacher may request completion of examined student achievements.

If a student who has been failed twice for the same examination element wishes to change examiner before the next examination session, such a request is to be granted unless there are specific reasons to the contrary (Chapter 6 Section 22 HF).

If a student has received a certificate of disability study support from the University of Gothenburg with a recommendation of adapted examination and/or adapted forms of assessment, an examiner may decide, if this is consistent with the course’s intended learning outcomes and provided that no unreasonable resources would be needed, to grant the student adapted examination and/or adapted forms of assessment.

If a course has been discontinued or undergone major changes, the student must be offered at least two examination sessions in addition to ordinary examination sessions. These sessions are to be spread over a period of at least one year but no more than two years after the course has been discontinued/changed. The same applies to placement and internship (VFU) except that this is restricted to only one further examination session.

If a student has been notified that they fulfil the requirements for being a student at Riksidrottsuniversitetet (RIU student), to combine elite sports activities with studies, the examiner is entitled to decide on adaptation of examinations if this is done in accordance with the Local rules regarding RIU students at the University of Gothenburg.

The course is given one of the grades Pass with distinction (VG), Pass (G) and Fail (U). All compulsory elements of the course must be completed to obtain a passing grade. To receive a Pass with distinction, it is furthermore required that the final exam receives the assessment Pass with distinction.

Students who participate in or have completed the course are given the opportunity to anonymously express their experiences of and views on it in a course evaluation. A compilation of the course evaluation and the reflection of the teacher responsible for the course is made available to the students within a reasonable time after the end of the course. The next time the course is given, the summary and any implemented measures will be presented.

The course requires access to a computer (or equivalent) with internet connection.
The course may not be included in the degree together with the course LOG110 or LOG111.