Readings in
 Logic

orcmid>
readings>

logic>
2008-08-28 -17:24 -0700


visitors to popular Orcmid's Lair pages
see also:
Readings in Theory of Computation
Readings in Philosophy
Readings in Mathematics
    
    
[Barwise1977]
Barwise, Jon (ed.).  Handbook of Mathematical Logic.  Elsevier Science BV (Amsterdam: 1977).  ISBN 0-444-86388-5 pbk.
     I have misgivings about this book.  When I ordered it, I didn't realize that it was the same book I had owned once before.  Part of the problem is that it seems like there is something missing.   I get the feeling that much of this material only makes sense to those who wrote it (something I have to watch out for also).  Along with that, I dread that there are errors in here that I won't be able to figure out.  I just get the feeling that I am dealing with something careless and that I won't be able to master it.  Even so, I am keeping this one around in anticipation that doors will open and that I will find that the book delivers on its promise.  dh: 2000-11-23
     "The Handbook of Mathematical Logic is an attempt to share with the entire mathematical community some modern developments in logic.  We have selected from the wealth of topics available some of those which deal with the basic concepts of the subject, or are particularly important for applications to other parts of mathematics, or both.
     "Mathematical logic is traditionally divided into four parts: model theory, set theory, recursion theory and proof theory.  We have followed this division ... .  The first chapter or two in each part are introductory in scope.  More advanced chapters follow, as do chapters on applied or applicable parts of mathematical logic.  Each chapter is definitely written for someone who is not a specialist in the field in question. ... 
     "We hope that many mathematicians will pick up this book out of idle curiosity and leaf through it to get a feeling for what is going on in another part of mathematics.  It is hard to imagine a mathematician who could spend ten minutes doing this without wanting to pursue a few chapters, and the introductory sections of others, in some detail.  It is an opportunity that hadn't existed before and is the reason for the Handbook."  -- From the Foreword, p. vii.
  Contents
     Foreword
     Contributors
     Part A: Model Theory
          Guide to Part A
          A.1. An introduction to first-order logic, Jon Barwise
          A.2. Fundamentals of model theory, H. Jerome Keisler
          A.3. Ultraproducts for algebraists, Paul C. Eklof
          A.4. Model completeness, Angus Macintyre
          A.5. Homogenous sets, Michael Morley
          A.6. Infinitesimal analysis of curves and surfaces, K. D. Stroyan
          A.7. Admissible sets and infinitary logic, M. Makkai
          A.8. Doctrines in categorical logic, A. Kock and G. E. Reyes
     Part B: Set Theory
          Guide to Part B
          B.1. Axioms of set theory, J. R. Shoenfield
          B.2. About the axiom of choice, Thomas J. Jech
          B.3. Combinatorics, Kenneth Kunen
          B.4. Forcing, John P. Burgess
          B.5. Constructibility, Keith J. Devlin
          B.6. Martin's Axiom, Mary Ellen Rudin
          B.7. Consistency results in topology, I. Juhász
     Part C: Recursion Theory
          Guide to Part C
          C.1. Elements of recursion theory, Herbert B. Enderton
          C.2. Unsolvable problems, Martin Davis
          C.3. Decidable theories, Michael O. Rabin
          C.4. Degrees of unsolvability: a survey of results, Stephen G. Simpson
          C.5. a-recursion theory, Richard A. Shore
          C.6. Recursion in higher types, Alexander Kechris and Yiannis N. Moschovakis
          C.7. An introduction to inductive definitions, Peter Aczel
          C.8. Descriptive set theory: Projective sets, Donald A. Martin
     Part D: Proof Theory and Constructive Mathematics
          Guide to Part D
          D.1. The incompleteness theorems, C. Smorynski
          D.2. Proof theory: Some applications of cut-elimination, Helmut Schwichtenberg
          D.3. Herbrand's Theorem and Gentzen's notion of a direct proof, Richard Statman
          D.4. Theories of finite type related to mathematical practice, Solomon Feferman
          D.5. Aspects of constructive mathematics, A. S. Troelstra
          D.6. The logic of topoi, Michael P. Fourman
          D.7. The type free lambda calculus, Henk Barendregt
          D.8. A mathematical incompleteness in Peano Arithmetic, Jeff Paris and Leo Harrington
     Author Index
     Subject Index
   
