# Universal and Existential Quantifiers

We’ve seen in Predicate vs Proposition that replacing a function’s variables with actual values changes a predicate into a proposition. Another way of changing a predicate into a proposition is using quantifiers.

## Universal Quantifier ∀

The symbol `∀` is called a universal quantifier, and the statement `∀x F(x)` is called a universally quantified statement. In `∀x F(x)`, the `∀` states that all the values in the domain of `x` will yield a true statement. Our job is to test this statement. But instead of trying to prove that all the values of `x` will return a true statement, we can follow a simpler approach by finding a value of `x` that will cause the statement to return false.

When a value in the domain of x proves the universal quantified statement false, the x value is called a counterexample. A counterexample is the number 1 in the following example.

Counterexample
The domain of x is all positive integers (e.g., 1,2,3,…)
`∀x F(x): x - 1 > 0` (x minus 1 is greater than 0)

All the numbers in the domain prove the statement true except for the number 1, called the counterexample.

## Existential Quantifier ∃

The symbol `∃` is called an existential quantifier, and the statement `∃x F(x)` is called an existentially quantified statement. In `∃x F(x)`, the ∃ states that there is at least one value in the domain of `x` that will make the statement true. The object becomes to find a value in an existentially quantified statement that will make the statement true. If we find the value, the statement becomes true; otherwise, it becomes false.

In general terms, the existential and universal statements are called quantified statements.

The quantified statement `∃x (Q(x) ∧ W(x))` is read as `(∃x Q(x)) ∧ (∃x W(x))`. And this statement, `∀x (E(x) → R(x))`, is read as `(∀x (E(x))→ R(x)`.

## Bound and Free Variables

A bound variable is a variable that is bound by a quantifier, such as `∀x E(x)`. A statement with a bound variable is called a proposition because it evaluates true or false but never both.

A free variable is a variable that is not associated with a quantifier, such as `P(x)`. This statement is known as a predicate but changes to a proposition when assigned a value, as discussed earlier.

Bound variable example
`∀x (E(x) → R(x))` is rearranged as `(∀x (E(x))→ R(x)`
`(∀x (E(x))` this statement has a bound variable
`R(x)` and this statement has a free variable
∀x (E(x) → R(x)) as a whole statement, this is not a proposition

`∃x T(x)` is a proposition because it has a bound variable.
`(∃x S(x)) ∨ R(x)` is a predicate because part of the statement has a free variable.

## Nested Quantifiers

A predicate has nested quantifiers if there is more than one quantifier in the statement. Each quantifier can only bind to one variable, such as ∀x ∃y E(x, y). The first quantifier is bound to x (∀x), and the second quantifier is bound to y (∃y). Let’s run through an example.

Nested Quantifiers Example

The `∃` asserts that at least one value will make the statement true. If no value makes the statement true, the statement is false.
The `∀` asserts that all the values will make the statement true. The statement becomes false if at least one value does not meet the statement’s assertion.

`x = {0,1,2,3,4,5,6}` domain of x
`y = {0,1,2,3,4,5,6}` domain of y

`∃x ∀y E(x + y = 5)` reads as “At least one value of x plus any value of y equals 5.”
The statement is false because no value of x plus any value of y equals 5.

Instead of saying “reads as,” I will use the biconditional symbol ↔ to indicate that the nested quantifier example and its English translation have the same truth value.

`∀x ∃y E(x + y = 5)` ↔ “Any value of x plus at least one value of y will equal 5.”
The statement is true.

`∀x ∀y E(x + y = 5)` ↔ “Any value of x plus any value of y will equal 5.”
The statement is false.

`∃x ∃y E(x + y = 5`) ↔ “At least one value of x plus at least any value of y will equal 5.”
The statement is true.

In nested quantifiers, the variables x and y in the predicate, ∃x ∀y E(x + y = 5), are bound and the statement becomes a proposition. There are no free variables in the above proposition.

## Quantifiers and Negation

The symbol ¬ is the negation symbol. It reverses a statement’s value. If ∀x F(x) equals true, than ¬∀x F(x) equals false.

## De Morgan’s Law on Quantifiers

De Morgan’s law states that ¬(T ∨ Y) ≡ (¬T ∧ ¬Y), notice how distributing the negation changes the statement operator from disjunction ∨ to conjunction ∧. The ≡ symbol means that both statements are logically equivalent.

In quantifiers, De Morgan’s law applies the same way.
¬∃x P(x) ≡ ∀x ¬P(x)
¬∀x P(x) ≡ ∃x ¬P(x)

De Morgan’s law also applies to nested quantifiers.
¬∀x ∀y P(x, y) ≡ ∃x ∃y ¬P(x, y)
¬∀x ∃y P(x, y) ≡ ∃x ∀y ¬P(x, y)
¬∃x ∀y P(x, y) ≡ ∀x ∃y ¬P(x, y)
¬∃x ∃y P(x, y) ≡ ∀x ∀y ¬P(x, y)

## Summary

• The universal symbol, `∀`, states that all the values in the domain of `x` will yield a true statement
• The existential symbol, `∃`, states that there is at least one value in the domain of `x` that will make the statement true.
• A bound variable is associated with a quantifier
• A free variable is not associated with a quantifier
• A predicate has nested quantifiers if there is more than one quantifier in the statement.
Feedback?