Are there uncountably infinite complete extensions of finite theories of the natural numbers?

Solution 1:

Yes, there are uncountably many (in fact, continuum many) complete theories extending any given finite (in fact, any given computable) true theory of arithmetic strong enough for Godel's theorems to apply to it.

This can be proved via the incompleteness theorem, together with a bit of topology. Fix a computable true theory of arithmetic $T$, and a listing $\{\varphi_i:i\in\mathbb{N}\}$ of sentences in the language of arithmetic; we can associate to each infinite binary sequence $f$ a corresponding theory of arithmetic extending our original $T$; $$T_f=T\cup\{\varphi_i: f(i)=1\}\cup\{\neg\varphi_i: f(i)=0\}.$$ Now there's no reason for each $T_f$ to be consistent, but it's not hard to show that the set of $f$ such that $T_f$ is consistent forms a closed set in the sense of the usual topology on the set of infinite binary strings. (Note that the completions of $T$ are exactly these $T_f$s.)

We now use a neat fact about the topology above: that any closed countable set has isolated points. (Briefly: any set without isolated points is dense somewhere, hence uncountable if closed.) In this context, this means that if $\{f: T_f$ is consistent$\}$ is countable, then there is some finite binary string $\sigma$ such that there is exactly one infinite binary sequence $f$ extending $\sigma$ such that $T_f$ is consistent. But this means that the theory $$T_\sigma=T\cup\{\varphi_i: \sigma(i)=1\}\cup\{\neg\varphi_i: \sigma(i)=0\}$$ already proves or disproves every sentence of arithmetic, that is, is complete!

So $T_\sigma$ is a complete extension of $T$; but it is gotten by adding only finitely many sentences to $T$, hence is computable since $T$ is. And this contradicts Godel's theorem.

Solution 2:

There is no uncountable extension because a theory is set of wffs, and there are only countably many wffs.

But there are uncountably many complete extensions, each of which is countably infinite.

(First add enough axioms that Gödel's incompleteness theorem applies. Then enumerate all sentences. Each time you reach one that is not yet decided, you can add either that or its negation to the theory. You won't run out of undecided sentences in finite time, due to Gödel, because you have only added finitely many yet at each step. This way you can spend an entire infinite sequence of bits on deciding which extension to produce.)