[Bernays1968]
Bernays, Paul.  Axiomatic Set Theory.  With a historical introduction by Abraham A. Fraenkel. 2nd edition.  Studies in Logic and The Foundations of Mathematics.  North-Holland (Amsterdam: 1958, 1968).  Unabridged and unaltered republication by Dover Publications (New York: 1991).  ISBN 0-486-66637-9 pbk.
     The first part of this text, by Abraham Fraenkel, is valuable as a survey of the effort to deal with the inconsistencies that lurked in Cantor's formulation.  Fraenkel presents Zermelo's system in that light, and provides his own modification.  The approaches of Russell, Quine, von Neumann and Bernays are contrasted, among others.  The motivation for a complete axiomatization is to establish the (likely) consistency of the theory, with due respect to Gödel, and to also find ways to embrace as much as possible without crossing the line into inconsistency.  
     Bernays, for his part, provides a detailed axiomatic formulation and traces the origin of his axioms and their consequences and related definitions.   The progression is increasingly abstract, with historical connections accounted for.
     Since ZF (or ZFC) seems destined to stick around, a development of it in more-contemporary language is given by [Suppes1972].  Quine draws further contrast, with more details of von Neumann's approach, while contrasting his own efforts in [Quine1969].  Bernays does not keep the emphasis that von Neumann gave to functions, and that approach, of potential value in computational contexts, must be found elsewhere. -- dh:2002-07-24
   Content
     Preface
     Part I. Historical Introduction
          1. Introductory Remarks
          2. Zermelo's System.  Equality and Extensionality
          3. "Constructive" Axioms of "General" Set Theory
          4. The Axiom of Choice
          5. Axioms of Infinity and of Restriction
          6. Development of Set-Theory from the Axioms of Z
          7. Remarks on the Axiom Systems of von Neumann, Bernays, Gödel
     Part II. Axiomatic Set Theory
          Introduction
          Chapter I.  The Frame of Logic and Class Theory
          Chapter II. The Start of General Set Theory
          Chapter III.  Ordinals; Natural Numbers; Finite Sets
          Chapter IV. Transfinite Recursion
          Chapter V. Power; Order; Wellorder
          Chapter VI.  The Completing Axioms
          Chapter VII.  Analysis; Cardinal Arithmetic; Abstract Theories
          Chapter VIII. Further Strengthening of the Axiom System
     Index of Authors (Part I)
     Index of Symbols (Part II)
     Index of Matters (Part II)
     List of Axioms (Part II)
     Bibliography (Part I and II)
   
[Boole1854]
Boole, George.  An Investigation of the Laws of Thought on which Are Founded the Mathematical Theories of Logic and Probabilities.  Macmillan (Toronto, London: 1854).  Dover edition (New York: 1958) with all corrections made in the text.  ISBN 0-486-60028-9.
   Contents
     Preface
     I. Nature and Design of this Work
     II. Signs and their Laws
     III. Derivation of the Laws
     IV. Division of Propositions
     V. Principles of Symbolic Reasoning
     VI. Of Interpretation
     VII. Of Elimination
     VIII. Of Reduction
     IX. Methods of Abbreviation
     X. Conditions of a Perfect Method
     XI. Of Secondary Propositions
     XII. Methods in Secondary Propositions
     XIII. Clarke and Spinoza
     XIV. Example of Analysis
     XV. Of the Aristotelian Logic
     XVI. Of the Theory of Probabilities
     XVII. General Method in Probabilities
     XVIII. Elementary Illustrations
     XIX. Of Statistical Conditions
     XX. Problems on Causes
     XXI. Probability of Judgments
     XXII. Constitution of the Intellect 
    
[Boolos1993b]
Boolos, George.  The Logic of Provability.  Cambridge University Press (Cambridge: 1993).  ISBN 0-521-48325-5 pbk.
     "When modal logic is applied to the study of provability, it becomes provability logic.  This book is an essay on provability logic."  -- from the Preface, p. ix.
   Content
     Preface
     Introduction
     1. GL and Other Systems of Propositional Logic
     2. Peano Arithmetic
     3. The box as Bew(x)
     4. Semantics for GL and other Modal Logics
     5. Completeness and Decidability of GL and K, K4, T, B, S4, and S5
     6. Canonical Models
     7. On GL
     8. The Fixed Point Theorem
     9. The Arithmetical Completeness Theorems for GL and GLS
     10. Trees for GL
     11. An Incomplete System of Modal Logic
     12. An S4-Preserving Proof-Theoretical Treatment of Modality
     13. Modal Logic within Set Theory
     14. Modal Logic within Analysis
     15. The Joint Provability Logic of Consistency and ω-Consistency
     16. On GLB: The Fixed Point Theorem, Letterless Sentences, and Analysis
     17. Quantified Provability Logic
     18. Quantified Provability Logic with One One-Place Predicate Letter
     Notes
     Bibliography
     Index
     Notation and Symbols
   
