Structural proof theory is a branch of logic that studies the general structure and properties of logical and mathematical proofs. This book is both a concise introduction to the central results and methods of structural proof theory, and a work of research that will be of interest to specialists. The book is designed to be used by students of philosophy, mathematics and computer science. The book contains a wealth of results on proof-theoretical systems, including extensions of such systems from logic (...) to mathematics, and on the connection between the two main forms of structural proof theory - natural deduction and sequent calculus. The authors emphasize the computational content of logical results. A special feature of the volume is a computerized system for developing proofs interactively, downloadable from the web and regularly updated. (shrink)

Stephen Cole Kleene was one of the greatest logicians of the twentieth century and this book is the influential textbook he wrote to teach the subject to the next generation. It was first published in 1952, some twenty years after the publication of Godel's paper on the incompleteness of arithmetic, which marked, if not the beginning of modern logic. The 1930s was a time of creativity and ferment in the subject, when the notion of computable moved from the realm of (...) philosophical speculation to the realm of science. This was accomplished by the work of Kurt Gode1, Alan Turing, and Alonzo Church, who gave three apparently different precise definitions of computable. When they all turned out to be equivalent, there was a collective realization that this was indeed the right notion. Kleene played a key role in this process. One could say that he was there at the beginning of modern logic. He showed the equivalence of lambda calculus with Turing machines and with Godel's recursion equations, and developed the modern machinery of partial recursive functions. This textbook played an invaluable part in educating the logicians of the present. It played an important role in their own logical education.". (shrink)

By a `denoting phrase' I mean a phrase such as any one of the following: a man, some man, any man, every man, all men, the present King of England, the present King of France, the center of mass of the solar system at the first instant of the twentieth century, the revolution of the earth round the sun, the revolution of the sun round the earth. Thus a phrase is denoting solely in virtue of its form. We may distinguish (...) three cases: (1) A phrase may be denoting, and yet not denote anything; e.g., `the present King of France'. (2) A phrase may denote one definite object; e.g., `the present King of England' denotes a certain man. (3) A phrase may denote ambiguously; e.g. `a man' denotes not many men, but an ambiguous man. The interpretation of such phrases is a matter of considerably difficulty; indeed, it is very hard to frame any theory not susceptible of formal refutation. All the difficulties with which I am acquainted are met, so far as I can discover, by the theory which I am about to explain. (shrink)

The authors investigated the ontological argument computationally. The premises and conclusion of the argument are represented in the syntax understood by the automated reasoning engine PROVER9. Using the logic of definite descriptions, the authors developed a valid representation of the argument that required three non-logical premises. PROVER9, however, discovered a simpler valid argument for God's existence from a single non-logical premise. Reducing the argument to one non-logical premise brings the investigation of the soundness of the argument into better focus. Also, (...) the simpler representation of the argument brings out clearly how the ontological argument constitutes an early example of a ?diagonal argument? and, moreover, one used to establish a positive conclusion rather than a paradox. (shrink)

This essay notes a striking parallel between the original Hilbert‐Bernays treatment of definite descriptions and Russell's theory of logically proper names. The formal language for the original theory is laid out and the implications of a theory of vis a vis the statements that qualify as predications in a logically proper definite descriptions sense of the word ‘predication'different from the espoused by Frege, Russell and Meinong.

By a `denoting phrase' I mean a phrase such as any one of the following: a man, some man, any man, every man, all men, the present King of England, the present King of France, the center of mass of the solar system at the first instant of the twentieth century, the revolution of the earth round the sun, the revolution of the sun round the earth. Thus a phrase is denoting solely in virtue of its form. We may distinguish (...) three cases: (1) A phrase may be denoting, and yet not denote anything; e.g., `the present King of France'. (2) A phrase may denote one definite object; e.g., `the present King of England' denotes a certain man. (3) A phrase may denote ambiguously; e.g. `a man' denotes not many men, but an ambiguous man. The interpretation of such phrases is a matter of considerably difficulty; indeed, it is very hard to frame any theory not susceptible of formal refutation. All the difficulties with which I am acquainted are met, so far as I can discover, by the theory which I am about to explain. (shrink)

