# Spring-Summer 2024

0421202001 Introduction to mathematical logic

Thu 10:00 AM – 12:25 PM at Chengjun Hall 4, 305

Course Information

Instructor Dr. Bruno Bentzen

TA Dongheng Chen

Ofﬁce Location Chengjun Complex 4, 306

Ofﬁce 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, ﬁrst-order semantics, soundness and completeness for classical propositional and predicate logic, compactness and Löwenheim-Skolem, quantiﬁer 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 deﬁnitions;

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. The preferred way to send me your solutions is electronically by email. If you missed the homework 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 reﬂect 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 using LaTeX is highly encouraged for students interested in diving deeper into logic.

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:

Lecture 1:

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

Truth tables and truth under a valuation

Lecture 4:

Semantic consequence and validity

Logical equivalences and substitution salva veritate

Lecture 5:

Conjunctive and disjunctive normal forms

Functional completeness

Interdeﬁnability of connectives

Lecture 6:

Natural deduction for propositional logic

Induction principle for derivations

Admissible rules

Soundness of propositional logic

Lecture 7:

Gödel encoding

Completeness of propositional logic

Lecture 8:

First-order signatures

Identity, universal and existential quantiﬁers

Grammar of predicate logic

Induction principle for terms and formulas

Lecture 9:

Definitions by recursion on terms and formulas

Free and bound variables

Examples of structures: posets, groups, Peano arithmetic

Lecture 10:

Interpretation functions

Variable assignments

First-order semantics

Lecture 11:

Validity

Logical equivalence

Term substitution

Lecture 12:

Finite quantification

Prenex normal form

Lecture 13:

Quantiﬁer elimination

Structures and models of theories

Natural deduction: universal and existential quantifiers, identity

Lecture 14:

General elimination rules

Soundness for predicate logic

Lecture 15:

Completeness for predicate logic

Lecture 16:

Compactness for predicate logic

Löwenheim-Skolem

Past instances

Spring-Summer 2023

Spring-Summer 2022

Please let me know if you find any broken links.