4
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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?

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I personally am unsure. I remember seeing it as fields of characteristic 0 or p, prime. $\endgroup$ – El Gallo Negro Aug 28 '19 at 3:04
  • 2
    $\begingroup$ For any fixed p (either prime or 0), the theory of algebraically closed fields of characteristic p is complete. Probably the fastest way to see this is that the theory is uncountably categorical (any uncountable model is determined, up to isomorphism, by the cardinality of a transcendence basis over the prime field). Since the language here is countable, the Los-Vaught test then implies that the theory is complete. $\endgroup$ – Chris Eagle Aug 28 '19 at 3:07
  • 2
    $\begingroup$ On the other hand, if you don't fix $p$, then you get an incomplete theory (simply because it doesn't decide the characteristic of the field, which is a first-order property). $\endgroup$ – Chris Eagle Aug 28 '19 at 3:11
3
$\begingroup$

As Chris Eagle said, your example for (1) is wrong. Removing the characteristic specification does the trick (as they observe), but there are also far simpler examples. For instance, take the empty language $\{\}$ (so only "$=$" allowed, besides the pure logical grammar) and consider the theory $$T=\{\exists x,y\forall z(x=z\vee y=z)\}.$$ This theory has exactly two models up to isomorphism, a one-element set $M_1$ and a two-element set $M_2$. These aren't elementarily equivalent, so $T$ isn't complete, but it is decidable since we have $$T\vdash\varphi\quad\iff M_1\models\varphi\mbox{ and }M_2\models\varphi,$$ and checking whether a sentence holds in a finite structure is computable.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for this example! $\endgroup$ – El Gallo Negro Aug 28 '19 at 4:13
0
$\begingroup$

We can have undecidable and incomplete theories. e.g Peano Arithmetic

This is based on a very different definition of complete than what you wrote. Godel's Incompleteness Theorem uses the "if it is true then it is provable" pseudo definition of completeness. And he gets around the ambiguity of that definition by only needing to give 1 meaningful counterexample, a unary predicate $P$ with the quality that there is a proof for $P(0)$ and a proof for $P(1)$ and a proof for $P(2)$, etc, but there is no proof of $\forall x . P(x)$.

The definition of completeness you give is the one that a person would mean if they said "propositional logic is complete"; that is, that every propositional statement has a proof or disproof. But an IMO better way to phrase the definition in that case is "if it exists in this language, then it has a proof". In the definition there is no particular reason to separate cases according to $\lnot$.

If someone was to say a theory is complete, I'm not even sure I could guess what they mean. A theory is just a set of theorems (although usually in context, with some sort of deductive closure). It is usually meaningless to say a theory is (in)complete, except maybe relative to a grammar, you would instead say whether a logic is complete.

When they say "[a particular] first order logic" is complete, what they mean is that every statement that is a tautology (relative to whichever first order model theory they are using) has a proof in that logic. So when they talk about the completeness of [a particular] first order logic, in absolutely no way are they suggesting that it is decidable; that is, they are not at all alluding to the definition in the original question. It's all just first order model theory stuff.

Completeness is used to mean a lot of different things.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.