## Mathematical Logic

*08 Sep 2004 11:07*

If, in 1901, a talented and sympathetic outsider had been called upon (say, by a granting-giving agency) to survey the sciences and name the branch which would be least fruitful in century ahead, his choice might well have settled upon mathematical logic, an exceedingly recondite field whose practitioners could all have fit into a small auditorium --- algebraists consumed by abstractive passion, or philosophers pursuing fantasies out of Leibniz and Ramon Llull, or (like Whitehead) both. It had no practical applications, and not even that much mathematics to show for itself: its crown was an exceedingly obscure definition of cardinal numbers. When, in 1910, it produced a work which the learned world was forced to notice --- the first volume of Whitehead and Russell's Principia Mathematica --- it was, so to speak, the academic Brief History of Time of its day, often mentioned, never used.

Our outsider would, of course, have been wrong. Mathematical logic was the inspiration for perhaps only half of twentieth-century philosohpy (that is, of honest philosophy; by volume, as Kolakowski says, Stalin was the century's most influential philosopher); many of our finest mathematicians, such as Norbert Wiener, John von Neumann and Andrei Kolmogorov cut their teeth on it, and notation (and notions) which began in the obscurities of Peirce and Peano are now to be found in every undergraduate math book. True, some early application --- one thinks particularly of Woodger's axiomatization of biology --- have, perhaps unfairly, gone nowhere, and McCulloch and Pitt's "A Logical Calculus of the Ideas Immanent in Nervous Activity" is more important for launching neural nets upon the world than for using Carnap's formalism. But in one extremely important field, however, it reigns supreme, and that is computation. Programming is, simply, mathematical logic in action; the melding of theory and practice is so complete that most practioners have no idea that their speech --- recursion, lexical scope, data abstraction, even those banes of C novices, pointers, referencing and dereferncing --- is prose. (Speaking of speech, Chomsky of course began as a logican, and his early work (air force and navy supported!) on formal languages is as much a part of logic as it is of linguistics or the theory of computation.) Of course, some of the computer's intellectual roots were more obviously useful --- but since these were the study of Brownian motion, and the physics of crystals and spectral lines, not much. (Its practical origins were military needs and vast quantities of government subsidies, which continue, but let's not disturb the myths about private enterprise any more than we must.)

I don't really know what the moral is, beyond the obvious one that useless knowledge isn't.

*Things I want to understand better:* Tarski's truth theory; the
Russell-Whitehead "relation-arithmetic" and its descendants; model theory.

*See also:*
Gödel's Theorem;
Computation;
Logical Positivism;
Math I Ought to Learn

- Recommended:
- Boolos and Jeffrey, Computability and Logic
- Peter J. Cameron, Sets, Logic and Categories
- Martin Gardner, Logic Machines and Logic Diagrams
- Jaako Hintikka, The Principles of Mathematics Revisited ["Proposes a new basic first-order logic and uses it to explore the foundations of mathemaitcs. This new logic enables logicians to express on the first-order level such concepts as equicardinality, infinity and truth in the same language. The famous impossibility results by Gödel and Tarski that have dominated the field for the past sixty years turn out to be much less significant than has been thought. All of ordinary mathematics can in principle be done on this first-order level, thus dispensing with all problems concerning the existence of sets and other higher-order entities." Homage to Russell's titles intended and fully appropriate.]
- Warren McCulloch and Walter Pitts, "A Logical Calculus of the Ideas Immanent in Nervous Activity", in McCulloch's Embodiments of Mind
- María Manzano, Model Theory
- Peter Nidditch, The Development of Mathematical Logic [Very short, and, as it is written in Basic English (!), ungainly; but clear and adequate]
- Willard Van Orman Quine
- Mathematical Logic [My review]
- Set Theory and Its Logic

- Bertrand Russell
- Introduction to Mathematical Philosophy
- Logic and Knowledge

- G. Spencer-Brown, The Laws of Form [Strictly for laughs]
- John von Neumann, "The General and Logical Theory of Automata" (in Collected Works)
- Alfred North Whitehead and Bertrand Russell, Principia Mathematica [I've read the abridgment, "To *56", plus some of the stuff on relation-numbers in vol. II...]
- J. H. Woodger, Axiomatic Method in Biology [OK, so I haven't finished the last two chapters, but it really is good, even if it does use the theory of types]

- To read:
- Steve Awodey, Category Theory
- Boole, The Laws of Thought
- Rudolf Carnap
- Introduction to Semantics, and Formalization of Logic
- The Logical Syntax of Language
- Introduction to Symbolic Logic and Its Applications
- Meaning and Necessity

- Alonzo Church, Introduction to Mathematical Logic
- Thierry Coquand and Henri Lombardi, "A logical approach to abstract
algebra", Mathematics Structures
in Computer Science
**16**(2006): 885--900 - David Deutsch, Artur Ekert and Rossella Lupacchini, "Machines, Logic and Quantum Physics," math.LO/9911150
- Anita Burdman Feferman and Solomon Feferman, Alfred Tarski: Life and Logic [Review in American Scientist]
- Solomon Feferman, "Tarski's influence on computer science", cs.GL/0608062
- Steven R. Givant, The Structure of Relation Algebras Generated by Relativizations
- Robert Goldblatt, Logics of Time and Computation
- Alessio Guglielmi, "A System of Order and Structure," cs.LO/9910023
- Robert A. Herrmann, "Logic for Everyone", arxiv:math/0601709
- Andrew Hodges, Alan Turing: The Engima
- Richard W. Kaye, The Mathematics of Logic: A Guide to Completeness Theorems and their Applications
- H. Jerome Keisler and Sergio Fajardo, Model Theory of Stochastic Processes
- Kleene, Introduction to Metamathematics
- J. Lambek and P. J. Scott, Higher-Order Categorical Logic
- Paolo Mancosu, Sergio Galvan, and Richard Zach, An Introduction to Proof Theory: Normalization, Cut-Elimination, and Consistency Proofs
- Colin McLarty, Elementary Categories, Elementary Toposes
- Emil Post, The Two-Valued Iterative Systems of Mathematical Logic
- Hartley Rogers, Jr., Theory of Recursive Functions and Effective Computability
- Erik Sandewall, Features and Fluents: The Representation of Knowledge about Dynamical Systems [Oxford Logic Guides, vol. 30]
- Eric Schechter, CClassical and Nonclassical Logics: An Introduction to the Mathematics of Propositions
- Gunther Schmidt, Relational Mathematics
- Raymond Smullyan
- First-Order Logic
- Recursion Theory for Metamathematicians
- Theory of Formal Systems

- Antonin Spacek, "Statistical Estimation of Semantic Provability", pp. 655--668 in vol. I of Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability
- Keith Stenning and Michiel van Lambalgen,
- Alfred Tarski
- Jouko Vaananen, Dependence Logic: A New Approach to Independence Friendly Logic
- Jan von Plato, The Great Formal Machinery Works: Theories of Deduction and Computation at the Origins of the Digital Age
- R. F. Walters, Categories and Computer Science
- William Weiss and Cherie D'Mello, Fundamentals of Model Theory [Free online]
- Alexander S. Yessenin-Volpin, Christer Hennix, "Beware of the Gödel-Wette paradox!" math.LO/0110094