MATH 4L03/6L03, Fall 2018
INTRODUCTION TO MATHEMATICAL LOGIC
Is it possible to completely automate the process of "doing mathematics"? To answer this question, we first need to make notions like "statement", "proof" and "truth" mathematically rigorous. This will lead us to predicate logic, the most popular formalization of mathematical thinking, and we will connect these notions in Gödel's completeness theorem. But does this mean the answer to our question is "yes"? Not so fast: one proof technique--among the first encountered by mathematics students--is missing from this formalization, namely the proof by induction technique. It turns out--and this is Gödel's famous incompleteness theorem--that if we do also admit proofs by induction, then in any mathematical system in predicate logic that includes basic arithmetic (and which do not!?) the notions of "provability" and of "truth" are not the same. Most of this course is taken up by Gödel's completeness theorem. The proof of his incompleteness theorem is trickier in full detail, but we will give an overview that explains his ingenious twist on the liar's paradox leading to the proof.
INSTRUCTOR: P. Speissegger
First order logic, deduction systems, completeness and compactness theorems, model theory.
Three lectures; one term
Prerequisite(s): MATH 3E03 or 3GR3