An excellent introduction to mathematical logic, this book provides readers with a sound knowledge of the most important approaches to the subject, stressing the use of logical methods in attacking nontrivial problems. It covers the logic of classes, of propositions, of propositional functions, and the general syntax of language, with a brief introduction that also illustrates applications to so-called undecidability and incompleteness theorems. Other topics include the simple proof of the completeness of the theory of combinations, Church's (...) theorem on the recursive unsolvability of the decision problem for the restricted function calculus, and the demonstrable properties of a formal system as a criterion for its acceptability. 1950 ed. (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.

As to the misconceptions: In the first place, the existence of "undecidable propositions" or "unsolvable problems" has only remote connections with the failure of excluded middle. More precisely, from the fact that a certain problem is unsolvable, one cannot infer that the affirmative and negative answers to that problem are both incorrect. Both Gödel's and Church's theorems were originally proved for systems with the excluded middle, i.e. for systems in which 'p or not p' is provable for every proposition 'p'; (...) though in the light of Gödel's theorem there are propositions 'p' such that neither 'p' nor 'not p' is provable in those systems. Careful distinction should be made between the following locutions. (shrink)

I first seriously contemplated writing a book on degree theory in 1976 while I was visiting the University of Illinois at Chicago Circle. There was, at that time, some interest in ann-series book about degree theory, and through the encouragement of Bob Soare, I decided to make a proposal to write such a book. Degree theory had, at that time, matured to the point where the local structure results which had been the mainstay of the earlier papers in the area (...) were finding a steadily increasing number of applications to global degree theory. Michael Yates was the first to realize that the time had come for a systematic study of the interaction between local and global degree theory, and his papers had a considerable influence on the content of this book. During the time that the book was being written and rewritten, there was an explosion in the number of global theorems about the degrees which were proved as applications of local theorems. The global results, in turn, pointed the way to new local theorems which were needed in order to make further progress. I have tried to update the book continuously, in order to be able to present some of the more recent results. It is my hope to introduce the reader to some of the fascinat ing combinatorial methods of Recursion Theory while simultaneously showing how to use these methods to prove some beautiful global theorems about the degrees. (shrink)

"A valuable collection both for original source material as well as historical formulations of current problems."-- The Review of Metaphysics "Much more than a mere collection of papers . . . a valuable addition to the literature."-- Mathematics of Computation An anthology of fundamental papers on undecidability and unsolvability by major figures in the field, this classic reference opens with Godel's landmark 1931 paper demonstrating that systems of logic cannot admit proofs of all true assertions of arithmetic. Subsequent (...) papers by Godel, Church, Turing, and Post single out the class of recursive functions as computable by finite algorithms. Additional papers by Church, Turing, and Post cover unsolvable problems from the theory of abstract computing machines, mathematical logic, and algebra, and material by Kleene and Post includes initiation of the classification theory of unsolvable problems. Suitable for graduate and undergraduate courses. 1965 ed. (shrink)

The contributions in the book examine the historical and contemporary manifestations of organized crime, the symbiotic relationship between legitimate and ...

This book offers a historical explanation of important philosophical problems in logic and mathematics, which have been neglected by the official history of modern logic. It offers extensive information on Gottlob Frege’s logic, discussing which aspects of his logic can be considered truly innovative in its revolution against the Aristotelian logic. It presents the work of Hilbert and his associates and followers with the aim of understanding the revolutionary change in the axiomatic method. Moreover, it (...) offers useful tools to understand Tarski’s and Gödel’s work, explaining why the problems they discussed are still unsolved. Finally, the book reports on some of the most influential positions in contemporary philosophy of mathematics, i.e., Maddy’s mathematical naturalism and Shapiro’s mathematical structuralism. Last but not least, the book introduces Biancani’s Aristotelian philosophy of mathematics as this is considered important to understand current philosophical issue in the applications of mathematics. One of the main purposes of the book is to stimulate readers to reconsider the Aristotelian position, which disappeared almost completely from the scene in logic and mathematics in the early twentieth century. (shrink)

A non-classical logic is proposed that extends classical logic and set theory as conservatively as possible with respect to three domains: the logic of natural language, the logcal foundations of mathematics, and the logical-philosophical paradoxes. A universal mechanics of consciousness connects these domains, and its best witness is the liar paradox. Its solution rests formally on a subject-object partition, mentally arising and disappearing perpetually. All deep paradoxes are paradoxes of consciousness. There are two kinds, solvable ones and (...) unsolvable ones. The solvable ones disappear by proper partitions, the unsolvable ones arise by inevitably improper partitions enforced by the natural worldview. The categorial distinctions of subject and object, certainty and truth, consciousness and being, inner freedom and outer constraint, psyche and physis, mental practice and formal theory indicate an immemorial mystical monism of consciousness without which mathematical Platonism could not survive. (shrink)

This book presents new results in computability theory, a branch of mathematical logic and computer science that has become increasingly relevant in recent years. The field's connections with disparate areas of mathematical logic and mathematics more generally have grown deeper, and now have a variety of applications in topology, group theory, and other subfields. This monograph establishes new directions in the field, blending classic results with modern research areas such as algorithmic randomness. The significance of the (...) book lies not only in the depth of the results contained therein, but also in the fact that the notions the authors introduce allow them to unify results from several subfields of computability theory. (shrink)

Demonstrating the different roles that logic plays in the disciplines of computer science, mathematics, and philosophy, this concise undergraduate textbook covers select topics from three different areas of logic: proof theory, computability theory, and nonclassical logic. The book balances accessibility, breadth, and rigor, and is designed so that its materials will fit into a single semester. Its distinctive presentation of traditional logic material will enhance readers' capabilities and mathematical maturity. The proof theory portion presents classical (...) propositional logic and first-order logic using a computer-oriented (resolution) formal system. Linear resolution and its connection to the programming language Prolog are also treated. The computability component offers a machine model and mathematical model for computation, proves the equivalence of the two approaches, and includes famous decision problems unsolvable by an algorithm. The section on nonclassical logic discusses the shortcomings of classical logic in its treatment of implication and an alternate approach that improves upon it: Anderson and Belnap's relevance logic. Applications are included in each section. The material on a four-valued semantics for relevance logic is presented in textbook form for the first time. Aimed at upper-level undergraduates of moderate analytical background, Three Views of Logic will be useful in a variety of classroom settings. Gives an exceptionally broad view of logic. Treats traditional logic in a modern format. Presents relevance logic with applications. Provides an ideal text for a variety of one-semester upper-level undergraduate courses. (shrink)

Many books explain what is known about the universe. This book investigates what cannot be known. Rather than exploring the amazing facts that science, mathematics, and reason have revealed to us, this work studies what science, mathematics, and reason tell us cannot be revealed. In The Outer Limits of Reason, Noson Yanofsky considers what cannot be predicted, described, or known, and what will never be understood. He discusses the limitations of computers, physics, logic, and our own thought processes. Yanofsky (...) describes simple tasks that would take computers trillions of centuries to complete and other problems that computers can never solve; perfectly formed English sentences that make no sense; different levels of infinity; the bizarre world of the quantum; the relevance of relativity theory; the causes of chaos theory; math problems that cannot be solved by normal means; and statements that are true but cannot be proven. He explains the limitations of our intuitions about the world -- our ideas about space, time, and motion, and the complex relationship between the knower and the known. Moving from the concrete to the abstract, from problems of everyday language to straightforward philosophical questions to the formalities of physics and mathematics, Yanofsky demonstrates a myriad of unsolvable problems and paradoxes. Exploring the various limitations of our knowledge, he shows that many of these limitations have a similar pattern and that by investigating these patterns, we can better understand the structure and limitations of reason itself. Yanofsky even attempts to look beyond the borders of reason to see what, if anything, is out there. (shrink)

