Does the existence of uncomputable functions imply that a theory is incomplete?

Question

For example Kolmogorov complexity is uncomputable and Chaitin used that fact to prove incompleteness.

If this is not the case, can you give me a counter example?

Set of axioms is countable.

Answer 1

No, this is not quite correct.

One crucial point is that there be a definable non-computable function. For instance, Presburger Arithmetic is complete and recursive; the point is that no interesting functions are definable in its language. By contrast, in Chaitin's proof a crucial point is that Kolmogorov complexity is definable in PA.

Another crucial point is that you also need to take into account the complexity of the theory. For instance, the full first-order theory of arithmetic, $Th(\mathbb{N})$, is complete by definition, even though plenty of noncomputable functions are definable in arithmetic. The point is that every function definable in the language of arithmetic is recursive relative to $Th(\mathbb{N})$.

Here's one correct way to say what you're getting at:

Suppose $T$ is a theory in some language $L$, and $T$ is satisfied by an $L$-structure $\mathcal{N}$ whose underlying set is $\mathbb{N}$, and the elements of this underlying set are effecitvely definable in the sense that there is a recursive map $g:\mathbb{N}\rightarrow\mathbb{N}$ such that $g(i)$ is (the Godel number of) a formula defining $i$ in $\mathcal{N}$. Then if $f$ is a function definable in $L$, whose interpretation in $\mathcal{N}$ (viewed as a function on $\mathbb{N}$) is not recursive relative to $T$, then $T$ is incomplete.

There are many other ways to formalize this. For instance, we might not want to assume much about the "truth" of $T$ - this is where representability, as opposed to mere definability, comes into play.