Wednesday, April 22, 2015

System-relativity of proofs

There is a generally familiar way in which the question whether a mathematical statement has a proof is relative to a deductive system: for a proof is a proof in some system L, i.e., the proof starts with the axioms of L and proceeds by the rules of L. Something can be provable in one system—say, Euclidean geometry—but not provable in another—say, Riemannian geometry.

But there is a less familiar way in which the provability of a statement is relative. The question whether a sentence p is provable in a system L is itself a mathematical question. Proofs are themselves mathematical objects—they are directly the objects in a mathematical theory of strings of symbols and indirectly they are the objects of arithmetic when we encode them using something like Goedel numbering. The question whether there exists a proof of p in L is itself a mathematical question, and thus it makes sense to ask this question in different mathematical systems, including L itself.

If we want to make explicit both sorts of relativity, we can say things like:

  1. p has (does not have) a proof in a system L according to M.
Here, M might itself be a deductive system, in which case the claim is that the sentence "p has (does not have) a proof in L" can itself be proved in M (or else we can talk of the Goedel number translation of this), or M might be a model in which case the claim is that "p has a proof in L" is true in that model.

This is not just pedantry. Assume Peano Arithmetic (PA) is consistent. Goedel's second incompleteness theorem then tells us that the consistency of PA cannot be proved in PA. Skipping over the distinction between a sentence and its Goedel number, let "Con(PA)" say that PA is consistent. Then what we learn from the second incompleteness theorem is that:

  1. Con(PA) has no proof in PA.
Now, statement (2), while true, is itself not provable in PA.[note 1] Hence there are non-standard models of PA according to which (2) is false. But there are also models of PA according to which (2) is true, since (2) is in fact true. Thus, there are models of PA according to which Con(PA) has no proof and there are models of PA according to which Con(PA) has a proof.

This has an important consequence for philosophy of mathematics. Suppose we want to de-metaphysicalize mathematics, move us away from questions about which axioms are and are not actually true. Then we are apt to say something like this: mathematics is not about discovering which mathematical claims are true, but about discovering which mathematical claims can be proved in which systems. However, what we learn from the second incompleteness theorem is that the notion of provability carries the same kind of exposure to mathematical metaphysics, to questions about the truth of axioms, as naively looking for mathematical truths did.

And if one tries to de-metaphysicalize provability by saying that what we are after in the end is not the question whether p is provable in L, but whether p is provable in L according to M, then that simply leads to a regress. For the question whether p is provable in L according to M is in turn a mathematical question, and then it makes sense to ask according which system we are asking it. The only way to arrest the regress seems to be to suppose that at some level that we simply are talking of how things really are, rather than how they are in or according to a system.

Maybe, though, one could say the following to limit one's metaphysical exposure: Mathematics is about discovering proofs rather than about discovering what has a proof. However, this is a false dichotomy, since by discovering a proof of p, one discovers that p has a proof.

No comments: