8.3 The consistency proof -- 8.4 Applications of the consistency proof -- 8.5 Second-order arithmetic -- Problems -- Chapter 9: Set Theory -- 9.1 Axioms for sets -- 9.2 Development of set theory -- 9.3 Ordinals -- 9.4 Cardinals -- 9.5 Interpretations of set theory -- 9.6 Constructible sets -- 9.7 The axiom of constructibility -- 9.8 Forcing -- 9.9 The independence proofs -- 9.10 Large cardinals -- Problems -- Appendix The Word Problem -- Index.

The Fourth Edition of this long-established text retains all the key features of the previous editions, covering the basic topics of a solid first course in ...

Classic text considersgeneral theory of computability, computable functions, operations on computable functions, Turing machines self-applied, unsolvable decision problems, applications of general theory, mathematical logic, Kleene hierarchy, computable functionals, classification of unsolvable decision problems and more.

This exploration of a notorious mathematical problem is the work of the man who discovered the solution. Written by an award-winning professor at Stanford University, it employs intuitive explanations as well as detailed mathematical proofs in a self-contained treatment. This unique text and reference is suitable for students and professionals. 1966 edition. Copyright renewed 1994.

In this article, Lucas maintains the falseness of Mechanism - the attempt to explain minds as machines - by means of Incompleteness Theorem of Gödel. Gödel’s theorem shows that in any system consistent and adequate for simple arithmetic there are formulae which cannot be proved in the system but that human minds can recognize as true; Lucas points out in his turn that Gödel’s theorem applies to machines because a machine is the concrete instantiation of a formal system: therefore, for (...) every machine consistent and able of doing simple arithmetic, there is a formula that it can’t produce as true but that we can see to be true, and so human minds and machines have to be different. Lucas considers as well in this article some possible objections to his argument: for any Gödelian formula we could, for instance, construct a machine able to produce it or we could put the Gödelian formulae that we had proved as axioms of a further machine. However - as Lucas underlines - for every of such machines we could again formulate another Gödelian formula, the Gödelian formula of these machines, that they are not able to proof but that we can recognize as true. More general arguments, such as the possibility to escape Gödelian argument by suggesting that Gödel’s theorem applies to consistent systems while we could be inconsistent ones, are moreover refuted by Lucas by maintaining that our inconsistency corresponds to occasional malfunctioning of a machine and not to his normal inconsistency; indeed, a inconsistent machine is characterized by producing any statement, on the contrary human being are selective and not disposed to assert anything. (shrink)

This is an extensively revised edition of Mr. Quine's introduction to abstract set theory and to various axiomatic systematizations of the subject. The treatment of ordinal numbers has been strengthened and much simplified, especially in the theory of transfinite recursions, by adding an axiom and reworking the proofs. Infinite cardinals are treated anew in clearer and fuller terms than before. Improvements have been made all through the book; in various instances a proof has been shortened, a theorem strengthened, a space-saving (...) lemma inserted, an obscurity clarified, an error corrected, a historical omission supplied, or a new event noted. (shrink)

First English translation of revolutionary paper that established that even in elementary parts of arithmetic, there are propositions which cannot be proved or disproved within the system. Introduction by R. B. Braithwaite.

Hailed by the Bulletin of the American Mathematical Society as "undoubtedly a major addition to the literature of mathematical logic," this volume examines the essential topics and theorems of mathematical reasoning. No background in logic is assumed, and the examples are chosen from a variety of mathematical fields. Starting with an introduction to symbolic logic, the first eight chapters develop logic through the restricted predicate calculus. Topics include the statement calculus, the use of names, an axiomatic treatment of the statement (...) calculus, descriptions, and equality. Succeeding chapters explore abstract set theory—with examinations of class membership as well as relations and functions—cardinal and ordinal arithmetic, and the axiom of choice. An invaluable reference book for all mathematicians, this text is suitable for advanced undergraduates and graduate students. Numerous exercises make it particularly appropriate for classroom use. (shrink)

This article defends a modest version of the Physical Church-Turing thesis (CT). Following an established recent trend, I distinguish between what I call Mathematical CT—the thesis supported by the original arguments for CT—and Physical CT. I then distinguish between bold formulations of Physical CT, according to which any physical process—anything doable by a physical system—is computable by a Turing machine, and modest formulations, according to which any function that is computable by a physical system is computable by a Turing machine. (...) I argue that Bold Physical CT is not relevant to the epistemological concerns that motivate CT and hence not suitable as a physical analog of Mathematical CT. The correct physical analog of Mathematical CT is Modest Physical CT. I propose to explicate the notion of physical computability in terms of a usability constraint, according to which for a process to count as relevant to Physical CT, it must be usable by a finite observer to obtain the desired values of a function. Finally, I suggest that proposed counterexamples to Physical CT are still far from falsifying it because they have not been shown to satisfy the usability constraint. (shrink)