In a recent paper Berto introduces a semantic system for a logic of imagination, intended as positive conceivability, and aboutness of imaginative acts. This system crucially adopts elements of both the semantics of conditionals and the semantics of analytical implications in order to account for the central logical traits of the notion of truth in an act of imagination based on an explicit input. The main problem left unsolved is to put forward a complete set of axioms for the (...) proposed system. In the present paper I offer a solution to this problem by providing a complete axiomatization of a generalization of the original semantics. The difficulty in proving completeness lies in the fact that the modalities that capture the notion of truth in an act of imagination are neither standard nor minimal, so that the construction of the canonical model and the proof of the truth lemma are to be substantially modified. (shrink)

This book presents a set of historical recollections on the work of Martin Davis and his role in advancing our understanding of the connections between logic, computing, and unsolvability. The individual contributions touch on most of the core aspects of Davis’ work and set it in a contemporary context. They analyse, discuss and develop many of the ideas and concepts that Davis put forward, including such issues as contemporary satisfiability solvers, essential unification, quantum computing and generalisations of Hilbert’s (...) tenth problem. The book starts out with a scientific autobiography by Davis, and ends with his responses to comments included in the contributions. In addition, it includes two previously unpublished original historical papers in which Davis and Putnam investigate the decidable and the undecidable side of Logic, as well as a full bibliography of Davis’ work. As a whole, this book shows how Davis’ scientific work lies at the intersection of computability, theoretical computer science, foundations of mathematics, and philosophy, and draws its unifying vision from his deep involvement in Logic. (shrink)

The fundamental ideas concerning computation and recursion naturally find their place at the interface between logic and theoretical computer science. The contributions in this book, by leaders in the field, provide a picture of current ideas and methods in the ongoing investigations into the pure mathematical foundations of computability theory. The topics range over computable functions, enumerable sets, degree structures, complexity, subrecursiveness, domains and inductive inference. A number of the articles contain introductory and background material which it is (...) hoped will make this volume an invaluable resource for specialists and non-specialists alike. (shrink)

Russell’s substitutional theory conferred philosophical advantages over the simple type theory it was to emulate. However, it faced propositional paradoxes, and in a 1906 paper “On ‘Insolubilia’ and Their Solution by Symbolic Logic”, he modified the theory to block these paradoxes while preserving Cantor’s results. My aim is to draw out several quandaries for the interpretation of the role of substitution in Russell’s logic. If he was aware of the substitutional (_p_0_a_0) paradox in 1906, why did he advertise (...) “Insolubilia” as a solution to the Epimenides? If he was dissatisfied with the solution, as his correspondence suggests, why did he go on to publish it? Why did substitution reappear with orders in “Mathematical Logic as Based on the Theory of Types” if he had rejected a hierarchy of orders as intolerable? I offer the following as possible explanations: he construed the “logical Epimenides” as a version of the _p_0_a_0 paradox; his dissatisfaction with the “Insolubilia” solution was philosophical, not technical; and substitution re-emerged because he hoped for a new philosophical gloss on orders. Whether or not my explanations are correct, these issues must be addressed in accounting for Russell’s reasons for ramification. (shrink)

Informal construction -- Formal construction -- Limiting results.

Let $\mathcal A$ be a mathematical structure with an additional relation $R$. The author is interested in the degree spectrum of $R$, either among computable copies of $\mathcal A$ when $(\mathcal A,R)$ is a ``natural'' structure, or (to make this rigorous) among copies of $(\mathcal A,R)$ computable in a large degree d. He introduces the partial order of degree spectra on a cone and begin the study of these objects. Using a result of Harizanov--that, assuming an effectiveness condition on (...) $\mathcal A$ and $R$, if $R$ is not intrinsically computable, then its degree spectrum contains all c.e. degrees--the author shows that there is a minimal non-trivial degree spectrum on a cone, consisting of the c.e. degrees. (shrink)

林毓材(1948~ ),云南师范大学数学系教授,任计算机科学教研室主任与研究室主任,云南省科委应用基础研究基金委员会委员,云南省软件评测委员会主任委员等职.

