Mathematical Logic

Deduction: Introductory Symbolic Logic, 2nd Edition by Daniel Bonevac (Blackwell) Near the end of the eighteenth century, Immanuel Kant wrote that logic was a closed and completed subject, to which nothing significant had been contributed since the time of Aristotle and to which nothing significant remained to be contributed. Many logic students today receive a similar impression from their introductory logic courses, except that Russell and Whitehead have assumed the venerated position that Aristotle held in Kant's time.

But logic is not cut‑and‑dried. It is open‑ended and filled with activity, excitement, and controversy. Research on understanding reasoning in natural language is active and growing; many critical issues remain to be settled. Exposing students to the excitement of logical research is the chief aim of this book.

Deduction is a comprehensive introduction to contemporary symbolic logic. It presents classical first‑order logic as efficiently and elegantly as possible. It uses a tree system based on the work of Gentzen, Beth, Hintikka, and Jeffrey, as well as a natural deduction system inspired by that of Kalish and Montague. Both are very natural and easy to learn, with minimal complexity in rules. In particular, the definition of a formula excludes free variables, and the deduction system uses Show fines; the com­bination allows rules (e.g., univeral introduction) to be stated very simply.

Deduction’s main innovation, however, is its final part, which contains chapters on variants and extensions of classical logic: many‑valued logic (including fuzzy and intuitionistic logic), modal logic, deontic logic, counterfactuals, common‑sense reasoning, and quantified modal logic. These have been areas of great logical and philosophical interest over the past 40 years, but few other textbooks treat them in any depth. Deduc­tion makes these areas accessible to introductory students. All chapters have discussions of the underlying semantics in intuitive terms. All present both truth tree and deduction systems. The treatments of many‑valued logic and common‑sense reasoning are new to this edition.

These variants and extensions of classical logic merit attention for several reasons. First, the resources of natural language far outstrip those of classical logic. Many arguments in English and other natural languages depend on nontruth‑functional connectives that have no representation in classical systems. Second, classical logic at best roughly approximates what is arguably the most important connective in English, if. Devising more accurate theories of if has motivated much research in contempor­ary logic, including that covered in the chapters on modal logic, counter­factuals, and common‑sense reasoning in this book. Finally, studying variants and extensions of classical logic helps one understand what it is like to think as a logician. It communicates a mode of thinking, illustrat­ing how logicians construct and evaluate theories. For that reason, it is perhaps the best way to understand what logic is.

Several features of Deduction prove especially useful in the classroom. First, the semantic and proof‑theoretic techniques presented here are simple and powerful. The truth tree method is very easy to teach and to learn. The natural deduction system is as straightforward as such a system can be. The pattern of rules is easy to understand; most connectives have introduction and exploitation rules. The system's form greatly simplifies deductive rules and strategies. Neither the tree system nor the deduction system uses free variables; instantiation always involves a constant or closed function term. Indeed, formulas never contain free variables. For­mulas always correspond to sentences.

Second, Deduction takes natural language more seriously than many logic texts do. To teach symbolization, for example, Bonevac  does more than offer examples and suggestions; he outlines strategies that almost add up to an algorithm for a fragment of English. That helps students learn symboliza­tion faster and more successfully. It teaches them about the limitations of logical systems, as they see what translates into formal notation only with a loss of meaning and what does not translate at all. Finally, it helps students become more careful readers and writers.

Third, Deduction supplies instructors and students with a large bank of problems of varying levels of difficulty. Many are crafted to illustrate logical techniques, but many are also drawn from real‑world texts on a wide variety of topics. The problem sets of this edition have been care­fully graded from simple to quite difficult examples.

From Frege to Godel: A Source Book in Mathematical Logic, 1879-1931 by Jean Van Heijenoort (Harvard University Press) This reprint of the classic anthology is nonparallel guide to principle texts. Gathered together in this book are the fundamental texts of the great classical period in modern logic. A complete translation of Gottlob Frege's Begriffsschrift--which opened a great epoch in the history of logic by fully presenting propositional calculus and quantification theory--begins the volume. The texts that follow depict the emergence of set theory and foundations of mathematics, two new fields on the borders of logic, mathematics, and philosophy. Essays trace the trends that led to Principia mathematica, the appearance of modern paradoxes, and topics including proof theory, the theory of types, axiomatic set theory, and Löwenheim's theorem. The volume concludes with papers by Herbrand and by Gödel, including the latter's famous incompleteness paper. "There can be no doubt that the book is a valuable contribution to the logical literature and that it will certainly spread the knowledge of mathematical logic and its history in the nineteenth and twentieth centuries." --Andrzej Mostowski, Synthese "It is difficult to describe this book without praising it...[From Frege to Gödel] is, in effect, the record of an important chapter in the history of thought. No serious student of logic or foundations of mathematics will want to be without it." --Review of Metaphysics

Lectures in Mathematical Logic: The Algebra of Models Volume 1 by Waltar Felscher (Gordon and Breach Science Publishers) These three books of Lectures on Mathematical Logic, destined for students of mathematics or computer science, in their third or fourth year at the university, as well as for their instructors. The were written as the traditional combination of textbook and monograph: while the titles of chapters and sections will sound familiar to those moderately acquainted with logic, their content and its presentation is likely to be new also to the more experienced reader. In particular, concepts have been set up such that the proofs do not act as mousetraps, from which the reader cannot escape without acknowledging the desired result, but make it obvious why they entail their result with an inner necessity. In so far, the book expects from the reader a certain maturity; while accessible to students, it also will be helpful to lecturers who look for motivations of procedures which they may only have come to know in the form of dry prescriptions.

Lectures in Mathematical Logic: The Algebra of Models Volume 1 is a beginners' course devoted to the semantical relation of con­sequence, studied first for equations and then for propositional logic, open predicate logic and quantifier logic. Considering semantical satisfaction in structures, it must be set theoretical in the widest sense, and its central theorems turn out to be equivalent to a set theoretical principle, the prime ideal axiom. The simple case of the logic of equations in Chapter 6 suggests an algebraic approach, connecting semantical consequence with the genera­tion of suitable congruence relations, and this can be carried over to quanti­fier logic in Chapter 15. In the same way, Birkhoff's characterization of equationally defined classes of algebras in Chapter 7 carries over to the characterization of elementary classes in Chapter 17. Still, what is being done here is not algebraic logic where (in the case of cylindric or polyadic algebras say) new algebraic structures would be studied in their own right: algebra here is pursued only to that extent which is required for a perspi­cuous analysis of the (semantical) concepts of logic. A useful conceptual tool for this purpose is the consideration of Boolean valued (instead of only 2‑valued) structures; a more technical, but not less important tool are the substitution maps studied in Chapter 13. Outside this general theme of an algebra of models, various more combinatorial topics are developed, of which I here only mention the extensions of Menger's parser to terms without or with parentheses in Chapter 5, Whitman's solution of the word problem for free lattices in Chapter 6, the study of normal forms in Chapter 9 and of their term rewriting algorithms in Chapter 10, and a new proof of the finiteness theorem for quantifier logic, employing the notion of straight formulas and presented at the beginning of Chapter 14.

Lectures in Mathematical Logic: Calculi for Derivations and Deductions Volume 2 by Waltar Felscher (Gordon and Breach Science Publishers) In this volume, logic starts from the observation that in everyday argument, as hrought forward say by a lawyer, statements are transformed linguistically, connect­ing them in formal ways irrespective of their contents. Understanding such argu­ments as deductive situations, or "sequents" in the technical terminology, the transformations between them can be expressed as logical rules. This leads to Gentzen's calculi of derivations, presented first for positive logic: and then, depend­ing on the requirements made on the behaviour of negation, for minimal, intuitionist and classical logic. Identifying interdeducible formulas, each of these calculi gives rise to a lattice-like ordered structure. Describing the generation of filters in these structures leads to corresponding modus ponens calculi, and these turn out to be semantically complete because they express the algorithms generating semantical consequences, as obtained in volume I of these lectures. The operators transforming derivations from one type of calculus into the other are also studied with respect to changes of the lengths of derivations, and operators eliminating defined predicate and function symbols are described explicitly. The book ends with the algorithms producing the results of Gentzen's midsequent theorem and Herbrand's theorem for prenex formulas.

This volume will prove useful to graduates and researchers in the field of math­ematical logic. It is also a reference on logic for professionals in pure mathematics and theoretical computer science.

Excerpt:

Lectures in Mathematical Logic: Calculi for Derivations and Deductions Volume 2 is a combinatorial study of derivations and deductions. Gentzen's rules of sequential logic are motivated for the positive connectives in Chap­ter 1 and for quantifiers in Chapter 8 ; the rules for negation are analysed in Chapter 4 , and classical logic is discussed in Chapter 5 with particular attention to the Peirce rule. Chapter 2 is devoted to the familiar cut elimi­nation going down from the top; Chapter 3 presents Mints' algorithm of cut elimination going upwards. In the case of classical logic, the usual superexponential bounds are improved to twofold exponential ones, but reasons of space have prevented me from including a discussion of Hudel­mayer's bounds for intuitionistic logic. Chapter 6 is an excursion into algebra, associating to every sequential calculus the class of algebras defined by the equations given by interdeducible formulas; the classes of algebras arising in this manner are then characterized by generators of the unit filter of their free algebras. These are just the axioms for modus ponens calculi generating such filters, and in Chapter 7 the modus ponens calculi corres­ponding to the sequential calculi are set up - with sharp upper bounds for the lengths of proofs obtained under the transformations between sequential derivations and modus ponens deductions.

The premisses of the non-critical quantifier rules can be formulated in two ways: either referring to replacement instances of the formula to be quanti­fied, in which the quantifying variable is replaced by a term t which is free for that formula, or instead referring to substitution instances which involve a built-in renaming of the bound variables which occur in t. For the first case, Chapter 8 contains the known result that cut elimination works for derivations with an endsequent in which no variable occurs both free and that cut elimination must always work, and the second part of Chapter 8 contains a syntactical proof for this fact. Chapter 9 develops modus ponens calculi for quantifier logic based on the algorithmic descriptions of conse­quence in Chapter 1.15 ; Chapter 10 contains various applications such as the conservativeness of equality logic, conservativeness of extensions with predicate and function symbols, the midsequent theorem and Herbrand's theorem.

The semantical approach to logic starts from truth and from mathematical structures, and it proceeds to an analysis of the relation of semantical con­sequence, as well as to various, and sometimes surprising, properties of models of axiom systems. It is a mathematician's approach, talking about a world of - preferably infinite - sets, as it was developed in Book 1 of this work.

The approach to be followed in the present Book 2 may be described as argumentative or linguistic in that it starts from the rhetorical and literary practice of presenting collections of (usually successive) arguments, con­nected by logical laws referring to their linguistic form and independent from their contents. In view of its formal linguistic character, this approach may also be called syntactical, and the treatment of linguistic objects will use techniques, which, in mathematics, are counted as combinatorial. The combinatorial rules then describe particular collections of arguments as de­ductions and derivations in a uniform manner, and the systems of such rules make up what are called logical calculi. In so far, that approach can also be called algorithmic or computational - although the actual design of programs for devices, performing such computations, will not be discussed here.

While there are many ways to define when a collection of arguments may be called a deduction, singling out a particular one among them can hardly avoid being arbitrary and accidental. It was the basic idea of Gentzen to begin, rather, with an abstract notion of general deductive situations, and to develop the foundation of logic from an analysis of the transformations be­tween such deductive situations, as effected by the logical connectives and quantifiers occurring in them. The setting then is that of deductive situa­tions, and meant to say that a statement can, in an unspecified manner, be deduced from a collection M of assumptions. Con­sider now a deductive situation that involves, either as its conclusion v or among its assumptions M, a logically composite statement. An analysis of the linguistic meaning, of the propositional connectives or of the quantifiers governing this composition, will lead to conditions, acceptable to every con­sensus (fair and reasonable), about the form of one or several other deduc­tive situations which (a) involve the components of that compo­site statement and (b) are such that the deducibility may be lin­guistically concluded from the deducibilities as premises. Con­densing such relationships between premisses and conclusions into logical rates, I arrive at a calculus of deductive situations, built from the weakest requirements which those logical transformations between deductions are to obev  for the case of positive connectives this will be carried out immediately.

Various applications are discussed in Chapter 10, beginning with the cor­respondence between sequent and modus ponens calculi in the presence of quantifiers, and ending with a detailed discussion of Herbrand's theorem.

Lectures in Mathematical Logic: The Logic of Arithmetic Volume 3 by Waltar Felscher (Gordon and Breach Science Publishers) is mainly about logical properties of arithmetic, namely the decidability and consistency of some of its weaker fragments, and the undecidability and the unprovability of consistency for stronger ones. For the arithmetic of successor and order in Chapter 1, and for Presburger arithmetic in Chapter 2, decidability is obtained from quantifier elimination, and this, being established syntactically, will entail consistency proofs. In Chapter 3 the Liar paradox is discussed and is used to analyze, in a nontechnical manner, the undefinability of truth and the incompleteness of provability; this Chapter requires no mathematical knowledge and may be accessible to the educated layman. General incompleteness theorems are set up in Chapter 4 ; here encodings are‑assumed to be given and certain encoding functions are assumed to be representable. In Chapters 5 and 6 basic facts about recursive functions and relations are developed. In Chapter 8 undecidability of provability from axioms in an arithmetized language is connected with the representability of recursive relations; this is applied in order to find a uniformization of recursive functions, and also in order obtain the SMN‑property, needed to conclude that this uniformization is isomorphic to other uniformizations known from computability theory. Chapter 9 discusses Robinson's arithmetic and Church's result on the undecidability of pure logic.

In Chapter 10 it is shown that Peano arithmetic PA (actually, already Heyting arithmetic) can be extended conservatively by function symbols for primitive recursive functions. There follows a discussion of primitive recursive arithmetic in which it is emphasized that recursion equations and their consequences now become provable as free variable formulas. In Chapter 11 the unprovability of the consistency of PA is shown by verifying the Bernays‑Lob provability conditions. In order to see that El‑formulas imply their provability, the process of internalization is isolated and studied. It is hoped that the presentation of the basic results of these last two chapters, both in their strength and their limitations, will make them accessible to a wider readership.

More about the book's content will be said in its introduction and in the introductory sections of its chapters.

Headline 3

insert content here

WT Main | About WT | Review Links | Contact | Review Sources | Search