Home page for accesible maths 2 Logic 2.3 The logic model 3 Mathematical proofs

Style control - access keys in brackets

Font (2 3) - + Letter spacing (4 5) - + Word spacing (6 7) - + Line spacing (8 9) - +

2.4 Quantifiers

In this section we shall introduce two more symbols. Statements involving ‘‘for all’’ or ‘‘there exist(s)’’ are very common in mathematics; for example,

\text{for all}\ n\in\mathbb{N},\ n^{2}\in\mathbb{N}

(that is, the square of any natural number is a natural number — which is true), or

\text{there exists}\ x\in\mathbb{R}\ \text{such that}\ x^{2}+1=0

(that is, the equation $x^{2}+1=0$ has a real solution — which is false).

Notation 2.4.1

The universal quantifier $\forall$ means ‘‘for all’’; the existential quantifier $\exists$ means ‘‘there exist(s)’’.

Example 2.4.2

In this notation, the two statements above could be written

(\forall n\in\mathbb{N})(n^{2}\in\mathbb{N})\qquad\text{and}\qquad(\exists\,x% \in\mathbb{R})(x^{2}+1=0),

respectively.

Remark 2.4.3

(i)

The symbol $\forall$ (an upside-down letter ‘‘A’’) is suggested by the word ‘‘all’’, while the symbol $\exists$ (a back-to-front letter ‘‘E’’) refers to the word ‘‘exists’’.
(ii)

$\forall$ may also be read ‘‘for every’’ or ‘‘for each’’, while $\exists$ may alternatively be read ‘‘there is/are’’, ‘‘for some’’ or ‘‘for at least one’’.

Example 2.4.4

(i)

The statement ‘‘for every pair of integers, their product is positive’’ can be written

$(\forall m\in\mathbb{Z})(\forall n\in\mathbb{Z})(mn>0).$

This statement is false because $0\cdot 0=0$ is not positive.
(ii)

The statement ‘‘There exists a natural number whose square root is greater than five’’ can be written

$(\exists\,n\in\mathbb{N})(\sqrt{n}>5),$

and this statement is true because $\sqrt{36}=6>5.$
(iii)

The statement ‘‘for every non-zero rational number $r$ , there is a rational number $s$ such that $rs=1$ ’’ can be written

$(\forall r\in\mathbb{Q}\setminus\{0\})(\exists\,s\in\mathbb{Q})(rs=1),$

and this statement is true.
(iv)

The statement ‘‘there is a rational number which is greater than every natural number’’ can be written

$(\exists\,r\in\mathbb{Q})(\forall n\in\mathbb{N})(r>n),$

and this statement is false (as we shall explain in Example 3.4.1 below).

Remark 2.4.5

(i)

In English, the phrase ‘‘there exist(s)’’ is almost always followed by ‘‘… such that’’, which does not appear in the symbolic version.
(ii)

In English, a statement like ‘‘some politicians are honest’’ may carry the suggestion that others are not. In mathematics, however, there are no such subtle nuances about statements of this form. For instance, the statement

$(\exists\,x\in P)(x\in H)$

(where $P=\{\text{politicians}\}$ and $H=\{\text{honest people}\}$ ) carries no such overtones; all it asserts is the existence of (at least) one honest politician.

Sometimes mathematical statements that do not explicitly use the words ‘‘for all’’ or ‘‘there exist(s)’’ (or their equivalents) may be recast as statements involving quantifiers, as the following example shows.

Example 2.4.6

(i)

We may express the statement ‘‘ $A\cap B\neq\emptyset$ ’’ as

$(\exists\,x\in A)(x\in B).$
(ii)

The statement ‘‘ $\sqrt{2}$ is a rational number’’ (or, in symbols, ‘‘ $\sqrt{2}\in\mathbb{Q}$ ’’) may be written

$(\exists\,a\in\mathbb{Z})\bigl(\exists\,b\in\mathbb{Z}\setminus\{0\}\bigr)% \biggl(\sqrt{2}=\frac{a}{b}\biggr).$

(We shall soon see that this is false).

(iii)

We may express the statement ‘‘every integer greater than $1$ can be written as a product of primes’’ as

(\forall n\in\{2,3,4,\ldots\})(\exists\,m\in\mathbb{N})(\exists\,p_{1}\in% \mathbb{P})(\exists\,p_{2}\in\mathbb{P})\ldots(\exists\,p_{m}\in\mathbb{P})\\ (n=p_{1}p_{2}\cdots p_{m}),

