Added to Favorites

Related Searches

Definitions

In the study of formal theories in mathematical logic, bounded quantifiers are often added to a language. These are two quantifiers in addition to $forall$ and $exists$. 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.
## Bounded quantifiers in arithmetic

## Bounded quantifiers in set theory

## References

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: $forall\; n\; <\; t$ and $exists\; n\; <\; t$. 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:

- $exists\; n\; <\; t,\; phi\; Leftrightarrow\; exists\; n\; (n\; <\; t\; land\; phi)$

- $forall\; n\; <\; t,\; phi\; Leftrightarrow\; forall\; n\; (n\; <\; t\; rightarrow\; phi)$

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 $phi$ is a decidable predicate then $exists\; n\; <\; t\; ,\; phi$ and $forall\; n\; <\; t,\; phi$ 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 $langle\; 0,1,+,times,\; <,\; =rangle$, 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 $Sigma^0\_0$, $Delta^0\_0$, and $Pi^0\_0$. The superscript 0 is sometimes omitted.

Suppose that L is the language $langle\; in,\; ldots,\; =rangle$ 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: $forall\; x\; in\; t$ and $exists\; x\; in\; t$. 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:

- $exists\; x\; in\; t,\; phi\; Leftrightarrow\; exists\; x\; (x\; in\; t\; land\; phi)$

- $forall\; x\; in\; t,\; phi\; Leftrightarrow\; forall\; x\; (x\; in\; t\; rightarrow\; phi)$

A formula of set theory which contains only bounded quantifiers is called Δ_{0}.

Bounded quantifiers are important in Kripke-Platek set theory and constructive set theory, where only Δ_{0} separation is included. That is, it includes separation for formulas with only bounded quantifiers, but not separation for other formulas. In KP 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). In constructive set theory, it is motivated on predicative grounds.

- 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.

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Wednesday June 04, 2008 at 11:18:55 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Wednesday June 04, 2008 at 11:18:55 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2015 Dictionary.com, LLC. All rights reserved.