This book, written by one of the most distinguished of contemporary philosophers of mathematics, is a fully rewritten and updated successor to the author's earlier The Unprovability of Consistency. Its subject is the relation between provability and modal logic, a branch of logic invented by Aristotle but much disparaged by philosophers and virtually ignored by mathematicians. Here it receives its first scientific application since its invention. Modal logic is concerned with the notions of necessity and possibility. What George Boolos does (...) is to show how the concepts, techniques, and methods of modal logic shed brilliant light on the most important logical discovery of the twentieth century: the incompleteness theorems of Kurt Godel and the 'self-referential' sentences constructed in their proof. The book explores the effects of reinterpreting the notions of necessity and possibility to mean provability and consistency. (shrink)

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)

We give a proof of Gödel's first incompleteness theorem based on Berry's paradox, and from it we also derive the second incompleteness theorem model-theoretically.

According to several commentators, Kurt Godel's incompleteness discoveries were assimilated promptly and almost without objection by his contemporaries - - a circumstance remarkable enough to call for explanation. Careful examination reveals, however, that there were doubters and critics, as well as defenders and rival claimants to priority. In particular, the reactions of Carnap, Bernays, Zermelo, Post, Finsler, and Russell, among others, are considered in detail. Documentary sources include unpublished correspondence from Godel's Nachlass.

In this article the author first described the developments which brought to focus the importance of consistency proofs for mathematics, and which led Hilbert to promote the science of metamathemat-ics. Further comments and remarks concern the (partly analogous) beginnings of the work on the decision problem, Gödel?s theorems and related matters, and general metamathematics. An appendix summarizes a text by the author on completeness and categoricity.

The paper is devoted to the discussion of some philosophical and historical problems connected with the theorem on the undefinability of the notion of truth. In particular the problem of the priority of proving this theorem will be considered. It is claimed that Tarski obtained this theorem independently though he made clear his indebtedness to Gödel’s methods. On the other hand, Gödel was aware of the formal undefinability of truth in 1931, but he did not publish this result. Reasons for (...) that are also considered. (shrink)

What has been the historical relationship between set theory and logic? On the one hand, Zermelo and other mathematicians developed set theory as a Hilbert-style axiomatic system. On the other hand, set theory influenced logic by suggesting to Schröder, Löwenheim and others the use of infinitely long expressions. The questions of which logic was appropriate for set theory - first-order logic, second-order logic, or an infinitary logic - culminated in a vigorous exchange between Zermelo and Gödel around 1930.

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 ...

In Infinity and the Mind, Rudy Rucker leads an excursion to that stretch of the universe he calls the "Mindscape," where he explores infinity in all its forms: potential and actual, mathematical and physical, theological and mundane. Here Rucker acquaints us with Gödel's rotating universe, in which it is theoretically possible to travel into the past, and explains an interpretation of quantum mechanics in which billions of parallel worlds are produced every microsecond. It is in the realm of infinity, he (...) maintains, that mathematics, science, and logic merge with the fantastic. By closely examining the paradoxes that arise from this merging, we can learn a great deal about the human mind, its powers, and its limitations. Using cartoons, puzzles, and quotations to enliven his text, Rucker guides us through such topics as the paradoxes of set theory, the possibilities of physical infinities, and the results of Gödel's incompleteness theorems. His personal encounters with Gödel the mathematician and philosopher provide a rare glimpse at genius and reveal what very few mathematicians have dared to admit: the transcendent implications of Platonic realism. (shrink)

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.

In the first part of this paper we discuss some aspects of Detlefsen's attempt to save Hilbert's Program from the consequences of Godel's Second Incompleteness Theorem. His arguments are based on his interpretation of the long standing and well-known controversy on what, exactly, finitistic means are. In his paper [1] Detlefsen takes the position that there is a form of the ω-rule which is a finitistically valid means of proof, sufficient to prove the consistency of elementary number theory Z. On (...) the other hand, he claims that Z with its first-order logic is not strong enough to allow a formalization of such an ω-rule. This would explain why the unprovability of $\operatorname{Con}(Z)$ in Z does not imply that the consistency of Z cannot be proved by finitistic means. We show that Detlefsen's proposal is unacceptable as originally formulated in [1], but that a reasonable modification of the rule he suggest leads to a partial program already studied for many years. We investigate the scope of such a program in terms of proof-theoretic reducibilities. We also show that this partial program encompasses mathematically important theories studied in the "Reverse Mathematics" program. In order to investigate the provability with such a modified rule, we define new consistency and provability predicates which are weaker than the usual ones. We then investigate their properties, including a few that have no apparent philosophical significance but compare interestingly with the properties of the program based on the iteration of our ω-rule. We determine some of the limitations of such programs, pointing out that these limitations partly explain why partial programs that have been successfully carried out use quite different and substantially more radical extensions of finitistic methods with more general forms of restricted reasoning. (shrink)

