Syllabus for Mathematical Logic
Matematisk logik
Syllabus
 10 credits
 Course code: 1MA213
 Education cycle: First cycle
 Main field(s) of study and indepth level: Mathematics G2F, Computer Science G2F
 Grading system: Fail (U), 3, 4, 5
 Established: 20120308
 Established by: The Faculty Board of Science and Technology
 Revised: 20121022
 Revised by: The Faculty Board of Science and Technology
 Applies from: week 30, 2013
 Entry requirements: 60 credits in mathematics including Algebra II, Discrete Mathematics or Set Theory.
 Responsible department: Department of Mathematics
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öwenheimSkolem 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 socalled 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öwenheimSkolem 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 EhrenfeuchtFraï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).
Other directives
The course can not be included in a degree together with Logic II.
Syllabus Revisions
 Latest syllabus (applies from week 30, 2013)
 Previous syllabus (applies from week 31, 2012)
 Previous syllabus (applies from week 30, 2012)
Reading list
Reading list
Applies from: week 30, 2013

Hedman, Shawn
A first course in logic : an introduction to model theory, proof theory, computability, and complexity
Oxford: Oxford University Press, 2004
Mandatory