Logic – Decidability vs Completeness Explained

decidabilityincompletenesslogicmodel-theoryproof-theory

I am trying to clear up the distinction between decidability and completeness.

  • Decidable A theory T is decidable if there exists an effective procedure to determine whether $T\vdash\varphi$ where $\varphi$ is any sentence of the language.
  • Completeness A theory T is syntactically complete if for every sentence of the language $\varphi$ it is true that $T\vdash\varphi$ or $T\vdash\neg\varphi$.

So whether a theory T is decidable is an epistemological fact. A statement about what we can effectively know, but completeness is a metaphysical fact about the theory. Whether or not we can effictively know that $T\vdash\varphi$ does not bear one whether $T\vdash\varphi$.

This means,

  1. We can have decidable, but incomplete theories because we can have an effective procedure to tell use which sentences are theorems while there still being some sentences where neither it nor its negation are a theorem. e.g Theory of algebraically closed fields of characteristic 0
  2. We can have undecidable, but complete theories. eg $Th(\mathbb{N})$
  3. If a theory is complete and has recursive axioms, then it is decidable. This is because if the axioms are recursive, then the proofs are as well. This gives you your effective procedure.
  4. We can also have decidable and complete theories. e.g Presburger Arithmetic (glory to Presburger Arithemtic)
  5. We can have undecidable and incomplete theories. e.g Peano Arithmetic

In short, we can have every combination of these two properties for a theory.

Is this an accurate summary?

Best Answer

Your summary seems accurate, with one exception: The theory of algebraically closed fields of characteristic 0 is complete. Perhaps you meant the theory of algebraically closed fields, without specifying the characteristic?

Related Question