00662 - Mathematical Logic

Course contents

This course offers and introduction to notions and methods of mathematical logic.

Particularly, the course will cover the following topics:

1) Propositional logic

• Propositional formulae and truth tables
  
• Proof systems
  
• Soundness and completeness
  
• Compactness

2) First-order logic and model theory

• Structures, formulae, models
• Definability and elementary equivalence
• Proof systems
• Soundness and completeness
• Compactness

3) Set theory

• Zermelo-Fraenkel Axioms
  
• Axiom of Choice
• Ordinals and cardinality
• Independence results (sketch)
  

4) Computability theory

• Models of computation and Church-Turing Thesis
• Decidable sets and computable functions
• The Halting Problem
• Gödel's Incompletness Theorems (sketch)

Readings/Bibliography

The students are invited to consult the course notes that will be made available, as well as the following textbook:

• Kunen, Kenneth, The foundations of mathematics. Studies in Logic, 19. Mathematical Logic and Foundations. College Publications, London, 2009. ISBN: 978-1-904987-14-7 --- Available at: https://people.math.wisc.edu/~awmille1/old/m771-10/kunen770.pdf
  

Other books on the topic of the course (whose reading is optional):

• Enderton, Herbert B. A mathematical introduction to logic. Second edition. Harcourt/Academic Press, Burlington, MA, 2001. xii+317 pp. ISBN: 0-12-238452-0
• Marker, David. Model theory. An introduction. Graduate Texts in Mathematics, 217. Springer-Verlag, New York, 2002. viii+342 pp. ISBN: 0-387-98760-6
• Enderton, Herbert B. Elements of set theory. Academic Press, New York-London, 1977. xiv+279 pp
• Kunen, Kenneth Set theory. Studies in Logic, 34. College Publications, London, 2011. viii+401 pp. ISBN: 978-1-84890-050-9
• Enderton, Herbert B. Computability theory. An introduction to recursion theory. Elsevier/Academic Press, Amsterdam, 2011. xii+174 pp. ISBN: 978-0-12-384958-8

Teaching methods

The course will be delivered through 48 hours of frontal lectures, dedicated to the discussion of the material as well as problems. Furthermore, practice problems will be given to students to verify their understanding of the course, and to practice solving problems.

The solutions to the practice problems will be discussed during practice sessions offered by the tutor, which will be in addition to the lecture hours of the course lecturer.

Assessment methods

The assessment for the course comprises both a written exam and an oral exam.

Both the written and the oral exam aim at assessing the comprehension of the topics covered in the course, and the ability of the student to apply them in the solution of problems.

Teaching tools

On the online platform Virtuale, the students will find:

• the course notes, to be consulted in addition to the textbook and the notes taken during frontal lectures by the student;
• practice problems list, to be solved independently for practice, and whose solution will be discussed during the exercise sessions.

Office hours will be by appointment, either in person or online.

Office hours

See the website of Martino Lupini