Introduction to mathematical logic

Time:2024-06-03 ~ 2024-07-11 Mon,Thu 13:30-15:05

Venue:A3-1a-205 ;Zoom: 482 240 1589 Password: BIMSA

Speaker:Boris Shapiro (Visiting Professor)


This course will use a material written by J.Carlström. It can be downloaded by


Day 1 Introduction

• History and purpose of logic.

• Boolean algebras.

Inductively defined sets (Ch. 3 of Carlström)

• Motivation: What is formal syntax? What are formulas?

• The natural numbers; recursion and induction principles

• General inductively defined sets; their recursion and induction principles

• Example: binary trees

Suggested Exercises: Carlström exercises 3.2.28, 3.2.29.

Day 2 Propositional logic (Ch. 4)

• Syntax: the inductively defined set of propositional formulas

• Interpretation of formulas as truth-value

• Semantics: valuations, interpretations, tautologies

• Logical equivalence and entailment.

Suggested exercises: Any from Ch. 4, especially 4.1.6, 4.2.32, 4.2.34, 4.2.37, 4.2.41

Day 3 Natural deduction (Ch. 5)

• Rules of natural deduction

• Notation: φ1, φ2, … φn ⊢ ψ

• Formal definition of derivations, derivability;

Suggested exercises: any from Ch. 5, especially 5.2.4, 5.2.7, 5.3.6–10, 5.4.4, 5.6.1, 5.6.3, and 5.6.6 (this one is a bit more challenging than the rest).

Day 4 Soundness Theorem (Ch. 6)

• Statement of Soundness Theorem (6.1.5): connection between derivability and validity in interpretations

• Proof of soundness

Suggested exercises: any from Ch.6, especially 6.1.22, 6.1.25, 6.1.28, 6.1.34, 6.1.38, 6.3.4

Day 5 Applications of Soundness (Ch. 6)

• Theories and consistency

• Proofs vs countermodels

Suggested exercises: any from Ch.6, especially 6.1.22, 6.1.25, 6.1.28, 6.1.34, 6.1.38, 6.3.4

NOTE: For now, we’re skipping Ch.7, Normalization. We may come back to it later in the course, if time allows

Day 6 Completeness (Ch. 8)

• Statement of completeness

• Statement of model existence lemma

• Roadmap to proof of completeness

• Maximal consistency

Suggested exercises: 8.1.3, 8.1.14, 8.1.17, 8.2.1, 8.2.6, 8.2.7

Day 7 Predicate Logic (Ch.9)

• Concept, examples: languages/theories of groups, posets, arithmetic

• Arity types (aka signatures, etc.)

• Terms, Formulas

• Substitution

• Free/bound occurrences of variables

Suggested exercises: 9.1.15, 9.1.17, 9.1.19, 9.2.7.

Day 8 Semantics (Ch. 10)

• Structures for signatures; valuations of variables.

• NOTE: we define/notate interpretations slightly differently from Carlström — we consider the valuation of variables v as separate from the structure 𝒜, not a part of 𝒜 as in Carlström.

• Interpretation of terms and formulas, 

Suggested exercises: Any from Ch. 10

Day 9 Semantics (Ch. 10), cont’d

• Lemma: interpretation of a term/formula depends only on its free variables

• Notations, terminology: A,v ⊨ φ, etc.

Simplifications (Ch. 11)

• Definition of “bound for”, “free for” (OBS: confusing terminology — this is completely different from “bound in”, “free in”!)

• Lemmas on interpretation of substitutions

Day 10 Natural deduction for predicate logic (Ch. 12)

• New rules for predicate logic

• Rules for equality

• Rules for quantifiers

• Heuristics for derivations in predicate logic

• Useful building-block derivations

Soundness for predicate logic (Ch. 13)

• Statement + proof outline

Suggested exercises: Any from Ch. 12; especially 12.1.6, 12.1.12, but also all from §12.2 are good. For finding derivations: practice, practice, practice!

Day 11 Soundness (Ch. 13)

• Proof of soundness for predicate logic

• Adaptation of outline to predicate setting

• Cases for the new rules

Suggested exercises: Any from Ch. 13.

Day 12 Completeness (Ch. 14)

• Outline of proof: model existence lemma, constructing model from suitable theory

• Maximal consistency and the existence property

• Any maximally consistent theory with the existence property has a model

• Any consistent theory has (up to variable-renaming) a maximally consistent extension with the existence property

Suggested exercises: proof of 14.1.3, 14.1.4, 14.1.5, 14.1.15, 14.2.16.

DATEMay 30, 2024
Related News
    • 0

      Logic and Computation II

      Prerequisite"Logic and Computation I". Those who did not take our course last semester had better consult with the lecturer or TA before enrolling this course. Please find more information on "Logic and Computation I" at AbstractIn the last semester, we studied basics of computable functions, first-order logic and complexity theory. In this semester, we...

    • 1

      Mathematical Statistics

      IntroductionMathematical statistics is the application of probability theory to data analysis. It involves collecting, organizing, analyzing, interpreting, and presenting data using rigorous mathematical methods. This course covers the basic principles and techniques of statistical theory for graduate students.Lecturer IntroSixu Liu received her Ph.D. degree from Peking University in 2019. She ...