Most scholars think of David Hilbert's program as the most demanding and ideologically motivated attempt to provide a foundation for mathematics, and because they see technical obstacles in the way of realizing the program's goals, they regard it as a failure. Against this view, Curtis Franks argues that Hilbert's deepest and most central insight was that mathematical techniques and practices do not need grounding in any philosophical principles. He weaves together an original historical account, philosophical analysis, and his own development (...) of the meta-mathematics of weak systems of arithmetic to show that the true philosophical significance of Hilbert's program is that it makes the autonomy of mathematics evident. The result is a vision of the early history of modern logic that highlights the rich interaction between its conceptual problems and technical development. (shrink)

This is a critical analysis of the first part of Go¨del’s 1951 Gibbs lecture on certain philosophical consequences of the incompleteness theorems. Go¨del’s discussion is framed in terms of a distinction between objective mathematics and subjective mathematics, according to which the former consists of the truths of mathematics in an absolute sense, and the latter consists of all humanly demonstrable truths. The question is whether these coincide; if they do, no formal axiomatic system (or Turing machine) can comprehend the mathematizing (...) potentialities of human thought, and, if not, there are absolutely unsolvable mathematical problems of diophantine form. (shrink)

Graduate-level historical study is ideal for students intending to specialize in the topic, as well as those who only need a general treatment. Part I discusses traditional and symbolic logic. Part II explores the foundations of mathematics, emphasizing Hilbert’s metamathematics. Part III focuses on the philosophy of mathematics. Each chapter has extensive supplementary notes; a detailed appendix charts modern developments.

This is a survey of Gödel's perennial preoccupations with the limits of finitism, its relations to constructivity, and the significance of his incompleteness theorems for Hilbert's program, using his published and unpublished articles and lectures as well as the correspondence between Bernays and Gödel on these matters. There is also an important subtext, namely the shadow of Hilbert that loomed over Gödel from the beginning to the end.

This lively introduction to mathematical logic, easily accessible to non-mathematicians, offers an historical survey, coverage of predicate calculus, model theory, Godel’s theorems, computability and recursivefunctions, consistency and independence in axiomatic set theory, and much more. Suggestions for Further Reading. Diagrams.

I consider here several versions of finitism or conceptions that try to work around postulating sets of infinite size. Restricting oneself to the so-called potential infinite seems to rest either on temporal readings of infinity (or infinite series) or on anti-realistic background assumptions. Both these motivations may be considered problematic. Quine’s virtual set theory points out where strong assumptions of infinity enter into number theory, but is implicitly committed to infinity anyway. The approaches centring on the indefinitely large and the (...) use of schemata would provide a work-around to circumvent usage of actual infinities if we had a clear understanding of how schemata work and where to draw the conceptual line between the indefinitely large and the infinite. Neither of this seems to be clear enough. Versions of strict finitism in contrast provide a clear picture of a (realistic) finite number theory. One can recapture standard arithmetic without being committed to actual infinities. The major problem of them is their usage of a paraconsistent logic with an accompanying theory of inconsistent objects. If we are, however, already using a paraconsistent approach for other reasons (in semantics, epistemology or set theory), we get finitism for free. This strengthens the case for paraconsistency. (shrink)

Classical interpretations of Goedels formal reasoning, and of his conclusions, implicitly imply that mathematical languages are essentially incomplete, in the sense that the truth of some arithmetical propositions of any formal mathematical language, under any interpretation, is, both, non-algorithmic, and essentially unverifiable. However, a language of general, scientific, discourse, which intends to mathematically express, and unambiguously communicate, intuitive concepts that correspond to scientific investigations, cannot allow its mathematical propositions to be interpreted ambiguously. Such a language must, therefore, define mathematical truth (...) verifiably. We consider a constructive interpretation of classical, Tarskian, truth, and of Goedel's reasoning, under which any formal system of Peano Arithmetic---classically accepted as the foundation of all our mathematical Languages---is verifiably complete in the above sense. We show how some paradoxical concepts of Quantum mechanics can, then, be expressed, and interpreted, naturally under a constructive definition of mathematical truth. (shrink)

Another exceptionally fine text by Suppes. Designed for those who can follow a mathematical argument, but presupposes no special knowledge of mathematics or symbolic logic. The system developed is that of Zermelo-Fraenkel. Especially noteworthy is the discussion of the exact role played by the various axioms.--N. D. B., Jr.

The material contained in this book is based on lectures given by Cohen at Harvard in 1965. It consists of a presentation of logic, set theory and other material, culminating in Cohen's ingenious proof of the independence of the continuum hypothesis and the axiom of choice. Since this proof is certainly one of the major developments in modern mathematics, Cohen's book is something of a necessity for every serious student of the foundations of set theory and mathematics. In addition to (...) Cohen's proof, the book also contains a chapter on Gödel's proof of the consistency of the continuum hypothesis and the axiom of choice, and a good deal of other material of general interest.—H. P. K. (shrink)