2023/10/15 by Anton Freund, Freund, Anton
Computer Science · #03-01 #Advanced Algebra and Logic #Computability, Logic, AI Algorithms #FOS: Mathematics #Logic (math.LO) #Logic, Reasoning, and Knowledge
paper · pdf · doi:10.48550/arxiv.2310.09921
openalex publication_date 2023/10/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This introduction begins with a section on fundamental notions of mathematical logic, including propositional logic, predicate or first-order logic, completeness, compactness, the Löwenheim-Skolem theorem, Craig interpolation, Beth's definability theorem and Herbrand's theorem. It continues with a section on Gödel's incompleteness theorems, which includes a discussion of first-order arithmetic and primitive recursive functions. This is followed by three sections that are devoted, respectively, to proof theory (provably total recursive functions and Goodstein sequences for IΣ1), computability (fundamental notions and an analysis of Kőnig's lemma in terms of the low basis theorem) and model theory (ultraproducts, chains and the Ax-Grothendieck theorem). We conclude with some brief introductory remarks about set theory (with more details reserved for a separate lecture). The author uses these notes for a first logic course for undergraduates in mathematics, which consists of 28 lectures and 14 exercise sessions of 90 minutes each. In such a course, it may be necessary to omit some material, which is straightforward since all sections except for the first two are independent of each other.