4 Quantifiers and Quantified Arguments

4.1 Quantifiers
Recall from Chapter 3 the definition of a predicate as an assertion con-
taining one or more variables such that, if the variables are replaced by
objects from a given Universal set U then we obtain a proposition.
Let p(x) be a predicate with one variable.
Definition
If for all x ∈ U , p(x) is true, we write ∀x : p(x).
∀ is called the universal quantifier.
Definition
If there exists x ∈ U such that p(x) is true, we write ∃x : p(x).
∃ is called the existential quantifier.
Note
(1) ∀x : p(x) and ∃x : p(x) are propositions and so, in any given example,
we will be able to assign truth-values.
(2) The definitions can be applied to predicates with two or more vari-
ables. So if p(x, y) has two variables we have, for instance, ∀x, ∃y : p(x, y) if
“for all x there exists y for which p(x, y) is holds”.
(3) Let A and B be two sets in a Universal set U . Recall the definition
of A ⊆ B as

“every element of A is in B.”

This is a “for all” statement so we should be able to symbolize it. We do
so by first rewriting the definition as

“for all x ∈ U , if x is in A then x is in B, ”

which in symbols is

∀x ∈ U : if (x ∈ A) then (x ∈ B) ,
or

∀x : (x ∈ A) → (x ∈ B) .

1
 (4*) Recall that a variable x in a propositional form p(x) is said to be
free. The variable x in ∀x : p(x) or ∃x : p(x) is said to be bound, that is, it
is bound by the quantifier ∀ and ∃ respectively. In a statement of the form
∀x : p(x, y) the variable x is bound while the variable y is free.
Example 43
Let p(x) be the predicate “x > 0”.
Then if U = N = {1, 2, ...} the proposition “∀x : x > 0” is TRUE.
But if U = Z = {..., −1, 0, 1, 2, ...} the proposition “∀x, x > 0” is FALSE.
So, the Universal set is important.
Example What are the truth values of the following propositions?
(i) U = R, ∀x : if 6 + x = 12 then 5 + x = 11.
Answer: True.
Reason: To be true we need that (6 + x = 12) → (5 + x = 11) is true for
every possible choice of x ∈ R. If we choose an x such that 6 + x = 12 is
False then, since p → q is True if p is False, we have that (6 + x = 12) →
(5 + x = 11) is True. So the only possible problem is if we choose x such that
6+x = 12 is True. This means we choose x = 6. But then 5+x = 5+6 = 11,
i.e. 5 + x = 11 is True. So in this case (6 + x = 12) → (5 + x = 11) is True
→ True, which we know is true.
Hence in all cases, (6 + x = 12) → (5 + x = 11) is True.
(ii) U = R, if ∀x : 6 + x = 12 then ∀x : 5 + x = 11.
Answer: True.
Reason: In symbols this is

(∀x : 6 + x = 12) → (∀x : 5 + x = 11) . (1)

But ∀x : 6 + x = 12 is False (it is easy to choose an x ∈ R such that
6 + x = 12 is false, i.e. x = 0), hence (1) is True.
(iii) U = R, ∀x : if ∃y : x + y = 0 then ∃y : xy = 0.
Answer: True.
Reason: We have to answer the question of whether, given any x ∈ R,

(∃y : x + y = 0) → (∃y : xy = 0) (2)

is True. But given x we can find y such that x + y = 0 (choose y = −x), so
∃y : x + y = 0 is True. Similarly, given x we can find y such that xy = 0
(choose y = 0), so ∃y : xy = 0 is True. Thus (2) is an example of True →
True, which is True.

2
Example 44 Let U = R.
Let p(x, y) be the predicate “x + y = 0”.
Given any x ∈ R choose y = −x so that x + y = 0. Thus, for all x we
can find a y such that x + y = 0, i.e. ∀x ∃y : x + y = 0 is TRUE.
Yet ∃x ∀y : x + y = 0 is FALSE for it says there exists an x such that
for all y, x + y = 0. Just choose y = 1 − x to see x + y = 1 6= 0.
So ∀x ∃y : p(x, y) need not be the same as ∃x ∀y : p(x, y) and thus the
order of the quantifiers is important.
Example 45 Let U = set of animals.
Symbolize “All cats eat meat”.
Read this as: “For all x ∈ U , if x is a cat then x eats meat”.
So if Cx ≡ “x is a cat”, M x ≡ “x eats meat”, we get

