I’ve been wondering about “levels of incompleteness”. There might be some cool decidability theory hiding in here. I started the exploration with a few definitions (and haven’t gotten very far):
A recursive set of sentences A is called weakly incomplete if A is incomplete and there is a recursive set of sentences S ⊃ A which is complete.
A recursive set of sentences is called strongly incomplete if it is incomplete and not weakly incomplete.
We know that number theory (+,*,exp) is strongly incomplete by these definitions; i.e. it is incomplete, and if you try to complete it, its incompleteness will just pop up somewhere else. This is Gödel’s incompleteness theorem. The question is the converse: is every strongly incomplete set of sentences strong enough to contain number theory (Turing complete)?
Here is an easy theorem:
Theorem: all models of a strongly incomplete set of sentences are infinite.
Proof: Let A be a strongly incomplete set. Call the number of finite models of A n. Note that n is finite. Let φ be a sentence independent of A. There is a model of A in which φ holds and a model in which ¬φ holds. Pick one according to your favorite football team. Add φ or ¬φ to A, and note that n has just decreased by at least one. Repeat until one of these holds:
- There is exactly one finite model of A. By the completeness theorem, A is now complete. However, the above was a finite process, so A is still recursive, so it was actually weakly incomplete.
- There are no finite models of A. The last φ or ¬φ we chose must not have been independent of A; in fact we just proved its negation. So this case is impossible. If there were no finite models to start with, then we’re done because we were trying to prove that.
EDIT This theorem is invalid. When I say “note that n is finite”, I have made an error. There needn’t be finitely many finite models. I conject that the theorem is still true, but I have to find a different proof.
I could have sworn that when I went on a walk today to think about this stuff, I had a proof that if every strongly incomplete set embeds number theory then there is a decision procedure for determining whether a sentence is independent of a weakly incomplete set. I can’t remember it now!