[Boolos1998]
Boolos, George.  Burgess, John P., Jeffrey, Richard (ed.).  Logic, Logic, and Logic.  Harvard University Press (Cambridge, MA: 1998).  With Introductions and Afterword by John P. Burgess.  ISBN 0-674-53767-X pbk.
     This collection of articles by George Boolos provides the more accessible works not part of the work on provability theory and not strenuously technical.  There are a number of skeptical accounts on set theory and logic that are useful in understanding pitfalls that abide in formulations such as ZFC.  Whether this provides sufficient cause for caution in ones reliance on the accepted applications of logic and set theory, one will have to divine by examining the topics here more closely.  -- dh:2002-07-26
   Content
     Editorial Preface (John P. Burgess and Richard Jeffrey)
     Editor's Acknowledgments
     I. Studies on Set Theory and the Nature of Logic
          Introduction
          1. The Interative Concept of Set [1971]
          2. Reply to Charles Parsons' "Sets and Classes" [1974b, first publication here]
          3. On Second-Order Logic [1975c]
          4. To Be is to Be a Value of a Variable (or to Be Some Values of Some Variables) [1984e]
          5. Nominalist Platonism [1985c]
          6. Iteration Again [1989a]
          7. Introductory Note to Kurt Gödel's "Some Basic Theorems on the Foundations of Mathematics and their Implications" [1995b]
          8. Must We Believe in Set Theory [1997d]
     II. Frege Studies
          Introduction
          9. Gottlob Frege and the Foundations of Arithmetic 11997b, first publication here]
          10. Reading the Begriffsschrift [1985d]
          11. Saving Frege from Contradiction [1986-87]
          12. The Consistency of Frege's Foundations of Arithmetic [1987a]
          13. The Standard of Equality of Numbers [1990e]
          14. Whence the Contradiction [1993]
          15. 1879? [1994a]
          16. The Advantages of Honest Toil over Theft [1994b]
          17. On the Proof of Frege's Theorem [1996b]
          18. Frege's Theorem and the Peano Postulates [1995a]
          19. Is Hume's Principle Analytic? [1997c]
          20. Die Grundlagen der Arithmetik, §§82-83 (with Richard Heck) [1997]
          21. Constructing Cantorian Counterexamples (with a note by Vann McGee) [1997a]
     III. Various Logical Studies and Lighter Papers
          Introduction
          22. Zooming Down the Slippery Slope [1991]
          23. Don't Eliminate Cut [1984a]
          24. The Justification of Mathematical Induction [1985b]
          25. A Curious Inference [1987b]
          26. A New Proof of the Gödel Incompleteness Theorem [1989b]
          27. On "Seeing" the Truth of the Gödel Sentence [1990b]
          28. Quotational Ambiguity [1995c]
          29. The Hardest Logical Puzzle Ever [1996a]
          30. Gödel's Second Incompleteness Theorem Explained in Words of One Syllable [1994c]
     Afterword
     Bibliography
     Index
   
[Boolos2002]
Boolos, George S., Burgess, John P., Jeffrey, Richard.  Computability and Logic. ed.4.  Cambridge University Press (Cambridge: 2002).  ISBN 0-521-00758-5 pbk.
     The three previous editions, by Boolos and Jeffrey, were published in 1974, 1985, and 1989.  This is one of those books that is restless on my bookshelf.  Is it logic?  Computability?  No logic.  Like that.  I collect my notes here, under Logic, because it is a fitting companion to [Boolos1993b] and [Boolos1998].  More than that, from the very outset the book takes a logical stance, addressing some of the key questions of set theory that impinge on computation and effective computability.  The result is very economical in coming at the key questions around computation and the relationship of computation and logic. -- dh:2002-09-07
   Content
     Preface
     Computability Theory
     1.  Enumerability
     2.  Diagonalization
     3.  Turing Computability
     4.  Uncomputability
     5.  Abacus Computability
     6.  Recursive Functions
     7.  Recursive Sets and Relations
     8.  Equivalent Definitions of Computability
     Basic Metalogic
     9.  A Précis of First-Order Logic: Syntax
     10. A Précis of First-Order Logic: Semantics
     11. The Undecidability of First-Order Logic
     12. Models
     13. The Existence of Models
     14. Proofs and Completeness
     15. Arithmetization
     16. Representability of Recursive Functions
     17. Indefinability, Undecidability, Incompleteness
     18. The Unprovability of Consistency
     Further Topics
     19. Normal Forms
     20. The Craig Interpolation Theorem
     21. Monadic and Dyadic Logic
     22. Second-Order Logic
     23. Arithmetic Definability
     24. Decidability of Arithmetic without Multiplication
     25. Nonstandard Models
     26. Ramsey's Theorem
     27. Modal Logic and Provability
     Hints for Selected Problems
     Annotated Bibliography
     Index
   
[Burgess1998]
Burgess, John P.  Introductions and Afterword in [Boolos1998]
   
[Burgess2002]
Boolos, George S., Burgess, John P., Jeffrey, Richard.  Computability and Logic. ed.4.  Cambridge University Press (Cambridge: 2002).  ISBN 0-521-00758-5 pbk.  See [Boolos2002]
    
