Related Directory Categories
- Bound Brook (11)
- Outward Bound (7)
- South Bound Brook (6)
- Bound (5)
- Business and Economy (5)
- SSX - Out of Bounds (4)
- Linear Bounded Automata (3)
- Prometheus Bound (3)
- Guides and Directories (2)
- Business and Economy (2)
Sources
Help build the largest human-edited directory on the web.
Submit a site - Become an editor
Wikipedia. Licensed under the GNU Free Documentation License.
Are you an expert in this subject? Join the discussion and share your knowledge at Wikipedia.org.
Bounded quantifier
From Wikipedia, the free encyclopedia
In the study of formal theories in mathematical logic, bounded quantifiers are often added to a language. These are two quantifiers in addition to 
and 
. They are motivated by the fact that determining whether a sentence with only bounded quantifiers is true is not as difficult as determining whether an arbitrary sentence is true.
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 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.
The semantics of these quantifiers is determined by the following rules:
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 quantifers. 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.
Suppose that L is the language 
of set theory, where the ellipsis may be replaced by term-forming operations such as a symbol for the powerset operation. There are two bounded quantifiers: 
and 
. These quantifiers bind the set variable x and contain a term t which may not mention x but which may have other free variables.
The semantics of these quantifiers is determined by the following rules:
Bounded quantifiers are important in Kripke-Platek set theory, which includes comprehension for formulas with only bounded quantifiers but not comprehension for other formulas. The motivation is the fact that whether a set x satisfies a bounded quantifier formula only depends on the collection of sets that are close in rank to x (as the powerset operation can only be applied finitely many times to form a term).
A formula of set theory which contains only bounded quantifiers is called Δ0.
- Hinman, P. (2005). Fundamentals of Mathematical Logic. A K Peters. ISBN 1-568-81262-0.
- Kunen, K. (1980). Set theory: An introduction to independence proofs. Elsevier. ISBN 0-444-86839-9.