##  [Decidable Theory](/decidable-theory-0) 

 Definition

A theory is decidable if there exists an algorithm that, given any sentence in the theory's language, determines in finite time whether that sentence is a consequence of the theory (i.e., whether the sentence belongs to the theory's set of theorems).

 

 

 

 

 

 





## Principle

Principle

Effectivity of theoremhood: decidability requires that the set of sentences provable from the theory is a decidable (computable) set, so theoremhood is mechanically checkable rather than merely recursively enumerable or semidecidable.

 

 

 

 

 





## Demonstration

Demonstration

Example: Presburger arithmetic (the theory of the integers with addition) is decidable; the theory of real closed fields is decidable because quantifier elimination reduces sentences to quantifier-free statements that can be checked algorithmically; many theories with quantifier elimination or strong quantifier control are decidable.

 

 

 

 

## Misapplication

Misapplication

Assuming that decidability implies practical feasibility: a decidable theory may have extremely high computational complexity making theorem search infeasible; or assuming decidability is invariant under harmless language expansions or extensions of axioms without checking computability effects.

 

 

 

 

 





## Consequence

Consequence

Decidability yields an effective procedure for determining theoremhood, which enables automated reasoning, algorithmic classification of sentences, and reproducible verification of properties; it also interacts with complexity theory to characterize practical tractability.

 

 

 

 

## Reversal

Reversal

An undecidable theory lacks any algorithm that decides theoremhood: examples include sufficiently expressive arithmetic systems where no algorithm can determine provability in general, leading to inherent limitations on automation.

 

 

 

 

 





## Boundary

Boundary

Decidability depends on the choice of language, signature, and axioms; a theory may be decidable in one language but undecidable after adding symbols or axioms. Distinguish decidability from semidecidability (r.e. sets) and from completeness, which is a separate notion.

 

 

 

 

 





## Semantic Tension

Semantic Tension

Decidability vs completeness and axiomatizability: completeness is about truth-values for sentences, axiomatizability about recursive enumerability of axioms; decidability demands an effective decision procedure for the full set of consequences and thus lies at the intersection of logical expressivity and computability constraints.

 

 

 

 

 





## Synthesis

Synthesis

A decidable theory is one whose logical consequences can be mechanically and reliably determined: it makes theoremhood an algorithmic fact rather than a theoretical possibility, enabling automatic verification and concrete computation in model-theoretic and algebraic applications.