Quantifier elimination

<p>Quantifier elimination is a concept of simplification used in <a href="/facts/Mathematical_logic/SaI7Y3wN">mathematical logic</a>, <a href="/facts/Model_theory/vLWVV8sQ">model theory</a>, and <a href="/facts/Theoretical_computer_science/jSkGGuvy">theoretical computer science</a>. Informally, a quantified statement "
  
    
      
        ∃
        x
      
    
    {\displaystyle \exists x}
  
 such that ..." can be viewed as a question "When is there an 
  
    
      
        x
      
    
    {\displaystyle x}
  
 such that ...?", and the statement without quantifiers can be viewed as the answer to that question.
</p><p>One way of classifying <a href="/facts/Well-formed_formula/YpTVlzuj">formulas</a> is by the amount of <a href="/facts/Quantifier_(logic)/bgmvwxoo">quantification</a>. Formulas with less <a href="/facts/Quantifier_(logic)/bgmvwxoo">depth of quantifier alternation</a> are thought of as being simpler, with the quantifier-free formulas as the simplest.
A <a href="/facts/Logical_theory/vLWVV8sQ">theory</a> has quantifier elimination if for every formula 
  
    
      
        α
      
    
    {\displaystyle \alpha }
  
, there exists another formula 
  
    
      
        
          α
          
            Q
            F
          
        
      
    
    {\displaystyle \alpha _{QF}}
  
 without quantifiers that is <a href="/facts/Logical_equivalence/ysCWmsxA">equivalent</a> to it (<a href="/facts/Modulo_(jargon)/lg6V4FF9">modulo</a> this theory).
</p>

Quantifier elimination open-in-new

Quantifier elimination