NMAA13036U Introduction to Mathematical Logic

Volume 2016/2017
Education

MSc Programme in Mathematics

Content

First order logic, languages, models and examples. Formal deduction, deduction metatheorems, soundness, completeness and compactness, and applications of compactness. Recursion theory, computable functions on the natural numbers, Turing machines, recursively enumerable sets, and arithmetization of first order syntax. Basic axiomatic set theory, ordinals and cardinals.

Learning Outcome

Knowledge: By the end of the course, the student is expected to be able to explain the concepts of: a first order language; of a model of a first order language; of formal deduction; of a computable relation and function; arithmetization of first order syntax; the axioms of Zermelo-Fraenkel set theory; ordinals and cardinals.

Skills: By the end of the course, the student must be able to define the satisfacation relation, account for the axioms of the deductive system, define the notion of recursive function, and prove that a repository of common functions and relations are recursive, including the coding of basic syntactical notions. The student must be able to prove the key theorems of the course, such as the deduction theorem, the soundness theorem, and the compactness theorem.

Competences: Use of first order languages and structures in mathematics, the formalization of proofs, the coding of syntactical notions in arithmetic. Use ordinal analysis and transfinite recursion.

4 hours lecture and 3 hours tutorials per week for 7 weeks.
• Category
• Hours
• Colloquia
• 21
• Exam
• 40
• Excursions
• 2
• Guidance
• 4
• Lectures
• 28
• Preparation
• 70
• Project work
• 20
• Theory exercises
• 21
• Total
• 206
Credit
7,5 ECTS
Type of assessment
Oral examination, 30 min
With 30 minutes preparation time
Exam registration requirements

To be eligible to take the final exam the student must have handed in the 2 mandatory homework assignments, and these must both have been approved.

Aid
Only certain aids allowed

Notes and the text book.

Marking scale