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.)

Advertisements

10 Comments

  1. Was this in response to http://science.reddit.com/info/yf4l/comments ?

    Also, it’s my understanding that you’ve just shown one example of an unprovable theorem, but there are other ones besides the usual paradoxes. These other ones might be more likely to be considered “true.” Eg. the Reimann hypothesis is suspected unprovable but true by some.

    Comment by Carl — January 16, 2007 @ 4:13 am

  2. But what would that mean, that something was true but unprovable? In the world of physics it would mean that its consequences agreed wih observation, although you couldn’t say why. But in math it means nothing. Thus it is nonsense to say something is true but uprovable, it only makes sense to say that you think a proof exists, but hasn’t been found yet, or that it is inprovable and thus can be considered either true or false depending on your model (since anything undecidable by defintion can be consistently considered true or false, otherwise you could prove it by condradiction, by assuming it was false and then showing something inconsistent followed).

    Comment by Peter — January 16, 2007 @ 11:19 am

  3. It would mean the same thing it means in physics. “In every case we’ve checked, the Reimann hypothesis has held. However, we cannot prove this will always be the case if we try bigger numbers, but induction suggests it will.”

    Comment by Carl — January 16, 2007 @ 1:04 pm

  4. Then you believe that its negation, that the Reimann hypothesis doesn’t hold, is inconsistant, which is why it must hold for all numbers, and thus that it can be proved by contradiction, at least.

    Comment by Peter — January 16, 2007 @ 1:15 pm

  5. You can believe ~RH to be wrong without believing that you can prove ~RH wrong.

    Comment by Carl — January 16, 2007 @ 2:00 pm

  6. http://en.wikipedia.org/wiki/Chaitin%27s_constant is a better example. Ω is a number that describes the probability of a program halting, so it should be a definite number in the sense that it’s a description of a concrete reality, but it’s incomputable, so we can’t pin it down past a certain number of digits.

    Comment by Carl — January 16, 2007 @ 2:08 pm

  7. There are three classes of statements provable, disprovable, undecidable, and inconsistant. If something is provable then its negation results in a contradiction. If something is disprovable then its affirmation results in a contradiction. If something is uncedidable then neither it nor its negation results in a contradiction. And if something is inconsistant both it and its negation result in a contradiction. These are exhaustive, and thus the only possibilities. Which one is RH? If you think that it is true then you think that it is impossible for RH to be false for any value. This means that you think that for some value p RH not holding is a contradiction (like 1 = 2). And this means you are in case #1, the provable. If you think instead that RH is in case #3, undecidable, then you can’t say that you think it is true, because it is perfectly consistent with your axioms to assert that it doesn’t hold for some values. The same thing can be said about omega, which can be seen as about the number of undeciable statements. The theorem “X” is undecidable is itself provable, disprovable, … ect for the same reasons, and is thus true, false, or neither for the same reasons.

    Comment by Peter — January 16, 2007 @ 3:12 pm

  8. It could be that the only way to prove RH is to calculate it out infinitely, and that there’s no “shortcut” way to prove that once you’ve done the first billion zeros the rest work the same way. In this case, it’s true in the sense that if you work on the assumption that it’s true, you’ll never be lead wrong, but undecidable in the sense that you can’t show this to be case.

    Comment by Carl — January 16, 2007 @ 5:31 pm

  9. Skip down to the last third of http://www.cs.auckland.ac.nz/CDMTCS/chaitin/inv.html to see where I’ve been misremembering my ideas from.

    Comment by Carl — January 16, 2007 @ 5:56 pm

  10. Well whether something is practically provable, I will grant you, is a different idea. But a bit different from the thrust of Godel’s argument.

    Comment by Peter — January 16, 2007 @ 6:09 pm


RSS feed for comments on this post.

Blog at WordPress.com.

%d bloggers like this: