Undecidable Theories

Author: Alfred Tarski,Andrzej Mostowski,Raphael Mitchel Robinson

Publisher: Elsevier

ISBN: 0444533788

Category: Decidability (Mathematical logic)

Page: 98

View: 2645


Zermelo’s Axiom of Choice

Its Origins, Development, and Influence

Author: G.H. Moore

Publisher: Springer Science & Business Media

ISBN: 1461394783

Category: Mathematics

Page: 412

View: 742

This book grew out of my interest in what is common to three disciplines: mathematics, philosophy, and history. The origins of Zermelo's Axiom of Choice, as well as the controversy that it engendered, certainly lie in that intersection. Since the time of Aristotle, mathematics has been concerned alternately with its assumptions and with the objects, such as number and space, about which those assumptions were made. In the historical context of Zermelo's Axiom, I have explored both the vagaries and the fertility of this alternating concern. Though Zermelo's research has provided the focus for this book, much of it is devoted to the problems from which his work originated and to the later developments which, directly or indirectly, he inspired. A few remarks about format are in order. In this book a publication is indicated by a date after a name; so Hilbert 1926, 178 refers to page 178 of an article written by Hilbert, published in 1926, and listed in the bibliography.

Introduction to Logic

and to the Methodology of Deductive Sciences

Author: Alfred Tarski

Publisher: Courier Corporation

ISBN: 0486318893

Category: Mathematics

Page: 272

View: 5877

This classic undergraduate treatment examines the deductive method in its first part and explores applications of logic and methodology in constructing mathematical theories in its second part. Exercises appear throughout.

Set Theory and the Continuum Hypothesis

Author: Paul J. Cohen,Martin Davis

Publisher: Courier Corporation

ISBN: 0486469212

Category: Mathematics

Page: 154

View: 8289

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.

Alfred Tarski

Life and Logic

Author: Anita Burdman Feferman,Solomon Feferman

Publisher: Cambridge University Press

ISBN: 9780521802406

Category: Biography & Autobiography

Page: 425

View: 5008

Alfred Tarski, one of the greatest logicians of all time, is widely thought of as 'the man who defined truth'. His mathematical work on the concepts of truth and logical consequence are cornerstones of modern logic, influencing developments in philosophy, linguistics and computer science. Tarski was a charismatic teacher and zealous promoter of his view of logic as the foundation of all rational thought, a bon-vivant and a womanizer, who played the 'great man' to the hilt. Born in Warsaw in 1901 to Jewish parents, he changed his name and converted to Catholicism, but was never able to obtain a professorship in his home country. A fortuitous trip to the United States at the outbreak of war saved his life and turned his career around, even while it separated him from his family for years. By the war's end he was established as a professor of mathematics at the University of California, Berkeley. There Tarski built an empire in logic and methodology that attracted students and distinguished researchers from all over the world. From the cafes of Warsaw and Vienna to the mountains and deserts of California, this first full length biography places Tarski in the social, intellectual and historical context of his times and presents a frank, vivid picture of a personally and professionally passionate man, interlaced with an account of his major scientific achievements.

The Undecidable

Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions

Author: Martin Davis

Publisher: Courier Corporation

ISBN: 9780486432281

Category: Mathematics

Page: 413

View: 2979

"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 is ideally suited as a text for graduate and undergraduate courses in logic, philosophy, and foundations of mathematics. It is also appropriate for self-study. The text 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. Supplementary items include corrections, emendations, and added commentaries by Godel, Church, and Kleene for this volume's original publication, along with a helpful commentary by the editor.

Set Theory and its Philosophy

A Critical Introduction

Author: Michael Potter

Publisher: Clarendon Press

ISBN: 0191556432

Category: Philosophy

Page: 360

View: 2139

