A concise introduction to mathematical logic (Q5920562)

This is a translation of the author's textbook (in German) on mathematical logic [Einführung in die mathematische Logik. Wiesbaden: Vieweg (2001; Zbl 0989.03001)]. The book's goal is to provide three main theorems of mathematical logic: 1) Gödel's theorem about semantical completeness of predicate calculus with respect to the set of valid first-order predicate formulas (true in every possible interpretation); 2) Church's theorem about algorithmic undecidability of predicate calculus; 3) Gödel's theorem about syntactic incompleteness of axiomatic arithmetic (with respect to the semantically true formulas of arithmetic). A result of Tarski is expounded on the way: the set of all true formulas of arithmetic is not arithmetical. The solution of Hilbert's 10th problem is outlined. Resolution and Prolog programming are also introduced. Recursive function theory is presented in the amount necessary for the proof of the main theorems. Formalisms are described in the form of Gentzen's natural inference, which is nearest to the usual run of mathematical reasoning. The chosen notions have allowed the author to come to the three main theorems most quickly and economically, and to make their proofs transparent and elegant. New in the educational literature is the chapter about Gödel's modal logic G, which formalizes the part of the proof theory which concerns self-referential formulas (they state their own unprovability). The book is organized in seven chapters: 1) Propositional logic; 2) Predicate logic; 3) Gödel's completeness; 4) Elements of logic programming; 5) Elements of model theory; 6) Incompleteness and undecidability; 7) Self-reference theory. There are exercises. The book can be useful for students and for lecturers who prepare a mathematical logic course at a (technical) university.