Bounded Quantifier - Bounded Quantifiers in Arithmetic

Bounded Quantifiers in Arithmetic

Suppose that L is the language of Peano arithmetic (the language of second-order arithmetic or arithmetic in all finite types would work as well). There are two types of bounded quantifiers: and . These quantifiers bind the number variable n and contain a numeric term t which may not mention n but which may have other free variables. (By "numeric terms" here we mean terms such as "1 + 1", "2", "2 × 3", "m + 3", etc.)

These quantifiers are defined by the following rules ( denotes formulas):

There are several motivations for these quantifiers.

• In applications of the language to recursion theory, such as the arithmetical hierarchy, bounded quantifiers add no complexity. If is a decidable predicate then and are decidable as well.
• In applications to the study of Peano Arithmetic, formulas are sometimes provable with bounded quantifiers but unprovable with unbounded quantifiers.

For example, there is a definition of primality using only bounded quantifiers. A number n is prime if and only if there are not two numbers strictly less than n whose product is n. There is no quantifier-free definition of primality in the language, however. The fact that there is a bounded quantifier formula defining primality shows that the primality of each number can be computably decided.

In general, a relation on natural numbers is definable by a bounded formula if and only if it is computable in the linear-time hierarchy, which is defined similarly to the polynomial hierarchy, but with linear time bounds instead of polynomial. Consequently, all predicates definable by a bounded formula are Kalmár elementary, context-sensitive, and primitive recursive.

In the arithmetical hierarchy, an arithmetical formula which contains only bounded quantifiers is called, and . The superscript 0 is sometimes omitted.