Quantifiers | Engineering Mathematics - Civil Engineering (CE) PDF Download

Quantifiers

There are mainly two types of quantifiers that are universal quantifiers and existential quantifiers. Besides this, we also have other types of quantifiers such as nested quantifiers and Quantifiers in Standard English Usages. Quantifier is mainly used to show that for how many elements, a described predicate is true. It also shows that for all possible values or for some value(s) in the universe of discourse, the predicate is true or not.

Example 1:

This statement is false for x= 6 and true for x = 4. Now we will compare the above statement with the following statement

This statement is definitely false. Now we will again define a statement
"There exists an x such that "x ≤ 5 ∧ x > 3"
This statement is definitely true. The phrase "there exists an x such that" is known as the existential quantifier, and "for every x" phrase is known as the universal quantifier. The variables in a formula cannot be simply true or false unless we bound these variables by using the quantifier.

Example 2:
Suppose we have two statements that are ∀x : x² +1 > 0 and ∀x : x² > 2. For x = 1, the first statement ∀x : x² +1 > 0 is true, but the second statement ∀x : x² > 2 is false, because it does not satisfy the predicate. On the other side, if we write the second statement as ∃x : x 2 > 2, it will be true, because x = 2 is an example that satisfies it.
In the quantified expression, if there is a variable, then we always assume that the variable comes from some base set. If we specify x as a real number, then the statement ∀x : x² +1 > 0 will be true. But this statement will be false if we specify x as a complex number such as i. In this case, the predicate will not satisfy by x = i because we don't specify the value of i.

Universal Quantifiers

Sometimes the mathematical statements assert that if the given property is true for all values of a variable in a given domain, it will be known as the domain of discourse. Using the universal quantifiers, we can easily express these statements. The universal quantifier symbol is denoted by the ∀, which means "for all". Suppose P(x) is used to indicate predicate, and D is used to indicate the domain of x. The universal statement will be in the form "∀x ∈ D, P(x)". The main purpose of a universal statement is to form a proposition. In the quantifiers, the domain is very important because it is used to decide the possible values of x. When we change the domain, then the meaning of universal quantifiers of P(x) will also be changed. When we use the universal quantifier, in this case, the domain must be specified. Without a domain, the universal quantifier has no meaning.
The sentence ∀xP(x) will be true if and only if P(x) is true for every x in D or P(x) is true for every value which is substituted for x. The statement ∀xP(x) will be false if and only if P(x) is false for at least one x in D. The value for x for which the predicate P(x) is false is known as the counterexample to the universal statement. If finite values such as {n₁, n₂, n₃, …, n_k} are contained by the universe of discovery, the universal quantifier will be the conjunction of all elements, which is described as follows:
∀xP(x) ⇔ P(n₁) ∧ P(n₂) ∧ · · · ∧ P(n_k)

Example 1: Suppose P(x) indicates a predicate where "x must take an electronics course" and Q(x) also indicates a predicate where "x is an electrical student". Now we will find the universal quantifier of both predicates.
Solution: Suppose the students are from ABC College. For both predicates, the universe of discourse will be all ABC students.
The statements can be: "Every electrical student must take an electronics course". The following syntax is used to define this statement:
∀x(Q(x) ⇒ P(x))
This statement can be expressed in another way: "Everybody must take an electronics course or be an electrical student". The following syntax is used to define this statement:
∀x(Q(x) ∨ P(x))

Example 2: Suppose P(x) indicates a predicate where "x is a square" and Q(x) also indicates a predicate where "x is a rectangle". Now we will find the universal quantifier of these predicates.
Solution:
The statement must be:
∀x (x is a square ⇒ x is a rectangle), i.e., "all squares are rectangles.'' The following syntax is used to describe this statement:
∀xP(x) ⇒Q(x)
Sometimes, we can use this construction to express a mathematical sentence of the form "if this, then that," with an "understood" quantifier.

Universal conditional statement:

This statement has the form: ∀x, if P(x) then Q(x).

For example: In this example, we will rewrite the below statement in the form:

If Jack is 18 years old or older, then he is eligible to vote.

Existential Quantifiers