[Cantor1915]
Cantor, Georg.  Contributions to the Founding of the Theory of Transfinite Numbers.  Translation, Introduction and Notes by Philip E.  B. Jourdain.  Open Court (London: 1915). Unabridged and unaltered republication by Dover Publications (New York: 1955).  ISBN 0-486-60045-9 pbk.
     "Wierstrass [starting in the 1840's] carried research into the principles of arithmetic farther than it had been carried before.  But we must also realize that there were questions, such as the nature of the whole number itself, to which he made no valuable contributions.  These questions, though logically the first in arithmetic, were, of course, historically the last to be dealt with.  Before this could happen, arithmetic had to receive a development by means of Cantor's discovery of transfinite numbers, into a theory of cardinal and ordinal numbers, both finite and transfinite, and logic had to be sharpened, as it was by Dedekind, Frege, Peano and Russell--to a great extent owing to the needs which this theory made evident."  From the Introduction, p.23.
     "In 1873, Cantor set out from the question whether the linear continuum (of real numbers) could be put in a one-one correspondence with the aggregate of the whole numbers, and found the rigorous proof that this is not the case.  This proof ... was published in 1874."  From the Introduction, p.38.
     "... Conception of  (1, 1)-correspondence between aggregates was the fundamental idea in a memoir of 1877, published in 1878, in which some important theorems of this kind of relation between various aggregates were given and suggestions made of a classification of aggregates on this basis.
     "If two well-defined aggregates can be put into such a (1, 1)-correspondence (that is to say, if, element to element, they can be made to correspond completely and uniquely), they are said to be of the same "power" (Mächtigkeit) or to be "equivalent" (aequivalent).  When an aggregate is finite, the notion of power corresponds to that of number (Anzahl), for two such aggregates have the same power when, and only when, the number of their elements is the same.
     "A part (Bestandteil; any other aggregate whose elements are also elements of the original one) of a finite aggregate has always a power less than that of the aggregate itself, but this is not always the case with infinite aggregates--for example, the series of positive integers is easily seen to have the same power as that part of it consisting of the even integers--and hence, from the circumstances that an infinite aggregate M is part of N (or is equivalent to a part of N), we can only conclude that the power of M is less than that of N if we know that these powers are unequal."  From the Introduction, pp.40-41.  
     Cantor (p.86) defines "part" as Jordain does, assuming that Jordain's translation is faithful.  It is what we now call a proper subset.
     Over time, Cantor also addressed the conditions for an aggregate being well-defined and being enumerable--equivalent to the set of natural numbers, and this is laid out by Jordain as preparation for the Begründung translated in this work. 
     In the key papers translated here, Cantor summarizes the conception of a set (aggregate: Menge) in four pages (85-89).  The work moves on through the development of transfinite cardinals to applicability of this powerful instrument to analysis.  This is Jourdain's justification for changing the title [Preface, p.v].  Reading it today, I would say that Cantor is not directly restricting himself to "numbers" even though he may well have that application in mind and, in some sense, numbers can't be escaped.  (I suppose Pythagoras would be dumbfounded as well as pleased.)  It seems to me that Cantor knew exactly what he was doing and the original title should stand.  Hence my classification of the work under logic (including set theory).   dh:2002-06-18.
   Contents
     Preface [Jourdain 1915]
     Table of Contents
     Introduction [Jourdain 1915]
     Contributions to the Founding of the Theory of Transfinite Numbers [Beiträge zur Begründung der transfiniten Mengenlehre]
          Article I (1895)
          Article II (1897)
     Notes [Jourdain 1915]
     Index
   
[Church1936]
Church, Alonzo.  An Unsolvable Problem of Elementary Number Theory.  American Journal of Mathematics 58 (1936), 345-363.  Reprinted in pp. 88-107 of [Davis1965]
     This is the paper in which Church makes the assertion since known as Church's Thesis (and lately, the Church-Turing Thesis).
   Content
     1. Introduction
     2. Conversion and λ-definability
     3. The Gödel representation of a formula
     4. Recursive functions
     5. Recursiveness of the Kleene p-function
     6. Recursiveness of certain functions of formulas
     7. The notion of effective calculability
     8. Invariants of conversion
   
