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:
“Postmodernism is, almost by definition, a transitional cusp of social, cultural, economic and ideological history when modernism’s high-minded principles and preoccupations have ceased to function, but before they have been replaced with a totally new system of values. It represents a moment of suspension before the batteries are recharged for the new millennium, an acknowledgment that preceding the future is a strange and hybrid interregnum that might be called the last gasp of the past.”
—Gilbert Adair, British author, critic. Sunday Times: Books (London, April 21, 1991)
“The principle office of history I take to be this: to prevent virtuous actions from being forgotten, and that evil words and deeds should fear an infamous reputation with posterity.”
—Tacitus (c. 55–117)
“Modern Western thought will pass into history and be incorporated in it, will have its influence and its place, just as our body will pass into the composition of grass, of sheep, of cutlets, and of men. We do not like that kind of immortality, but what is to be done about it?”
—Alexander Herzen (1812–1870)