Quantifier Elimination - History

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 front of these sinister facts, the first lesson of history is the good of evil. Good is a good doctor, but Bad is sometimes a better.
    Ralph Waldo Emerson (1803–1882)

    A poet’s object is not to tell what actually happened but what could or would happen either probably or inevitably.... For this reason poetry is something more scientific and serious than history, because poetry tends to give general truths while history gives particular facts.
    Aristotle (384–323 B.C.)

    America is the only nation in history which miraculously has gone directly from barbarism to degeneration without the usual interval of civilization.
    Georges Clemenceau (1841–1929)