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 variableR(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 xy = {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 ofxwill yield a true statement - The existential symbol,
∃, states that there is at least one value in the domain ofxthat 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.