∀x : Cx → M x

Example 46 Let U = set of animals.

Symbolize “Some dogs drink wine”.
Read this as: “There exists x ∈ U such that x is a dog and x drinks
wine”.
So if Dx ≡ “x is a dog”, W x ≡ “x drinks wine”, we get

∃x : Dx ∧ W x
Note (i) “Most times” a “For All” statement will have a → following the
∀, while a “There Exists” statement will have a ∧ after the ∃.
(ii) The statment ∀x : Cx → M x does not assert the existance of a cat in
the universe of all animals, it just says that if a cat exists then it will have
certain properties. On the other hand ∃x : Dx ∧ W x does assert that at least
one of the animals in the universe is a dog, and you can in fact go further
and find one of these dogs that drinks wine.
4.2 Negation
The rules are:
¬ (∀x : p(x)) ≡ ∃x : ¬ p(x)
¬ (∃x : p(x)) ≡ ∀x : ¬ p(x)

3
Example 47

¬ (∀x : x > 0) ≡ ∃x : ¬ (x > 0)

≡ ∃x : x ≤ 0
If U = N then ∃x : x ≤ 0 is FALSE while if U = Z then it is TRUE. So
we see that the negation of what was true in Example 43 is now false and
visa-versa, as you would expect with negation.
Example 48 Let U = R.

¬ (∀x ∃y : x + y = 0) ≡ ∃x : ¬ (∃y : x + y = 0)
≡ ∃x : ∀y ¬ (x + y = 0)
≡ ∃x ∀y : x + y 6= 0

The last expression here is FALSE, for if such an x exists choose y = −x

to find an example when x + y 6= 0 does not hold.
Example 49 Let U = set of animals and Cx, M x be as in Example 45, then

¬ (∀x : Cx → M x) ≡ ∃x : ¬ (Cx → M x)
≡ ∃x : Cx ∧ (¬ M x)

(Using ¬ (p → q) ≡ p ∧ ¬q as seen in question Ex. 16.)

The final result says “Some cat does not eat meat” which is the negation
of “All cats eat meat”.
Example 50 Let U = set of animals and Dx, W x be as in Example 45, then

¬ (∃x, Dx ∧ W x) ≡ ∀x : ¬ (Dx ∧ W x)
≡ ∀x : Dx → (¬ W x)

(Using ¬ (p ∧ q) ≡ p → ¬q as can be checked by the student.)

The final results says “All dogs do not drink wine” which is the negation
of “Some dogs drink wine”.
We see that negation fits in with the expectation noted earlier that ∀ is
followed by a → while a ∃ is followed by a ∧. For, as above,

¬ (∃x : px ∧ qx) ≡ ∀x : px → (¬ qx)

¬ (∀x : px → qx) ≡ ∃x : px ∧ (¬ qx)
On the right-hand side we see that ∀ is followed by an → while ∃ is
followed by an ∧.

4
4.3 Arguments
We have the following rules:
U.S. Universal Specification
Given ∀x : p(x) as a premise we can assume p(u) for any u ∈ U .
E.S. Existential Specification
Given ∃x : p(x) as a premise we can assume p(u0 ) for some u0 ∈ U .
U.G. Universal Generalisation
If, for any u ∈ U , we can conclude p(u) then we can conclude ∀x : p(x).
E.G. Existential Generalisation
If, for some u0 ∈ U , we can conclude p(u0 ) then we can conclude ∃x :
p(x).
Negation
If we have a step of the form ¬ (∀x : p(x)) we can conclude ∃x : ¬ p(x),
and vice versa.
If we have a step of the form ¬ (∃x : p(x)) we can conclude ∀x : ¬ p(x),
and vice versa.

