78 LOGIC AND PROPOSITIONAL CALCULUS [CHAP. 4
Frequently, whenAis some set of numbers, the conditionp(x)has the form of an equation or inequality involving
the variablex.
EXAMPLE 4.7 Find the truth set for each propositional functionp(x)defined on the setNof positive integers.
(a) Letp(x)be “x+ 2 >7.” Its truth set is{ 6 , 7 , 8 ,...}consisting of all integers greater than 5.(b) Letp(x)be “x+ 5 <3.” Its truth set is the empty set. That is,p(x)is not true for any integer inN.(c) Letp(x)be “x+ 5 >1.” Its truth set isN. That is,p(x)is true for every element inN.Remark:The above example shows that ifp(x)is a propositional function defined on a setAthenp(x)could
be true for allx∈A, for somex∈A, or for nox∈A. The next two subsections discuss quantifiers related to
such propositional functions.
Universal Quantifier
Letp(x)be a propositional function defined on a setA. Consider the expression(∀x∈A)p(x) or ∀x p(x) ( 4. 1 )which reads “For everyxinA,p(x)isa true statement” or, simply, “For allx,p(x).” The symbol
∀which reads “for all” or “for every” is called theuniversal quantifier. The statement (4.1) is equivalent to the
statement
Tp={x|x∈A, p(x)}=A ( 4. 2 )
that is, that the truth set ofp(x)is the entire setA.
The expressionp(x)by itself is an open sentence or condition and therefore has no truth value. However,
∀x p(x), that isp(x)preceded by the quantifier∀, does have a truth value which follows from the equivalence
of (4.1) and (4.2). Specifically:
Q 1 :If{x|x∈A, p(x)}=Athen∀x p(x)istrue;otherwise,∀x p(x)isfalse.EXAMPLE 4.8
(a) The proposition(∀n∈N)(n+ 4 > 3 )is true since{n|n+ 4 > 3 }={ 1 , 2 , 3 , ...}=N.(b) The proposition(∀n∈N)(n+ 2 > 8 )is false since{n|n+ 2 > 8 }={ 7 , 8 , ...} =N.(c) The symbol∀can be used to define the intersection of an indexed collection{Ai|i∈I}of setsAias follows:∩(Ai|i∈I)={x|∀i∈I, x∈Ai}Existential Quantifier
Letp(x)be a propositional function defined on a setA. Consider the expression(∃x∈A)p(x) or ∃x, p(x) ( 4. 3 )