[Church1956]
Church, Alonzo.  Introduction to Mathematical Logic.  Princeton University Press (Princeton, NJ: 1944, 1956).  ISBN 0-691-02906-7 pbk.  With 1958 errata.
     Originally identified as "Volume I," the material has been expanded and updated, and Volume II is destined to never appear, at this point.  I give the expansion of the Introduction content to identify areas that students may want to explore in understanding Church's approach to mathematical logic.  
     "In order to set up a formalized language we must of course make use of a language already known to us, say English or some portion of the English language, stating in that language the vocabulary and rules of the formalized language.  This procedure is analogous to that familiar to the reader in language study--as, e.g., in the use of a Latin grammar written in English--but differs in the precision with which rules are stated, in the avoidance of irregularities and exceptions, and in the leading idea that the rules of the language embody a theory or system of logical analysis.
     "The device of employing one language in order to talk about another is one for which we shall have frequent occasion not only in setting up formalized languages but also in making theoretical statements as to what can be done in a formalized language, our interest in formalized languages being less often in their actual and practical use as languages than in the general theory of such use and in its possibilities in principle.  Whenever we employ a language in order to talk about some other language (itself or another), we shall call the latter language the object language, and we shall call the former the meta-language." -- From section 07, The logistic method, p.47.
  Content
     Preface
     Introduction
          00. Logic
          01. Names
          02. Constants and variables
          03. Functions
          04. Propositions and propositional functions
          05. Improper symbols, connectives
          06. Operators, quantifiers
          07. The logistic method
          08. Syntax
          09. Semantics
     I. The Propositional Calculus
     II. The Propositional Calculus (Continued)
     III. Functional Calculi of First Order
     IV. The Pure Functional Calculi of First Order
     V. Functional Calculi of Second Order
     Index of Definitions
     Index of Authors Cited
     Errata
   
[Copi1978]
Copi, Irving M.  Introduction to Logic,  ed. 5.  Macmillan (New York: 1953, 1961, 1968, 1972, 1978).  ISBN 0-02-324880-7.
     "There are obvious benefits to be gained from the study of logic: heightened ability to express ideas clearly and concisely, increased skill in defining one's terms, enlarged capacity to formulate arguments rigorously and to analyze them critically.  But the greatest benefit, in my judgment, is the recognition that reason can be applied in every aspect of human affairs."  Preface, p.vii.
   Content
     Preface
     Part One: Language
          1. Introduction
          2. The Uses of Language
          3. Informal Fallacies
          4. Definition
     Part Two: Deduction
          5. Categorical Propositions
          6. Categorical Syllogisms
          7. Arguments in Ordinary Language
          8. Symbolic Logic
          9. The Method of Deduction
          10. Quantification Theory
     Part Three: Induction
          11. Analogy and Probable Inference
          12. Causal Connections: Mill's Methods of Experimental Inquiry
          13. Science and Hypothesis
          14. Probability
     Solutions to Selected Exercises
     Special Symbols
     Index
   
[Curry1977]
Curry, Haskell B.  Foundations of Mathematical Logic.  Dover Publications (New York: 1963, 1977).  ISBN 0-486-63462-0 pbk.
     "... This book is intended to be self-contained.  It aims to give a thorough account of a part of mathematical logic which is truly fundamental, not in a theoretical or philosophical sense, but from the standpoint of a student; a part which needs to be thoroughly understood, not only by those who will later become specialists in logic, but by all mathematicians, philosophers, and scientists whose work impinges upon logic.
     "The part of mathematical logic which is selected for treatment may be described as the constructive theory of the first-order predicate calculus.  That this calculus is central in modern mathematical logic does not need to be argued.  Likewise, the constructive aspects of this calculus are fundamental for its higher study.  Furthermore, it is becoming increasingly apparent that mathematicians in general need to be aware of the difference between the constructive and the nonconstructive, and there is hardly any better way of increasing this awareness than by giving a separate treatment of the former.  Thus there seems to be a need for a graduate-level exposition of this fundamental domain."  -- From the Preface, p.iii.
   Content
     Preface to the Dover Edition
     Preface
     Explanation of Conventions
     1. Introduction
          A. The nature of mathematical logic
          B. The logical antinomies
          C. The nature of mathematics
          D. Mathematics and logic
          S. Supplementary topics
     2. Formal Systems
          A. Preliminaries
          B. Theories
          C. Systems
          D. Special forms of systems
          E. Algorithms
          S. Supplementary topics
     3. Epitheory
          A. The nature of epitheory
          B. Replacement and monotone relations
          C. The theory of definition
          D. Variables
          S. Supplementary topics
     4. Relational Logical Algebra
          A. Logical algebras in general
          B. Lattices
          C. Skolem lattices
          D. Classical Skolem lattices
          S. Supplementary topics
     5. The Theory of Implication
          A. General principles of assertional logical algebra
          B. Propositional algebras
          C. The systems LA and LC
          D. Equivalence of the systems
          E. L deducibility
          S. Supplementary topics
     6. Negation
          A. The nature of negation
          B. L systems for negation
          C. Other formulations of negation
          D. Technique of classical negation
          S. Supplementary topics
     7. Quantification
          A. Formulation
          B. Theory of the L* systems
          C. Other forms of quantification theory
          D. Classical epitheory
          S. Supplementary topics
     8. Modality
          A. Formulation of necessity
          B. The L theory of necessity
          C. The T and H formulations of necessity
          D. Supplementary topics
     Bibliography
     Index
   