The remainder set A⟂B of a set of sentences A modulo a set of sentences B is the set of all maximal subsets of A not implying any element of B. A remainder equation is an expression containing remainder sets, such as {A} = B⟂X, in which at least one set is unknown. Solutions to some classes of remainder equations are reported, and some unsolved problems are listed.

Kurt Gödel, mathematician and logician, was one of the most influential thinkers of the twentieth century. Gödel fled Nazi Germany, fearing for his Jewish wife and fed up with Nazi interference in the affairs of the mathematics institute at the University of Göttingen. In 1933 he settled at the Institute for Advanced Study in Princeton, where he joined the group of world-famous mathematicians who made up its original faculty. His 1940 book, better known by its short title, The Consistency of (...) the Continuum Hypothesis, is a classic of modern mathematics. The continuum hypothesis, introduced by mathematician George Cantor in 1877, states that there is no set of numbers between the integers and real numbers. It was later included as the first of mathematician David Hilbert's twenty-three unsolved math problems, famously delivered as a manifesto to the field of mathematics at the International Congress of Mathematicians in Paris in 1900. In The Consistency of the Continuum Hypothesis Gödel set forth his proof for this problem. In 1999, Time magazine ranked him higher than fellow scientists Edwin Hubble, Enrico Fermi, John Maynard Keynes, James Watson, Francis Crick, and Jonas Salk. He is most renowned for his proof in 1931 of the 'incompleteness theorem,' in which he demonstrated that there are problems that cannot be solved by any set of rules or procedures. His proof wrought fruitful havoc in mathematics, logic, and beyond. (shrink)

This paper surveys John von Neumann's work on the mathematical foundations of quantum theories in the light of Hilbert's Sixth Problem concerning the geometrical axiomatization of physics. We argue that in von Neumann's view geometry was so tied to logic that he ultimately developed a logical interpretation of quantum probabilities. That motivated his abandonment of Hilbert space in favor of von Neumann algebras, specifically the type II1II1 factors, as the proper limit of quantum mechanics in infinite dimensions. Finally, (...) we present the reasons why his axiomatic program remained an “unsolved problem” in mathematical physics. A recent unpublished result by Huzimiro Araki, proving that no algebra with a tracial state defined on it, such as the type II1II1 factors, can support any (regular) representation of the canonical commutation relations, is also reviewed and its consequences for von Neumann's projects are discussed. (shrink)

We consider first order modal logic C firstly defined by Carnap in “Meaning and Necessity” [1]. We prove elimination of nested modalities for this logic, which gives additionally the Skolem-Löwenheim theorem for C. We also evaluate the degree of unsolvability for C, by showing that it is exactly 0′. We compare this logic with the logics of Henkin quantifiers, Σ11 logic, and SO. We also shortly discuss properties of the logic C in finite models.

In addition to a somewhat detailed exposition of certain portions of what may be called the book-work of formal logic, the following pages contain a number of problems worked out in detail and unsolved problems, by means of which the student may test his command over logical processes. In the expository portions of Parts I, II, and III, dealing respectively with terms, propositions, and syllogisms, the traditional lines are in the main followed, though with certain modifications; e.g., in the (...) systematisation of immediate inferences, and in several points of detail in connexion with the syllogism. For purposes of illustration Euler's diagrams are employed to a greater extent than is usual in English manuals. In Part IV, which contains a generalisation of logical processes in their application to complex inferences, a somewhat new departure is taken. So far as I am aware this part constitutes the first systematic attempt that has been made to deal with formal reasonings of the most complicated character without the aid of mathematical or other symbols of operation, and without abandoning the ordinary non-equational or predicative form of proposition. This attempt has on the whole met with greater success than I had anticipated; and I believe that the methods formulated will be found to be both as easy and as effective as the symbolical methods of Boole and his followers. The book concludes with a general and sure method of solution of what Professor Jevons called the inverse problem, and which he himself seemed to regard as soluble only by a series of guesses. (shrink)