where we have introduced the symbol $\mathbb{P}$ for the set of prime numbers. (You may know that this is true; we shall give a formal proof at the end of the course.)

In Examples 2.4.4(iii)–(iv) and 2.4.6(ii)–(iii), we used several quantifiers; statements involving two or more quantifiers are fairly common. If the quantifiers are all of the same type (that is, all ‘‘ $\forall$ ’’ or all ‘‘ $\exists$ ’’), then there is no difficulty, but if there is a mixture, then it is important to be careful about their order, as the following example shows.

Example 2.4.7

The statement

(\forall n\in\mathbb{N})(\exists\,m\in\mathbb{N})(m=n+1)

asserts that, for every natural number $n$ , there is a natural number $m$ which is exactly $1$ greater than $n$ (which is clearly true), whereas

(\exists\,m\in\mathbb{N})(\forall n\in\mathbb{N})(m=n+1)

states that there is a natural number $m$ which is exactly $1$ greater than every natural number $n$ (which is clearly false).

We conclude this section by considering how negation interacts with quantifiers. Often we may wish to negate a quantified statement. The simplest way to do this is just to put a ‘‘ $\neg$ ’’ at the beginning, but it is usually more informative to convert this into a positive statement.

Example 2.4.8

(i)

The negation of the statement ‘‘all cows eat grass’’ is

‘‘there is a cow which does not eat grass’’.

The negation must be a statement about cows, eating and grass!
(ii)

The negation of the statement ‘‘all students attended the workshop’’ is

‘‘somebody did not attend the workshop’’,

or in other words

‘‘at least one student did not attend the workshop’’.

In general, for a set $A$ and a statement $P(x)$ involving a variable $x$ ,

\framebox{$\neg\Bigl((\forall x\in A)\bigl(P(x)\bigr)\Bigr)\qquad\text{is % logically equivalent to}\qquad(\exists\,x\in A)\bigl(\neg P(x)\bigr).$}

Example 2.4.9

(i)

The negation of the statement ‘‘there is a lecturer who writes legibly’’ is

‘‘all lecturers write illegibly’’.
(ii)

The negation of the statement ‘‘someone failed the exam’’ is

‘‘nobody failed the exam’’

or in other words

‘‘everybody passed the exam’’.

In general, for a set $A$ and a statement $P(x)$ involving a variable $x$ ,

\neg\Bigl((\exists\,x\in A)\bigl(P(x)\bigr)\Bigr)\qquad\text{is logically % equivalent to}\qquad(\forall x\in A)\bigl(\neg P(x)\bigr).

To deal with statements involving multiple quantifiers, we work through each in turn.

Example 2.4.10

(i)

The statement

$\neg\bigl((\forall x\in\mathbb{R})(\exists\,y\in\mathbb{R})(x+y=0)\bigr)$

is logically equivalent to

$(\exists\,x\in\mathbb{R})\Bigl(\neg\bigl((\exists\,y\in\mathbb{R})(x+y=0)\bigr% )\Bigr)$

which in turn is logically equivalent to

$(\exists\,x\in\mathbb{R})(\forall y\in\mathbb{R})(x+y\neq 0).$
(ii)

Similarly, the statement

$\neg\bigl((\exists\,x\in\mathbb{Z})(\forall y\in\mathbb{Z})(xy=y)\bigr)$

is logically equivalent to

$(\forall x\in\mathbb{Z})\Bigl(\neg\bigl((\forall y\in\mathbb{Z})(xy=y)\bigr)\Bigr)$

which in turn is logically equivalent to

$(\forall x\in\mathbb{Z})(\exists\,y\in\mathbb{Z})(xy\neq y).$

For a case involving a compound statement at the end, we may use the logical equivalences established in the previous section.

Example 2.4.11

The statement

\neg\Bigl((\exists\,x\in\mathbb{R})\bigl((\sqrt{2}+x\in\mathbb{Q})\ \&\ (\sqrt% {2}-x\in\mathbb{Q})\bigr)\Bigr)

is logically equivalent to

(\forall x\in\mathbb{R})\Bigl(\neg\bigl((\sqrt{2}+x\in\mathbb{Q})\ \&\ (\sqrt{% 2}-x\in\mathbb{Q})\bigr)\Bigr),

which by Example 2.3.5 is logically equivalent to

(\forall x\in\mathbb{R})\bigl((\sqrt{2}+x\notin\mathbb{Q})\ \text{or}\ (\sqrt{% 2}-x\notin\mathbb{Q})\bigr).