Is it necessary for a logical system to be both sound and complete in order to be decidable?


closed as off-topic by Namaste, Shailesh, José Carlos Santos, choco_addicted, hardmath Sep 12 '18 at 13:35

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Namaste, Shailesh, José Carlos Santos, choco_addicted, hardmath
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ As many authors define these terms, an inconsistent system would be decidable. Perhaps you could cite the textbook or source from which you take the definitions? Adding context would improve your Question. $\endgroup$ – hardmath Sep 12 '18 at 13:34

If you take, say, the classical semantics of propositional logic as granted, then it's very easy to define a formal system that is neither sound nor complete, yet perfectly decidable.

For example, consider this system:

  • A well-formed formula is a logical axiom iff it contains exactly one negation sign.
  • There are no rules of inference.

This is clearly decidable: a formula is provable exactly if it is an axiom, which is easy to check. But it is not sound (because it proves $A\land\neg A$), and it is not complete (because $\neg A\lor\neg\neg A$ is not provable, yet it is valid -- remember that we're assuming the usual semantics).

A thornier question is: Given a deductive system, can we find a semantics that it is sound and complete with respect to? The main problem here is to delineate exactly what would qualify as a "semantics". If we are too strict here, we might find ourselves excluding even tested and true ideas such as Kripke frames. On the other hand if we're too liberal the question could easily become trivial, because one could just slap the name "semantics" onto the formal system itself or something that simulates it.


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