History
In early model theory, quantifier elimination was used to demonstrate that various theories possess certain model-theoretic properties like decidability and completeness. A common technique was to show first that a theory admits elimination of quantifiers and thereafter prove decidability or completeness by considering only the quantifier-free formulas. This technique is used to show that Presburger arithmetic, i.e. the theory of the additive natural numbers, is decidable.
Theories could be decidable yet not admit quantifier elimination. Strictly speaking, the theory of the additive natural numbers did not admit quantifier elimination, but it was an expansion of the additive natural numbers that was shown to be decidable. Whenever a theory in a countable language is decidable, it is possible to extend its language with countably many relations to ensure that it admits quantifier elimination (for example, one can introduce a relation symbol for each formula).
Example: Nullstellensatz in ACF and DCF.
Read more about this topic: Quantifier Elimination
Famous quotes containing the word history:
“We may pretend that we’re basically moral people who make mistakes, but the whole of history proves otherwise.”
—Terry Hands (b. 1941)
“The history of all countries shows that the working class exclusively by its own effort is able to develop only trade-union consciousness.”
—Vladimir Ilyich Lenin (1870–1924)
“The history of the Victorian Age will never be written: we know too much about it.”
—Lytton Strachey (1880–1932)