Example 51 Let U = the set of all people.

(i) Consider:
All maths lecturers have studied logic.
Dr. Coleman is a maths lecturer.
Therefore, Dr. Coleman has studied logic.
Let m(x) ≡ “x is a maths lecturer”, l(x) ≡ “x has studied logic”, and u0 ∈ U
is the person called Dr. Coleman. Then the argument is symbolised as

∀x : m(x) → l(x), m(u0 ) ` l(u0 ).

Here is a proof of validity:

1 ∀x : m(x) → l(x) A
2 m(u0 ) → l(u0 ) Universal Specification 1
3 m(u0 ) A
4 l(u0 ) MPP 2-3

Thus the argument is valid.

5
(ii) Consider:
All maths lecturers have studied logic.
Dr. Coleman is a maths lecturer.
Therefore, some person has studied logic.
This time the argument is symbolised as

∀x : m(x) → l(x), m(u0 ) ` ∃x : l(x).

Here is a proof of validity:

1 ∀x : m(x) → l(x) A
2 m(u0 ) → l(u0 ) Universal Specification 1
3 m(u0 ) A
4 l(u0 ) MPP 2-3
5 ∃x : l(x) E.G. 4

Thus the argument is valid.

(iii) Consider:
All maths lecturers have studied logic.
Some person is a maths lecturer.
Therefore, some person has studied logic.
This time the argument is symbolised as

∀x : m(x) → l(x), ∃x : m(x) ` ∃x : l(x).

Here is a proof of validity:

1 ∃x : m(x) A
2 m(u0 ) E.S. 1
3 ∀x : m(x) → l(x) A
4 m(u0 ) → l(u0 ) Universal Specification 1
5 l(u0 ) MPP 2,4
6 ∃x : l(x) E.G. 5

Thus the argument is valid.

The idea is to use the rules above to replace propositional forms containing
quantifiers by forms without quantifiers on which we can use any and all
of the rules of inference. Then, if the argument we are examining has a
conclusion containing quantifiers, we must use the four rules again, because

6
the rules of inference can only be applied to and have a conclusion of the
form not containing quantifiers.
Example 52 Let U = set of all animals.
Consider:
Elephants have large ears,
All animals with large ears can hear well.
Therefore, elephants can hear well.
Let Ex ≡ “x is an Elephant”, Lx ≡ “x has large ears”, Hx ≡ “x can hear
well”.
The first premise does not contain the word “All” but nonetheless we
know that it is a statement about “All elephants”. Thus the argument can
be symbolized as

∀x : Ex → Lx, ∀x : Lx → Hx ` ∀x : Ex → Hx.

To prove ∀x : Ex → Hx we need to prove Eu → Hu for all u ∈ U. To prove

Eu → Hu we use C.P.
(Ask yourself how you would have proved that the non-quantified argu-
ment, e → `, ` → h ` e → `, is valid. Not too difficult since we have seen
this argument earlier in the course.)

1 d Eu A(C.P) and Specification to any u ∈ U ,

2 | ∀x : Ex → Lx A
3 | Eu → Lu US 2
4 | Lu MPP 1,3
5 | ∀x : Lx → Hx A
6 | Lu → Hu US 5
7 b Hu MPP 4,6
8 Eu → Hu CP 1-7
9 ∀x : Ex → Hx UG 8

This method of proof is an extension of the Natural Deduction of section

2. We recall that Natural Deduction is a syntactic method, depending only
on the form of the statements, not the meaning.
Is there a semantic method for predicate arguments? As we noted earlier
it can be easier to prove a propositional argument is invalid by the semantic
method rather than by the syntactic.
We cannot use truth tables but we can use the idea behind the truth-table
method and say that a predicate argument is invalid if there is an instance