In this paper, the authors show that there is a reading of St. Anselm's ontological argument in Proslogium II that is logically valid (the premises entail the conclusion). This reading takes Anselm's use of the definite description "that than which nothing greater can be conceived" seriously. Consider a first-order language and logic in which definite descriptions are genuine terms, and in which the quantified sentence "there is an x such that..." does not imply "x exists". Then, using an ordinary logic (...) of descriptions and a connected greater-than relation, God's existence logically follows from the claims: (a) there is a conceivable thing than which nothing greater is conceivable, and (b) if <em>x</em> doesn't exist, something greater than x can be conceived. To deny the conclusion, one must deny one of the premises. However, the argument involves no modal inferences and, interestingly, Descartes' ontological argument can be derived from it. (shrink)

Despite the renown of ‘On Denoting’, much criticism has ignored or misconstrued Russell's treatment of scope, particularly in intensional, but also in extensional contexts. This has been rectified by more recent commentators, yet it remains largely unnoticed that the examples Russell gives of scope distinctions are questionable or inconsistent with his own philosophy. Nevertheless, Russell is right: scope does matter in intensional contexts. In Principia Mathematica, Russell proves a metatheorem to the effect that the scope of a single occurrence of (...) a description in an extensional context does not matter, provided existence and uniqueness conditions are satisfied. But attempts to eliminate descriptions in more complicated cases may produce an analysis with more occurrences of descriptions than featured in the analysand. Taking alternation and negation to be primitive (as in the first edition of Principia), this can be resolved, although the proof is non-trivial. Taking the Sheffer stroke to be primitive (as proposed by Russell in the second edition), with bad choices of scope the analysis fails to terminate. (shrink)

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.

When philosophers talk about descriptions, usually they have in mind singular definite descriptions such as ‘the finest Greek poet’ or ‘the positive square root of nine’, phrases formed with the definite article ‘the’. English also contains indefinite descriptions such as ‘a fine Greek poet’ or ‘a square root of nine’, phrases formed with the indefinite article ‘a’ (or ‘an’); and demonstrative descriptions (also known as complex demonstratives) such as ‘this Greek poet’ and ‘that tall woman’, formed with the demonstrative articles (...) ‘this’ and ‘that’. Following the custom in philosophy, in this chapter often we use ‘description’ as short for ‘definite description’; and following the custom in linguistics, often we use ‘definite’, ‘indefinite’, and ‘demonstrative’ as shorthand nouns. For the most part we focus on definite and indefinites, although a few words about demonstratives are called for. At the centre of debates about descriptions is the matter of whether they are devices of reference or of predication (simple or higher-order), and much discussion focuses on how various proposals are to be incorporated into broader theories of the semantics of natural language. But philosophical interest goes beyond the confines of linguistics, logic, and the philosophy of language because choices made about the semantics of descriptions have repercussions elsewhere, particularly in epistemology and metaphysics. A simple match of form and meaning appears to fail.1 First, many occurrences of expressions of both forms ‘the φ’ and ‘a φ’ appear to be used to talk about particular individuals. Consider (1). (shrink)

This introduction to the basic ideas of structural proof theory contains a thorough discussion and comparison of various types of formalization of first-order logic. Examples are given of several areas of application, namely: the metamathematics of pure first-order logic (intuitionistic as well as classical); the theory of logic programming; category theory; modal logic; linear logic; first-order arithmetic and second-order logic. In each case the aim is to illustrate the methods in relatively simple situations and then apply them elsewhere in much (...) more complex settings. There are numerous exercises throughout the text. In general, the only prerequisite is a standard course in first-order logic, making the book ideal for graduate students and beginning researchers in mathematical logic, theoretical computer science and artificial intelligence. For the new edition, many sections have been rewritten to improve clarity, new sections have been added on cut elimination, and solutions to selected exercises have been included. (shrink)