[Davis1965]  
Davis, Martin (ed.). The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions. Raven Press (New York: 1965). ISBN 0-911216-01-4. 
   Content
     Kurt Gödel
          On Formally Undecidable Propositions of the Principia Mathematica and Related Systems, I [1931, translated from the German by Elliott Mendelson]
          On undecidable propositions of formal mathematical systems [1934 notes by S. C. Kleene and J. B. Rosser with 1964 postscriptum by Gödel ]
          On Intuitionistic Arithmetic and Number Theory [1933e, translated from the German by Martin Davis]
          On the Length of Proofs [1936a, translated from the German by Martin Davis]
          Remarks Before the Princeton Bicentennial Conference on Problems in Mathematics [1946]
     Alonzo Church
          An unsolvable problem of elementary number theory [1936]
          A Note on the Entscheidungsproblem [1936a]
     Alan M. Turing
          On computable numbers, with an application to the entscheidungsproblem [1936 with 1937 corrections]
          Systems of Logic Based on Ordinals [1939]
     J. B. Rosser
          An Informal Exposition of Proofs of Gödel's Theorem and Church's Theorem [1939]
          Extensions of Some Theorems of Gödel and Church [1936]
     Stephen C. Kleene
          General Recursive Functions of Natural Numbers [1936 with 1938 corrections]
          Recursive Predicates and Quantifiers [1943]
     Emil Post
          Finite Combinatory Processes, Formulation I [1936]
          Recursive Unsolvability of a Problem of Thue [1947]
          Recursively enumerable sets of positive integers and their decision problems [1944]
          Absolutely Unsolvable Problems and Relatively Undecidable Propositions -- Account of an Anticipation [1941 published 1964]
     Index
   
[Davis2000]
Davis, Martin.  Engines of Logic: Mathematicians and the Origin of the Computer.   W. W. Norton (New York: 2000).  ISBN 0-393-32229-7 pbk.  Paperback edition of book originally published as The Universal Computer: The Road from Liebniz to Turing.
     "As computers have evolved from the room-filling behemoths that were the computers of the 1950s to the small, powerful machines of today that perform a bewildering variety of tasks, their underlying logic has remained the same.  These logical concepts have developed out of the work of a number of gifted thinkers over a period of centuries.  In this book I tell the story of the lives of these people and explain some of their thoughts.  The stories are fascinating in themselves, and my hope is that readers will not only enjoy them, but that they will also come away with a better sense of what goes on insider their computers and with an enhanced respect for the value of abstract thought."  -- from the Preface, p. ix.
     I really do discipline myself -- sometimes successfully -- to leave books on their shelves, a practice best sustained by avoiding bookstores.  The other day, while shopping for a specific book and thereby vulnerable, my thoughts were on "the unusual effectiveness of mathematics." I opened Engines of Logic to see what Davis has to say about Einstein saying anything.  Although I found no direct connection on the peculiar-seeming harmony of theory and reality in the 8 places (and further in the notes) where Einstein figures in this dance, I was led to the discussion of Hilbert's life and the important meetings in Königsberg (pp. 102-105).  I was startled to see the connections among the players in modern logic, and also be reminded of the terrible events of and between the World Wars and how this led to the great dispersal in which Princeton's Institute for Advanced Study arose as a safe haven.  Reading Hilbert's epitaph, I wept silently as I walked to the checkout counter.  
     Despite repeated evidence, I am regularly surprised by the personal aspects of the lives of mathematicians and those singular individuals who have forever altered our view of the world and demonstrated the power of abstract conceptions in their immortal legacy.  There is an amazing, connected community of participants, colleagues, adversaries, teachers, students and scholars who knew each other as correspondents, as professors, and as compatriots and friends in a chain of lived relationships on which was anchored the development of mathematical logic and the practical creation of the computer.  This book brings the humanity of the mathematician's world to life for me.   I recommend it along with the many sources in its notes and references.  It evokes for me the same passion that I awaken on re-reading Berlinski's books (on calculus and on the algorithm) and  the venerable Men of Mathematics. -- dh:2002-09-05
   Content
     Preface
         Note to the Paperback Edition
     Introduction
     1.  Liebniz's Dream
     2.  Boole Turns Logic into Algebra
     3.  Frege: From Breakthrough to Despair
     4.  Cantor: Detour through Infinity
     5.  Hilbert to the Rescue
     6.  Gödel Upsets the Applecart
     7.  Turing Conceives of the All-Purpose Computer
     8.  Making the First Universal Computers
     9.  Beyond Liebniz's Dream
     Epilogue
     Notes
     References
     Index
   
