Decidability (logic)

Lore & Background

Decidability is a central concept in logic, distinguishing systems where an effective method exists to determine logical validity or theory membership from those where no such method can exist. Propositional logic is decidable via truth tables, while first-order logic is undecidable in general, except for monadic predicate calculus with identity. Theories such as Presburger arithmetic and the theory of real closed fields are decidable, whereas Robinson arithmetic and the theory of groups are undecidable.

Reader's Guide

Decidability is a fundamental property in logic, separating tractable from intractable systems. It underpins the limits of algorithmic reasoning: propositional logic is decidable, but first-order logic is not, except for restricted fragments. Decidable theories like Presburger arithmetic allow complete algorithmic analysis, while undecidable theories like Robinson arithmetic show inherent limitations. The concept is distinct from completeness; for example, algebraically closed fields are decidable but incomplete, while true arithmetic is complete but undecidable. Semidecidability is a weaker property, where positive membership can be verified but non-membership may not be. Decidability results shape fields from computer science to mathematics, guiding what problems can be solved algorithmically.

Did You Know?

• Propositional logic is decidable because the truth-table method can determine logical validity.
• First-order logic is not decidable in general; the set of logical validities in any signature with equality and at least one other predicate symbol with two or more arguments is undecidable.
• Every inconsistent theory is decidable, as every formula in its signature is a member.
• Robinson arithmetic is essentially undecidable, meaning every consistent extension of it is also undecidable.