This two-volume work bridges the gap between introductory expositions of logic or set theory on one hand, and the research literature on the other. It can be used as a text in an advanced undergraduate or beginning graduate course in mathematics, computer science, or philosophy. The volumes are written in a user-friendly conversational lecture style that makes them equally effective for self-study or class use. Volume 1 includes formal proof techniques, a section on applications of compactness (including nonstandard analysis), a generous dose of computability and its relation to the incompleteness phenomenon, and the first presentation of a complete proof of Godel's 2nd incompleteness since Hilbert and Bernay's Grundlagen theorem.

A comprehensive and user-friendly guide to the use of logic in mathematical reasoning Mathematical Logic presents a comprehensive introduction to formal methods of logic and their use as a reliable tool for deductive reasoning. With its user-friendly approach, this book successfully equips readers with the key concepts and methods for formulating valid mathematical arguments that can be used to uncover truths across diverse areas of study such as mathematics, computer science, and philosophy. The book develops the logical tools for writing proofs by guiding readers through both the established "Hilbert" style of proof writing, as well as the "equational" style that is emerging in computer science and engineering applications. Chapters have been organized into the two topical areas of Boolean logic and predicate logic. Techniques situated outside formal logic are applied to illustrate and demonstrate significant facts regarding the power and limitations of logic, such as: Logic can certify truths and only truths. Logic can certify all absolute truths (completeness theorems of Post and Gödel). Logic cannot certify all "conditional" truths, such as those that are specific to the Peano arithmetic. Therefore, logic has some serious limitations, as shown through Gödel's incompleteness theorem. Numerous examples and problem sets are provided throughout the text, further facilitating readers' understanding of the capabilities of logic to discover mathematical truths. In addition, an extensive appendix introduces Tarski semantics and proceeds with detailed proofs of completeness and first incompleteness theorems, while also providing a self-contained introduction to the theory of computability. With its thorough scope of coverage and accessible style, Mathematical Logic is an ideal book for courses in mathematics, computer science, and philosophy at the upper-undergraduate and graduate levels. It is also a valuable reference for researchers and practitioners who wish to learn how to use logic in their everyday work.

This survey of computability theory offers the techniques and tools that computer scientists (as well as mathematicians and philosophers studying the mathematical foundations of computing) need to mathematically analyze computational processes and investigate the theoretical limitations of computing. Beginning with an introduction to the mathematisation of “mechanical process” using URM programs, this textbook explains basic theory such as primitive recursive functions and predicates and sequence-coding, partial recursive functions and predicates, and loop programs. Advanced chapters cover the Ackerman function, Tarski’s theorem on the non-representability of truth, Goedel’s incompleteness and Rosser’s incompleteness theorems, two short proofs of the incompleteness theorem that are based on Lob's deliverability conditions, Church’s thesis, the second recursion theorem and applications, a provably recursive universal function for the primitive recursive functions, Oracle computations and various classes of computable functionals, the Arithmetical hierarchy, Turing reducibility and Turing degrees and the priority method, a thorough exposition of various versions of the first recursive theorem, Blum’s complexity, Hierarchies of primitive recursive functions, and a machine-independent characterisation of Cobham's feasibly computable functions.

This book is ideal for a first or second year discrete mathematics course for mathematics, engineering, and computer science majors. The author has extensively class-tested early conceptions of the book over the years and supplements mathematical arguments with informal discussions to aid readers in understanding the presented topics. “Safe” – that is, paradox-free – informal set theory is introduced following on the heels of Russell’s Paradox as well as the topics of finite, countable, and uncountable sets with an exposition and use of Cantor’s diagonalisation technique. Predicate logic “for the user” is introduced along with axioms and rules and extensive examples. Partial orders and the minimal condition are studied in detail with the latter shown to be equivalent to the induction principle. Mathematical induction is illustrated with several examples and is followed by a thorough exposition of inductive definitions of functions and sets. Techniques for solving recurrence relations including generating functions, the O- and o-notations, and trees are provided. Over 200 end of chapter exercises are included to further aid in the understanding and applications of discrete mathematics.

Learn the skills and acquire the intuition to assess the theoretical limitations of computer programming Offering an accessible approach to the topic, Theory of Computation focuses on the metatheory of computing and the theoretical boundaries between what various computational models can do and not do—from the most general model, the URM (Unbounded Register Machines), to the finite automaton. A wealth of programming-like examples and easy-to-follow explanations build the general theory gradually, which guides readers through the modeling and mathematical analysis of computational phenomena and provides insights on what makes things tick and also what restrains the ability of computational processes. Recognizing the importance of acquired practical experience, the book begins with the metatheory of general purpose computer programs, using URMs as a straightforward, technology-independent model of modern high-level programming languages while also exploring the restrictions of the URM language. Once readers gain an understanding of computability theory—including the primitive recursive functions—the author presents automata and languages, covering the regular and context-free languages as well as the machines that recognize these languages. Several advanced topics such as reducibilities, the recursion theorem, complexity theory, and Cook's theorem are also discussed. Features of the book include: A review of basic discrete mathematics, covering logic and induction while omitting specialized combinatorial topics A thorough development of the modeling and mathematical analysis of computational phenomena, providing a solid foundation of un-computability The connection between un-computability and un-provability: Gödel's first incompleteness theorem The book provides numerous examples of specific URMs as well as other programming languages including Loop Programs, FA (Deterministic Finite Automata), NFA (Nondeterministic Finite Automata), and PDA (Pushdown Automata). Exercises at the end of each chapter allow readers to test their comprehension of the presented material, and an extensive bibliography suggests resources for further study. Assuming only a basic understanding of general computer programming and discrete mathematics, Theory of Computation serves as a valuable book for courses on theory of computation at the upper-undergraduate level. The book also serves as an excellent resource for programmers and computing professionals wishing to understand the theoretical limitations of their craft.

Set theory is an autonomous and sophisticated field of mathematics that is extremely successful at analyzing mathematical propositions and gauging their consistency strength. It is as a field of mathematics that both proceeds with its own internal questions and is capable of contextualizing over a broad range, which makes set theory an intriguing and highly distinctive subject. This handbook covers the rich history of scientific turning points in set theory, providing fresh insights and points of view. Written by leading researchers in the field, both this volume and the Handbook as a whole are definitive reference tools for senior undergraduates, graduate students and researchers in mathematics, the history of philosophy, and any discipline such as computer science, cognitive psychology, and artificial intelligence, for whom the historical background of his or her work is a salient consideration - Serves as a singular contribution to the intellectual history of the 20th century - Contains the latest scholarly discoveries and interpretative insights

The final volume in a series of four books presenting the seminal papers from the Caltech-UCLA 'Cabal Seminar'.

Since their inception, the Perspectives in Logic and Lecture Notes in Logic series have published seminal works by leading logicians. Many of the original books in the series have been unavailable for years, but they are now in print once again. Reverse mathematics is a program of research in the foundations of mathematics, motivated by two foundational questions: 'what are appropriate axioms for mathematics?' and 'what are the logical strengths of particular axioms and particular theorems?' This volume, the twenty-first publication in the Lecture Notes in Logic series, contains twenty-four original research papers from respected authors that present exciting new developments in reverse mathematics and subsystems of second order arithmetic since 1998.

Model theory is one of the central branches of mathematical logic. The field has evolved rapidly in the last few decades. This book is an introduction to current trends in model theory, and contains a collection of articles authored by top researchers in the field. It is intended as a reference for students as well as senior researchers.