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.