2
$\begingroup$

Is the shortest formula which is provably equivalent to the Gödel sentence also the shortest undecidable formula?

I know that even if one accepts the Gödel sentence as an axiom, then yet another undecidable formula can be constructed, but it will be longer, not shorter: if we append to PA its Gödel sentence G then we can get a Gödel sentence G' for PA+G. G' is also undecidable in PA itself, and not equivalent to G (i.e. G = G' is not a theorem of PA), but G' is longer than G, and presumably the shortest formulas in each of their respective equivalence classes have the same relationship.

In other words, is any formula decidable if it is shorter than the shortest G-equivalent?

  • 0
    Voting to close; I think I can ask a more interesting soft-question about the relationship between string length and decidability.2011-03-25

2 Answers 2

6

Almost certainly not.

Gödel was the first to show how one could explicitly construct an undecidable proposition. If you notice the title of the paper where he presented the approach, the paper is labeled as part I. Gödel expected he would need to carry out all the details of his approach before people would be convinced of his surprising result, but in fact people quickly understood it and he never needed to write the followup paper. His paper explicitly describes the proposition as easy to construct in principle but "cumbersome" (English translation), and he was not trying to achieve the simplest undecidable proposition, but rather just the easiest one to prove. Since he didn't complete all the (very boring) details (including boring choices that must be made along the way), we should remember that "Gödel's undecidable proposition" is not only incredibly large, but it is not even a unique well-defined object.

Chaitin, on the other hand, has shown that in some sense most propositions are undecidable. In the words of the abstract of his 1982 paper Gödel's theorem and information, he says that "if a theorem contains more information than a given set of axioms, then it is impossible for the theorem to be derived from the axioms," and in the introduction he phrases it more memorably as "if one has ten pounds of axioms and a twenty-pound theorem, then that theorem cannot be derived from those axioms." To understand this, it is important to remember that, given a reasonable syntax, most propositions of a certain size contain information roughly proportional to their length. (See Chaitin's previous works for formalized versions of these claims.) Therefore once your propositions get longer than your axioms (normalized for the proportion of length that is due simply to syntax requirements), most propositions are undecidable (and they are not equivalent to each other, either).

Looking at Gödel's undecidable proposition (or rather the set of propositions that one could consider to fit this appellation) in the light of Chaitin's results, we see that it is extremely unlikely that anything in this set is the shortest or even equivalent to the shortest undecidable formula.

1

Assuming that PA is consistent:

Extend the language of arithmetic with a new constant symbol $c$, and let $\mathsf{PAc}$ be the theory consisting of all the axioms of PA, and nothing else, but interpreted in the extended language.

We can now "crank the Gödel handle" and produce a Gödel sentence $G$ for $\mathsf{PAc}$, which is certainly undecidable.

Yet another undecidable sentence is $ c=0 $ (This is undecidable, because if we had a proof of it, we could replace $c$ with $S(0)$ everywhere in the proof and get a proof of $S(0)=0$ in good old PA, which does not exist because we assume that PA is consistent. On the other hand, if we had a proof of $c\ne 0$, replacing $c$ with $0$ everywhere in that proof would produce a proof of $0\ne 0$, which likewise doesn't exist).

$c=0$ is not provably equivalent to $G$ either, because if we add $G$ as an axiom, $c=0$ is still unprovable, by exactly the same reasoning as before.

$c=0$ is certainly a shortest undecidable sentence of $\mathsf{PAc}$, for the boring reason that it has the smallest possible length of any wff. So $\mathbf{PAc}$ certainly doesn't have the property that its shortest undecidable sentence is equivalent to a Gödel sentence, and there is no particular reason to believe that $\mathsf{PA}$ would have this property either.