# MATHEMATICAL LOGIC

Degree course:
Corso di Second cycle degree in MATHEMATICS
Academic year when starting the degree:
2018/2019
Year:
1
Academic year in which the course will be held:
2018/2019
Course type:
Compulsory subjects, characteristic of the class
Credits:
8
Period:
First Semester
Standard lectures hours:
64
Detail of lecture’s hours:
Lesson (64 hours)
Requirements:

There are no prerequisites except the basic knowledge provided by a mathematically oriented bachelor degree: fundamentals of arithmetic, mathematical analysis, and elementary topology. It is useful although not required, to know the basics of computer programming.

Final Examination:
Orale

The examination is oral, but frequenting students may opt to do four intermediate written assignments during the course to avoid the final examination.
During the oral examination it will be verified that
- the student is able to perform a formal proof in one of the logical systems illustrated during the course: propositional logic, classical and intuitionistic; first-order logic, classical and intuitionistic.
- the student has acquired the knowledge presented during the course. This will be done by asking her to state and prove some theorems among the ones discussed in the lessons. The theorems will be chosen to cover all the five chapters of the course.
- the student has to show she is able to link the content of the course with her own mathematical interests by a question that allows to use the specific content of the course in a subject she likes.
The marking will be given according to the degree of study and knowledge, to the formal manipulation ability, and to the capacity to link the fundamental concepts of the course to other mathematical subjects.

The intermediate assignments are an option reserved to attending students. They are four and they cover chapters 1, 2, 3 and 4, and 5, respectively.
Every assignment is composed by three questions:
1. to formally prove an exercise in a formal system (assignments 1 and 2), or on a formal system (assignments 3 and 4).
2. to state and to prove a result among the ones studied during the lessons (assignment 1, chapter 1 – assignment 2, chapter 3 – assignment 3, chapters 3 and 4 – assignment 4, chapter 5).
3. to perform a proof or a construction non illustrated during the lessons, using the studied notions.
The marking of every assignment will be given according to the degree of correctness of the first and second questions, and according to the effectiveness of the line of reasoning in the third questions. The final mark will the the average of the intermediate markings.

Assessment:
Voto Finale

Aims and outcomes
This is an introductory course in Mathematical Logic. It starts by introducing classical propositional logic and classical first-order logic, with a glance at their model theory. Then, intuitionistic logic will be illustrated together with its relation to calculability. The course will conclude showing the main limiting results, namely Gödel’s incompleteness theorems.

At the end of the course, a student is expected to acquire the following skills:
1. to prove simple statements in a formal system among the illustrated ones (propositional logic, both classical and intuitionistic, first-order logic, both classical and intuitionistic, lambda-calculus and the simple theory of types).
2. to prove properties of a formal system among the illustrated ones (soundness, completeness, synthesising non-standard models by compactness).
3. to critically view the fundamentals concepts in mathematics (existence of multiple notions of set, existence of multiple notions of number, truth is not the same as provable).
4. to link proofs and computations (propositions as types interpretation, notion of being constructive).
5. to relate formal systems to other mathematical domains (Logic as a study of the foundations of mathematics).

It is also foreseen that studying logic will lead the student to learn an adequate scientific terminology, allowing her to critically review the already acquired mathematical knowledge, and to extend her consciousness of unity of all the mathematical disciplines.

Program
1. Classical propositional logic: syntax, natural deduction, truth-table semantics and algebraic semantics, soundness, completeness.
2. Classical first-order logic: syntax, natural deduction, Tarski’s semantics, soundness, completeness, compactness, hints on model theory.
3. Zermelo-Frænkel’s set theory: classes and sets, ordinals, cardinals and their induction principles, the axiom of choice, the continuum hypothesis.
4. Fundamentals of intuitionistic logic: syntax, propositional algebraic semantics, soundness and completeness, hints to the link with the theory of computations, a sketch of the lambda calculus and the simple theory of types.
5. Limiting results: Gödel incompleteness theorems, and hints on natural incompleteness results.

The slides of the lectures, available on the course website, are the official text.
Further bibliographic references are given in the final slide of each lesson, and they are suggested but not compulsory.

A collection of solved exercises, the texts and the solutions to previous intermediate assignments are also available on the course website. At the end of each intermediate assignment, the corresponding text and solution will be published on the website.

Conventional frontal lecture in English with slides and blackboard.
The teaching objectives are pursued as follows:
1. each of the five chapters of the course will be introduced by a general discussion to relate the topics to the other mathematical subjects, and to illustrate the philosophical meaning of what it going to be explained.
2. the fundamental definitions and theorems will be illustrated to provide a solid and well organised mathematical framework.
3. examples will complement the particularly relevant results, both to clarify their meaning, and to illustrate their applications.
4. the parts which need (the formal proofs) will be complemented with exercises to be solved in the classroom by the lecturer, with an emphasis on the techniques to solve them.
5. at the end of each chapter, a summary of what has been achieved is given, to provide the right perspective to critically evaluate the results, both with respect to their inner mathematical meaning, and with respect to what has been acquired in other courses.
Because of the double nature, mathematical and philosophical of the subject, students are strongly encouraged to attend the lessons, even if not compulsory.

The website for the course is: https://marcobenini.me/lectures/mathematical-logic/
Students are received upon appointment to fix by email.