4

I was reading a Wikipedia article on arithmetical hierarchy and came across bounded quantifiers. I didn't know what those were and so quickly went to another article to read up on them and only became more confused. Here's the definition, given by Wikipedia:

"In the study of formal theories in mathematical logic, bounded quantifiers are often added to a language in addition to the standard quantifiers "∀" and "∃". Bounded quantifiers differ from "∀" and "∃" in that bounded quantifiers restrict the range of the quantified variable."

I don't exactly understand what this means, though. Could somebody explain to me what a bounded and unbounded quantifier is (as simple as possible)? Thanks in advance.

2 Answers2

4

When we use quantifiers such as "$\forall$" and "$\exists$" we are quantifying over some domain. For example, the domain of discourse over which we are operating may be the natural numbers $\mathbb{N}$. Consider the following sentence: $$\forall x \exists y (x <y).$$ Given the context, this means "for every element $x$ of $\mathbb{N}$ there exists another element $y$ of $\mathbb{N}$ such that $x$ is less than $y$."

Now suppose we are not interested in all of $\mathbb{N}$, but rather every natural number less than $10$. Then we may use a bounded quantifier to express (the obviously false sentence) "for every number $x$ less than $10$ there is another number $y$ less than $10$ such that $x$ is less than $y$." Symbolically, $$\forall x <10 \exists y <10(x<y).$$ Since by using $x <10$ after the traditional quantifiers we are specifying that our numbers are coming from the set $\{1,2,...,10\}$ and not all of $\mathbb{N}$, the quantifiers "$\forall x <10$" and "$\exists y < 10$" are called bounded quantifiers.

Interestingly, most sentences using bounded quantifiers may be rephrased without using bounded quantifiers. For example, our sentence may be rewritten $$\forall x(x < 10 \to (\exists y(y <10 \wedge x < y))).$$

Exit path
  • 4,328
2

Unbounded qualifier- there exist x such that $x^2= 2$. Bounded qualifier- there exist x between 1 and 2 such that $x^2= 2$.

user247327
  • 18,710