MATHEMATICAL LOGIC

Last Updated 28/04/05

BACK TO LPSG CONTENTS

1. The Paper

The paper covers formal methods and results relevant to the philosophy of mathematics and philosophy of logic. It forms a natural pair with the Philosophy of Mathematics paper; each informs the other, but neither depends on the other. Most theories worthy of the name can be formalized. Mathematical logic is about general properties of these formalizations. More specifically, it is about deduction and consistency, about models, truth and consequence, about computability and axiomatizability.

Mathematical logic will give one a firm grasp of concepts that are vital for philosopical logic and helpful in philosophy of language: truth, validity, consequence. In a first year introduction to logic, one learns deductive systems for propositional and first order predicate logic. But how do we know that these systems permit us to deduce only what is logically valid (soundness) and all of what is logically valid (completeness)? This course gives the answers. On the way, it presents basic reasoning techniques and basic semantic concepts: interpretation, satisfaction, truth under an interpretation, model.

These are just the initial metatheorems of logic. Others are more surprising: while propositional logic is decidable  we can program a computer to decide whether any given propositional formula is a logical truth  full first-order predicate logic is not. This is the famous Church-Turing undecidability theorem. Other far-reaching limitative' results to be presented are the Löwenheim-Skolem theorem, Tarski's undefinability of truth' theorem, and Gödel's famous theorems establishing the incompleteness of interesting formal theories and the impossibility of internal consistency proofs. The course enables one to understand these theorems and their proofs. These are conceptually rewarding and important for philosophy of logic and philosophy of mathematics.

The paper is relatively demanding of one's mathematical abilities, but you do not have to be mathematically learned or clever. Success in the first year Introductory Logic course is pre-requisite. Mathematical logic, as all other mathematical subjects, is not a spectator sport; one must do the problems, as well go through the lecture notes (or textbook) to make sure you understand what is going on, after each lecture. If you keep up with this you are likely to do well in the exam.

The Mathematical Logic paper has a sister paper, Set Theory and Further Logic. The common parent was a paper, now defunct at the B.A. level, called Symbolic Logic: once modal logic became part of the staple diet it was felt that there was too much ground for an undergraduate to cover in any depth in one paper; hence the split. The courses are taught in alternate years: if Mathematical Logic is taught one year, Set Theory and Further Logic is taught the next. But B.A. exam papers for both are set every year.

2. Textbooks

• Enderton, H. A Mathematical Introduction to Logic. 2nd edition. San Diego, Cal: Academic Press 2001.

This is an excellent textbook that covers a lot of ground in an efficient way, with the right balance of material between proof (syntax), models (semantics), and computability. It does assume some familiarity with mathematical modes of expression and procedure, but nothing that cannot be explained informally by the lecturer.

I would strongly advise sticking to one textbook and mastering that. If one wants a feel for the mathematical background to ease the way, try

• Devlin, K. 1992. Sets, Functions & Logic: an Introduction to Abstract Mathematics. 2nd ed. London: Chapman & Hall.

For information only I mention some other well known textbooks on mathematical logic.

• Boolos, G. & Jeffrey, R. Computability and Logic. 3 rd edition. Cambridge: Cambridge University Press 1989.

Its special characteristic is that it presents proof that various accounts of computability coincide. Another famous textbook that covers the much the same ground is

• Mendelson, E. Introduction to Mathematical Logic. 4th ed. London: Chapman & Hall 1997.

A fine textbook for graduate level students, with material that is not found in other textbooks is

• Shoenfield, J. Mathematical Logic. Reading, Mass.: Addison-Wesley 1967.

In the days of the single Symbolic Logic' paper we used Moshé Machover's Set Theory, Logic & Their Limitations. It is now out of print but may be found in libraries. If you continue study of mathematical logic I recommend Bell and Machover's blue book', which covers the ground of their once famous M.Sc. course:

• Bell, J. & Machover, M. A Course in Mathematical Logic. Amsterdam: North-Holland 1977

Also the golden classic

• Kleene, S. Introduction to Metamathematics. Amsterdam: North-Holland 1952.