Quantifier

Quantifiers are symbols that allow us to talk about parameters in predicates.

Two kinds:

• Existential Quantification (there exists)
• Universal Quantification (for all)

info

Quantifiers allow us to form propositions out of predicates without filling in any specific value for parameters.

Existential Quantification

The existential quantifier has the symbol $\exists$ and means "there exists".

$$\exists x \in \mathbb{Z} \, (x^2 = 4)$$

The above expression means that "There exists $x$ from $\mathbb{Z}$ such that $x^2 = 4$ is true".

tip

We don't get to known which value of $x$ works, just that some value of $x$ works.

Examples

Existential Quantifiers Examples:

• $\exists x \in S \, p(x)$ means "There exists an $x$ in $S$ such that $p(x)$ is true".
• $\exists x \in \text{ANIMALS } \, x \text{ is a fish}$ means that "There exists an $x$ in $\text{ANIMALS}$ such that $x$ is a fish is true".
• $\exists x \in \mathbb{R} \, (x \in \mathbb{Z})$ means that "There exists some real number $x$ such that $x$ is an integer".

Universal Quantification

The universal quantifier has the symbol $\forall$ and means "for all".

$$\forall x \in \mathbb{Z}( x^2 \geq 0)$$

The above expression means that "For every $x$ in $\mathbb{Z}$, $x^2 \geq 0$ is always true".

Examples

Universal Quantifiers Examples:

• $\forall x \in S \, p(x)$ means that "For all $x$ from $S$, $p(x)$ is true".
• $\forall x \in \text{ANIMALS} \, (x \text{ is a cat})$ means that "For all $x$ in $\text{ANIMALS}$, $x$ is a cat".
• $\forall x \in \mathbb{Z} \, (x \in \mathbb{R})$ mean that "All integers are real numbers".

Free Parameters

Consider $A(y) = \exists x \, p(x,y)$.

• The parameter $x$ is quantified over, so we cannot fill it in.
• The parameter $y$ is not quantified over, so we can fill it in.
• $y$ is called a free parameter.
• The truth value of $A(y)$ depends on the value of parameter $y$.

info

If there are no free parameters, then the predicate is fully quantified.

Necessary and Sufficient Conditions

When $\forall x \, (p(x) \implies q(x))$ we say:

• $p(x)$ is a sufficient condition for $q(x)$.
• $q(x)$ is a necessary condition for $p(x)$.

When $\forall x \, p(x) \iff q(x)$ we say:

• $p(x)$ is necessary and sufficient for $q(x)$.
• $q(x)$ is necessary and sufficient for $p(x)$.

Example

Statement: "Squareness is a sufficient condition for rectangularity".

We can say that $\forall x$, if $x$ is a square, then x is a rectangle.

References

• Week5 Materials