Barendregt, Henk P. The Type Free Lambda Calculus.
Chapter D.7 in The Handbook of Mathematical
Logic, Jon Barwise, editor. Elsevier (Amsterdam: 1977).
ISBN 0-444-86388-5 pbk.
Barendregt, Hendrik Pieter. The Lambda Calculus: Its Syntax and
Semantics. North-Holland (Amsterdam, 1981). ISBN 0-444-85490-8.
Studies in Logic and the Foundations of Mathematics, vol. 103.
This is one of my fundamental sources on the
lambda calculus. I want to pay particular attention to combinatory
logic (CL) and combinatory algebra (CA). My
notes on this book focus on that.
Content Preface
Part I. Towards the Theory
1. Introduction
2. Conversion
3. Reduction
4. Theories
5. Models
Part II. Conversion
6. Classical
Lambda Calculus
7. The Theory of
Combinators
8. Classical
Lambda Calculus (continued)
9. The λI-Calculus
10. Böhm Trees
Part III. Reduction
11. Fundamental
Theorems
12. Strongly
Equivalent Reductions
13. Reduction
Strategies
14. Labelled
Reduction
15. Other Notions
of Reduction
Part IV. Theories
16. Sensible
Theories
17. Other Lambda
Theories
Part V. Models
18. Construction
of Models
19. Local
Structure of Models
20. Global
Structure of Models
21. Combinatory
Groups Appendices
Appendix A. Typed
Lambda Calculus
Appendix B.
Illative Combinatory Logic
Appendix C.
Variables References
Index of Names
Index of Definitions
Index of Symbols
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-115 with supplemental notes in [Davis1965]
This is the paper in which Church makes the
assertion since known as Church's Thesis (and lately, the Church-Turing
Thesis), in the last sentence, and its footnote, in section 1.
Subsequent sections refer to work to appear or underway related to
investigations by Church, Rosser, Kleene, Gödel, and others. .
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. A formulation of the Simple Theory of Types.
J. Symbolc Logic 5, 2 (June 1940), 56-48. DOI:
10.2307/22661700 available on JSTOR <https://www.jstor.org/stable/226170>.
Identified as inspirational in [Scott1993] and [Paulson2018], this
work identifies simple type
ο (omicron) as the type of propositions and
represents a logic thereby. For a lower-level computational model such
as for oMiser, there need not be an explicit type; discriminators such
as Uβ accomplish this without a distinct type,
just as for early programming languages, including LISP. The
notation for functional type has also been refined over the years,
achieving consistent widespread usage.
Church, Alonzo. The Calculi of Lambda-Conversion.
Annals of Mathematics Studies 6. Princeton University Press
(Princeton: 1941). 1951 Second printing with bibliography addenda ISBN 0-691-08394-0 pbk.
Content
I. Introduction
1. The concept of a function
2. Extension and intension
3. Functions of several variables
4. Abstraction
II. Lambda-Conversion
5. Primitive symbols, and formulas
6. Conversion
7.
Fundamental theorems on well-formed formulas and on the normal form
III. Lambda-Definability
8. Lambda-definability of functions
of positive integers
9. Ordered pairs and traids, the
predecessor function
10. Propositional functions, the Kleene p-function
11. Definition by recursion
IV. Combinations, Gödel Numbers
12. Combinations
13. Primitive sets of formulas
14. An application of the theory of
combinations
15. A combinatory equivalent of conversion
16. Gödel numbers
V. The Calculi of λ-K-Conversion and
λ-δ-Conversion
17. The calculus of λ-K-conversion
18. The calculus of restricted λ-K-conversion
19. Transfinite ordinals
20. The calculus of λ-δ-conversion
21. A system of symbolic logic
Index of the Principal Formulas Introduced by
Definition
Bibliography
Corrections and Additions
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
Combinatory Logic.
Wikipedia
Article. Accessed on
2018-05-15. Re-accessed on
2024-07-25.
2024-07-25: I find that Wikipedia articles on
abstruse topics tend to be hyper-abstruse to the next level. I'm
also unclear how that can be resolved within the guidelines for
Wikipedia articles. I do recall there being near-tutorial articles
in encyclopedias during my high-school fascination with how one could
assay the chemical composition of minerals. Perhaps I was naive.
One might also wonder what accounts for the apparent instability of
articles of this kind when the
History is viewed. The article's
Talk
page may be useful in some respects, although it is not always obvious
how the article was influenced, if at all. Now I wonder how it
came about that I understood the introduction in [Rosenbloom1950]
without so much difficulty.
I cite this article mainly for its discussion and some ideas,
with a caution that if something doesn't seem to make sense it might be
good to find a different source for comparison; the historical
discussion and mentions of resources are still somewhat usable.
Important questions related to mathematical logic are addressed here,
although understanding that seems inessential, as much as it does
indicate what the interest of theoreticians is all about.
For an intense treatment, consider [Barendregt1981:
Chapter 7]. My own introduction was [Rosenbloom1950:
Section 4, starting on p.111]. [Burge1975:
Section 1.9] is perhaps the most straightforward with regard to
functional-/applicative-programming employment, in contrast/conjunction
with Lambda Conversion (Section 1.8 there). The coverage of [Barendregt1977]
is a valuable background and guide into the formal mathematical-logic
considerations.
The origin of combinatory logic is available
[Schönfinkel1924].
The introduction of [Quine1977] is valuable,
along with understanding of the motivation for eliminating quantifiers
and quantified terms.
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
Feferman, Solomon. Theories of Finite Type Related to
Mathematical Practice. Chapter D.4 in The Handbook of
Mathematical Logic, Jon Barwise, editor. Elsevier
(Amsterdam: 1977). ISBN 0-444-86388-5 pbk.
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.
Gödel, Kurt. The consistency of the axiom of choice and
the generalized continuum hypothesis with the axioms of set theory.
Annals of Mathematics Studies, vol. 3. Lecture notes taken by
George W. Brown. Reprinted with additional notes in 1951 and with
further notes in 1966. Princeton University Press (Princeton, NJ:
1940, 1953, 1966). ISBN 0-691-07927-7 pbk. Reprinted in pp. 33-101 of [Gödel1990].
This is the source for what is known as the [von
Neumann-]Bernays-Gödel (BG) set theory. -- dh:2002-07-25
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.
"... Each article or closely related group
of articles is preceded by an introductory note which elucidates it and
places it in historical context. These notes have been written by
the members of the editorial board as well as a number of outside
experts [Burton Dreben, A. S. Troelstra, Warren D. Goldfarb, W. V. Quine,
Judson Webb, and Rohit Parikh in volume 1]. ...
"We expect these volumes to be of interest
and value to professionals and students in the areas of logic,
mathematics, philosophy, history of science, computer science, and even
physics, as well as many non-specialist readers with a broad scientific
background." -- from the Preface, p.i.
I have omitted the numerous reviews and have
not identified the notes and supplemental contextual material
in the full Content. There are useful notes by Stephen Kleene on
achieving consistency of the λ-calculus and Gödel's gradual
acceptance of Church's Thesis in the form of Turing computable
functions.
One
incidental value of this amazing effort is that it provides a standard
citation scheme for Gödel's work, and I have incorporated those
forms, below. I have also adopted the citation numbers of [vanHeijenoort1977]
for other bibligraphic entries here.
There is an Addenda and Corrigenda for this
volume in the back matter of the second volume.
I think we are yet to digest the full import of
the edifice that Gödel has entrusted to us by his words. --
dh:2002-07-25
Content [abridged] Preface
Information for the reader
Copyright permissions
Gödel's life and work, Solomon Feferman
A Gödel chronology, John W. Dawson, Jr. On the completeness of the calculus of logic
(dissertation) [Gödel1929]
The completeness of the axioms of the calculus
of logic [Gödel1930]
Some metamathematical results on completeness
and consistency [Gödel1930b]
On formally undecidable propositions of Principia
mathematica and related systems I [Gödel1931]
Discussion on providing a foundation for
mathematics [Gödel1931a]
On the intuitionistic propositional calculus [Gödel1932]
A special case of the decision problem for
theoretical logic [Gödel1932a]
On completeness and consistency [Gödel1932b]
A property of the realizations of the
propositional calculus [Gödel1932c]
On independence proofs in the propositional
calculus [Gödel1933a]
On the isometric embeddability of quadruples of
points of R_{3} in the surface of a sphere [Gödel1933b]
On Wald's axiomatization of the notion of
betweenness [Gödel1933c]
On the axiomatization of the relations of
connection in elementary geometry [Gödel1933d]
On intuitionistic arithmetic and number theory
[Gödel1933e]
An interpretation of the intuitionistic
propositional calculus [Gödel1933f]
Remark concerning projective mappings [Gödel1933g]
Discussion concerning coordinate-free
differential geometry [Gödel1933h]
On the decision problem for the functional
calculus of logic [Gödel1933i] On undecidable propositions of formal
mathematical systems [Gödel1934]
On the length of proofs [Gödel1936a] Textual 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.2: Publications 1938-1974. Oxford University Press (New York:
1990). ISBN 0-19-514721-9 pbk.
This book continues on the model established
for the first volume. Beside the
editors, contributors of notes on articles in this volume include S. W.
Hawking, Howard Stein, A. S. Troelstra, Judson C. Webb, and Jens Erik
Fenstad. There is an intriguing progression in these later works,
as stitched together by the introductory notes. These stand out
for me:
a. Robert M. Solovay's discussion on the
development of consistency results for the axiom of choice (AC) and the
generalized continuum hypothesis (GCH) also points out the value of Gödel's
formulation of axiomatic set theory, BG (for [von Neumann-]Bernays-Gödel),
in [Gödel1940].
b. Charles Parsons' introductory note to [Gödel1944]
illustrates the degree to which Gödel saw foundational questions
for mathematical logic as still unsettled.
c. Gregory H. Moore's note for [Gödel1947]
and its sequel [Gödel1964] provides a sense of the perplexing state
of affairs regarding the continuum problem, as we are now left with it.
d. A. S. Troelstra's note for [Gödel1958]
and its [Gödel1972] unpublished revision provide a sense of how
investigation is moving into model-theoretic and constructive
approaches. It is plain here and in (a) that explorations of
mathematical logic moved into more-abstracted and intricate realms,
seemingly far removed from the naive origins of axiomatic set theory.
e. Solomon Feferman, Robert M. Solovay, and
Judson C. Webb riff on the few paragraphs [Gödel1972a] we're given
with Gödel's (provisional?) generalizing of the unprovability-of-consistency result, a broadened
undecidability theorem, and a perceived error in Turing's reasoning
about mental procedures versus mechanical ones.
-- dh:2002-07-25
Content
Preface Information for the reader
Copyright permissions
List of illustrations [p.188 and 218
entries are reversed]
The consistency of the axiom of choice and of
the generalized continuum hypothesis [Gödel1938]
The consistency of the generalized continuum
hypothesis [Gödel1939]
Consistency proof for the generalized continuum
hypothesis [Gödel1939a] The consistency of the axiom of choice and
of the generalized continuum hypothesis with the axioms of set theory
[Gödel1940]
Russell's mathematical logic [Gödel1944]
Remarks before the Princeton bicentennial
conference on problems in mathematics [Gödel1946]
What is Cantor's continuum problem? [Gödel1947]
An example of a new type of cosmological
solutions of Einstein's field equations of gravitation [Gödel1949]
A remark about the relationship between
relativity theory and idealistic philosophy [Gödel1949a]
Rotating universes in general relativity theory [Gödel1952]
On a hitherto unutilized extension of the
finitary standpoint [Gödel1958]
What is Cantor's continuum problem? [Gödel1964]
On an extension of finitary mathematics which
has not yet been used [Gödel1972]
Some remarks on the undecidability results [Gödel1972a]
Remark on non-standard analysis [Gödel1974] Textual notes
References
Addenda and corrigenda to Volume I
Index
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.
This book continues on the model established
for the first and second
volumes. Beside the
editors, contributors of notes on articles in this volume include Cheryl
Dawson, Stephen C. Kleene, Israel Halperin, Wilfred Sieg, Martin Davis, A. S.
Troelstra, Howard, Stein, David B. Malament, George Boolos, Dagfinn Føllesdal,
and Robert Merrihew Adams. The unpublished works have citations
with * in front of the date. I have abridged the table of contents
in the same manner as for the earlier volumes. -- dh:2002-07-31
"In this volume, our primary criteria for
judging an item to be worthy of inclusion were: (1) the manuscript had
to be sufficiently coherent to permit editorial reconstruction; (2) the
text was not to duplicate other works substantially in both content and
tone (though treatments of similar topics aimed at different audiences
or differing in degrees of detail might warrant inclusion); (3) the
material had to possess intrinsic scientific interest.
"Additional justification for our
selections came from two lists prepared by Gödel himself, both
preserved in his Nachlass and entitled "Was ich publizieren
könnte" ("What I could publish"). ...
"Despite their presence on these lists, we
recognize that Gödel did not consider any of the texts presented
here to be in final form; before submitting them for publication, he
would no doubt have made a number of stylistic, and, in some cases,
substantive changes. ...
"Taken as a whole, the texts presented in
this volume substantially enlarge our appreciation of Gödel's
scientific and philosophical thought, and in a number of cases they add
appreciably to our understanding of his motivations." -- from
the Preface, pp.v-vi.
Content
Preface Information for the reader
Copyright permissions
List of illustrations
The Nachlass of Kurt Gödel: an
overview, John W. Dawson, Jr. Gödel's Gabelsberger shorthand, Cheryl
A. Dawson Lecture on completeness of the functional
calculus [Gödel*1930c]
On undecidable sentences [Gödel*1931?]
The present situation in the foundations of
mathematics [Gödel*1933o]
Simplified proof of a theorem of Steinitz [Gödel*1933?]
Lecture at Zilsel's [Gödel*1938a]
Lecture at Göttingen [Gödel*1939b]
Undecidable diophantine propositions [Gödel*193?]
Lecture on the consistency of the continuum
hypothesis (Brown University) [Gödel*1940a]
In what sense is intuitionisstic logic
constructive? [Gödel*1941]
Some observations about the relationship
between theory of relativity and Kantian philosophy [Gödel*1946/9]
Lecture on rotating universes [Gödel*1949b]
Some basic theorems on the foundations of
mathematics and their implications [Gödel*1951]
Is mathematics syntax of language? [Gödel*1953/9]
The modern development of the foundation of
mathematics in the light of philosophy [Gödel*1961/?]
Ontological proof [Gödel*1970]
Some considerations leading to the probable
conclusion that the true power of the continuum is aleph-2 [Gödel*1970a]
A proof of Cantor's continuum hypothesis from a
highly plausible axiom about orders of growth [Gödel*1970b]
Unsent letter to Alfred Tarski [Gödel*1970c]
Appendix A: Excerpt from *1946/9-A
Appendix B: Texts related to the ontological
proof Textual notes
References
Addenda and corrigenda to Volumes I and II
Addendum to this volume
Index
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]
Halmos, Paul Richard. Naive Set Theory. Springer-Verlag
(New York: 1960, 1974). ISBN 0-387-90092-6. Undergraduate
texts in mathematics.
"Every mathematician agrees
that every mathematician must know some set theory; the disagreement
begins in trying to decide how much is some. This book contains my
answer to that question. The purpose of the book is to tell the
beginning student of advanced mathematics the basic set-theoretic facts
of life, and to do so with the minimum of philosophical discourse and
logical formalism." -- from the Preface, p. v.
"The student's task in learning set theory
is to steep himself in unfamiliar but essentially shallow generalities
till they become so familiar that they can be used with almost no
conscious effort. In other words, general set theory is pretty
trivial stuff really, but if you want to be a mathematician, you need
some, and here it is; read it, absorb it, and forget it." --
from the Preface, p. vi.
Content Preface
1. The Axiom of Extension
2. The Axiom of Specification
3. Unordered Pairs
4. Unions and Intersections
5. Complements and Powers
6. Ordered Pairs
7. Relations
8. Functions
9. Families
10. Inverses and Composites
11. Numbers
12. The Peano Axioms
13. Arithmetic
14. Order
15. The Axiom of Choice
16. Zorn's Lemma
17. Well Ordering
18. Transfinite Recursion
19. Ordinal Numbers
20. Sets of Ordinal Numbers
21. Ordinal Arithmetic
22. The Schröder-Bernstein
Theorem
23. Countable Sets
24. Cardinal Arithmetic
25. Cardinal Numbers Index
Holmes, M.Randall. Elementary Set Theory with a Universal Set.
Université catholique de Louvain Département de Philosophie, Cahiers
du Centre de Logique v.10. Academia Bruylant (Louvain-la-Neuve,
Belgium: 1998). ISBN 2-87209-488-1 pbk.
Content
1. Introduction: Why Save the Universe?
2. The Set Concept
3. Boolean Operations on Sets
4. Building Finite Structures
5. The Theory of Relations
6. Sentences and Sets
7. Stratified Comprehension
8. Philosophical Interlude
9. Equivalence and Order
10. Introducing Functions
11. Operations on Functions
12. The Natural Numbers
13. The Real Numbers
14. The Axiom of Choice
15. Ordinal Numbers
16. Cardinal Numbers
17. Three Theorems
18. Sets of Real Numbers
19. Strongly Cantorian Sets
20. Well-Founded Extensional Relations
21. Surreal Numbers
22. The Structure of the Transfinite
23. Stratified Lambda-Calculus
24. Acknowledgements and Notes
Appendix: Selected Axioms and Theorems 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
republished edition by Dover Publications (New York: 1955). ISBN
0-486-60045-9 pbk. See [Cantor1915]
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]
Stolyar, Abram Aronovich. Introduction to Elementary
Mathematical Logic. Dover (New York: 1970). ISBN
0-486-64561-4 pbk. Unabridged and unaltered 1983 republication of
the work published by MIT Press (Cambridge, MA: 1970). Translation
of Elementarnoe vvedenie v matematicheskuiu logiku,
Prosveshcheniye Press (Moscow: 1965), with translation from the Russian
edited by Elliot Mendelson. See [Stolyar1970]
Mendelson, Elliott. Introduction to Mathematical Logic.
ed.4. Chapman &
Hall/CRC
(Boca Raton, FL: 1964, 1979, 1987, 1997). ISBN
0-412-80830-7.
"This is a compact introduction to some of
the principal topics of mathematical logic. In the belief that
beginners should be exposed to the easiest and most natural proofs, I
have used free-swinging set-theoretic methods. The significance of
a demand for constructive proofs can be evaluated only after a certain
amount of experience with mathematical logic has been obtained. If
we are to be expelled from ‘Cantor's paradise’ (as non-constructive set
theory was called by Hilbert), at least we should know what we are
missing. ...
"I believe that the essential parts of the
book can be read with ease by anyone with some experience in abstract
mathematical thinking. There is, however, no specific
prerequisite." -- from the Preface, p.ix.
"Although logic is basic to all studies,
its fundamental and apparently self-evident character discouraged any
deep logical investigations until the late 19th century. Then,
under the impetus of the discovery of non-Euclidean geometry and the
desire to provide a rigorous foundation for calculus and higher
analysis, interest in logic revived. This new interest, however,
was still rather unenthusiastic until, around the turn of the century,
the mathematical world was shocked by the discovery of the
paradoxes--that is, arguments that lead to contradictions. The
most important paradoxes are described here. ...
"Whatever approach one takes to the
paradoxes, it is necessary first to examine the language of logic and
mathematics to see what symbols may be used, to determine the ways in
which these symbols are put together to form terms, formulas, sentences
and proofs, and to find out what can and cannot be proved if certain
axioms and rules of inference are assumed. This is one of the
tasks of mathematical logic, and, until it is done, there is no basis
for comparing rival foundations of logic and mathematics. The deep
and devastating results of Gödel, Tarski, Church, Rosser, Kleene,
and many others have been ample reward for the labour invested and have
earned for mathematical logic its status as an independent branch of
mathematics." -- from the Introduction, pp.1, 4-5.
This is a weighty book. In many ways it
provides more depth on the standard topics, and connections to a variety
of inter-related topics that are valuable under the covers of one book,
arranged with consistent attention. This is also a high-density
book. I was amazed to see how little white space there is in the
10-page introduction. Don't worry, the pages have margins and
there is more use of layout in the main chapters. And there is a
certain economy and intensity that leads me to have alternative coverage
of common-ground topics, like Enderton's
book, to fall back on when I hit a pot hole in my excursions here.
-- dh:2002-07-17
I give the expanded contents of the last three
chapters for the benefit of computer scientists who want to comprehend
the bearing that mathematical logic has on their field.
Content Preface
Introduction
1. The Propositional Calculus
2. Quantification Theory
3. Formal Number Theory
3.1 An axiom
system
3.2
Number-theoretic functions and relations
3.3 Primitive
recursive and recursive functions
3.4
Arithmetization. Gödel numbers
3.5 The
fixed-point theorem. Gödel's incompleteness theorem
3.6 Recursive
undecidability. Church's theorem
4. Axiomatic Set Theory
4.1 An axiom
system
4.2 Ordinal
numbers
4.3
Equinumerosity. Finite and denumerable sets
4.4 Hartogs'
Theorem. Initial ordinals. Ordinary arithmetic
4.5 The axiom of
choice. The axiom of regularity
4.6 Other
axiomatizations of set theory
5. Computability
5.1
Algorithms. Turing machnes
5.2 Diagrams
5.3 Partial
recursive functions. Unsolvable problems
5.4 The
Kleene-Mostovski hierarchy. Recursively enumerable sets
5.5 Other notions
of computability
5.6 Decision
problems
Appendix. Second Order Logic Answers to Selected Exercises
Bibliography
Notation
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]
Nelson, Edward. Predicative Arithmetic.
Mathematical Notes 32. Princeton University Press (Princeton, NJ:
1986). ISBN 0-691-08455-6 pbk.
"The reason for mistrusting the induction
principle is that it involves an impredicative concept of number.
It is not correct to argue that induction only involves the number from
0 to n [when establishing that θ(n)
implies θ(n+1)]; the property of n being
established may be a formula with bound variables that are thought of as
ranging over all numbers. That is, the induction principle assumes
that the natural number system is given. ...
"It appears to be universally taken for
granted by mathematicians, whatever their views on foundational
questions may be, that the impredicativity inherent in the induction
principle is harmless--that there is a concept of number given in
advance of all mathematical constructions, that discourse within the
domain of numbers is meaningful. But numbers are symbolic
construction; a construction does not exist until it is made; when
something new is made, it is something new and not a selection from a
pre-existing collection. There is no map of the world because the
world is coming into being.
"Let us explore the possibility of
developing arithmetic predicatively." -- from section 1, The
impredicativity of induction, pp. 1-2.
Content Acknowledgments
1. The impredicativity of induction
2. Logical terminology
3. The axioms of arithmetic
4. Order
5. Induction by relativization
6. Interpretability in Robinson's theory
7. Bounded induction
8. The bounded least number principle
9. The Euclidean algorithm
10. Encoding
11. Bounded separation and minimum
12. Sets and functions
13. Exponential functions
14. Exponentiation
15. A stronger relativization scheme
16. Bounds on exponential functions
17. Bounded replacement
18. An impassable barrier
19. Sequences
20. Cardinality
21. Existence of sets
22. Semibounded replacement
23. Formulas
24. Proofs
25. Derived rules of inference
26. Special constants
27. Extensions by definition
28. Interpretations
29. The arithmetization of arithmetic
30. The consistency theorem
31. Is exponentation total?
32. A modified Hilbert program Bibliography
General index
Index of defining axioms
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]
Quine, Willard Van Orman. Set Theory and Its Logic.
Revised edition. Harvard University Press (Cambridge, MA: 1963,
1969). ISBN 0-674-80207-1 pbk.
"Set theory is the mathematics of
classes. Sets are classes. The notion of class is so
fundamental to thought that we cannot hope to define it in more
fundamental terms. We can say that a class is an aggregate, any
collection, any combination of objects of any sort; if this helps, well
and good. But even this will be less help than hindrance unless we
keep clearly in mind that the aggregating or collecting or combining
here is to connote no actual displacement of the objects, any further
than the aggregation or collection or combination of say seven given
pairs of shoes is not to be identified with the aggregation or
collection or combination of those fourteen shoes, nor with that of the
twenty-eight soles and uppers. In short, a class may be thought of
as an aggregate or collection or combination of objects just so long as
'aggregate' or 'collection' or 'combination' is understood strictly in
the sense of 'class'." From the Introduction, p.1.
After taking great pains to compare various
approaches, including those of Zermelo-Fraenkel
and Bernays-von
Neumann,
and the contingent results on their consistency, Quine ends with this
parting shot: "Let me seize this opportunity to leave the reader
with a sense of how open the problem of the best foundation for set
theory remains." p.329.
Content Preface to the Revised Edition
Preface to the First Edition
Introduction
Part One. The Elements
I. Logic
II. Real Classes
III. Classes of Classes
IV. Natural Numbers
V. Iteration and Arithmetic
Part Two. Higher Forms of Number
VI. Real Numbers
VII. Order and Ordinals
VIII. Transfinite Recursion
IX. Cardinal Numbers
X. The Axiom of Choice
Part Three. Axiom Systems
XI. Russell's Theory of Types
XII. General Variables and Zermelo
XIII. Stratification and Ultimate Classes
XIV. Von Neumann's System and Others Synopsis of Five Axiom Systems
List of Numbered Formulas
Bibliographical References
Index
Quine, W. V. Introduction to [Schönfinkel1924]
"On the Building Blocks of Mathematical Logic," pp.355-357 in From Frege to Gödel: A Source Book
in Mathematical Logic, 1879-1931, 3rd. printing [vanHeijenoort1977].
"The initial aim of the paper is reduction
of the number of primitive notions of logic. ... Then presently,
the purpose deepens. It comes to be nothing less than the general
elimination of variables."
There is, in particular, a strong desire to escape the use of
quantifiers and instead determne class membership with predicates (i.e.,
functions), avoiding or at least significantly-reducing presumption of
(transfinite) entireties.
"Schönfinkel's notions, which do suffice to do the work of
quantifiers and their variables altogether, go far beyond ... .
The crux of the matter is that Schönfinkel lets functions stand as
arguments."
This remarkable provision seems to escape the type theories of [Whitehead
& Russell] and will lead to a different notion, emerging as
functional types, with Category Theory perhaps taking over the
type-hierarchy burden. That this improvement is interpretable in
realizable models of computation on denumerable entities is remarkable
in turn. dh:2024-07-29
Quine, Willard Van Orman. Elementary Logic. Revised
edition. Harvard University Press (Cambridge, MA: 1941, 1965,
1980). ISBN 0-674-24451-6 pbk.
This may be more elementary than
I had been seeking. Having been chided to dig into FOL and
demonstrate some mastery of it, I went looking for something that would
take me gently up through the complete results. This is not that
book. I think it might take me to the threshold
in a gentle way, however. Albeit gentler, I am of the mind that Methods
of Logic, provides superior coverage for those wanting to
understand the overall reach of predicate logics. I have expanded
the content of the last part of Elementary Logic to assist in
that determination. [dh:2004-02-13]
"This little book provides
a single strand of simple techniques for the central business of modern
logic, seldom looking to the right or to the left for alternative
methods or peripheral problems. Basic formal concepts are
explained, the paraphrasing of words into symbols is treated at some
length, a testing procedure is given for truth-function logic, and a
complete proof procedure is given for the logic of quantifiers. At
the end there are brief glimpses of further matters." Preface
to the Revised Edition, p.vii.
"To say that mathematics in general has
been reduced to logic hints of some new firming up of mathematics at its
foundations. This is misleading. Set theory is less settled
and more conjectural than the classical mathematical superstructure that
can be founded upon it. These infirmities of set theory are
themselves good reason to see set theory as an extralogical department
of mathematics. Logic in the best and narrowest sense
has all the firmness and dependability that its name connotes.
Reality being what it is, we cannot expect most truths to admit of
foundation purely within logic in such a sense." §48
Membership, p.125.
I shall continue to compile citations on set
theory under the topic of logic in honor of custom and laziness.
[dh:2004-02-12]
Content Preface, 1980
Preface to the Revised Edition [1965]
Preface to the 1941 Edition
1. Introduction
I. Statement Composition
II. Truth-Functional Transformations
III. Quantification
IV. Quantificational Inference
39.
Quantificational Schemata
40. Predicates
41. Restraints on
Introducing
42. Substitution
Extended
43. Validity
Extended
44. Equivalence
Extended
45. Inconsistency
Proofs
46. Logical
Arguments
47. Identity and
Singular Terms
48. Membership Index
Quine, Willard Van Orman. From a Logical Point of View: Nine
Logico-Philosophical Essays. Second Edition, revised. Harvard
University Press (Cambridge, MA: 1953, 1961, 1980). ISBN
0-674-32351-3 pbk.
I have this book for at least two reasons. It has
"On what there is" and, in addition, the formulation of New
Foundations that is often discussed and not so well described. In
this material, Quine has not yet surrendered the Principia
Mathematica notations and concepts that are reluctantly
surrendered in the fourth edition of Methods of Logic. For
a comparison, Quine's Elementary
Logic, Set Theory and Its Logic,
and and Mathematical Logic preserve their
Whitehead and Russell influence.
For Quine's own appraisal of the relative
merits of ZF, NF, ML, and von Neumann's approach, it is useful to
consult the supplementary material in Chapter V and the 1980 Foreword.
With regard to the notion of inherent meaning,
Quine points out that some of the essays "reflected a dim view of
the notion of meaning. A discouraging response from somewhat the
fringes of philosophy has been that my problem comes of taking words as
bare strings of phonemes rather than seeing that they are strings with
meaning. Naturally, they say, if I insist on meaningless strings I
shall be at a loss for meanings. They fail to see that a
bare and identical string of phonemes can have a meaning, or
several, in one or several languages, through its use by sundry people
or peoples, much as I can have accounts in several banks and relatives
in several countries without somehow containing them or being several
persons. ... I hope this paragraph has been superfluous for most
readers." Foreword, 1980, p.viii.
With regard to the connection of logic with
language and meaning, the last essay has much to offer: "We freed
ourselves, six paragraphs back, of any general constraint to admit the
inference of ‘a exists’ from ‘Fa’ and ‘~Fa’.
We are led to wonder, however, just what statements containing ‘a’
shouldbe
required as requiring for their truth that a exist."
Meaning and existential inference, p.164.
Content Foreword, 1980
Preface to the Second Edition [1962]
Preface
I. On what there is [1948]
II. Two dogmas of empiricism [1951]
III. The problem of meaning in linguistics
[1951]
IV. Identity, ostension, and hypostasis [1950]
V. New foundations for mathematical logic
[1937]
VI. Logic and the reification of universals
[1939, 1947, 1950]
VII. Notes on the theory of reference [1951]
VIII. Reference and modality [1943, 1947, 1952]
IX. Meaning and existential reference [1947,
1953] Origins of the Essays
Bibliographical references
Index
Quine, Willard Van Orman. Mathematical Logic. revised
edition. Harvard University Press (Cambridge, MA: 1940, 1951,
1979, 1981). ISBN 0-674-55451-5 pbk.
It would appear that there is little change
between this and the 1951 edition. The original work
endures.
This work is solidly grounded in the Principia
Mathematica model, with great improvement in clarity:
"I like to think that I also helped in the
struggle against confusions of use and mention. Certainly I was
persistent in precept and scrupulous in example, and happily the
situation has vastly improved. Still, my efforts against the
related confusion of implication with the conditional, and of
equivalence with what I named the biconditional, have been only
partially successful if we may judge by lingering nomenclature.
"The final chapter has two purposes. One
purpose was to show how the metalogical discourse about a formal system
would look when formalized in turn. The other and higher purpose
was to teach a proof of Gödel's incompleteness theorem. My
proof, unlike Gödel's shuns numbers until the coup de grâce.
It proceeds rather in what I called protosyntax, as a proof that
protosyntactical truth is not definable in protosyntax. Thus seen,
it is a case of Tarski's theorem that theories meeting certain
reasonable conditions cannot contain their own truth definitions.
Finally, Gödel's theorem is derived by correlating protosyntax with
number theory." -- From the Preface, 1981, p.v.
To provide a sense of the foundational work
around formalization and the use of language and metalanguage, I display
here the complete content for Chapters One - Three and for Chapter
Seven. This is an useful contrasting to the mathematical
logics of Church and Curry,
and another backdrop to the modern conceptualization in Mendelson.
-- dh:2002-07-25.
Content Preface, 1981
Preface to the Revised Edition (1951)
Preface
Introduction
Chapter One. Statements 1.
Conjunction, Alternation, and Denial
2. The
Conditional
3. Iterated
Composition
4. Use Versus
Mention
5. Statements
about Statements
6.
Quasi-Quotation
7. Parentheses
and Dots
8. Reduction to
Three Primitives
9. Reduction to
One Primitive
10. Tautology
11. Selected
Tautologous Forms
Chapter Two. Quantification 12. The
Quantifier
13. Formulae
14. Bondage,
Freedom, Closure
15. Axioms of
Quantification
16. Theorems
17. Metatheorems
18.
Substitutivity of the Biconditional
19. Existential
Quantification
20. Distribution
of Quantifiers
21. Alphabetic
Variance
Chapter Three. Terms 22. Class and
Member
23. Logical
Formulae
24. Abstraction
25. Identity
26. Abstraction
Resumed
27. Descriptions
and Names
Chapter Four. Extended Theory of
Classes
Chapter Five. Relations
Chapter Six. Number
Chapter Seven. Syntax 53. Formality
54. The
Syntactical Primitive
55. Protosyntax
56. Formula and
Matrix Defined
57. Axioms of
Quantification Defined
58. Theorem
Defined
59. Protosyntax
Self-Applied
60.
Incompleteness
Appendix. Theorem versus Metatheorem List of Definitions
List of Theorems and Metatheorems
Bibliographical References
Index of Proper Names
Index of Subjects
Quine, Willard Van Orman. Methods of Logic. Fourth
Edition. Harvard University Press (Cambridge, MA: 1959, 1972,
1978, 1982). ISBN 0-674-57176-2 pbk.
I am looking for a book that
works through predicate logic to the point where its application can be
appreciated and the relationships among First-Order Logic (FOL),
Higher-Order Logics (HOLs), Peano Arithmetic (PA) toward number theory,
and set theory can be appreciated and differentiated where clarity is
important. This seems like a friendly place to commence such a
journey.
I must confess that another incentive for me
was to find Quine's discussion of the Geach-Kaplan sentence on
p.293. For me, this just compounds my bafflement about how
"Some people admire only one another" is translated into an
HOL reading. [dh:2004-02-13]
"Logic, like any science has as its
business the pursuit of truth. What are true are
certain statements; and the pursuit of truth is the endeavor to sort out
the true statements from the others, which are false. ... But scientific
activity is not the indiscriminate amassing of truths; science is
selective and seeks the truths that count for most, either in point of
intrinsic interest or as instruments for coping with the
world." Introduction, p.1.
Content Preface [1982]
Introduction
Part I. Truth Functions
Part II. General Terms and Quantifiers
Part III. General Theory of Quantification
27. Schemata
Extended
28. Substitution
Extended
29. Pure
Existentials
30. The Main
Method
31. Application
32. Completeness
33. Löwenheim's
Theorem
34. Decisions and the Undecidable
35. Functional Normal Forms
36. Herbrand's Method
37. Other Methods of Validity
38. Deduction
39. Soundness
40. Deductive Strategy
Part IV. Glimpses Beyond
41. Singular
Terms
42. Identity
43. Descriptions
44. Elimination
of Singular Terms
45. Elimination
of Variables
46. Classes
47. Number
48. Axiomatic Set
Theory Partial Answers to Exercises
Bibliography
Index
Quine, Willard Van Orman. Philosophy of Logic.
ed.2. Harvard University Press (Cambridge, MA: 1970, 1986).
ISBN 0-674-66563-5.
"If pressed to [provide] a discursive
definition of [deductive logic], I would say that logic is the
systematic study of the logical truths. Pressed further, I would
say to read this book.
"Since I see logic as the resultant of two
components, truth and grammar, I shall treat truth and grammar
prominently. But I shall argue against the doctrine that the
logical truths are true because of grammar, or because of language.
"The notions of proposition and meaning
will receive adverse treatment. Set theory will be compared and
contrasted with logic, and ways will be examined of disguising each to
resemble the other. The status and claims of alternative logic
will be discussed, and reasons will be adduced for being thankful for
what we have." -- from the Preface, 1986, p.vii.
Content Preface, 1986
1. Meaning and Truth
2. Grammar
3. Truth
4. Logical Truth
5. The Scope of Logic
6. Deviant Logics
7. The Ground of Logical Truth For Further Reading
Index
Robinson, Abraham. Non-Standard Analysis. ed.2.
Princeton University Press (Princeton, NJ: 1965, 1973,
1996). ISBN 0-691-04490-2 pbk. Re-issue of the 1973 second
edition with a 1996 foreword by Wilhelmus A. J. Luxemburg.
This book is about mathematics, in particular
analysis, based on a non-standard model of numbers in which
infinitesimal and infinitely large elements have first-class standing as
individuals of the theory. A highly-productive approach grounded
in mathematical logic, this book provides an application of
model-theoretic approaches. The chapter
on logic supports other materials on mathematical logic. More
information is under Readings in Mathematics.
Rosenbloom, Paul. The Elements of Mathematical Logic.
Dover (New York: 1950). pbk.
I wore out my original copy of this book,
acquired sometime before 1962. Although now out-of-print, a
replacement lives up to Dover's promise that this is a permanent book.
[dh: 2000-10-11]
"In this book we shall study the laws of
logic by mathematical methods. This may seem unfair, since logic
is used in constructing mathematical proofs, and it might appear that
the study of logic should come before the study of mathematics.
Such a procedure is, however, typical of science. Our actual
knowledge is a narrow band of light flanked on both sides by
darkness. We may, on the one hand, go forward and develop further
the consequences of known principles. Or else we may press
backward the obscurity in which the foundations of science are
enveloped. Just by using mathematical methods ... we can throw new
and important light on the logical principles used in mathematics.
This approach has led to more knowledge about logic in one century
than had been obtained from the death of Aristotle up to 1847, when
Boole's masterpiece was published." From the Introduction, p.i.
Contents Introduction
I. The Logic of Classes
1. Informal
introduction. Fundamental theorems
2. Boolean
algebra as a deductive science
3. The structure
and representation of Boolean algebras
II. The Logic of Propositions
1. Fundamentals
2. Alternative
formulations
3. Deductive
systems
4. Many valued
logics, modal logics, intuitionism
III. The Logic of Propositional Functions
1. Informal
introduction
2. The functional
logic of the first order
3. Some very
expressive languages
4. Combinatory
logics
5. The
development of mathematics within an object language
6. The paradoxes
7. The axiom of
choice
IV. The General Syntax of Language
1. Basic
concepts. Simple languages
2. Production,
canonical languages, extension, and definition
3. Normal
languages. Theorems of Post and Gödel
Appendix 1. Canonical forms of L_{1},
L_{2}', and L_{z
} Appendix 2. Algebraic approach to
languages. Church's theorem. Bibliographical and Other Remarks Index
Russell, Bertrand. The Principles of Mathematics. ed. 2. George Allen & Untwin Ltd. (London: 1903,
1937).
I have heard it asked: "What was Cantor
trying to do when he came up with transfinite numbers (the cardinals
for the powers of infinite sets)?" What he was trying to deal
with was problems of reasoning about the infinite that came up in
everything beyond the natural numbers: reals, spaces of reals, measures,
quantities, the foundations of mathematical physics.
What was at stake can be seen in Russell's
ambitious table of contents. It is not that Russell saw these as
resolved by mathematical logic, though he would have though such to be
achievable at least until Gödel unseated the
undertaking. I don't take that to mean that the effort was not
worthwhile, although the laborious formulation of Principia
Mathematica has been found to be avoidable within the more succinct
approaches of present-day logic with axiomatic set theory.
We have not ceased to rely on the logic and
mathematics of the unattainable, nor did Gödel compel us to.
The situation at hand is far more subtle than the black-and-white
resolution we yearn for. Russell's 1937 introduction lays out the
dilemma for all to see, no matter which direction we might favor and
what of Russell's particular spin we choose to neglect. The
inquiry continues into its second century. This provides useful
background to subsequent commentators. It is interesting that,
however much the details are refined and the reasoning improved and
streamlined, the great questions remain. -- dh:2002-07-27
"The fundamental thesis of the following
pages, that mathematics and logic are identical, is one which I have
never since seen any reason to modify. This thesis was, at first,
unpopular ... but such feelings would have no lasting influence if they
had been unable to find support in more serious reasons for doubt.
These reasons are, broadly speaking, of two opposite kinds: first, that
there are certain unsolved difficulties in mathematical logic, which
make it appear less certain than mathematics is believed to be; and
secondly that, if the logical basis of mathematics is accepted, it
justifies, or tends to justify, much work, such as that of Georg Cantor,
which is viewed with suspicion by many mathematicians on account of the
unsolved paradoxes which it shares with logic. These two opposite
lines of criticism are represented by the formalists, led by Hilbert,
and the intuitionists, led by Brouwer.
"The formalist interpretation ... consists
in leaving the integers undefined, but asserting concerning them such
axioms as shall make possible the deduction of the usual arithmetical
propositions. That is to say, we do not assign any meaning to our
symbols 0, 1, 2, . . except that they are to have certain properties
enumerated in the axioms. ... The later integers may be defined
when 0 is given, but 0 is to be merely something having the assigned
characteristics. Accordingly the symbols 0, 1, 2, ... do not
represent one definite series, but any progression whatever.
The formalists have forgotten that numbers are needed. ... For the
symbol '0' may be taken to mean any finite integer, without thereby
making any of Hilbert's axioms false; and thus every number-symbol
becomes infinitely ambiguous. The formalists are like a watchmaker
who is so absorbed in making his watches look pretty that he has
forgotten their purpose of telling the time, and has therefore omitted
to insert any works.
"There is another difficulty ... and that
is as regards existence. ... For [Hilbert] 'existence' as usually
understood, is an unnecessary metaphysical concept, which should be
replaced by the precise concept of non-contradiction. ... Here again, he
has forgotten that arithmetic has practical uses. ... Our reasons
for being specially interested in the axioms that lead to ordinary
arithmetic lie outside arithmetic, and have to do with the application
of numbers to empirical material. This application itself forms no
part of either logic or arithmetic; but a theory which makes it a
priori impossible cannot be right. ...
"The intuitionist theory ... is a more
serious matter. ... The essential point here is the refusal to regard a
proposition as either true or false unless some method exists of
deciding the alternative. Brouwer denies the law of excluded
middle where no such method exists. This destroys, for example,
the proof that there are more real numbers than rational numbers, and
that, in the series of real numbers, every progression has a
limit. Consequently large parts of analysis, which for centuries
have been thought well established, are rendered doubtful." -- from
the Introduction to the Second Edition, pp.v-vi.
2004-12-02: "Pure
mathematics is the class of all propositions of the form 'p
implies q,' where p and q are propositions
containing one or more variables, the same in the two propositions, and
neither p nor q contains any constants except logical
constants. And logical constants are all notions defined in terms
of the following: Implication, the relation of a term to a class of
which it is a member, the notion of such that, the notion of
relation, and such further notions as may be involved in the general
notion of propositions of the above form. In addition to these,
mathematics uses a notion which is not a constituent of the
propositions which it considers, namely the notion of truth." --
Chapter I, p.3.
Content Introduction to the Second Edition
Preface
Part I. The
Indefinables of Mathematics
Chapter I.
Definition of Pure Mathematics
Chapter II.
Symbolic Logic
Chapter
III. Implication and Formal Implication
Chapter IV.
Proper Names, Adjectives and Verbs.
Chapter V.
Denoting
Chapter VI.
Classes
Chapter
VII. Propositional Functions
Chapter
VIII. The Variable
Chapter IX.
Relations
Chapter X.
The Contradiction
Part II. Number
Chapter XI.
Definition of Cardinal Numbers
Chapter
XII. Addition and Multiplication
Chapter
XIII. Finite and Infinite
Chapter
XIV. Theory of Finite Numbers
Chapter XV.
Addition of Terms and Addition of Classes
Chapter
XVI. Whole and Part
Chapter XVII.
Infinite Wholes
Chapter XVIII.
Ratios and Fractions
Part III. Quantity
Chapter XIX.
The Meaning of Magnitude
Chapter XX.
The Range of Quantity
Chapter XXI.
Numbers as Expressing Magnitudes: Measurement
Chapter XXII.
Zero
Chapter XXIII.
Infinity, the Infinitesimal, and Continuity
Part IV. Order
Chapter XXIV.
The Genesis of Series
Chapter XXV.
The Meaning of Order
Chapter XXVI.
Asymmetrical Relations
Chapter XXVII.
Difference of Sense and Difference of Sign
Chapter XXVIII.
On the Difference Between Open and Closed Series
Chapter XXIX.
Progressions and Ordinal Numbers
Chapter XXX.
Dedekind's Theory of Number
Chapter XXXI.
Distance
Part V. Infinity
and Continuity
Chapter XXXII.
The Correlation of Series
Chapter XXXIII.
Real Numbers
Chapter XXXIV.
Limits and Irrantional Numbers
Chapter XXXV.
Cantor's First Definition of Continuity
Chapter XXXVI.
Ordinal Continuity
Chapter XXXVII.
Transfinite Cardinals
Chapter XXXVIII.
Transfinite Ordinals
Chapter XXXIX.
The Infinitesimal Calculus
Chapter XL.
The Infinitesimal and the Improper Infinite
Chapter XLI.
Philosophical Arguments Concerning the Infinitesimal
Chapter XLII.
The Philosophy of the Continuum
Chapter XLIII.
The Philosophy of the Infinite
Part VI. Space
Chapter XLIV.
Dimensions and Complex Numbers
Chapter XLV.
Projective Geometry
Chapter XLVI.
Descriptive Geometry
Chapter XLVII.
Metrical Geometry
Chapter XLVIII.
Relation of Metrical to Projective and Descriptive Geometry
Chapter XLVIX.
Definitions of Various Spaces
Chapter L.
The Continuity of Space
Chapter LI.
Logical Arguments against Points
Chapter LII.
Kant's Theory of Space
Part VII. Matter and
Motion
Chapter LIII.
Matter
Chapter LIV.
Motion
Chapter LV.
Causality
Chapter LVI.
Definition of a Dynamical World
Chapter LVIL.
Newton's Laws of Motion
Chapter LVIII.
Absolute and Relative Motion
Chapter LIX.
Hertz's Dynamics
Appendix A. The Logical and Arithmetical
Doctrines of Frege
Appendix B. The Doctrine of Types Index
Schönfinkel, Moses. Über die Bausteine der mathematischen
Logik. Mathematische Annalen 92 (1924), 305-316.
Stefan Bauer-Mengelberg English translation "On the Building Blocks of
Mathematical Logic" reprinted in [vanHeijenoort1977:
355-366] with an introduction by W.V.Quine [Quine1977].
Smullyan, Raymond M. Theory of Formal Systems.
Annals of Mathematical Studies Number 47. Princeton University Press
(Princeton, NJ: 1961). ISBN 0-691-08047-X pbk.
It is difficult to believe that I picked this
small book off of a shelf at Seattle's University Bookstore when it first appeared, in its now-quaint typewritten
manuscript. I did not expect to find it still in print, until I
had occasion to check after recommending its treatment of formal systems
from somewhere near the ground up. I am delighted to have it again
in my possession. There is much here that provides value
today. dh:2004-06-15
"We are interested in first giving a
precise definition of a 'formal' or 'finitary' mathematical system, and
then in establishing an important theorem, based on the works of Church
and Post, concerning an interesting limitation of our possible knowledge
of such systems. ...
"Our plan is to define first a certain
type of system termed an 'elementary formal system' which will serve as
a basis for our study of metamethematics [sic] (theory of mathematical
systems). The general notion of a 'formal system' will then be
defined in terms of these elementary systems." - Chapter I, p.1.
Content Annals of Mathematics Studies [bonus
list of the first 47] Preface
I. Formal Mathematical Systems
II. Formal Representability and Recursive
Enumerability
III. Incompleteness and Undecidability
IV. Recursive Function Theory
V. Creativity and Effective Inseparability
Supplement: Applications to Mathematical Logic
Reference and Brief Bibliography
Smullyan, Raymond M. First-Order Logic. Dover
Publications (New York: 1968, 1995). ISBN 0-486-68370-2 pbk.
Unabridged, corrected republication of the work first published by
Springer-Verlag, New York, 1968.
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]
Stoll, Robert R. Set Theory and Logic. Dover
Publications (New York: 1961, 1964). ISBN 0-486-63829-4.
This book subsumes the material of Stoll's
earlier Sets,
Logic, and Axiomatic Theories, providing more comprehensive
treatment.
"Cantor's investigation of questions
pertaining to trigonometric series and series of real numbers led him to
recognize the need for a means of comparing the magnitude of infinite
sets of numbers. To cope with this problem, he introduced the
notion of the power (or size) of a set by defining two sets as having
the same power if the members of one can be paired with those of
the other. ... The notion of power for infinite sets provides a
generalization of everyday counting numbers. Cantor developed the
theory, including an arithmetic, of these generalized (or transfinite)
numbers and in so doing created a theory of sets. His
accomplishments in this area are regarded as an outstanding example of
mathematical creativity.
"Cantor's insistence on dealing with the
infinite as an actuality ... was an innovation at that time.
Prejudices against this viewpoint were responsible for the rejection of
his work by some mathematicians, but others reacted favorably because
the theory provided a proof of the existence of transcendental
numbers. Other applications in analysis and geometry were found,
and Cantor's theory of sets won acceptance to the extent that by 1890 it
was recognized as an autonomous branch of mathematics. About the
turn of the century there was some change in attitude with the discovery
that contradictions could be derived within the theory. That these
were not regarded as serious defects is suggested by their being called
paradoxes--defects which could be resolved, once full understanding was
acquired. ..." -- from Chapter 1, Sets and Relations,
pp. 1-2.
The development of Set Theory is along the
standard Zermelo-Fraenkel lines (cf. [Suppes1972]). The
von Neumann-Bernays-Gödel
approach is sketched, with appropriate references to the original
formulations. This treatment provides coverage of Boolean
algebras and algebraic systems, going beyond the foundational treatments
of other works. It ends with a discussion of Skolem's paradox and
the uncertainty we are left with. --dh:2002-07-24
Contents
Preface
Chapter 1. Sets and Relations
1. Cantor's
Concept of a Set
2. The Basis of
Intuitive Set Theory
3. Inclusion
4. Operations for
Sets
5. The Algebra of
Sets
6. Relations
7. Equivalence
Relations
8. Functions
9. Composition
and Inversion for Functions
10. Ordering
Relations
Chapter 2. The Natural Number Sequence and
Its Generalizations
1. The Natural
Number Sequence
2. Proof and
Definition by Induction
3. Cardinal
Numbers
4. Countable Sets
5. Cardinal
Arithmetic
6. Order Types
7. Well-ordered
Sets and Ordinal Numbers
8. The Axiom of
Choice, the Well-ordering Theorem, and Zorn's Lemma
9. Further
Properties of Cardinal Numbers
10. Some Theorems
Equivalent to the Axiom of Choice
11. The Paradoxes
of Intuitive Set Theory
Chapter 3. The Extension of the Natural
Numbers to the Real Numbers
1. The
System of Natural Numbers
2. Differences
3. Integers
4. Rational
Numbers
5. Cauchy
Sequences of Natural Numbers
6. Real Numbers
7. Further
Properties of the Real Number Systems
Chapter 4. Logic
1. The Statement
Calculus. Sentential Connectives
2. The Statement
Calculus. Truth Tables
3. The Statement
Calculus. Validity
4. The Statement
Calculus. Consequence
5. The Statement
Calculus. Applications
6. The Predicate
Calculus. Symbolizing Everyday Language
7. The Predicate
Calculus. A Formulation
8. The Predicate
Calculus. Validity
9. The Predicate
Calculus. Consequence
Chapter 5. Informal Axiomatic Mathematics
1. The Concept of
an Axiomatic Theory
2. Informal
Theories
3. Definitions of
Axiomatic Theories by Set-theoretical Predicates
4. Further
Features of Informal Theories
Chapter 6. Boolean Algebras
1. A Definition
of a Boolean Algebra
2. Some Basic
Properties of a Boolean Algebra
3. Another
Formulation of the Theory
4. Congruence
Relations for a Boolean Algebra
5.
Representations of Boolean Algebras
6. Statement
Calculi as Boolean Algebras
7. Free Boolean
Algebras
8. Applications
of the Theory of Boolean Algebras to Statement Calculi
9. Further
Interconnections between Boolean Algebras and Statement Calculi
Chapter 7. Informal Axiomatic Set Theory
1. The Axioms of
Extension and Set Formation
2. The Axioms of
Pairing
3. The Axioms of
Union and Power Set
4. The Axioms of
Infinity
5. The Axiom of
Choice
6. The Axiom
Schemas of Replacement and Restriction
7. Ordinal
Numbers
8. Ordinal
Arithmetic
9. Cardinal
Numbers and Their Arithmetic
10. The von
Neumann-Bernays-Gödel Theory of Sets
Chapter 8. Several Algebraic Theories
1. Features of
Algebraic Theories
2. Definition of
a Semigroup
3. Definition of
a Group
4. Subgroups
5. Coset
Decompositions and Congruence Relations for Groups
6. Rings,
Integral Domains, and Fields
7. Subrings and
Difference Rings
8. A
Characterization of the System of Integers
9. A
Characterization of the System of Rational Numbers
10. A
Characterization of the Real Number System
Chapter 9. First-Order Theories
1. Formal
Axiomatic Theories
2. The Statement
Calculus as a Formal Axiomatic Theory
3. Predicate
Calculi of First Order as Formal Axiomatic Theories
4. First-order
Axiomatic Theories
5.
Metamathematics
6. Consistency
and Satisfiability of Sets of Formulas
7. Consistency,
Completeness, and Categoricity of First-order Theories
8. Turing
Machines and Recursive Functions
9. Some
Undecidable and Some Decidable Theories
10. Gödel's
Theorems
11. Some Further
Remarks about Set Theory References
Symbols and Notation
Author Index
Subject Index
Stolyar, Abram Aronovich. Introduction to Elementary
Mathematical Logic. Dover (New York: 1970). ISBN
0-486-64561-4 pbk. Unabridged and unaltered 1983 republication of
the work published by MIT Press (Cambridge, MA: 1970). Translation
of Elementarnoe vvedenie v matematicheskuiu logiku,
Prosveshcheniye Press (Moscow: 1965), with translation from the Russian
edited by Elliot Mendelson.
"By virtue of its numerous applications in
the most varied fields of science and technology ..., present-day
mathematical logic is attracting the attention of a large number of
persons in various specialties, including high-school mathematics
teachers.
"The elements of mathematical logic and
certain of its applications are included in the programs of high schools
that place emphasis on mathematics. They can serve as interesting
material for out-of-class work for students in the higher grades of any
high school. ...
"... This book cannot be regarded as an
introduction to mathematical logic as a whole. However, a
familiarity with the material expounded in it will make it easier for
the reader who is seriously interested in studying the subject to read
the literature recommended for this purpose at the end of the
book." -- From the Author's Preface.
This book was developed for high school
students. I recommend it as an introduction to logic because of
its availability (under $10 in 2002), gentle pace, and introduction to the
formalization of logic with careful attention to motivation and
application. In the past, access to elementary formal/axiomatic
logic arose in the works designed to popularize the symbology and
approach of Principia Mathematica.
Stolyar provides a treatment that is consistent with the now-popular
notations of formalized theories, carrying the reader through to
first-order logic with equality. This is a nice starter kit for
further exploration and the application of logic in computer science,
say by studying Enderton. --
dh:2002-07-25.
Content Author's Preface
Introduction Chapter 1: Propositional Logic
1. Objects and
operations
2.
Formulas. Equivalent formulas. Tautologies.
3. Examples of
the application of the laws of the logic of propositions in derivations.
4. Normal forms
of functions. Minimal forms.
5. Application of
the algebra of propositions to the synthesis and analysis of
discrete-action networks. Chapter 2: The Propositional Calculus
1. The axiomatic
method. The construction of formalized languages.
2. Construction
of a propositional calculus (alphabet, formulas, derived formulas).
3. Consistency,
independence, and completeness of a system of axioms in the
propositional calculus. Chapter 3: Predicate Logic
1. Sets.
Operations on sets.
2. The inadequacy
of propositional logic. Predicates.
3. Operations on
predicates. Quantifiers.
4. Formulas of
predicate logic. Equivalent formulas. Universally valid
formulas.
5. Traditional
logic (the logic of one-place predicates).
6. Predicate
logic with equality. Axiomatic construction of mathematical
theories in the language of predicate logic with equality. Appendices
I. A proof of the
duality principle for propositional logic.
II. A proof of
the deduction theorem for the propositional calculus.
III. A proof of
the completeness theorem for the propositional calculus. Bibliography
Index of Special Symbols
Index
Suppes,
Patrick Colonel. Axiomatic Set Theory. D. Van
Nostrand (New York: 1960). Unabridged and corrected republication
with new preface and section 8.4, Dover Publications (New York:
1972). ISBN 0-486-61630-4
pbk.
"This book is intended primarily to serve
as a textbook for courses in axiomatic set theory. The
Zermelo-Fraenkel system is developed in detail. The mathematical
prerequisites are minimal; in particular, no previous knowledge of set
theory or mathematical logic is assumed. On the other hand,
students will need a certain degree of general mathematical
sophistication, especially to master the last two chapters.
Although some logical notations is used throughout the book, proofs are
written in an informal style and an attempt has been made to avoid
excessive symbolism. A glossary of the more frequently used
symbols is provided." -- from the Preface to the First Edition, p.vii.
"The working mathematician, as well as the
man in the street, is seldom concerned with the unusual question: What
is a number? But the attempt to answer this question precisely has
motivated much of the work by mathematicians and philosophers in the
foundations of mathematics during the past hundred years.
Characterization of the integers, rational numbers and real numbers has
been a central problem for the classical researches of Weierstrass,
Dedekind, Kronecker, Frege, Peano, Russell, Whitehead, Brouwer, and
others. ...
"Yet the real development of set theory
was not generated directly by an attempt to answer this central problem
of the nature of number, but by the researches of Georg
Cantor around 1870 in the theory of infinite series and related
topics of analysis. Cantor, who is usually considered the founder
of set theory as a mathematical discipline, was led by his work into a
consideration of infinite sets or classes of arbitrary character.
In 1874 he published his famous proof that the set of real numbers
cannot be put into one-one correspondence with the set of natural
numbers (the non-negative integers). In 1878 he introduced the
fundamental notion of two sets being equipollent or having the same
power (Mächtigkeit) if they can be put into one-one
correspondence with each other. ... The notion of power leads in
the case of infinite sets to a generalization of the notion of a natural
number to that of an infinite cardinal number. Development of the
general theory of transfinite numbers was one of the great
accomplishments of Cantor's mathematical researches.
" ... From the standpoint of the
foundations of mathematics the philosophically revolutionary aspect of
Cantor's work was his bold insistence on the actual infinite, that is,
on the existence of infinite sets as mathematical objects on a par with
numbers and finite sets. There is scarcely a serious philosopher
of mathematics since Aristotle who has not been much exercised about
this difficult concept." -- from the Introduction §1.1,
pp.1-2.
I have been mining in here to train myself at
clarifying questions involving denumerable sets as the ceiling under
which computation (and any other effective process) is compelled to
operate. This leads me to take a cycle around the foundational
topics of set, number, and the transfinite. In selecting sections
to identify the expanded content for, I realized that the only ones I
might safely neglect are chapters 3 and 7, and I am not so certain of
that. So here are all of the section titles. -- dh:2002-07-24
Content Preface to the Dover Edition
Preface to the First Edition
1. Introduction
1.1 Set Theory
and the Foundations of Mathematics
1.2 Logic and
Notation
1.3 Axiom Schema
of Abstraction and Russell's Paradox
1.4 More
Paradoxes
1.5 Preview of
Axioms
2. General Developments 2.1
Preliminaries: Formulas and Definitions
2.2 Axioms of
Extensionality and Separation
2.3 Intersection,
Union, and Difference of Sets
2.4 Pairing Axiom
and Ordered Pairs
2.5 Definition by
Abstraction
2.6 Sum Axiom and
Families of Sets
2.7 Power Set
Axiom
2.8 Cartesian
Product of Sets
2.9 Axiom of
Regularity
2.10 Summary of
Axioms
3. Relations and Functions 3.1
Operations on Binary Relations
3.2 Ordering
Relations
3.3 Equivalence
Relations and Partitions
3.4 Functions
4. Equipollence, Finite Sets, and Cardinal
Numbers 4.1
Equipollence
4.2 Finite Sets
4.3 Cardinal
Numbers
4.4 Finite
Cardinals
5. Finite Ordinals and Denumerable Sets 5.1
Definition and General Properties of Ordinals
5.2 Finite
Ordinals and Recursive Definitions
5.3 Denumerable
Sets
6. Rational Numbers and Real Numbers 6.1
Introduction
6.2 Fractions
6.3 Non-negative
Rational Numbers
6.4 Rational
Numbers
6.5 Cauchy
Sequences of Rational Numbers
6.6 Real Numbers
6.7 Sets of the
Power of the Continuum
7. Transfinite Induction and Ordinal Arithmetic 7.1
Transfinite Induction and Definition by Transfinite Induction
7.2 Elements of
Ordinal Arithmetic
7.3 Cardinal
Numbers Again and Aleph
7.4 Well-Ordered
Sets
7.5 Revised
Summary of Axioms
8. The Axiom of Choice 8.1 Some
Applications of the Axiom of Choice
8.2 Equivalents
of the Axiom of Choice
8.3 Axioms Which
Imply the Axiom of Choice
8.4 Independence
of the Axiom of Choice and the Generalized Continuum Hypothesis References
Glossary of Symbols
Author Index
Subject Index
Tarski, Alfred., Mostowski, Andrzej., Robinson, Raphael M. Undecidable
Theories. North-Holland (Amsterdam: 1953).
Studies in Logic and the Foundation of Mathematics.
Content Preface
I. A General Method in Proofs of Undecidability,
Alfred Tarski
I.1 Introduction
I.2 Theories with
standard formulation
I.3 Undecidable
and essentially undecidable theorems
I.4
Interpretability and weak interpretability
I.5
Relativization of quantifiers
I.6 Examples and
applications
II. Undecidability and Essential Undecidability
in Arithmetic, Andrzej Mostowski, Raphael M. Robinson, and Alfred
Tarski II.1 A
summary of results; notations
II.2 Definability
in arbitrary theories
II.3 Formalized
arithmetic of natural numbers and its sub-theories
II.4
Recursiveness and definability in subtheories of arithmetic
II.5
Undecidability of subtheories of arithmetic
II.6 Extension of
the results to other arithmetical theories and to various theories of
rings III. Undecidability of the Elementary
Theory of Groups, Alfred Tarski Bibliography
Index
Tarski, Alfred. Logic, Semantics, Metamathematics: Papers
from 1923 to 1938. translated by J. H. Woodger. Oxford
University Press (London: 1956).
This book is in the holdings of the Seattle
Public Library and I needed a member of the staff to check it out to
me. It is also not renewable and I am capturing the contents
before returning it unread (this time). Some of the articles have
been updated slightly from the original published versions, so this is
generally a superior reference to many of those earlier papers.
dh:2004-10-22.
Content Translator's Preface
Author's Acknowledgments
1. On the Primitive Term of Logistic [1923]
2. Foundations of the Geometry of Solids [1929]
3. On Some Fundamental Concepts of
Metamathematics [1930]
4. Investigations into the Sentential Calculus
(with Jan Łukasiewicz) [1930]
5. Fundamental Concepts of the Methodology of
the Deductive Sciences [1930]
6. On Definable Sets of Real Numbers [1931]
7. Logical Operations and Projective Sets (with
Casimir Kuratowski) [1931]
8. The Concept of Truth in Formalized Languages
[1935]
9. Some Observations on the Concepts of
ω-Consistency and ω-Completeness [1933]
10. Some Methodological Investigations on the
Definability of Concepts [1935]
11. On the Foundations of Boolean Algebra
[1935]
12. Foundations of the Calculus of
Systems [1936]
13. On the Limitations of the Means of
Expression of Deductive Theories (with Adolf Lindenbaum) [1935]
14. On Extensions of Incomplete Systems of the
Sentential Calculus [1935]
15. The Establishment of Scientific Semantics
[1936]
16. On the Concept of Logical Consequence
[1936]
17. Sentential Calculus and Topology [1938] Abbreviations
Bibliography
Subject Index
Index of Names of Persons
Index of Symbols
van Heijenoort, Jean (ed). From Frege to Gödel: A Source Book in
Mathematical Logic, 1879-1931. Harvard University Press
(Cambridge, MA: 1967), 3rd (1977) printing. ISBN 0-674-32449-8
(paper).
Contents General Editor's Preface
Preface
Note to the Second Printing
Note to the Third Printing Gottlob Frege. Begriffsschrift, a formal
language, modeled upon that of arithmetic, for pure thought [1879] Giuseppe Peano. The principles of
arithmetic, presented by a new method [1889] Richard Dedekind. Letter to Keferstein
[1890a] Cesare Burali-Forti. A question on
transfinite numbers [1897] Cesare Burali-Forti. On well-ordered classes
[1897a] Georg Cantor. Letter to Dedekind [1899] Alessandro Padoa. Logical introduction to
any deductive theory [1900] Bertrand Russell. Letter to Frege [1902] Gottlob Frege. Letter to Russell [1902] David Hilbert. On the foundations of
logic and arithmetic [1904] Ernst Zermelo. Proof that every set can
be well-ordered [1904] Jules Richard. The principles of
mathematics and the problem of sets [1905] Julius König. On the foundations of set
theory and the continuum problem [1905a] Bertrand Russell. Mathematical logic as
based on the theory of types [1908a] Ernst Zermelo. A new proof of the
possibility of a well-ordering [1908] Ernst Zermelo. Investigations in the
foundations of set theory I [1908a] Alfred North Whitehead and Bertrand
Russell. Incomplete symbols: Descriptions [1910] Norbert Wiener. A simplification of the
logic of relations [1914] Leopold Löwenheim. On possibilities in
the calculus of relatives [1915] Thoralf Skolem. Logico-combinatorial
investigations in the satisfiability or provability of mathematical
propositions: A simplified proof of a theorem by L. Löwenheim and
generalizations of the theorem [1920] Emil Leon Post. Introduction to a general
theory of elementary propositions [1921] Abraham A. Fraenkel. The notion
"definite" and the independence of the axiom of choice [1922b] Thoralf Skolem. Some remarks on
axiomatized set theory [1922] Thoralf Skolem. The foundations of
elementary arithmetic established by means of the recursive mode of
thought, without the use of apparent variable ranging over infinite
domains [1923] Luitzen Egbertus Jan Brouwer. On the
significance of the principle of excluded middle in mathematics,
especially in function theory. [1923b, 1954, 1954a] John von Neumann. On the introduction of
transfinite numbers. [1923] Moses Schönfinkel. On the building
blocks of mathematical logic [1924] David Hilbert. On the infinite [1925] John von Neumann. An axiomatization of
set theory [1925] Andrei Nikolaevich Kolmogorov. On the
principle of excluded middle [1925] Paul Finsler. Formal proofs and
undecidability [1926] Luitzen Egbertus Jan Brouwer. On the
domains of definition of functions [1927] David Hilbert. The foundations of
mathematics [1927] Hermann Weyl. Comments on Hilbert's
second lecture on the foundations of mathematics [1927] Paul Bernays. Appendix to Hilbert's
lecture "The foundations of mathematics" [1927a] Luitzen Egbertus Jan Brouwer.
Intuitionistic reflections on formalism [1927] William Ackermann. On Hilbert's
construction of the real numbers [1928] Thoralf Skolem. On mathematical logic
[1928] Jacques Herbrand. Investigations in proof
theory: The properties of true propositions [1930] Kurt Gödel. The completeness of the
axioms of the functional calculus of logic [1930a] Kurt Gödel. Some metamathematical
results on completeness and consistency [1930b] Kurt Gödel. On formally undecidable
propositions of Principia Mathematica and related systems [1931] Kurt Gödel. On completeness and
consistency [1931a] Jacques Herbrand. On the consistency of
arithmetic [1931] References
Index
Corrections made in the second printing
Corrections made in the third printing
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]
von Neumann, John. Zur Einführung der transfiniten Zahlen.
Acta litterarum ac scientiarum Regiae Universitatis Hungaricae
Francisco-Josephinae, Section scientiarum mathematicarum 1
(1923), 199-208. Translated with an editorial preface by Jean van
Heijenoort as "On the introduction of transfinite numbers" on
pp. 346-354 in From Frege to Gödel: A Source Book in
Mathematical Logic, 1879-1931. Jean van Heijenoort, editor.
Harvard University Press
(Cambridge, MA: 1967), 3rd (1977) printing. ISBN 0-674-32449-8
(paper). See [vanHeijenoort1977]
von Neumann, John. Eine Axiomatisierung der Mengenlehre (An
Axiomatization of Set Theory). Journal
für die reine und angewandte Mathematik 154,
219-240. Berichtigung, ibid. 155, 128.
Translated by Stefan Bauer-Mengelberg and Dagfinn Fellesdal with an
editorial preface as "An axiomatization of set theory" on pp.
393-413 in From Frege to Gödel: A Source Book in
Mathematical Logic, 1879-1931. Jean van Heijenoort, editor.
Harvard University Press
(Cambridge, MA: 1967), 3rd (1977) printing. ISBN 0-674-32449-8
(paper). See [vanHeijenoort1977]
Whitehead, Alfred North., Russell, Bertrand. Principia
Mathematica to *56. Cambridge Mathematical Library
edition. Cambridge University Press (London: 1910, 1927, 1962,
1997). ISBN 0-521-62606-4 pbk.
Contents Preface (1910)
Alphabetical List of Propositions Referred to
by Names
Introduction to the Second Edition (1927)
Introduction
I. Preliminary
Explanations of Ideas and Notations
II. The Theory of
Logical Types
III. Incomplete
Symbols
Part I. Mathematical Logic
A. The Theory of
Deduction
B. Theory of
Apparent Variables
C. Classes and
Relations
D. Logic of
Relations
Part II. Prolegomena to Cardinal Arithmetic
A. Unit Classes
and Couples
Appendix A
*8. The
Theory of Deduction for Propositions containing Apparent Variables
Appendix C
Truth-Functions
and others List of Definitions
Zermelo, Ernst. Untersuchungen über die Grundlagen der
Mengenlehre I (Investigations in the Foundations of Set Theory). Mathematische Annalen 65 (1908),
261-281. Translation by Stefan Bauer-Mengelberg with introductory
note by Jean van Heijenoort as "Investigations in the foundations
of set theory I" on pp. 199-215 in From Frege to Gödel: A Source Book in
Mathematical Logic, 1879-1931. Jean van Heijenoort, editor.
Harvard University Press
(Cambridge, MA: 1967), 3rd (1977) printing. ISBN 0-674-32449-8 pbk.
See [vanHeijenoort1977]
This is the paper in which Zermelo sets out to
the first axiomatic system for Cantor's set
theory. With Abraham Fraenkel's improvement, it has remained intact in
every fundamental respect as the ever-popular system,
ZF,
or its cousin, ZFC (ZF + Axiom of Choice). The
differences between this progression and the alternative formulation, [von
Neumann-]Bernays-Gödel,
do not impact the standing of the transfinite and of the non-too-large
cardinals.
The paper is divided into two
sections, §1 Fundamental Definitions and Axioms and §2
Theory of Equivalence, the treatment of cardinality and the transfinite.
-- dh:2002-07-25