Brogramo
Guest
Guest

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.