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

Question

I can show that given a finite segment of true sentences about the natural numbers there are infinitely many complete extensions (using the incompleteness theorems). I'm curious if there are uncountably infinite complete extensions.

Answer 1

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.)

Answer 2

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.

Answer 3

Yes, by the incompleteness theorem. An easy argument is to enumerate the sentences in the language of arithmetic. Assign to each node $\sigma $ of the tree $2^{<\omega}$ a theory $T_\sigma $ as follows: Let $T_\emptyset=T $ be the theory you begin with (which we may assume is powerful enough so the first incompleteness theorem applies. For instance, since $T $ is true, we can replace it with $T+Q $ if needed, where $Q $ is Robinson's arithmetic, which is finitely axiomatizable). Each $T_\sigma $ is a finite consistent extension of $T $ and therefore the incompleteness theorem still applies to it. To define these theories, proceed recursively as follows: Given $T_\sigma $, pick the first sentence in your enumeration not decided by $T_\sigma $, say $\phi $, let $T_{\sigma^\frown0}=T_\sigma+\phi $ and $T_{\sigma^\frown1}=T_\sigma+\lnot\phi $. To each $x\in 2^\omega $ assign $T_x:=\bigcup_n T_{x\upharpoonright n} $. This is consistent by compactness and complete by construction. The construction also ensures that these theories are pairwise incompatible and therefore different.

It is perhaps worth remarking that although the tree so built is fairly simple (each node is computable from $0'$), the branches are fairly complicated.