Incompleteness Razor

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 SA 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:

  1. 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.
  2. 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!

About these ads

One thought on “Incompleteness Razor

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s