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:
“... in a history of spiritual rupture, a social compact built on fantasy and collective secrets, poetry becomes more necessary than ever: it keeps the underground aquifers flowing; it is the liquid voice that can wear through stone.”
—Adrienne Rich (b. 1929)
“I think that Richard Nixon will go down in history as a true folk hero, who struck a vital blow to the whole diseased concept of the revered image and gave the American virtue of irreverence and skepticism back to the people.”
—William Burroughs (b. 1914)
“No one is ahead of his time, it is only that the particular variety of creating his time is the one that his contemporaries who are also creating their own time refuse to accept.... For a very long time everybody refuses and then almost without a pause almost everybody accepts. In the history of the refused in the arts and literature the rapidity of the change is always startling.”
—Gertrude Stein (1874–1946)