MATHEMATICAL LOGIC
- Overview
- Assessment methods
- Learning objectives
- Contents
- Full programme
- Teaching methods
- Contacts/Info
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.
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, λ-calculus, simple theory of types.
- 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 seven 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.
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 2 – assignment 2, chapter 3 – assignment 3, chapters 4 and 5 – assignment 4, chapters 6 and 7).
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.
This is an introductory course in Mathematical Logic. The course aims at studying the proving process, the connection between proof and truth, the concept of construction and computable construction. The course shows and discusses the limits of mathematical proving as a way to access truth.
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.
1. Introduction: a brief history of logic; formalism, syntax, semantics, intended interpretation; an infinite variety of logics; foundational issues; soundness, completeness.
2. Classical propositional logic: syntax, natural deduction; truth-table semantics and algebraic semantics; soundness, completeness.
3. Classical first-order logic: syntax, natural deduction; Tarski’s semantics; soundness and completeness; compactness; hints on model theory.
4. Zermelo-Frænkel’s set theory: classes and sets; ordinals, cardinals and their induction principles; the axiom of choice, the continuum hypothesis.
5. Fundamentals of computability: computable functions, primitive recursive functions, partial recursive functions; enumeration theorem and universal function; fixed points; pure λ-calculus and representable functions; simple theory of types and strong normalisation.
6. Fundamentals of intuitionistic logic: motivation; syntax and expressive power; propositional algebraic semantics; soundness and completeness; propositions as types; normalisation.
7. Limiting results: Gödel incompleteness theorems; hints on natural incompleteness results.
1. Introduction: a brief history of logic; formalism, syntax, semantics, intended interpretation; an infinite variety of logics; foundational issues; soundness, completeness.
2. Classical propositional logic: syntax, natural deduction; truth-table semantics and algebraic semantics; soundness, completeness.
3. Classical first-order logic: syntax, natural deduction; Tarski’s semantics; soundness and completeness; compactness; hints on model theory.
4. Zermelo-Frænkel’s set theory: classes and sets; ordinals, cardinals and their induction principles; the axiom of choice, the continuum hypothesis.
5. Fundamentals of computability: computable functions, primitive recursive functions, partial recursive functions; enumeration theorem and universal function; fixed points; pure λ-calculus and representable functions; simple theory of types and strong normalisation.
6. Fundamentals of intuitionistic logic: motivation; syntax and expressive power; propositional algebraic semantics; soundness and completeness; propositions as types; normalisation.
7. Limiting results: Gödel incompleteness theorems; hints on natural incompleteness results.
Conventional frontal lecture in English with slides and blackboard.
The teaching objectives are pursued as follows:
1. each of the seven 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 is 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.
Professors
Borrowers
-
Degree course in: MATHEMATICS