Decidability (logic)
Decidability concerns effective methods for logical membership.
Decidability in logic addresses whether a true/false decision problem can be solved by an effective method—a procedure that always yields the correct answer after a finite, though potentially lengthy, amount of time. For logical systems, this property concerns the set of logically valid formulas, often called theorems. A system is decidable if an effective method exists to determine whether any arbitrary formula is a theorem. Propositional logic, for instance, is decidable because truth tables provide such a method. In contrast, first-order logic is generally undecidable; this holds for any signature that includes equality and at least one other predicate symbol with two or more arguments. Higher-order logics, such as second-order logic and type theory, are also undecidable. However, a restricted fragment—monadic predicate calculus with identity, which allows only equality and unary predicates—is decidable. Some logical systems, like Kleene’s logic, have no theorems at all; for these, decidability is defined using broader criteria, such as the validity of sequents or the consequence relation.
A theory, defined as a set of formulas closed under logical consequence, is decidable if there is an effective procedure to determine membership for any formula in its signature. Every inconsistent theory is decidable, as all formulas are members. Every complete, computably enumerable first-order theory is also decidable. However, extending a decidable theory can yield an undecidable one; for example, undecidable theories exist even in propositional logic, though the set of validities remains decidable. A consistent theory is essentially undecidable if every consistent extension of it is undecidable. Robinson arithmetic is essentially undecidable, so any theory that includes or interprets it is also undecidable. Decidable first-order theories include the theory of real closed fields and Presburger arithmetic (natural numbers with addition), while undecidable examples include the theory of groups and Robinson arithmetic. Methods to establish decidability include quantifier elimination, model completeness, and the Łoś–Vaught test.
- field
- Logic
- known_for
- Distinction between decidable and undecidable logical systems and theories
Lore & Background
Decidability in logic concerns whether an effective method exists to determine, in every case, the correct answer to a true/false decision problem. For a logical system, this means there is a procedure to decide if any arbitrary formula is a theorem (logically valid). Propositional logic is decidable, with the truth-table method serving as such a procedure. First-order logic is not decidable in general; specifically, the set of logical validities in any signature containing equality and at least one other predicate symbol of two or more arguments is undecidable. However, monadic predicate calculus with identity—first-order logic restricted to signatures with no function symbols and only unary predicates besides equality—is decidable. Some logical systems, such as Kleene’s logic, have no theorems at all, so decidability may instead be defined for sequents or the consequence relation. For a theory (a set of formulas closed under logical consequence), decidability means an effective method determines whether an arbitrary formula belongs to that theory. Every inconsistent theory is decidable, as is every complete computably enumerable first-order theory. An extension of a decidable theory may be undecidable; for instance, undecidable theories exist in propositional logic even though the set of validities is decidable. A consistent theory is essentially undecidable if every consistent extension of it is undecidable; Robinson arithmetic is such a theory, and any theory that includes or interprets it is also essentially undecidable. Decidable first-order theories include Presburger arithmetic (natural numbers with addition), Skolem arithmetic (natural numbers with multiplication), the theory of real closed fields, and the theory of Boolean algebras. Undecidable theories include the theory of groups and Robinson arithmetic. Methods used to establish decidability include quantifier elimination and model completeness.
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.
More in Mathematical Logic And Computation 1-21
Spotted an error? Know more?
This is a living reference — every entry is fact-audited, and reader corrections feed straight into our audit queue. Suggest an edit · See this site's audit record