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

Ais calledweakly incompleteifAis incomplete and there is a recursive set of sentencesS⊃Awhich is complete.A recursive set of sentences is called

strongly incompleteif 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:LetAbe a strongly incomplete set. Call the number of finite models ofAn. Note thatnis finite. Letφbe a sentence independent ofA. There is a model ofAin whichφholds and a model in which¬φholds. Pick one according to your favorite football team. Addφor¬φtoA, and note thatnhas just decreased by at least one. Repeat until one of these holds:

- There is exactly one finite model of
A. By the completeness theorem,Ais now complete. However, the above was a finite process, soAis 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 ofA; 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.

EDITThis theorem is invalid. When I say “note thatnis 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!

The converse of your theorem is more straightforward to prove. Every finite structure has a recursively axiomatizable complete theory (in fact, it can be finitely axiomatized by just listing sentences explaining how every one of the finitely many predicates and relations interacts with every one of the finitely many objects), and therefore any theory that is not a subtheory of a recursively axiomatizable complete theory can’t be a subtheory of any theory satisfied by a finite structure. Therefore, it can’t have any finite models.

Although perhaps this makes the same mistake you worry about – I assume that there are only finitely many relations and predicates in a finite structure, but if you’re just assuming that the set of objects is finite then this won’t always be true.