Michael Potter presents a comprehensive new philosophical introduction to set theory. Anyone wishing to work on the logical foundations of mathematics must understand set theory, which lies at its heart. Potter offers a thorough account of cardinal and ordinal arithmetic, and the various axiom candidates. He discusses in detail the project of set-theoretic reduction, which aims to interpret the rest of mathematics in terms of set theory. The key question here is how to deal with the paradoxes that bedevil set theory. Potter offers a strikingly simple version of the most widely accepted response to the paradoxes, which classifies sets by means of a hierarchy of levels. What makes the book unique is that it interweaves a careful presentation of the technical material with a penetrating philosophical critique. Potter does not merely expound the theory dogmatically but at every stage discusses in detail the reasons that can be offered for believing it to be true. Set Theory and its Philosophy is a key text for philosophy, mathematical logic, and computer science.

On Formally Undecidable Propositions of Principia Mathematica and Related Systems

Author: Kurt Gödel

Publisher: Courier Corporation

ISBN: 9780486669809

Category: Mathematics

Page: 72

View: 9063

In 1931, a young Austrian mathematician published an epoch-making paper containing one of the most revolutionary ideas in logic since Aristotle. Kurt Giidel maintained, and offered detailed proof, that in any arithmetic system, even in elementary parts of arithmetic, there are propositions which cannot be proved or disproved within the system. It is thus uncertain that the basic axioms of arithmetic will not give rise to contradictions. The repercussions of this discovery are still being felt and debated in 20th-century mathematics. The present volume reprints the first English translation of Giidel's far-reaching work. Not only does it make the argument more intelligible, but the introduction contributed by Professor R. B. Braithwaite (Cambridge University}, an excellent work of scholarship in its own right, illuminates it by paraphrasing the major part of the argument. This Dover edition thus makes widely available a superb edition of a classic work of original thought, one that will be of profound interest to mathematicians, logicians and anyone interested in the history of attempts to establish axioms that would provide a rigorous basis for all mathematics. Translated by B. Meltzer, University of Edinburgh. Preface. Introduction by R. B. Braithwaite.

Three Views of Logic

Mathematics, Philosophy, and Computer Science

Author: Donald W. Loveland,Richard E. Hodel,S. G. Sterrett

Publisher: Princeton University Press

ISBN: 140084875X

Category: Mathematics

Page: 344

View: 6364

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

Roads to Infinity

The Mathematics of Truth and Proof

Author: John C. Stillwell

Publisher: CRC Press

ISBN: 1439865507

Category: Mathematics

Page: 250

View: 3475

Winner of a CHOICE Outstanding Academic Title Award for 2011! This book offers an introduction to modern ideas about infinity and their implications for mathematics. It unifies ideas from set theory and mathematical logic, and traces their effects on mainstream mathematical topics of today, such as number theory and combinatorics. The treatment is historical and partly informal, but with due attention to the subtleties of the subject. Ideas are shown to evolve from natural mathematical questions about the nature of infinity and the nature of proof, set against a background of broader questions and developments in mathematics. A particular aim of the book is to acknowledge some important but neglected figures in the history of infinity, such as Post and Gentzen, alongside the recognized giants Cantor and Gödel.

Axiom of Choice

Author: Horst Herrlich

Publisher: Springer

ISBN: 3540342680

Category: Mathematics

Page: 198

View: 9436

AC, the axiom of choice, because of its non-constructive character, is the most controversial mathematical axiom. It is shunned by some, used indiscriminately by others. This treatise shows paradigmatically that disasters happen without AC and they happen with AC. Illuminating examples are drawn from diverse areas of mathematics, particularly from general topology, but also from algebra, order theory, elementary analysis, measure theory, game theory, and graph theory.

The Foundations of Mathematics

Author: Kenneth Kunen

Publisher: N.A

ISBN: 9781904987147

Category: Mathematics

Page: 251

View: 1749

