Definition and decidability of bounded quantifiersConsider quantifier-free formulas P ( x , y ) = Q ( x , y ) of Peano arithmetic.Consider P(x,y),Q(x,y) to be terms composed of variables x , y , succ , + , ×.Note that these are equivalent with polynomials P ( x , y ) , Q ( x , y ) ∈ Z + [ x , y ].Let R(x) be correspondingly a term, resp. a polynomial in Z + [ x ].The quantifier of a formula ( ∃ y ) P ( x , y ) = Q ( x , y ) is bounded if there is a polynomial R(y) such that ( ∀ x ) ( ( ( ∃ y ) P ( x , y ) = Q ( x , y ) ) → ( y ≤ R ( x ) ) ) which is equivalent with ( ∀ x ) ( ( ( ∃ y ) P ( x , y ) = Q ( x , y ) ) → ( ( ∃ z ) y + z = R ( x ) ) ) which is a pure PA sentence again.(Note that the righthand side of → is a only a shorthand!)I wonder:Is this the correct definition of a bounded quantifier?Has the defining sentence to be true or provable?Is the property of a sentence to have a bounded quantifier decidable?

Question

Definition and decidability of bounded quantifiersConsider quantifier-free formulas   P  (  x  ,  y  )  =  Q  (  x  ,  y  ) of Peano arithmetic.Consider P(x,y),Q(x,y) to be terms composed of variables   x  ,  y  ,  succ  ,  +  ,  ×.Note that these are equivalent with polynomials   P  (  x  ,  y  )  ,  Q  (  x  ,  y  )  ∈            Z        +    [  x  ,  y  ].Let R(x) be correspondingly a term, resp. a polynomial in             Z        +    [  x  ].The quantifier of a formula   (  ∃  y  )     P  (  x  ,  y  )  =  Q  (  x  ,  y  ) is bounded if there is a polynomial R(y) such that  (  ∀  x  )            (                  (        (  ∃  y  )     P  (  x  ,  y  )  =  Q  (  x  ,  y  )            )        →            (        y  ≤  R  (  x  )            )                  )      which is equivalent with  (  ∀  x  )            (                  (        (  ∃  y  )     P  (  x  ,  y  )  =  Q  (  x  ,  y  )            )        →            (        (  ∃  z  )     y  +  z  =  R  (  x  )            )                  )      which is a pure PA sentence again.(Note that the righthand side of   → is a only a shorthand!)I wonder:Is this the correct definition of a bounded quantifier?Has the defining sentence to be true or provable?Is the property of a sentence to have a bounded quantifier decidable?

takwerkyo0 · Accepted Answer

Step 1In general, a bounded quantifier is the abbreviation of a &quot;standard&quot; first-order formula like:  ∀  x  (  P  x  →  Q  x  )which we can abbreviate in slightly different forms according to the contexts :set theory :   ∀  x  ∈  P  :  Q  x, which is :   ∀  x  (  x  ∈  P  →  Q  x  );(formal) arithmetic :   ∀  x  ≤  n  :  Q  x, which is :   ∀  x  (  x  ≤  n  →  Q  x  ).Step 2Thus, if we consider the second case, we can &quot;unwind&quot; it as :  ∀  x  (  ∃  y  (  n  =  x  +  y  )  →  Q  x  )

Adrian Brown · Accepted Answer

Step 1Is this the correct definition of a bounded quantifier?I would say you are talking about &quot;boundable&quot; existential quantifiers, rather than bounded quantifiers.It is true that terms in Peano arithmetic are polynomials, so in the language of Peano arithmetic if we have a bounded quantifier   (  ∃  x  &amp;lt;  t  (  y  )  )  R  (  x  ,  y  ) then t(y) is a polynomial in y.You have defined what it means to be able to replace the existential quantifier in (∀y)  (  ∀  y  )  (  ∃  x  )  R  (  x  ,  y  ) with a bounded quantifier.Has the defining sentence to be true or provable?You will get two different notions depending whether you want to defining sentence to be true or provable. This follows from the next answer.Is the property of a sentence to have a bounded quantifier decidable?No. Let P(y) be any formula with one free variable y. Let S(x,y) be a formula such that it is satisfied only when   x  =      2    y  . Let R(x,y) be  [  x  =  0  ∧  (  ∀  z  &amp;lt;  y  )  P  (  z  )  ]  ∨  [  S  (  x  ,  y  )  ∧  (  ∃  z  &amp;lt;  y  )  ¬  P  (  z  )  ]  .Step 2Note that   (  ∀  y  )  (  ∃  x  )  R  (  x  ,  y  ) holds, provably in PA. But the quantifier is boundable (by a polynomial) if and only if   (  ∀  y  )  P  (  y  ) holds. And the quantifier is provably boundable if and only if   (  ∀  y  )  P  (  y  ) is provable. In general, the latter two are not equivalent.

Definition and decidability of bounded quantifiers. Consider quantifier-free formulas P(x,y)=Q(x,y) of Peano arithmetic.

Answered question

Answer & Explanation

New Questions in Algebra II