[Dawson1986]
Gödel, Kurt., Feferman, Solomon (editor-in-chief), Dawson, John W. Jr., Kleene, Stephen C., Moore, Gregory H., Solovay, Robert M., van Heijenoort, Jean (eds.).  Kurt Gödel: Collected Works, vol.1: Publications 1929-1936.  Oxford University Press (New York: 1986).  ISBN 0-19-514720-0 pbk.  See [Gödel1986]
   
[Dawson1990]
Gödel, Kurt., Feferman, Solomon (editor-in-chief), Dawson, John W. Jr., Kleene, Stephen C., Moore, Gregory H., Solovay, Robert M., van Heijenoort, Jean (eds.).  Kurt Gödel: Collected Works, vol.2: Publications 1938-1974.  Oxford University Press (New York: 1990).  ISBN 0-19-514721-9 pbk.  See [Gödel1990]
   
[Dawson1995]
Gödel, Kurt., Feferman, Solomon (editor-in-chief)., Dawson, John W. Jr., Goldfarb, Warren., Parsons, Charles., Solovay, Robert M. (eds.).  Kurt Gödel: Collected Works, vol.3: Unpublished essays and lectures.  Oxford University Press (New York: 1995).  ISBN 0-19-514722-7 pbk.  See [Gödel1995]
   
[Enderton2001]
Enderton, Herbert B.  A Mathematical Introduction to Logic.  ed.2.  Harcourt/Academic Press (Burlington, MA: 1972, 2001).  ISBN 0-12-238452-0.
     "The book is intended for the reader who has not studied logic previously, but who has some experience in mathematical reasoning.  There are no specific prerequisites aside from a willingness to function at a certain level of abstraction and rigor.  There is the inevitable use of basic set theory.  Chapter 0 gives a concise summary of the set theory used.  One should not begin the book by studying this chapter; it is instead intended for reference if and when the need arises." -- from the Preface, p.x.
     When asked what I recommend to computer scientists for delving deeper into logic and its connections with computation and language, I recommend two books.  Stolyar's elementary text as a starter, with Enderton's book as more-comprehensive but still-accessible introduction to further concepts that arise in the application of logic to mathematical subjects, including computer science.  Enderton provides a coherent progression through topics that I have encountered only by happenstance in earlier forays.  There is appropriate rigor and an useful foundation that I will certainly appropriate in my work and in discussions with others.  This book is a great place to sharpen ones understanding and application of logic and also as a place to direct others as a basis for a common background in theoretical explorations  -- dh:2002-07-16.
   Content
     Preface
     Introduction
     Chapter Zero.  Useful Facts About Sets
     Chapter One.  Sentential Logic
          1.0 Informal Remarks on Formal Languages
          1.1 The Language of Sentential Logic
          1.2 Truth Assignments
          1.3 A Parsing Algorithm
          1.4 Induction and Recursion
          1.5 Sentential Connectives
          1.6 Switching Circuits
          1.7 Compactness and Effectiveness
     Chapter Two. First-Order Logic
          2.0 Preliminary Remarks
          2.1 First-Order Languages
          2.2 Truth and Models
          2.3 A Parsing Algorithm
          2.4 A Deductive Calculus
          2.5 Soundness and Completeness Theorems
          2.6 Models of Theories
          2.7 Interpretations Between Theories
          2.8 Nonstandard Analysis
     Chapter Three.  Undecidability
          3.0 Number Theory
          3.1 Natural Numbers with Successor
          3.2 Other Reducts of Number Theory
          3.3 A Subtheory of Number Theory
          3.4 Arithmetization of Syntax
          3.5 Incompleteness and Undecidability
          3.6 Recursive Functions
          3.7 Sound Incompleteness Theorem
          3.8 Representing Exponentiation
     Chapter Four.  Second-Order Logic
          4.0 Second-Order Languages
          4.1 Skolem Functions
          4.2 Many-Sorted Logic
          4.3 General Structures
     Suggestions for Further Reading
     List of Symbols
     Index
   
[Feferman1986]
Gödel, Kurt., Feferman, Solomon (editor-in-chief), Dawson, John W. Jr., Kleene, Stephen C., Moore, Gregory H., Solovay, Robert M., van Heijenoort, Jean (eds.).  Kurt Gödel: Collected Works, vol.1: Publications 1929-1936.  Oxford University Press (New York: 1986).  ISBN 0-19-514720-0 pbk.  See [Gödel1986]
   
[Feferman1990]
Gödel, Kurt., Feferman, Solomon (editor-in-chief), Dawson, John W. Jr., Kleene, Stephen C., Moore, Gregory H., Solovay, Robert M., van Heijenoort, Jean (eds.).  Kurt Gödel: Collected Works, vol.2: Publications 1938-1974.  Oxford University Press (New York: 1990).  ISBN 0-19-514721-9 pbk.  See [Gödel1990]
   
