Could the decidability of a theorem be undecidable?

43 Views Asked by At

Given some theorem $T$, could the question "is $T$ decidable?" be undecidable?

I assume the answer is yes, and if it is, could the decidability of a theorem be undecidable even if the theorem itself is decidable?

1

There are 1 best solutions below

1
On

If T is undecideable within formal system F, it means (1):

  • F does not contain a proof of T, AND
  • F does not contain a proof of ~T.

Suppose the question "T is undecideable" is undecideable. That means (2):

  • F does not contain a proof that T is undecideable in F, AND
  • F does not contain a proof that T is not undecideable in F.

In particular, note the second dot point means (3):

  • F does not contain a proof that F contains a proof of T, AND
  • F does not contain a proof that F contains a proof of ~T.

Let's also assume that T is not undecideable. That means (4):

  • F contains a proof of T, OR
  • F contains a proof of ~T.

Either way, this contradicts (3), since if F contains a proof P of T, we can construct a proof that F contains a proof of T: that would be to note P, and check that it is a proof (which can be done if F is sufficiently powerful for godelian arguments to work). Likewise, if F contains a proof of ~T.