
06482147
b
2016c.00561
Nievergelt, Yves
Logic, mathematics, and computer science. Modern foundations with practical applications. 2nd edition, originally published under the title Foundations of logic and mathematics. Applications to computer science and cryptography.
New York, NY: Springer (ISBN 9781493932221/hbk; 9781493932238/ebook). xii, 391~p. (2015).
2015
New York, NY: Springer
EN
E35
E65
E55
M45
M55
textbook
logic
set theory
logic in computer science
logic in social sciences
applications of logic
arrow's theorem
Nash equilibria
foundations of mathematics
Zbl 1043.00002
doi:10.1007/9781493932238
This introductory textbook on logic and set theory stands out in that it does not only present its mathematical content in a thorough and accessible way, but also giving historical and philosophical background, explaining the role of logic and set theory in the foundations of mathematics as well as applications outside of mathematics. The last aspect is rarely encountered in textbooks on mathematical logic, but the relevance of mathematical logic for automatic theorem proving and even in aeronautics explained in the text not only broadens the horizon, but should only help to motivate the reader of a less theoretical persuasion to learn the topics. Other than the title might suggest, the book contains virtually no material on recursion theory or complexity theory. The relations to computer science are contained in applications of logic in computer science and various algorithmically explicit proofs, such as the proof of the deduction theorem, where a method is given for transforming a proof of $H\vdash S$ into one of $H\rightarrow S$. After some preliminary discussion on the use of logic in everyday life, the first chapter introduces propositional logic rather formally. Derived rules of the propositional calculus are connected by their connection to actual mathematical proof practice. A nice feature of this chapter is that it does not simply present one axiomatization, but discusses various alternatives, such as Kleene's, Church's, Frege's and Tarski's axioms and compares them; Section 7 also considers multivalued logics. The second chapter then introduces quantifiers and firstorder predicate calculus. Chapters 36 are concerned with set theory. Chapter 3 particularly emphasizes the connection between `informal' proofs and their formal counterpart by discussing for many examples the argument in the vernacular and proceeding to explain how to formalize proofs in the logical framework developed before. Chapter 4 discusses induction and recursive definitions, developing the basic laws of arithmetic from mere definitions and constructing natural numbers, integers and rationals. Transfinite induction is introduced in Chapter 5, while Chapter 6 discusses the axiom of choice, in particular proving the equivalence of various common formulations. A rather unique feature for a mathematical logic textbook is the final Chapter 7, which focuses on applications of the logical and settheoretical framework outside of mathematics, giving three examples that led to Nobel prizes in economics, namely Nash equilibria, Arrow's impossibility theorem and the optimal matching algorithm. In all cases, structural features of realworld situations are abstracted, reformulated in terms of sets, functions and relations and then solved in this setting. The book contains many exercises that should serve to further the understanding of the reader; many, but not all, solutions are given in an appendix, allowing lecturers who follow the book to use some of the problems as homework problems. The book should be accessible to readers with a basic general background in mathematics.
Merlin Carl (Konstanz)