I propose to sketch my views on several aspects of the philosophy of mathematics that I take to be especially relevant to philosophy as a whole. The relevance of my discussion would, I think, become more evident, if the reader keeps in mind the function of (the philosophy of) mathematics in philosophy in providing us with more transparent aspects of general issues. I shall consider: (1) three familiar examples; (2) logic and our conceptual frame; (3) communal agreement and objective certainty; (...) (4) the transcommunal universality of mathematics; (5) the big jump to the potential infinite; (6) the reconciliation of local creation with the hypothesis of discovery; (7) Platonism as realism plus conceptualism; (8) foundational studies and mathematical practice; and (9) the decomposition of philosophical disagreements. The views of Gödel and Wittgenstein are emphasized in order to add specificity to the discussions. (shrink)

On June 4, 1925, Hilbert delivered an address to the Westphalian Mathematical Society in Miinster; that was, as a quick calculation will convince you, almost exactly sixty years ago. The address was published in 1926 under the title Über dasUnendlicheand is perhaps Hilbert's most comprehensive presentation of his ideas concerning the finitist justification of classical mathematics and the role his proof theory was to play in it. But what has become of the ambitious program for securing all of mathematics, once (...) and for all? What of proof theory, the very subject Hilbert invented to carry out his program? The Hilbertian ambition reached out too far: in its original form, the program was refuted by Gödel's Incompleteness Theorems. And even allowing more than finitist means in metamathematics, the Hilbertian expectations for proof theory have not been realized: a constructive consistency proof for second-order arithmetic is still out of reach. Nevertheless, remarkable progress has been made. Two separate, but complementary directions of research have led to surprising insights: classical analysis can be formally developed in conservative extensions of elementary number theory; relative consistency proofs can be given by constructive means for impredicative parts of second order arithmetic. The mathematical and metamathematical developments have been accompanied by sustained philosophical reflections on the foundations of mathematics. This indicates briefly the main themes of the contributions to the symposium; in my introductory remarks I want to give a very schematic perspective, that is partly historical and partly systematic. (shrink)

Hilbert's program attempts to show that our mathematical knowledge can be certain because we are able to know for certain the truths of elementary arithmetic. I argue that, in the absence of a theory of mathematical truth, Hilbert does not have a complete theory of our arithmetical knowledge. Further, while his deployment of a Kantian notion of intuition seems to promise an answer to scepticism, there is no way to complete Hilbert's epistemology which would answer to his avowed aims.

It is argued that an instrumentalist notion of proof such as that represented in Hilbert's viewpoint is not obligated to satisfy the conservation condition that is generally regarded as a constraint on Hilbert's Program. A more reasonable soundness condition is then considered and shown not to be counter-exemplified by Godel's First Theorem. Finally, attention is given to the question of what a theory is; whether it should be seen as a "list" or corpus of beliefs, or as a method for (...) selecting beliefs. The significance of this question for assessing "intensional" results like Godel's Second Theorem, and their bearing on Hilbert's Program are discussed. (shrink)

Winner of the Wolf Prize for his contribution to our understanding of the universe, Penrose takes on the question of whether artificial intelligence will ever ...

I propose to consider the question, "Can machines think?" This should begin with definitions of the meaning of the terms "machine" and "think." The definitions might be framed so as to reflect so far as possible the normal use of the words, but this attitude is dangerous, If the meaning of the words "machine" and "think" are to be found by examining how they are commonly used it is difficult to escape the conclusion that the meaning and the answer to (...) the question, "Can machines think?" is to be sought in a statistical survey such as a Gallup poll. But this is absurd. Instead of attempting such a definition I shall replace the question by another, which is closely related to it and is expressed in relatively unambiguous words. The new form of the problem can be described in terms of a game which we call the 'imitation game." It is played with three people, a man (A), a woman (B), and an interrogator (C) who may be of either sex. The interrogator stays in a room apart front the other two. The object of the game for the interrogator is to determine which of the other two is the man and which is the woman. He knows them by labels X and Y, and at the end of the game he says either "X is A and Y is B" or "X is B and Y is A." The interrogator is allowed to put questions to A and B. We now ask the question, "What will happen when a machine takes the part of A in this game?" Will the interrogator decide wrongly as often when the game is played like this as he does when the game is played between a man and a woman? These questions replace our original, "Can machines think?". (shrink)

Wittgenstein's work remains, undeniably, now, that off one of those few philosophers who will be read by all future generations.