1.2 Quantifiers

The statement P(x): “X is greater than 3” is called “a propositional function” and has two parts. The first part is “the variable x” which is the subject of the statement. The second part, the predicate, “is greater than 3” refers to the property that the subject can have. One a value has been assigned to the variable x, the statement p(x) becomes a proposition and has a truth value.

We can also have statements having more than one variable such as



1.2.1 Example

If P(x)is the statement “x>3” then obviously P(4)(since 4>3) is true and P(2) is false (since 2<3).

1.2.2. Example

If P(x,y,z)is “x+y=z” then obviously P(1,2,3) is true while P(2,3,4) is false.

1.2 Quantifiers

1.2.3 Definition

“The universal quantification” of P(x) is the statement “P(x) for all values of x in the domain”. The notation “∀xP(x)” denotes the universal quantification of P(x). Here ∀ is called the “universal quantifier”. We read ∀xP(x) as “for all xP(x)”or “for every xP(x)”.

An element x for which P(x) is false is called “a counter example” of ∀xP(x).

1.2.4 Definition

“The existential quantification” of P(x) is the proposition.

“There exits an element x in the domain such that P(x)”

We use the notation ∃xP(x) for the existential quantification of P(x). Here ∃ is called the “existential quantifier”.

1.2.5 Remarks

(i)A domain must always be specified when quantifiers are used.

1.2 Quantifiers

(ii) The following table illustrates the meaning of the universal and existential quantifiers:


1.2.6 Example

Let P(x) and Q(x) be the statement “x+1>x” and “x<2”, respectively.
What are the truth values for the quantifications “∀xP(x)” and “∀xQ(x)” where the domain consists of all real numbers.

Solution

Since P(x) is true for all real numbers, the quantification “∀xP(x)” is true. while the quantification “∀xQ(x)” is false since ∃x=3 in the domain for which Q(x) is false i.e Q(3) is false.

1.2 Quantifiers

1.2.7 Remark

Note that the truth value of quantification depends on the domain (the universe of discourse). For example the quantification “∀x(x²≥x) is true if the domain is the set of all integers while this quantification is false if the domain is the set of all rational numbers (since e.g. ((½)²≱2).

1.2.8 Example

In the following cases we consider all real number as our domain.

(i) If P(x) is the statement “x≥3” then “∃xP(x)” is true since P(4) is true.
(ii) If P(x) is the statement “x=x+1” then “∃xP(x)” is false since P(x) is false of all real numbers.

1.2.9. Remark

(The negation of quantification). It is clear that

1.2 Quantifiers

1.2.10 Example

1.2.11 Definition
(Nested quantifiers). By a nested quantification we mean a quantification in which a quantifier lies within the scope of another one, such as: ∀xƎy (x+y=0)

1.2.12 Example

Assume that the domain of the variables x, y and z consists of all real numbers.
(i) The nested quantification “∀x∀y(x+y=y+x)” is the commutative law for addition.
(ii) The nested quantification “∀xxƎy(x+y=0)” expresses the existence of an additive inverse y for
every real number x.
(iii) The nested quantification “∀x∀y∀z((x+y)+z=x+(y+z))” is the associative law for addition.
(iv) The nested quantification “∀x∀y[(x>0 ^y<0)→xy<0] means that for every real number x and for every real number y, if x is positive and y is negative then xy is negative.