Die Leitgedanken meiner Untersuchungen über die Grundlagen der Mathematik, die ich - anknüpfend an frühere Ansätze - seit 1917 in Besprechungen mit P. BERNAYS wieder aufgenommen habe, sind von mir an verschiedenen Stellen eingehend dargelegt worden. Diesen Untersuchungen, an denen auch W. ACKERMANN beteiligt ist, haben sich seither noch verschiedene Mathematiker angeschlossen. Der hier in seinem ersten Teil vorliegende, von BERNAYS abgefaßte und noch fortzusetzende Lehrgang bezweckt eine Darstellung der Theorie nach ihren heutigen Ergebnissen. Dieser Ergebnisstand weist zugleich die Richtung (...) für die weitere Forschung in der Beweistheorie auf das Endziel hin, unsere üblichen Methoden der Mathematik samt und sonders als widerspruchsfrei zu erkennen. Im Hinblick auf dieses Ziel möchte ich hervorheben, daß die zeit weilig aufgekommene Meinung, aus gewissen neueren Ergebnissen von GÖDEL folge die Undurchführbarkeit meiner Beweistheorie, als irrtüm lich erwiesen ist. Jenes Ergebnis zeigt in der Tat auch nur, daß man für die weitergehenden Widerspruchsfreiheitsbeweise den finiten Stand punkt in einer schärferen Weise ausnutzen muß, als dieses bei der Be trachtung der elementaren Formallsmen erforderlich ist. Göttingen, im März 1934 HILBERT Vorwort zur ersten Auflage Eine Darstellung der Beweistheorie, welche aus dem HILBERTschen Ansatz zur Behandlung der mathematisch-logischen Grundlagenpro bleme erwachsen ist, wurde schon seit längerem von HILBERT ange kündigt. (shrink)

A way is found to add axioms to sequent calculi that maintains the eliminability of cut, through the representation of axioms as rules of inference of a suitable form. By this method, the structural analysis of proofs is extended from pure logic to free-variable theories, covering all classical theories, and a wide class of constructive theories. All results are proved for systems in which also the rules of weakening and contraction can be eliminated. Applications include a system of predicate logic (...) with equality in which also cuts on the equality axioms are eliminated. (shrink)

Intermediate Logic is an ideal text for anyone who has taken a first course in logic and is progressing to further study. It examines logical theory, rather than the applications of logic, and does not assume any specific technical grounding. The author introduces and explains each concept and term, ensuring readers have a firm foundation for study. He provides a broad, deep understanding of logic by adopting and comparing a variety of different methods and approaches.

The authors investigated the ontological argument computationally. The premises and conclusion of the argument are represented in the syntax understood by the automated reasoning engine PROVER9. Using the logic of definite descriptions, the authors developed a valid representation of the argument that required three non-logical premises. PROVER9, however, discovered a simpler valid argument for God's existence from a single non-logical premise. Reducing the argument to one non-logical premise brings the investigation of the soundness of the argument into better focus. Also, (...) the simpler representation of the argument brings out clearly how the ontological argument constitutes an early example of a ‘diagonal argument’ and, moreover, one used to establish a positive conclusion rather than a paradox. (shrink)

A way is found to add axioms to sequent calculi that maintains the eliminability of cut, through the representation of axioms as rules of inference of a suitable form. By this method, the structural analysis of proofs is extended from pure logic to free-variable theories, covering all classical theories, and a wide class of constructive theories. All results are proved for systems in which also the rules of weakening and contraction can be eliminated. Applications include a system of predicate logic (...) with equality in which also cuts on the equality axioms are eliminated. (shrink)

In this paper we study the termination behavior of Russell’s description elimination rewrite system. We discuss certain claims made by Kripke (2005) in his paper concerning the possible nontermination of elimination of descriptions.