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