Mathematical logic grew out of philosophical questions regarding the foundations of mathematics, but logic has now outgrown its philosophical roots, and has become an integral part of mathematics in general. This book is designed for students who plan to specialize in logic, as well as for those who are interested in the applications of logic to other areas of mathematics. Used as a text, it could form the basis of a beginning graduate-level course. There are three main chapters: Set Theory, Model Theory, and Recursion Theory. The Set Theory chapter describes the set-theoretic foundations of all of mathematics, based on the ZFC axioms. It also covers technical results about the Axiom of Choice, well-orderings, and the theory of uncountable cardinals. The Model Theory chapter discusses predicate logic and formal proofs, and covers the Completeness, Compactness, and Lowenheim-Skolem Theorems, elementary submodels, model completeness, and applications to algebra. This chapter also continues the foundational issues begun in the set theory chapter. Mathematics can now be viewed as formal proofs from ZFC. Also, model theory leads to models of set theory. This includes a discussion of absoluteness, and an analysis of models such as H( ) and R( ). The Recursion Theory chapter develops some basic facts about computable functions, and uses them to prove a number of results of foundational importance; in particular, Church's theorem on the undecidability of logical consequence, the incompleteness theorems of Godel, and Tarski's theorem on the non-definability of truth.

Mathematical Logic

Author: Stephen Cole Kleene

Publisher: Courier Corporation

ISBN: 0486317072

Category: Mathematics

Page: 416

View: 3378

Contents include an elementary but thorough overview of mathematical logic of 1st order; formal number theory; surveys of the work by Church, Turing, and others, including Gödel's completeness theorem, Gentzen's theorem, more.

Incompleteness in the Land of Sets

Author: Melvin Fitting

Publisher: N.A

ISBN: 9781904987345

Category: Mathematics

Page: 142

View: 6279

Russell's paradox arises when we consider those sets that do not belong to themselves. The collection of such sets cannot constitute a set. Step back a bit. Logical formulas define sets (in a standard model). Formulas, being mathematical objects, can be thought of as sets themselves-mathematics reduces to set theory. Consider those formulas that do not belong to the set they define. The collection of such formulas is not definable by a formula, by the same argument that Russell used. This quickly gives Tarski's result on the undefinability of truth. Variations on the same idea yield the famous results of Godel, Church, Rosser, and Post. This book gives a full presentation of the basic incompleteness and undecidability theorems of mathematical logic in the framework of set theory. Corresponding results for arithmetic follow easily, and are also given. Godel numbering is generally avoided, except when an explicit connection is made between set theory and arithmetic. The book assumes little technical background from the reader. One needs mathematical ability, a general familiarity with formal logic, and an understanding of the completeness theorem, though not its proof. All else is developed and formally proved, from Tarski's Theorem to Godel's Second Incompleteness Theorem. Exercises are scattered throughout.

Mathematical Logic for Computer Science

Author: Mordechai Ben-Ari

Publisher: Springer Science & Business Media

ISBN: 1447141296

Category: Mathematics

Page: 346

View: 866

Mathematical Logic for Computer Science is a mathematics textbook with theorems and proofs, but the choice of topics has been guided by the needs of students of computer science. The method of semantic tableaux provides an elegant way to teach logic that is both theoretically sound and easy to understand. The uniform use of tableaux-based techniques facilitates learning advanced logical systems based on what the student has learned from elementary systems. The logical systems presented are: propositional logic, first-order logic, resolution and its application to logic programming, Hoare logic for the verification of sequential programs, and linear temporal logic for the verification of concurrent programs. The third edition has been entirely rewritten and includes new chapters on central topics of modern computer science: SAT solvers and model checking.

Foundations of Mathematical Logic

Author: Haskell Brooks Curry

Publisher: Courier Corporation

ISBN: 9780486634623

Category: Mathematics

Page: 408

View: 7712

Written by a pioneer of mathematical logic, this comprehensive graduate-level text explores the constructive theory of first-order predicate calculus. It covers formal methods — including algorithms and epitheory — and offers a brief treatment of Markov's approach to algorithms. It also explains elementary facts about lattices and similar algebraic systems. 1963 edition.

Set Theory and Logic

Author: Robert R. Stoll

Publisher: Courier Corporation

ISBN: 0486139646

Category: Mathematics

Page: 512

View: 7636

Explores sets and relations, the natural number sequence and its generalization, extension of natural numbers to real numbers, logic, informal axiomatic mathematics, Boolean algebras, informal axiomatic set theory, several algebraic theories, and 1st-order theories.