EF Predicates and quantifiers

Section 4.1 Predicates and quantifiers

We often let variables represent arbitrary mathematical objects. However, as we have seen, object variables or free variables (as opposed to statement variables) lead to problems in logic. For example, the phrase “

f

is a differentiable function” can only be determined to be true or false when

f

represents a specific function.

🔗

In this section, we deal with these problems by quantifying such free variables: restricting ourselves to discussing whether “statements” involving one or more free variables are always/sometimes/never true for objects of the type represented by the free variables.

🔗

predicate: 🔗
a statement whose truth value depends on one or more free variables
$A (x)$: 🔗
a predicate statement $A$ whose truth value depends on the free variable $x$
$A (x, y)$: 🔗
a predicate statement $A$ whose truth value depends on the free variables $x$ and $y$

🔗

Example 4.1.1.

🔗

🔗
Let $A (f)$ represent the phrase “ $f$ is differentiable”, a predicate statement in one free variable $f .$
🔗
Let $B (m, n)$ represent the phrase “ $m$ is greater than $n$ ”, a predicate statement in two free variables $m$ and $n .$

🔗

Note 4.1.2.

🔗

A predicate is not a logical statement unless all of its variables represent specific objects.

🔗

domain: 🔗
the type of object that a variable in a predicate represents

🔗

Example 4.1.3.

🔗

In Example 4.1.1, the domain of the variable

f

could be “functions of a single real variable”, and the domains of the variables

m

and

n

could both be “natural numbers” (i.e. whole, nonnegative numbers).

🔗

Note 4.1.4.

🔗

Usually the domain of a variable in a predicate is implicit and can be determined from the context of the statement. However, if we want to make the domain explicit we can prefix it to the variable. For example,

\begin{matrix} A (f) = “function f is differentiable”, \\ B (m, n) = “integer m is greater than integer n ”. \end{matrix}

🔗

We can turn a predicate into a logical statement by being more specific about which objects in their domains the variables represent. However, we often do not want to be too specific (or else we would usually not need variables).

🔗

Example 4.1.5.

🔗

The following sentences are logical statements, because their truth value can be determined.

🔗
“Every function $f$ is differentiable.”
🔗
“There exists an integer $m$ that $2$ divides.”

🔗

The first statement is false; for example, the function

f (x) = | x |

is not differentiable at

x = 0 .

The second statement is true; this statement basically says that even integers exist.

🔗

quantifier: 🔗
the sentence fragments “for every” and “there exists” quantify whether a predicate should apply to all or only some of the objects in the domain of one of its variables.
universal quantifier: 🔗
the quantifier “for every”
$\forall$: 🔗
symbol for the universal quantifier
existential quantifier: 🔗
the quantifier “there exists”
$\exists$: 🔗
symbol for the existential quantifier

🔗

Example 4.1.6.

🔗

As before, let

A (f)

represent the predicate “

f

is differentiable.” Then the statement

(\forall f) A (f)

is false, because not every function is differentiable. However, the statement

(\exists f) A (f)

is true — for example, polynomials are differentiable.

🔗

Warning 4.1.7.

🔗

For an existentially quantified statement to be true, it is not necessary for there to be one and only one object in the implied domain that satisfies the conditions of the predicate — there could be many such objects. So, just as you should always read a disjunction

p \lor q

as “p or q or both,” you should always read an existentially quantified statement

(\exists x) A (x)

as “there exists at least one

x

such that

A (x)

is true.”

🔗

Mathematical statements often involve several quantified variables.

🔗

Worked Example 4.1.8. Working with quantified statements of several variables.

🔗

Let

B (m, n)

represent “

m

divides

n

”, where

m

and

n

are positive whole numbers. Which of the following statements are true?

🔗
$(\forall m) (\forall n) B (m, n)$
🔗
$(\exists m) (\exists n) B (m, n)$
🔗
$(\forall m) (\exists n) B (m, n)$
🔗
$(\exists m) (\forall n) B (m, n)$
🔗
$(\forall n) (\exists m) B (m, n)$
🔗
$(\exists n) (\forall m) B (m, n)$

Solution.

False.
This statement says “for every $m$ and for every $n,$ $m$ divides $n .$ ” One example of values for $m$ and $n$ with $m$ not dividing $n$ (such as $m = 3$ and $n = 2$ ) suffices to show that it is not always true that one number $m$ divides another number $n .$
True.
This statement says “there exists $m$ such that there exists $n$ such that $m$ divides $n .$ ” To demonstrate that this statement is true, we have to explicitly show that at least one pair of values for $m$ and $n$ exists by giving an example (such as $m = n = 2$ ).
True.
This statement says “for every $m$ there exists an $n$ such that $m$ divides $n .$ ” To show that this statement is true, we have to provide, for every possible value of $m,$ a value of $n$ that works. When $m = 1,$ we have example $n = 1 .$ When $m = 2,$ we have example $n = 2 .$ When $m = 3,$ we have example $n = 3 .$ Similarly, for each value of $m,$ we can choose $n$ to be the same value as $m$ as an example.

