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:
“A great proportion of the inhabitants of the Cape are always thus abroad about their teaming on some ocean highway or other, and the history of one of their ordinary trips would cast the Argonautic expedition into the shade.”
—Henry David Thoreau (1817–1862)
“Social history might be defined negatively as the history of a people with the politics left out.”
—G.M. (George Macaulay)
“All history is a record of the power of minorities, and of minorities of one.”
—Ralph Waldo Emerson (1803–1882)