Quantifier elimination

Quantifier elimination referred to in the model theory of a certain property of theories: It is said that a theory has quantifier elimination if every formula is within the theory to a formula without quantifiers equivalent. For example, in a body (ie, for example, in real numbers ), the formula indicates that a multiplicative inverse element having equivalent to, that is to that. In no quantifiers occur. Can convert every formula in such a quantifier-free formula, the theory has quantifier elimination. In theories with quantifier elimination so arbitrary formulas in quantifier-free, permitting simpler formulas can be reshaped.

  • 4.1 completeness
  • 4.2 Algebraic Geometry
  • 4.3 Other Applications

Definition

Be a language and a theory (ie, a set of propositions ). Then quantifier elimination has, if for all formulas a quantifier-free formula exists with.

Simple criterion

To check whether a theory has quantifier elimination, it suffices to prove this only for a simple type of formulas: The universal quantifier can be transferred by means of a double negation in an existential quantifier. This can inductively remove from the inside out, so that has to be proven only for formulas of the form with quantorenfreiem that they are equivalent to a quantifier-free formula.

Bringing in disjunctive normal form and pulls the existential quantifier at the disjunction over inward so you can see that one can restrict ourselves to those formulas that consist of a conjunction of elementary formulas or negations of such formulas. Formulas of the form, where has this shape, also called primitive existence formulas.

Examples

Infinite sets

The theory of infinite sets can be formulated in a language without constants, function and relation symbols: The formula states that there are at least elements. therefore axiomatized infinite sets. A primitive existence formula has the form, where is quantifier-free and has any free variables. If so, the formula is equivalent to. After all, the formula says that a is sought that matches all, leaving only a way for remains. If, however, it should be the formula equivalent since one is wanted by all different, which always exists according to the axioms of the theory of infinite sets. Thus, each primitive existence formula to a quantifier-free formula equivalent; the theory has quantifier elimination.

Other examples

Many other theories have quantifier elimination, including the following:

  • The theory of algebraically closed fields
  • The theory of dense linear orders without endpoints
  • For a solid body, the theory of infinite - vector spaces
  • The theory of real closed fields

Applications

Completeness

A consistent theory without constants, which has quantifier elimination is automatically and fully, that is, it proves for every statement, either itself or. This can be seen as follows: Each statement is in theory equivalent to a quantifier-free statement. Since there are no constants, the only quantifier statements true () and false () are statement. This proves the theory either or. An example of this case, the above theory of infinite sets.

In general: A theory with quantifier elimination is model- complete: there are two models, it is an elementary extension of the theories and and match. Because of the quantifier elimination, this must be proven only for quantifier-free formulas, but these are exactly then, when they are in because substructure is.

Algebraic Geometry

In algebraic geometry one deals with algebraic varieties, the zero sets of polynomials. From Chevalley coined the phrase that the projection of such a variety can be described in a sub-space again by polynomials, if the base is algebraically closed. This can be proved by using quantifier elimination of the theory of algebraically closed fields: Be the variety defined as the set of zeros of the polynomials for. The projection on the first coordinates is then given by. This formula is equivalent to a quantifier formula, which is a Boolean combination of the elementary formulas of the type " polynomials = 0", the projection is therefore a Boolean combination of varieties.

Other applications

Also, the Hilbert Nullstellensatz has a proof which is based on the quantifier elimination theory algebraically closed field. For Hilbert's seventeenth problem exists a proof which is based on the quantifier elimination of real closed body theory.

666962
de