Spring–Summer 2026
0421202001 Mathematical logic

Course information

Instructor Dr. Bruno Bentzen

TA -

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 is a self-contained introduction to mathematical logic suitable for graduate students. The main focus of this course is the major metamathematical results concerning the syntax and semantics of classical first-order logic with identity. After an overview of elementary set theory, students will be introduced to topics such as 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

The 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:

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

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

• Jeremy Avigad. Mathematical Logic and Computation
  ISBN: 9781108478755

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

• Homework 30%

• In-class problem set 50%

• 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.

Homework: There will be 1 take-home assignment near the eighth week of the course, to be posted on the class' Dingtalk group and due in two weeks' time. You should hand in your assignments to me. 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 your submission. 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 logic properly 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.

In-class problem set: There will be 1 in-class problem set assigned in the last class meeting testing on the material taught up until one week prior. The problems will have a format similar to those from the homework assignment. Detailed information about the content will be provided as it approaches.

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 for proofreading 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:

• 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:

• 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:

• Functional completeness

• Interdefinability of connectives

Lecture 7:

• Trees and their operations

• Natural deduction for propositional logic

Lecture 8:

• 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:

• Prenex normal form

• Skolemization and quantifier elimination

Lecture 13:

• Natural deduction for quantifiers and identity

• General elimination rules

Lecture 14:

• 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

• In-class problem sets

Past instances

• Spring-Summer 2024, 2023, 2022

Please let me know if you find any broken links.