[Feferman1995]
Gödel, Kurt., Feferman, Solomon (editor-in-chief)., Dawson, John W. Jr., Goldfarb, Warren., Parsons, Charles., Solovay, Robert M. (eds.).  Kurt Gödel: Collected Works, vol.3: Unpublished essays and lectures.  Oxford University Press (New York: 1995).  ISBN 0-19-514722-7 pbk.  See [Gödel1995]
   
[Forster1995]
Forster, T. E.  Set Theory with a Universal Set: Exploring an Untyped Universe.  ed.2.  Oxford University Press (Oxford: 1992, 1995).  ISBN 0-19-851477-8.
     "NF is a much richer and more mysterious system than the other set theories with a universal set, and there are large areas in its study (e.g., the reduction of the consistency question) which have no counterparts elsewhere in the study of set theories with V ∈ V.  There just is a great deal more to say about NF than about the other systems."  Preface to the First Edition, p.v.
     [dh:2004-02-19] I was led here by some startling references to Quine's New Foundations (NF) on some discussion lists that I follow.  This is often in the context of "ur-elements" and also "avoiding problems" or "applicable in computational models."  It seemed wise to find out what that is about.  I learned that there is an active community of interest in NF, and that Thomas Forster's work is prized as a valuable current treatment.  I am counting on the first two sections to provide equipment for comprehending these mentions.  But first, I must equip myself to comprehend the rather technical first two sections.  Meanwhile, I can simply enjoy the way Forster writes while I read for the gist of it.
   Content
     Preface to the First Edition
     Preface to the Second Edition
     1. Introduction
          1.1 Annotated definitions
          1.2 Some motivations and axioms
          1.3 A brief survey
          1.4 How do theories with V ∈ V avoid the paradoxes?
          1.5 Chronology
     2. NF and Related Systems
          2.1 NF
          2.2 Cardinal and ordinal arithmetic
          2.3 The Kaye-Specker equiconsistency lemma
          2.4 Subsystems, term models, and prefix classes
          2.5 The converse consistency problem
     3. Permutation Models
     4. Church-Oswald Models
     5. Open Problems
     Bibliography
     Index of Definitions
     Author Index
     General Index
   
[Forster2003]
Forster, Thomas.  Reasoning About Theoretical Entities.  Advances in Logic - vol.3.  World-Scientific Publishing (Singapore: 2003).  ISBN 981-238-567-3.
     "In this essay I am attempting to give a clear and comprehensive (and comprehensible!) exposition of the formal logic that underlies reductionist treatments of various topics in post-nineteenth-century analytic philosophy.  The aim is to explain in detail--in a number of simple yet instructive cases--how it might happen that talk about some range of putative entities could be meaningful, have truth conditions and so on, even if those entities should be spurious.  Although this ontological position has been adopted in relation to a wide range of putative entities at various times by various people I develop the logical gadgetry here quite specifically in connection with one such move: cardinal and ordinal numbers as virtual objects and always with the Burali-Forti paradox in mind.
     "Such a position (with respect to numbers at least) is one I associate with the work of Quine ('The subtle point is that any progression will serve as a version of number so long and only so long as we stick to one and the same progression.  Arithmetic is, in this sense, all there is to number: there is no saying absolutely what the numbers are; there is only arithmetic.') though I think it is associated in the minds of many others with Dedekind.  Indeed it seems to me to be wider than that, and to be an implicit part of the tradition.   So implicit, and deemed perhaps to be so obvious, that nobody--as far as I know--has bothered to spell it out.  This dereliction has had bad consequences."  From the Preface, p.1.
     "I am no reductionist: for me reductionism is a strategy for flushing out ontological commitment.  I share with the anti-reductionists a hunch that reductionism won't work.  What I do not share is their superstition that it is possible to understand the limitations of reductionist strategies without actually acquiring enough logic to formally execute them.  This is an error: the belief that something won't work is not automatically a reason for not trying it, for even if failures is certain the manner of it might be instructive."  From the Introduction, pp.6-7.
   Content
     Preface
     1. Introduction
     2. Definite Descriptions
     3. Virtual Objects
     4. Cardinal Arithmetic
     5. Iterated Virtuality in Cardinal Arithmetic
     6. Ordinals
     Bibliography
     Index of Definitions
     Index
   
[Fraenkel1922a]
Fraenkel, Abraham A.  Zu den Grundlagen der Cantor-Zermeloschen Mengenlehre.  Mathematische Annalen 86, 230-237.
     This is the article that [Fraenkel1968] cites when discussing Fraenkel's adjustments to Zermelo's system.
   
[Fraenkel1968]
Fraenkel, Abraham A.  Part I.  Historical Introduction.