Note.

If the domain for $m$ and $n$ included $0,$ then this third statement would actually be false, as demonstrated by the example $m = 0 .$
True.
This statement says “there exists $m$ such that for every $n$ we have $m$ divides $n .$ ” This is true, as the example $m = 1,$ which divides every number $n,$ demonstrates existence of this special $m$ (though it is the only example possible).
True.
This statement says “for every $n$ there exists an $m$ so that $m$ divides $n .$ ” Similarly to the justification for Statement 3, for every possible value of $n$ we need to provide an example $m$ so that $m$ divides $n,$ but this time it is the $n$ that is arbitrary and the $m$ that is to be the example. But again, every positive number divides itself, so we could always take $m$ to be the same value as $n$ as our example to demonstrate that such an $m$ exists. (Or, actually we could always choose $m = 1$ as the example for each different value of $n .$ )
False.
This statement says “there exists $n$ such that for every $m$ we have $m$ divides $n .$ ” However, there is no positive number that is divisible by every other positive number.

🔗

Warning 4.1.9.

🔗

While the order of two quantifiers of the same type does not matter (which is why we didn’t consider the statements with quantifiers in the order

(\forall n) (\forall m)

and

(\exists n) (\exists m)

in Worked Example 4.1.8 above), the order of a “mixed” pair of quantifiers matters! This is demonstrated by Statement 3 and Statement 6 in Worked Example 4.1.8 — both of these statements involve a

\forall m

and a

\exists n,

but in opposite orders. Since one of these two statements is true and one is false, they obviously cannot be the same statement.

🔗

Even more, the order of a “mixed” pair of quantifiers implies a dependence of the second quantified variable on the first.

🔗
If the statement $(\forall x) (\exists y) A (x, y)$ is true, it means that, corresponding to each and every object $x$ in the appropriate domain, there will exist at least one example of an object $y$ in the appropriate domain so that $A (x, y)$ is true. But the corresponding example $y$ could be different for different examples of the object $x .$
🔗
If the statement $(\exists y) (\forall x) A (x, y)$ is true, it means that there is at least one “special” example object $y$ that enjoys the property that $A (x, y)$ will be true for each and every object $x$ in the appropriate domain.

🔗

Example 4.1.10.

🔗

Suppose

A (x, y)

is a predicate statement, where

x

and

y

are variables that can only take on the values

0,

1,

2 .

Further suppose that it is known that

A (x, y)

is true in the specific instances

A (0, 1), A (1, 0), A (1, 1), A (1, 2), A (2, 2) .

🔗

Statement $(\forall x) (\exists y) A (x, y)$ is true because for each value of $x$ we can exhibit at least one value $y$ for which $A (x, y)$ is true:
- 🔗
  when $x = 0,$ we know $A (0, y)$ is true for at least one $y$ (for example, $y = 1$ );
- 🔗
  when $x = 1,$ we know $A (1, y)$ is true for at least one $y$ (for example, $y = 1$ ); and
- 🔗
  when $x = 2,$ we know $A (2, y)$ is true for at least one $y$ (for example, $y = 2$ ).
🔗
Statement $(\exists x) (\forall y) A (x, y)$ is true because we can exhibit at least one “special” value of $x$ for which $A (x, y)$ is true for each and every value of $y .$ In particular, we see that for $x = 1$ we have $A (1, y)$ true for each of $y = 0, 1, 2 .$

🔗

Remark 4.1.11.

🔗

Depending on grammar requirements or personal style, the quantifier “for every” might be expressed as “for all” or just “every” or “all”. The quantifier “there exists” can also be expressed as “some” or “there is at least one”, but remember that the reality of the situation could be “more than one.”

🔗

Warning 4.1.12.

🔗

Mathematicians are fond of using “any” or “for any” in place of “every” or “for every”.

🔗

Worked Example 4.1.13.

🔗

Prove that

n + 1

is an odd number for any even number

n .

Solution 1. (Incorrect)

It says to prove

n + 1

is odd for any even number

n,

so I will choose my favourite even number

n = 8 .

Then

8 + 1 = 9

is obviously odd.

Solution 2. (Correct)

The problem statement is really asking to prove that every even number has the property that the subsequent number is odd. So let

n

represent an arbitrary but unspecified even number. Then

n

is divisible by

2,

so there is some number

m

such that

n = 2 m .

Now,

n + 1 = 2 m + 1

is not divisible by

2,

since

(2 m + 1) / 2 = m + \frac{1}{2}

is not a whole number. Therefore,

n + 1

must be odd.

🔗

Note 4.1.14.

🔗

We will practice proving statements involving universally quantified predicates in Chapter 6.

Elementary Foundations: An introduction to topics in discrete mathematics

Search Results: