Computability and Logic has become a classic because of its accessibility to students without a mathematical background and because it covers not simply the staple topics of an intermediate logic course, such as Godel’s incompleteness theorems, but also a large number of optional topics, from Turing’s theory of computability to Ramsey’s theorem. Including a selection of exercises, adjusted for this edition, at the end of each chapter, it offers a new and simpler treatment of the representability of recursive functions, a (...) traditional stumbling block for students on the way to the Godel incompleteness theorems. (shrink)

This collection, nearly all chosen by Boolos himself shortly before his death, includes thirty papers on set theory, second-order logic, and plural quantifiers; ...

The Unprovability of Consistency is concerned with connections between two branches of logic: proof theory and modal logic. Modal logic is the study of the principles that govern the concepts of necessity and possibility; proof theory is, in part, the study of those that govern provability and consistency. In this book, George Boolos looks at the principles of provability from the standpoint of modal logic. In doing so, he provides two perspectives on a debate in modal logic that has persisted (...) for at least thirty years between the followers of C. I. Lewis and W. V. O. Quine. The author employs semantic methods developed by Saul Kripke in his analysis of modal logical systems. The book will be of interest to advanced undergraduate and graduate students in logic, mathematics and philosophy, as well as to specialists in those fields. (shrink)

In this festschrift for the eminent philosopher Hilary Putnam, a team of distinguished philosophers write on a broad range of topics and thus reflect the remarkably fertile and provocative research of Putnam himself. The volume is not merely a celebration of a man, but also a report on the state of philosophy in a number of significant areas. The essays fall naturally into three groups: a central core on the theme of conventionality and content in the philosophy of mind, language, (...) and science, and two smaller sections on the relationship of ethics and language, and on the philosophy of logic and aesthetics.In this festschrift for the eminent philosopher Hilary Putnam, a team of distinguished philosophers write on a broad range of topics and thus reflect the remarkably fertile and provocative research of Putnam himself. The volume is not merely a celebration of a man, but also a report on the state of philosophy in a number of significant areas. The essays fall naturally into three groups: a central core on the theme of conventionality and content in the philosophy of mind, language, and science, and two smaller sections on the relationship of ethics and language, and on the philosophy of logic and aesthetics. (shrink)

This paper contains a close analysis of Frege's proofs of the axioms of arithmetic §§70-83 of Die Grundlagen, with special attention to the proof of the existence of successors in §§82-83. Reluctantly and hesitantly, we come to the conclusion that Frege was at least somewhat confused in those two sections and that he cannot be said to have outlined, or even to have intended, any correct proof there. The proof he sketches is in many ways similar to that given in (...) Grundgesetze der Arithmetik, but fidelity to what Frege wrote in Die Grundlagen and in Grundgesetze requires us to reject the charitable suggestion that it was this (beautiful) proof that he had in mind in §§82-83. (shrink)

Cantor's diagonal argument provides an indirect proof that there is no one-one function from the power set of a set A into A. This paper provides a somewhat more constructive proof of Cantor's theorem, showing how, given a function f from the power set of A into A, one can explicitly define a counterexample to the thesis that f is one-one.

G is the result of adjoining the schema (qAA)qA to K; the axioms of G* are the theorems of G and the instances of the schema qAA and the sole rule of G* is modus ponens. A sentence is -provable if it is provable in P(eano) A(rithmetic) by one application of the -rule; equivalently, if its negation is -inconsistent in PA. Let -Bew(x) be the natural formalization of the notion of -provability. For any modal sentence A and function mapping sentence (...) letters to sentences of PA, inductively define A by: p = (p) (p a sentence letter); = ; (AB)su}= (A B); and (qA)= -Bew(A )(S) is the numeral for the Gödel number of the sentence S). Then, applying techniques of Solovay (Israel Journal of Mathematics 25, pp. 287–304), we prove that for every modal sentence A, G A iff for all , PA A ; and for every modal sentence A, G* A iff for all , A is true. (shrink)

The bimodal provability logics of analysis for ordinary provability and provability by the ω-rule are shown to be fragments of certain ‘polymodal’ logics introduced by G.K. Dzhaparidze. In addition to modal axiom schemes expressing Löb's theorem for the two kinds of provability, the logics treated here contain a scheme expressing that if a statement is consistent, then the statement that it is consistent is provable by the ω-rule.