Spring-Summer 2023
0421202001 Foundations of mathematical logic
Thu 1:25–3:50 PM at Chengjun complex 4, 305
Course Information
Instructor Dr. Bruno Bentzen
Office Location Chengjun Complex 4, 306
Office Hours by appointment
Email bbentzen at zju.edu.cn
Credits 48 hours (16 weeks)
Course Description
This course serves as an introduction to the foundations of mathematical logic. It covers fundamental concepts with emphasis on 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 and Löwenheim-Skolem, quantifier elimination, prenex normal forms, Herbrand’s theorem, the theory of recursive functions, Peano arithmetic, and an overview of Gödel’s incompleteness results.
Course Materials and Resources
This course is based on self-contained lecture notes which will be made available in advance before each class meeting.
Additional readings will not be necessary, but if you are looking for an alternative presentation of the material you can check the textbook:
Van Dalen, Dirk. Logic and Structure
ISBN: N 978-3-540-20879-2
The lecture notes of the previous version of this course are available here.
Course objectives
Upon the successful completion of this course, you will be able to:
read and give rigorous mathematical definitions;
understand and carry out formal proofs of mathematical theorems;
have a solid foundation to pursue further study of mathematical logic;
Prerequisites
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 90%
Attendance 10%
Homework
There will be six homework assignments during the course. 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.
Each homework assignment must be completed and turned in on time. If you missed the deadline because you were ill or for some other valid reason, please send me an email. I wish to evaluate your performance, so your homework should reflect your own efforts. Your English level will not be subject to evaluation, only the content of your homework solutions. But you should at least be able to communicate your ideas clearly and effectively. Both handwritten and printed assignments are equally acceptable, though for students trying to pursue further studies in logic, using LaTeX is highly encouraged.
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. Keep in mind that if you miss a class for any other reason it is your responsibility to make up the material missed and catch up with your classmates.
Feedback
I always welcome feedback about my teaching, be it positive or negative. You can either speak to me directly after class, send me an email, or, if you feel more comfortable, send me an anonymous note. Rest assured that giving feedback will not affect your grade, neither positively nor negatively, but it will help me to see my lectures from different angles and develop new ways of improving them.
Schedule
The schedule is tentative and subject to change with fair notice. The items below should be viewed as the key concepts you should grasp in that week and thus can be used as a study guide before each exam.
Week 01, 03/02:
Sets and functions
Inductive sets
Recursive definitions
Week 02, 03/09:
Strings
Proof strategies
Formal language and grammar of propositional logic
Truth tables and truth functionality
Validity and satisfaction
Week 03, 03/16:
Logical equivalences and substitution
Conjunctive and disjunctive normal forms
Week 04, 03/23:
Functional completeness
Interdefinability of connectives
Semantic consequence
Week 05, 03/30:
Natural deduction
Introduction and elimination rules
Week 06, 04/06:
Natural deduction (cont.)
Admissible rules
Soundness of propositional logic
Gödel encoding
Completeness of propositional logic
Week 07, 04/13:
Compactness of propositional logic
Universal and existential quantifiers
Interdefinability of quantifiers
Formal language and grammar of predicate logic
Week 08, 04/20:
Free and bound variables
Structures
First order semantics
Week 09, 04/27:
Validity
Logical equivalence
Week 10, 05/04:
Finite quantification
Prenex normal formulas
Week 11, 05/11:
Structures and models of theories
The language of identity, posets, groups, rings
Peano arithmetic
Week 12, 05/18:
Natural deduction: universal and existential quantifiers, identity
General elimination rules
Week 13, 05/25:
Soundness for predicate logic
Completeness for predicate logic
Compactness for predicate logic
Week 14, 06/01:
Löwenheim-Skolem
Quantifier elimination
Week 15, 06/08:
Prenex normal forms
Herbrand’s Theorem
Primitive recursive functions
Week 16, 06/15:
Revisiting Peano arithmetic
Undecidability of Peano arithmetic
Past instances
Spring-Summer 2022
Please let me know if you find any broken links.