Does First Incompleteness Theorem imply Strong Undecidability in general?

61 Views Asked by At

Let $T$ be a theory (in any proper language) whose consistent axiomatizable extensions are incomplete. Will this imply consistent extension of $T$ is undecidable?

I got this question from my friend but I don't know how to prove or disprove this statement.

1

There are 1 best solutions below

1
On BEST ANSWER

Yes. The point is the following (working over a computable language):

Any decidable (consistent) theory has a decidable (consistent) completion.

Proof: Suppose $T$ is decidable. Fix a computable list $(\varphi_i)_{i\in\mathbb{N}}$ of the sentences in the language of our theory. We'll define a new sequence of sentences $(\psi_i)_{i\in\mathbb{N}}$ of sentences recursively as follows:

  • $\psi_0=\varphi_0$ if $T\not\vdash\neg\varphi_0$, and $\psi_0=\neg\varphi_0$ otherwise.

  • $\psi_{i+1}=\varphi_{i+1}$ if $T\not\vdash(\bigwedge_{j\le i}\psi_j)\rightarrow\neg\varphi_{i+1}$ and $\psi_{i+1}=\neg\varphi_{i+1}$ otherwise.

Since $T$ is decidable, the sequence $(\psi_i)_{i\in\mathbb{N}}$ is computable and so the theory $$T^+=T\cup\{\psi_i:i\in\mathbb{N}\}$$ is decidable. By construction it is complete (and consistent assuming that $T$ was). $\quad\Box$