Spring-Summer 2024  
0421202001 Mathematical logic

Course information

Instructor Dr. Bruno Bentzen

TA Faqiang Li

Office Location Chengjun Complex 4, 306

Office Hours by appointment

Email bbentzen at zju.edu.cn

Credits 48 hours (16 weeks)

Language English

Course description

This course is a self-contained introduction to mathematical logic suitable for graduate students. The main focus of this course is the major metamathematical results concerning classical first-order logic with identity. Students will be introduced to topics such as elementary set theory, formal languages and grammars, truth tables, natural deduction, proof normalization, first-order semantics, soundness and completeness for classical propositional and predicate logic, compactness, downward and upward Löwenheim-Skolem, quantifier elimination, prenex normal forms, Herbrand’s theorem, the theory of recursive functions, Peano arithmetic, and, whenever time permits, an overview of Gödel’s incompleteness results.

Course materials and resources

This course is based on a series of self-contained lecture notes which will be made available in advance here. Please note that the document might occasionally be updated throughout the semester on an irregular basis for corrections, minor revisions, or the addition of new material.

Additional readings will not be necessary, but if you are looking for an alternative presentation of the material and supplements, I recommend:

• Van Dalen, Dirk. Logic and Structure
  ISBN: N 978-3-540-20879-2

• Gallier, Jean. Logic for Computer Science Foundations of Automatic Theorem Proving
  ISBN: 0486780821

Course objectives

Upon the successful completion of this course, you will be able to:

1. read and give rigorous mathematical definitions;

2. understand and carry out proofs of metamathematical theorems;

3. engage in advanced studies in mathematical logic.

Course prerequisites

Previous basic knowledge of mathematics such as elementary set theory is desirable, but not necessary. If you think such concepts can be challenging, it would be wise to devote some extra time to the course and practice your skills with more exercises from the book. If you are still having trouble keeping up with the classes, feel free to talk to me about your difficulties. Learning logic can be a really fun experience and I want you to enjoy taking this course.

Assessment and grades

• Problem sets 90%

• Participation 10%

Grades are awarded on a scale from 0 to 100, where 100 is the best grade and 60 is the minimum passing grade.

Problem sets: There will be 6 take-home problem sets assigned roughly every two weeks and due in two weeks' time. The problem sets will be posted on the class' Dingtalk group on Fridays and due on Thursdays. You should hand in your assignments to our TA. In general, no late homework will be accepted, but if you missed the deadline because you were ill or for another good reason, please contact me as soon as possible. Your solutions must be written legibly and you must name them. Both handwritten and printed solutions are equally acceptable, though using LaTeX is highly encouraged for students interested in diving deeper into formal logic. Problem sets are important because learning properly logic takes a lot of effort and constant practice. Learning logic is like learning a new language or a new skill like swimming or a musical instrument. It takes a lot of effort and daily practice. If you don’t practice the new skill, you lose it. 

Participation: I will not require you to speak up in class, but any form of engagement with the lectures is highly encouraged. The use of mobile phones, computers, and other portable devices is permitted for taking notes and class-related activities only. 

Attendance policy

You are expected to attend every lecture and be on time. If you cannot come to class due to an emergency, please let me know as soon as possible. If absence persist, a medical report or relevant documentation will be necessary. It is your responsibility to cover the material missed and catch up with your classmates. 

Plagiarism and AI policies

I wish to evaluate your performance, so your work should reflect your own efforts. You can discuss the problem sets with other students, but do not copy their solutions and submit them as your own. Any form of cheating and plagiarism is prohibited and will be taken as a serious offense by the university. The use of AI editing tools such as Grammarly or Hemingway Editor as language aids is permitted. However, the submission of assignments based on AI-generated solutions (such as those generated by ChatGPT prompts) is considered cheating. To submit AI-generated text as your own is no different from plagiarism and I will reserve the right to run AI writing detectors and request an impromptu oral explanation of your solutions whenever the suspicion arises.

Feedback

I always welcome feedback, be it positive or negative. If you wish, you can do this by speaking to me directly after class, sending me an email, or, if you prefer, sending me an anonymous note. Giving feedback will not have any effect on your grade, either positively or negatively. But it will help me to see my lectures from different angles and develop new ways of improving them.

Special Accommodations

Please contact me if you have a disability or other circumstances that require special accommodations.

Schedule

The following schedule is tentative and subject to change with fair notice: 

Lecture 1:

• Course overview

• Sets and functions

• Inductive closures

Lecture 2 (HM1 will be posted):

• Freely generated sets

• Recursive definitions

• Strings and their operations

Lecture 3:

• Defining the set of propositional formulas

• Free generation of the set of propositional formulas

• Recursive functions on propositions

Lecture 4 (HM2 will be posted):

• Truth tables and truth under a valuation

• Semantic consequence and validity

Lecture 5:

• Logical equivalences and substitution salva veritate

• Conjunctive and disjunctive normal forms

Lecture 6 (HM3 will be posted):

• Functional completeness

• Interdefinability of connectives

Lecture 7:

• Trees and their operations

• Natural deduction for propositional logic

Lecture 8 (HM4 will be posted):

• Admissible rules

• Soundness of propositional logic

• Grammar of predicate logic and first-order signatures

Lecture 9:

• Induction principle for terms and formulas

• Definitions by recursion on terms and formulas

• Free and bound variables

• Structures and interpretation functions

Lecture 10:

• Variable assignments

• First-order semantics

• Validity

Lecture 11:

• Logical equivalence

• Term substitution

• Finite quantification

Lecture 12 (HM5 will be posted):

• Prenex normal form

• Skolemization and quantifier elimination

Lecture 13:

• Natural deduction for quantifiers and identity

• General elimination rules

Lecture 14 (HM6 will be posted):

• Soundness for predicate logic

• Gödel encoding and enumerability of the language

Lecture 15:

• Completeness for propositional and predicate logic

• Compactness for predicate logic

• Non-standard models of Peano arithmetic

Lecture 16:

• Löwenheim-Skolem

• Overview of Gödel's incompleteness theorems

• Resources for further studies

Past instances

• Spring-Summer 2024, 2023, 2022

Please let me know if you find any broken links.