Monday, September 01, 2003

Mathematical Logic - An Extremely Brief Introduction

This post by Brad DeLong on propositional logic got me thinking again about the course in mathematical logic (mostly of the first order variety) I took back when I was a freshman. Even though I haven't studied the subject since those now distant days, I still recall the mind-blowing effect it had on my understanding of mathematics as a subject.

Of course, having read Douglas Hofstadter's excellent "Gödel, Escher, Bach: an Eternal Golden Braid" as a high school student, the contents of the subject weren't entirely alien to me. I was already well aware of the importance of Gödel's Incompleteness Theorem, and knew that Gödel numbering was central to a proof of the theorem. I knew that the cardinality of the the reals (usually denoted as c) was greater than that of the rationals* (which is usually written with the Hebrew character aleph as 0), and Cantor's Diagonal Method is simple enough that I could even prove the statement myself. And yet, even with all of this background knowledge at my disposal, many of the notions that I would learn about during the course would turn out to be revelations.

The big difference between first order predicate logic and the more familiar propositional sort encountered in elementary logic classes is the presence of universal (∀) and existential (∃) quantifiers. Universal quantifiers allow us to make statements of along the lines of "For all X, the statement Y holds true", while existential quantifiers permit statements like "There exists an X such that Y is true."

One consequence of the existence of quantifiers in predicate logic is that they rule out the use of truth tables for determining the validity of statements, because any such tables would have to be infinite in size. Fortunately, Gödel's Completeness Theorem comes to the rescue, by allowing us to use proofs to determine validity; it tells us that any statement p that is true of a model** M of a set of axioms T must be deducible from the axiom set T.

Many well-educated people are aware, even if only vaguely, of Gödel's deservedly celebrated Incompleteness Theorem, which tells us that any axiomatic system that is powerful enough to model the theory of numbers must either be incomplete - by which we mean that there are statements that can be made in the theory whose truth or falsity can never be deduced from within it - or inconsistent, which would mean that we could prove both a statement P and its' negation ~P; but this would mean that anything at all could be proven within the system, making it absolutely worthless. The incompleteness theorem has an obvious fascination for all of those who are interested in epistemological issues, but it's infamy means that it tends to crowd out a lot of other interesting results that are also worthy of wider attention.

One such result is the Löwenheim-Skolem Theorem, which says that any countable theory that has a model must have a countable model. In addition, it must have models of every cardinality greater than ℵ0. A straightforward consequence of this theorem is that for any first-order axiomatisation of the real numbers there must also be an interpretation that requires only a countable number of objects!

Another interesting consequence is that it establishes the possibility of interesting models of arithmetic like that embodied in Abraham Robinson's nonstandard analysis, in which infinitesimals - numbers that are smaller than any rational number but are nevertheless greater than 0 - make their appearance. Apart from the intrinsic interest nonstandard analysis might have for logicians, one of its' attractions is the ease with which many results that are difficult to obtain in classical analysis can be proven; another is that statements that seem "unnatural" in mainstream analysis, or whose meaning is hard to grasp in this framework, are often far more intuitive in the context of nonstandard analysis. Far from being merely a useful but abstruse aid to mathematicians, one surprising area in which nonstandard analysis has seen application has been in the field of economics (of all subjects!)

*In plain English, that the real numbers and the rationals are both infinitely large sets, but the former is of a "bigger" sort of infinity than the latter. In fact, one can go further, and construct an infinite sequence of infinities of successively increasing size, i.e, ℵ0 < ℵ1 < ℵ2 ...

**A model of a set of statements in first order logic (which are collectively called a theory) is an interpretation of the theory under which all of its' statements are true. Not all theories need have a model, and it is perfectly possible for a single theory to have several, or even an infinite number of models, as indicated by the Löwenheim-Skolem Theorem. If M is a model for a theory T, it is common to say that M satisfies T, and the fact that a model exists for T shows that the theory is satisfiable.