Sometimes the mathematical statements assert that we have an element that contains some properties. Using existential quantifiers, we can easily express these statements. The existential quantifier symbol is denoted by the ∃, which means "there exists". Suppose P(x) is used to indicate predicate, and D is used to indicate the domain of x. The existential statement will be in the form "∃x ∈ D such that P(x)". The main purpose of an existential statement is to form a proposition. The sentence ∃xP(x) will be true if and only if P(x) is true for at least one x in D. The statement ∃xP(x) will be false if and only if P(x) is false for all x in D. The value for x for which the predicate P(x) is false is known as the counterexample to the existential statement.
If finite values such as {n₁, n₂, n₃, …, n_k} are contained by the universe of discovery, the universal quantifier will be the disjunction of all elements, which is described as follows:
∃xP(x) ⇔ P(n₁) ∨ P(n₂) ∨ P(n₃) · · · ∨ P(n_k)

Example 1: Suppose P(x) contains a statement "x > 4". Now we will find the truth value of this statement.
Solution:
This statement is false for all real number which is less than 4 and true for all real numbers which are greater than 4.
This statement is false for x= 6 and true for x = 4. Now we will compare the above statement with the following statement. So
∃xP(x) is true

Negating Quantified Statements

Earlier we have explain a example in which the statement ∀x : x² > 2 is false and ∀x : x² +1 > 0 is true for x = 1. The first statement is false because x =1 is unable to satisfy the predicate. In this case, we find a solution that says we can negate a ∀ statement by flipping ∀ into ∃. After that, we will negate the predicate inside.
For example: The negation of ∀x : P(x) is ∃x : P(x).
If the statement predicate ∀x : P(x) is true, then ∃x : P(x). Here, the x that satisfies P(x) is known as the counterexample that claims ∀x : P(x). Similarly, if we want to negate ∃x : P(x), we have to claim that P(x) fails to hold for any value of x. So we again flip the quantifier and then negate the predicate like this:
the negation of ∃x : P(x) is ∀x : P(x)

Nested Quantifiers

The nested quantifier is used by a lot of serious mathematical statements. For example:
Let us assume a statement that says, "For every real number, we have a real number which is greater than it". We are going to write this statement like this:
∀x ∃y : y > x
Or assume a statement that says, "We have a Boolean formula such that every truth assignment to its variables satisfies it". We are going to write this statement like this:
∃ formulaF ∀ assignmentsA : A satisfies F.
It is very important to understand the difference between statements that indicate ∃x ∀y and a statement that indicate ∀x ∃y. For example, suppose we are talking about the real number. In this case, our above example ∀x ∃y : y > x is true. But it will be false if we try to write this with quantifiers in other order like this: ∃y ∀x : y > x. This version needs a single number that must be larger than every number.

Negating Nested Quantifiers

In the nested quantifier, we can negate a sequence with the help of flipping each quantifier in the sequence, and after that, we will negate the predicate like this:

When we think, we can realize that it makes sense intuitively. For example: here, we will consider the unbounded sequence definition from calculus. If there are real numbers that have infinite sequence a₁ ≤ a₂ ≤ a₃ ≤ …., then it will be unbounded if it eventually grows greater than x for every number x. Here the quantifiers lurking is already seen: ∀x ∃n : a_n > x.

Now there are some sequences that are unbounded such as 1, 4, 9, 16, 25, …., and some sequences that are not, such as 1/2 , 3/4 , 7/8 , ...... If a sequence is not bounded, it means that it contains an upper-bounded x such that sequence's every number is at most x.

If we want to derive this mathematically, we can do this by negating the definition of unboundedness. If unbounded has the statement ∀x ∃n : an > x, then not unbounded will have the statement ∃x ∀n : an ≤ x. That means by flipping the quantifiers, we can convert unbounded into not unbounded.

Quantifier in Standard English Usages

When we notice, we will realize that quantifiers and Standard English usages are familiar to each other. For example: if someone says, "All people in US has a job", we might reply that "I know someone in US who don't have job". At least subconsciously, we are interrupting this statement by writing this as:
"∀x in UK, x has a job"
If we want to disagree with this statement, we must negate the above statement by flipping ∃ into ∀. After that, the predicate will be negated like this: " ∃x at UK such that x don't have a job". Note that while doing this, we have to take care of the set over, which is used to quantify x. The set is all people in the US.
We can reverse the same things by flipping ∃ into ∀. If someone says, "India has a cricket player who makes over fifty crores a year", we can disagree with this statement by saying, "No, every cricket player makes under 50 crores a year".