Monday, February 18, 2013

This sentence is refutable (dualizing Goedel)

While the standard informal interpretation of Goedel's sentence:
[G]   I am (/This sentence is) not provable.
is quite well-known, it's dual sentence:
[DG] I am (/This sentence is) refutable.
studied, for instance, by Smullyan, isn't. Yet, pretty much like you can run an argument for incompleteness using the former, you can also run a parallel argument using the latter. Just because it's fun to see how this works (if you're geeky enough), here's how it goes (it's quite easy). 

For simplicity let's assume the background theory is sound (it proves only truths) and sufficiently expressive.

One of the easiest arguments for incompleteness using [G] goes like this.

  1. Suppose [G] is false. Then (because of what it says) it is provable, which contradicts soundness. So [G] is true.
  2. If [G] is true, it is not provable, so we have the first half of incompleteness.
  3. Given that [G] is true, its negation is false.
  4. If ~[G] is false, it cannot be provable, given soundness. This is the second half of incompleteness.
An analogous argument for [DG] is:

  1. Suppose [DG] is true. Then, by what it says, its negation is provable.
  2. If ~[DG] is provable, it is true (by soundness), so [DG] is false. 
  3. Assuming [DG] is true we inferred that it is false. So, unconditionally, [DG] is false.
  4. If [DG] is false, then (by soundness) it is not provable.
  5. If [DG] is false, ~[DG] is true, which means [DG] is not refutable. That is, ~[DG] is not provable either. 

No comments: