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

[edit] 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 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 $φ$ 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.

[edit] Bounded quantifiers in set theory

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)$

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

[edit] References

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.

Retrieved from "http://en.wikipedia.org../../../b/o/u/Bounded_quantifier.html"

Categories: Mathematical logic | Proof theory | Recursion theory