Happy New Year 2010 to anyone who happens to be reading this around that time. While still reading and hopefully soon writing more about termination analysis, I have decided to write a little about Solomon Feferman’s lucid and readable book, “In the Light of Logic”, Oxford University Press, 1998, which I’ve been reading for a month or so now. The call number is QA9.2.F44 1998 (apologies to interested readers at U. Iowa, since I have the book checked out at the moment — I’m planning to buy a copy, so this one will be checked back in shortly).
Today I’ll just write a little bit about the book’s Chapter 1, “Deciding the Undecidable”. Feferman does a really wonderful job, in my opinion, surveying important results and ideas, both technical and philosophical, in logic and foundations of mathematics in the late 19th (with Cantor) and 20th centuries. Feferman combines pre-eminent technical knowledge with broad historical and philosophical considerations in clear and accessible prose. It is certainly very educational reading for both technically-oriented and (I suppose) philosophically minded students and researchers. (Although Chapter 1 is for a less technical audience than some later chapters of the book.)
One of the central historical and foundational issues considered in Chapters 1 and 2, constituting the book’s Part I, “Foundational Problems”, is Hilbert’s program. As Feferman explains (and as readers probably already know a bit about, at least), the great German mathematician David Hilbert in 1900 posed 23 mathematical problems, which became greatly influential for much research in mathematics and logic to the present day. The ones that I am most interested in for purposes of this post are the 1st and 2nd: prove the Continuum Hypothesis (problem 1), and give a “finitary” consistency proof for a formal theory of arithmetic (problem 2). As Feferman tells us, Hilbert’s optimism that these problems could be solved was not dampened by dramatic and — as most experts see it today — devastating results by Goedel, who showed that (any extension of) Peano Arithmetic (PA) is incomplete if it is consistent. In particular, it cannot prove its own consistency. The conclusion, as Feferman says, is that “any system which incoporates all finitary methods cannot be proved consistent by those methods” (page 14). So no finitary consistency proof is possible. For problem 1, Goedel proved in 1938 that Zermelo-Fraenkel (ZF) set theory cannot disprove the Continuum Hypothesis (CH), and a number of years later (1963), Paul Cohen proved that ZF cannot prove CH. So CH is neither implied nor contradicted by the theory, which is again an example of incompleteness (completeness for a theory is the property that for every sentence , the theory entails either or ).
The fact that all consistent suitably strong theories are incomplete is philosophically interesting. Indeed, Feferman uses it (in Chapter 1 and also Chapter 2) to cast doubt on platonism, the idea that there exists (in some sense) an abstract realm of mathematical objects, which are then considered by mathematical discourse. Feferman (very briefly) contrasts platonism with the idea that mathematics “is somehow the objective part of human conceptions and constructions” (page 7). To me the situation seems a little different, as I’ll now explain.
When we consider the consequences of certain ideas — which when rigorously formulated are described via axioms or other formal expressions of our assumptions — we are working within the theory determined by those ideas. The incompleteness results mentioned above show definitively that for any suitably strong theory, there will always be statements which the axioms do not determine. So our axioms could be further developed in such a way as either to make a consequence, or a consequence. But the theory as it stands just does not cover completely the situation expressed by .
The platonist position, at least as attributed by Feferman to Goedel, is that the existing mathematical universe simply has not been adequately described by our axioms, and we must search for new ones that express enough of its truths to determine either or . I agree with Feferman in rejecting this position: the fact that the axioms can be consistenly (or relatively consistently) expanded to accommodate , or differently expanded to accommodate suggests to me that only someone operating on a powerful sense of a particular mathematical universe could believe that one of these expansions is the right one, and the other is wrong. That is, if you already have some pre-axiomatic mathematical ideas that go beyond your axioms, then of course you will simply seek to formalize more of those ideas to describe the mathematical universe you imagine. But the results above imply that you could expand your axioms a different way, thus capturing a different set of pre-axiomatic ideas, and still be no worse off, from the point of view of consistency.
So it seems to me that a better way of thinking about the philosophical consequences of the incompleteness results is what we might call hypotheticalism. Mathematical theories say what would be true, hypothetically, of any world satisfying the axioms. There is no existing mathematical universe that all axiom systems must describe. The axioms just speak hypothetically: if these things were true, then these consequences would follow. This does not reduce mathematics to a merely human construction. Mathematics, in various axiom systems that people have found useful or interesting for whatever practical or aesthetic reasons, is about truths, namely hypothetical truths. It seems to me that this perspective helps preserve the sense that mathematics is not an arbitrary human construction and is indeed about potentially important truths, without requiring acceptance of the idea of a unique existing mathematical universe. No doubt my expression of this hypotheticalism is naive from a philosophical perspective, and it leaves open the question of why one axiom system should be preferred (if at all) to another, but I hope it accommodates the incompleteness results in a more plausible way than Goedel’s platonism (as reported by Feferman).