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

Available for the first time in 20 years, here is the Rudolf Carnap's famous principle of tolerance by which everyone is free to mix and match the rules of ...

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)

We show that Bell inequalities can be violated in the macroscopic world. The macroworld violation is illustrated using an example involving connected vessels of water. We show that whether the violation of inequalities occurs in the microworld or the macroworld, it is the identification of nonidentical events that plays a crucial role. Specifically, we prove that if nonidentical events are consistently differentiated, Bell-type Pitowsky inequalities are no longer violated, even for Bohm's example of two entangled spin 1/2 quantum particles. We (...) show how Bell inequalities can be violated in cognition, specifically in the relationship between abstract concepts and specific instances of these concepts. This supports the hypothesis that genuine quantum structure exists in the mind. We introduce a model where the amount of nonlocality and the degree of quantum uncertainty are parameterized, and demonstrate that increasing nonlocality increases the degree of violation, while increasing quantum uncertainty decreases the degree of violation. (shrink)

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

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)

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

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)

Traditionally, many writers, following Kleene (1952), thought of the Church-Turing thesis as unprovable by its nature but having various strong arguments in its favor, including Turing’s analysis of human computation. More recently, the beauty, power, and obvious fundamental importance of this analysis, what Turing (1936) calls “argument I,” has led some writers to give an almost exclusive emphasis on this argument as the unique justification for the Church-Turing thesis. In this chapter I advocate an alternative justification, essentially presupposed by Turing (...) himself in what he calls “argument II.” The idea is that computation is a special form of mathematical deduction. Assuming the steps of the deduction can be stated in a first order language, the Church-Turing thesis follows as a special case of Gödel’s completeness theorem (first order algorithm theorem). I propose this idea as an alternative foundation for the Church-Turing thesis, both for human and machine computation. Clearly the relevant assumptions are justified for computations presently known. Other issues, such as the significance of Gödel’s 1931 Theorem IX for the Entscheidungsproblem, are discussed along the way. (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.

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.

Aimed at graduate students, research logicians and mathematicians, this much-awaited text covers over 40 years of work on relative classification theory for nonstandard models of arithmetic. The book covers basic isomorphism invariants: families of type realized in a model, lattices of elementary substructures and automorphism groups.

We discuss the foundations of constructive mathematics, including recursive mathematics and intuitionism, in relation to classical mathematics. There are connections with the foundations of physics, due to the way in which the different branches of mathematics reflect reality. Many different axioms and their interrelationship are discussed. We show that there is a fundamental problem in BISH (Bishop’s school of constructive mathematics) with regard to its current definition of ‘continuous function’. This problem is closely related to the definition in BISH of (...) ‘locally compact’. Possible approaches to this problem are discussed. Topology seems to be a key to understanding many issues. We offer several new simplifying axioms, which can form bridges between the various branches of constructive mathematics and classical mathematics (‘reuniting the antipodes’). We give a simplification of basic intuitionistic theory, especially with regard to so-called ‘bar induction’. We then plead for a limited number of axiomatic systems, which differentiate between the various branches of mathematics. Finally, in the appendix we offer BISH an elegant topological definition of ‘locally compact’, which unlike the current definition is equivalent to the usual classical and/or intuitionistic definition in classical and intuitionistic mathematics, respectively. (shrink)

This paper is the first in a two-part series in which we discuss several notions of completeness for systems of mathematical axioms, with special focus on their interrelations and historical origins in the development of the axiomatic method. We argue that, both from historical and logical points of view, higher-order logic is an appropriate framework for considering such notions, and we consider some open questions in higher-order axiomatics. In addition, we indicate how one can fruitfully extend the usual set-theoretic semantics (...) so as to shed new light on the relevant strengths and limits of higher-order logic. (shrink)

Alonzo Church's mathematical work on computability and undecidability is well-known indeed, and we seem to have an excellent understanding of the context in which it arose. The approach Church took to the underlying conceptual issues, by contrast, is less well understood. Why, for example, was "Church's Thesis" put forward publicly only in April 1935, when it had been formulated already in February/March 1934? Why did Church choose to formulate it then in terms of Gödel's general recursiveness, not his own λ (...) -definability as he had done in 1934? A number of letters were exchanged between Church and Paul Bernays during the period from December 1934 to August 1937; they throw light on critical developments in Princeton during that period and reveal novel aspects of Church's distinctive contribution to the analysis of the informal notion of effective calculability. In particular, they allow me to give informed, though still tentative answers to the questions I raised; the character of my answers is reflected by an alternative title for this paper, Why Church needed Gödel's recursiveness for his Thesis. In Section 5, I contrast Church's analysis with that of Alan Turing and explore, in the very last section, an analogy with Dedekind's investigation of continuity. (shrink)

Natural Formalization proposes a concrete way of expanding proof theory from the meta-mathematical investigation of formal theories to an examination of “the concept of the specifically mathematical proof.” Formal proofs play a role for this examination in as much as they reflect the essential structure and systematic construction of mathematical proofs. We emphasize three crucial features of our formal inference mechanism: (1) the underlying logical calculus is built for reasoning with gaps and for providing strategic directions, (2) the mathematical frame (...) is a definitional extension of Zermelo–Fraenkel set theory and has a hierarchically organized structure of concepts and operations, and (3) the construction of formal proofs is deeply connected to the frame through rules for definitions and lemmas. To bring these general ideas to life, we examine, as a case study, proofs of the Cantor–Bernstein Theorem that do not appeal to the principle of choice. A thorough analysis of the multitude of “different” informal proofs seems to reduce them to exactly one. The natural formalization confirms that there is one proof, but that it comes in two variants due to Dedekind and Zermelo, respectively. In this way it enhances the conceptual understanding of the represented informal proofs. The formal, computational work is carried out with the proof search system AProS that serves as a proof assistant and implements the above inference mechanism; it can be fully inspected at (see link below). (shrink)

The construction of a systematic philosophical foundation for logic is a notoriously difficult problem. In Part One I suggest that the problem is in large part methodological, having to do with the common philosophical conception of “providing a foundation”. I offer an alternative to the common methodology which combines a strong foundational requirement with the use of non-traditional, holistic tools to achieve this result. In Part Two I delineate an outline of a foundation for logic, employing the new methodology. The (...) outline is based on an investigation of why logic requires a veridical justification, i.e., a justification which involves the world and not just the mind, and what features or aspect of the world logic is grounded in. Logic, the investigation suggests, is grounded in the formal aspect of reality, and the outline proposes an account of this aspect, the way it both constrains and enables logic, logic's role in our overall system of knowledge, the relation between logic and mathematics, the normativity of logic, the characteristic traits of logic, and error and revision in logic. (shrink)

Abstract: According to the Veridicality Thesis, information requires truth. On this view, smoke carries information about there being a fire only if there is a fire, the proposition that the earth has two moons carries information about the earth having two moons only if the earth has two moons, and so on. We reject this Veridicality Thesis. We argue that the main notions of information used in cognitive science and computer science allow A to have information about the obtaining of (...) p even when p is false. (shrink)

Turing and Church formulated two different formal accounts of computability that turned out to be extensionally equivalent. Since the accounts refer to different properties they cannot both be adequate conceptual analyses of the concept of computability. This insight has led to a discussion concerning which account is adequate. Some authors have suggested that this philosophical debate—which shows few signs of converging on one view—can be circumvented by regarding Church’s and Turing’s theses as explications. This move opens up the possibility that (...) both accounts could be adequate, albeit in their own different ways. In this paper, I focus on the question of whether Church’s thesis can be seen as an explication in the precise Carnapian sense. Most importantly, I address an additional constraint that Carnap puts on the explicative power of axiomatic systems—an axiomatisation explicates when it is clear which mathematical entities form the theory’s intended model—and that implicitly applies to axiomatisations of recursion theory used in Church’s account of computability. To overcome this difficulty, I propose two possible clarifications of the pre-systematic concept of “computability” that can both be captured in recursion theory, and I show how both clarifications avoid an objection arising from Carnap’s constraint. (shrink)

We give a rough statement of the main result. Let D be a compact subset of ℝ3× ℝ. The propagation u of a wave can be noncomputable in any neighborhood of any point of D even though the initial conditions which determine the wave propagation uniquely are computable. A precise statement of the result appears below.

The best known and most widely discussed aspect of Kurt Gödel's philosophy of mathematics is undoubtedly his robust realism or platonism about mathematical objects and mathematical knowledge. This has scandalized many philosophers but probably has done so less in recent years than earlier. Bertrand Russell's report in his autobiography of one or more encounters with Gödel is well known:Gödel turned out to be an unadulterated Platonist, and apparently believed that an eternal “not” was laid up in heaven, where virtuous logicians (...) might hope to meet it hereafter.On this Gödel commented:Concerning my “unadulterated” Platonism, it is no more unadulterated than Russell's own in 1921 when in the Introduction to Mathematical Philosophy … he said, “Logic is concerned with the real world just as truly as zoology, though with its more abstract and general features.” At that time evidently Russell had met the “not” even in this world, but later on under the infuence of Wittgenstein he chose to overlook it.One of the tasks I shall undertake here is to say something about what Gödel's platonism is and why he held it.A feature of Gödel's view is the manner in which he connects it with a strong conception of mathematical intuition, strong in the sense that it appears to be a basic epistemological factor in knowledge of highly abstract mathematics, in particular higher set theory. Other defenders of intuition in the foundations of mathematics, such as Brouwer and the traditional intuitionists, have a much more modest conception of what mathematical intuition will accomplish. (shrink)