On Philosophy

January 16, 2007

What Gödel’s Theorem Shows

Filed under: Logic — Peter @ 12:02 am

Gödel’s Theorem has many interesting implications for truth in mathematics. I am not going to go into those details here, except for one minor point, which is developing into one of my pet peeves. Gödel’s theorem proves that there are some statements that can be neither proved nor disproved no matter what set of axioms you start with (statements that I will refer to as undecidable)*. Some would also claim, in addition to being neither provable nor disprovable, that these statements are true. Here I will demonstrate that this is not the case, and that Gödel’s theorem shows nothing about the truth of these statements.

To do this I will need to briefly go through Gödel’s proof. Obviously the proof itself, in all its rigorous detail, is too large to include here. And it wouldn’t be very helpful either, since not many people have studied enough mathematics to follow all of those details. So instead I will present a condensed version of the proof. The first step of the proof is to show that every formula, and sequence of formulas, (a proof being one example of a sequence of formulas) can be mapped uniquely to a whole number greater than zero (by which I mean that each sequence of formulas has a unique number, which no other sequence shares, and that from that number we can recover the initial sequence). We call this the Gödel number of a formula. Next is to construct the predicate dem(x, y), which is true if and only if the number x represents a sequence of formulas that is a valid proof of the formula represented by the number y. Showing that this predicate can actually be defined (using only arithmetic) is a tedious exercise, since there are many rules of inference that it needs to capture, for now just take my word that it exists (or refer to a full version of Gödel’s proof, in which its existence is proved in tedious detail). Finally, we need a substitution function, sub(x, y, z). This function takes the number that represents some formula, x, a number that represents some variable in that formula, and returns the number of the formula that results from taking the formula represented by x and substituting all instances of the variable represented by y with the number z. For example if x was the number representing “p = q” and y encoded the variable q and z was the number 42 then sub(x, y, z) would return the number that represents “p = 42”. Again, showing that one can construct such a function using only arithmetic is quite complicated, and thus one more thing I will omit here.

Let us now consider the formula ~∃x dem(x, sub(y, 17, y)). Since dem and sub are mathematical functions this formula has a Gödel number, let us call it m. Now consider the formula ~∃x dem(x, sub(m, 17, m)). This statement insists that the formula encoded by sub(m, 17, m) cannot be proved, and sub(m, 17, m) does correspond to a definite formula, since m is simply some large number (further note, let us assume 17 is the code to substitute for the variable y). But what formula does sub(m, 17, m) correspond to? It is the first formula that we considered except with m substituted for y. But this yields the formula ~∃x dem(x, sub(m, 17, m)). Therefore that formula states that it itself cannot be proved. And showing that it cannot be disproved is trivially easy. To disprove a formula you must be able to prove its negation, which in this case is ∃x dem(x, sub(m, 17, m)), which is impossible, since to prove that you would be showing that there is a valid proof of the claim that there is no proof, which is a contradiction.

And that is the brief version of Gödel’s theorem, which shows how to construct a statement that can be neither proved nor disproved. Now some would claim that this undecidable formula is also true. This is because the formula represented by sub(m, 17, m) seems to say that the formula itself cannot be proved. And this seems like a true claim, so surely the formula is true, although unprovable. But this cannot be a valid line of argument. For if it was a valid argument we could add the following axiom to our system: “y” = sub(“~∃x dem(x, z)”, z, “y”) -> y (where quotes are understood to be the function that yields the Gödel number). Which is to say that if the number of a formula y is the same number as the statement that there exists no demonstration of y then y is true. And this simply formalizes the reasoning we used to argue above that the undecidable sentence, ~∃x dem(x, sub(m, 17, m)), was true. But, even if this sentence is among our axioms, we can carry Gödel’s proof forward, yielding a sentence of the form: ~∃x dem(x, sub(m, 17, m)), although in this case the number m will be different than it was before, since the formula to decide if a sequence of formulas is a valid proof will have changed with the introduction of an additional axiom. But our new axiom proves this statement. Thus we have a contraction, and if our system contains a contradiction anything can be proven. This means that accepting the reasoning that led us to conclude that the original Gödel sentence was true would lead to contradictions if we accepted it, and thus that we cannot accept it.

One possible objection to this is to argue that Gödel’s proof can’t go forward on system that contain the axiom “y” = sub(“~∃x dem(x, z)”, z, “y”) -> y because the definition of the function dem would be recursive. I am of the opinion that this recursion could be worked around, and that the proof could go forwards. But if it couldn’t it would show that Gödel’s theorem worked only on some axiom sets, and that it is possible that there are some axiom sets in which all true statements can be proved, which completely eliminates the force of the theorem. (Although this would seemingly contradict Gödel’s second incompleteness theorem, which states that any set of axioms that maintains its completeness, which is what the axiom we added effectively amounts to, must be inconsistent.)

In any case it makes perfect sense to consider these undecidable formulas as neither true nor false. When the truth of mathematical systems is thought of in terms of models all that Gödel’s theorem states is that given a set of axioms we can construct a number of consistent models that agree with all those axioms and in which there is a formula, G, which some models can make true and some make false without contradiction. Thinking about it this way prevents us from erroneous “meta-mathematical” or common sense reasoning, which would lead us to believe that a formula can be true with respect to a set of axioms when we have just shown we can know nothing about its truth from those axioms alone.**

* An obvious corollary of this claim is that there is an infinite number of those statements, which follows from the fact that given a set of axioms, S, and an undecidable sentence, g, you could add that sentence to your axiom set, resulting in axioms set S’. Given S’ we can show that there is some statement g’ that can be never proved nor disproved under it. We could repeat this process by adding g’ to S’, ad infinitum. However since S is a subset of S’, S’’, ect and g’ is a undecidable sentence in S’, ect then g’ is a undecidable sentence in S, since S is weaker than S’, S’’, ect.

** It is obvious that whether a formula is true or not depends on the set of axioms you are working with. Thus our common sense reasoning about the truth of the undecidable sentence uncovered by Gödel’s proof only leads us to believe it to be true because of some additional principles, really additional axioms, and whether a sentence is true with respect to those additional axioms plus the original axioms is a different matter from whether that sentence is true with respect to the original axiom set by itself. (And yes, adding axioms can make even a demonstrably false sentence true, if the additional axioms contain a contradiction.)

Blog at WordPress.com.