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.
Read more about this topic: Bounded Quantifier
Famous quotes containing the words bounded and/or arithmetic:
“Me, what’s that after all? An arbitrary limitation of being bounded by the people before and after and on either side. Where they leave off, I begin, and vice versa.”
—Russell Hoban (b. 1925)
“‘Tis no extravagant arithmetic to say, that for every ten jokes,—thou hast got an hundred enemies; and till thou hast gone on, and raised a swarm of wasps about thine ears, and art half stung to death by them, thou wilt never be convinced it is so.”
—Laurence Sterne (1713–1768)