Bounded Quantifiers

“I could be bounded in a nutshell and count myself a king of infinite space”
—Shakespeare, Hamlet

For simplicity, the only official quantifiers in Predicate Logic and the “bare” universal and existential quantifiers. But we rarely see these in practice; most applications involve quantifying not over everything in the universe, but over some restricted set or domain. Here we show that Predicate Logic still suffices for real mathematics, because restricted quantifiers can be viewed as (extremely useful) abbreviations for more complex formulas.

Important Abbreviations

Bounded Universal Quantifiers

Definition

“For every $x$ such that …, $P(x)$ holds:

\begin{array}{lcl} \forall x{\in}S\ \, P(x) & := & \forall x\ (\,x\in S\ \to\ P(x)\,) \\ \forall x{\leq}N\ \, P(x)& := &\forall x\ (\,x\leq N\ \to\ P(x)\,) \\[10pt] \mathrm{etc.}\\ \end{array}

(where the $~:=~$ operator means we are defining the left-hand-side to be equal to the right-hand-side).

Bounded Existential Quantifiers

Definition

“For some $x$ such that …, $P(x)$ holds:

\begin{array}{lcl} \exists x{\in}S\ \, P(x)& := &\exists x\ (\,x\in S\ \land\ P(x)\,) \\ \exists x{\leq}N\ \, P(x)& := &\exists x\ (\,x\leq N\ \land\ P(x)\,) \\[10pt] \mathrm{etc.}\\ \end{array}

Unique Existential Quantifiers

Definition

“There exists a unique $x$ such that … where $P(x)$ holds:

\begin{array}{lcl} \exists!x{\in}S\ \, P(x)& := &\exists x\ \bigl(x\in S \land P(x) \land \forall y\ (y \in S \land P(y) \ \to\ x = y)\bigr) \\ \qquad\mathrm{or} & := &\exists x\ \bigl(x\in S \land P(x) \land \lnot\exists y\ (y \in S \land P(y) \land x \not= y)\bigr) \\ \end{array}

Important Equivalences

Example

The following equivalences hold and should be memorized.

Basically, they say that rules for pushing a negation into a quantified formula are the same for restricted quantifiers as we saw earlier for bare quantifiers.

\begin{array}{lcl} \lnot \forall x{\in}S\ \ P(x) & \equiv & \exists x{\in}S\ \ \ \lnot P(x) \\ \lnot \forall x{\leq}N\ \ P(x) & \equiv & \exists x{\leq}N\ \ \ \lnot P(x) \\[10pt] \lnot \exists x{\in}S\ \ P(x) & \equiv & \forall x{\in}S\ \ \ \lnot P(x) \\ \lnot \exists x{\leq}N\ \ P(x) & \equiv & \forall x{\leq}N\ \ \ \lnot P(x) \\ \end{array}

These equivalences can all be verified by expanding the formulas into their more primitive forms, and then applying familiar rules of logical equivalence.

We can verify the first equivalence above as follows:

\begin{array}{lcl} \lnot \forall x{\in}S\ \ P(x) & = & \lnot \forall x\ (x\in S\ \to\ P(x)) \\ &\equiv & \exists x\ \lnot (x\in S\ \to\ P(x)) \\ &\equiv & \exists x\ (x\in S\ \land\ \lnot P(x)) \\ &= & \exists x{\in}S\ \ \ \lnot P(x) \\ \end{array}

in general, we will work directly with bounded quantifiers and ignore the fact that logicians treat them as abbreviations for more primitive concepts.