7
of the argument where the premises are true yet the conclusion false. If, in
all instances, this never happens we say the argument is valid.
The following has not been covered in 2004.
Example 53 Consider ∀x : px → qx, qu0 ` pu0 for some u0 ∈ U the
universal set.
We look at an “instance” of this argument where px is replaced by p ∈ P
and qx by x ∈ Q for two sets P and Q to be chosen.
The first premise now becomes ∀x : (x ∈ P ) → (x ∈ Q) which is nothing
other than the definition of set inclusion, i.e. P ⊆ Q. So in terms of sets our
argument looks like

P ⊆ Q, u0 ∈ Q ` u0 ∈ P,
for some u0 ∈ U . We now make particular choices of the sets. For instance
P = {1, 2, 3, 4} and Q = {1, 2, 3, 4, 5} with u0 = 5. With these choices the
premises are both true yet the conclusion is false. We never want to see this
in a valid argument. Hence our argument is not valid, i.e. it is invalid.
*Example Consider ∃x : px, ∀x : qx → px ` ∃x : qx.
If we are to replace px and qx by p ∈ P and x ∈ Q for two sets P and
Q then the first premise says that P 6= ∅. So in terms of sets the argument
looks like

P 6= ∅, Q ⊆ P ` Q 6= ∅.
But the choice of P = {1} and Q = ∅ shows this argument to be invalid.

Further Examples
A more complicated example of the use of the rules of inference.
Example A

∀x : p(x) → (q(x) ∨ r(x)), ∀x : ¬q(x), ∃x : ¬r(x) ` ∃x : ¬p(x).

We will use proof by contradiction, RAA. (Ask yourself how you would have
proved that p → q ∨ r, ¬q, ¬r ` ¬p is valid?)

8
 1 d ¬(∃x : ¬p(x)) A(RAA)
2 | ∀x : ¬(¬(p(x))) negation
3 | ∃x : ¬r(x) A
4 | ¬r(u0 ) E.S 3
5 | ¬(¬(p(u0 ))) U.S 2
6 | p(u0 ) D.N 5
7 | ∀x : p(x) → (q(x) ∨ r(x)) A
8 | p(u0 ) → (q(u0 ) ∨ r(u0 )) U.S 7
9 | q(u0 ) ∨ r(u0 ) M.P.P 6,8
10 | q(u0 ) D.S 4,9
11 | ∀x : ¬q(x) A
12 | ¬q(u0 ) U.S 11
13 b q(u0 ) ∧ (¬q(u0 )) ∧I, 10,12
14 ∃x : ¬p(x) RAA 1-13.

A more complicated example of showing an argument is invalid is given

in:
*Example B Let U = Set of all people in the world.
Consider:
All Londoners live in England.
The President of France is not a Londoner.
Therefore, the President of France does not live in England.
All the propositions are true but does the conclusion “follow logically” from
the premises?
To examine the “form” of the argument let
Lx ≡ “x is a Londoner”,
M x ≡ “x lives in England”,
u0 = The President of France ∈ U .
Then in symbolic form the argument reads:

∀x : Lx → Ex, ¬Lu0 ` ¬Eu0 .

We look at another instance, for example as in Example 53 we look for an
example using sets. So we inteprete Lx : x ∈ L and Ex : x ∈ E for sets L
and E to be chosen. Then the argument becomes

L ⊆ E, u0 ∈
/ L ` u0 ∈
/E

9
for some u0 ∈ U . With the choice L = {a, b, c, d} , E = {a, b, c, d, e} and u0 =
e we find the premises are true while the conclusion is false. Hence the
argument is invalid.
*Example C Is ∃x : px ∧ qx, ∀x : px → rx ` ∃x : rx ∧ (¬qx) valid or
invalid?
So with U and P, Q, R ⊆ U to be chosen we inteprete px as p ∈ P , qx as
q ∈ Q and rx as r ∈ R. This time ∃x : px ∧ qx means there exists u ∈ U such
that u ∈ P and u ∈ Q. In particular, P ∩ Q is non-empty, i.e. P ∩ Q 6= ∅.
So the argument becomes

P ∩ Q 6= ∅, P ⊆ R ` R ∩ Qc 6= ∅.
The choice of U = {1, 2, 3} , P = {1} , Q = {1, 2} and R = {1} is an
instance where the premises are true but the conclusion false. Hence the
argument is invalid.

10