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:
“... the history of the race, from infancy through its stages of barbarism, heathenism, civilization, and Christianity, is a process of suffering, as the lower principles of humanity are gradually subjected to the higher.”
—Catherine E. Beecher (1800–1878)
“Man watches his history on the screen with apathy and an occasional passing flicker of horror or indignation.”
—Conor Cruise O’Brien (b. 1917)
“All history and art are against us, but we still expect happiness in love.”
—Mason Cooley (b. 1927)