Logic: Quantifiers – Foundations of Mathematics

Some sentences feel an awful lot like statements but aren't. For example,

$n$ is even

This is not a statement because it doesn't have a truth value; unless we know what $n$ is, we can't really do much.

Definition. A sentence with one or more variables, so that supplying values for the variables yields a statement, is called an open sentence.

You can think of an open sentence as a function whose values are statements. In fact we will use function notation to name open sentences.

$S(n)=$ n is even

Just as with ordinary functions, this notation works by substitution. With $S(n)$ defined as above,

$S(3)=$ 3 is even

which happens to be a false statement. $S(14)$ , on the other hand, is a true statement.

Along with an open sentence, we have to provide some kind of indication of what sort of thing the variable might be. For our example $S(n)$ , it makes most sense to let $n$ be a natural number or possibly an integer. We call possible values for the variable of an open sentence the universe of that sentence.

One thing that cannot be emphasized enough is that variables can represent any type of thing, not just numbers or other mathematical objects. So we could think about the open sentence

$A(r,t)=$ r is t years old

and say that the universe for $r$ is everyone in your section of MA 225 and the universe for $t$ is any whole number between 15 and 60.

Definition. Given an open sentence with one variable $S(x)$ , the statement $\forall x, S(x)$ is true when, no matter what value of $x$ we use, $S(x)$ is true; otherwise $\forall x, S(x)$ is false.
Given an open sentence with one variable $S(x)$ , the statement $\exists x: S(x)$ is true when there is some value of $x$ for which $S(x)$ is true; otherwise $\exists x:S(x)$ is false.

Terminology. We call $\forall$ the universal quantifier, and we read $\forall x, S(x)$ for all $x$ , $S(x)$ . We call $\exists$ the existential quantifier, and we read $\exists x:S(x)$ there exists $x$ such that $S(x)$ .

Observe that if there are only two possible values in the universe for $S(x)$ (let's call them $\alpha$ and $\beta$ ), then $\forall x,S(x)$ is true when both $S(\alpha)$ and $S(\beta)$ are true. But this is the same as $S(\alpha)\wedge S(\beta)$ being true. Similarly, $\exists x:S(x)$ is true when one of $S(\alpha)$ or $S(\beta)$ is true. But this is the same as $S(\alpha)\vee S(\beta)$ . So we see that the quantifiers are in some sense a generalization of $\vee$ and $\wedge$ . So the following makes sense:

De Morgan's Laws, quantifier version: For any open sentence $S(x)$ with variable $x$ ,

$\sim \left[\forall x,S(x)\right] \equiv \exists x:\left[\sim S(x)\right]$
$\sim \left[\exists x:S(x)\right] \equiv \forall x,\left[\sim S(x)\right]$

For example, a denial of the statement

There is a china teapot floating halfway between the earth and the sun.

Every china teapot is not floating halfway between the earth and the sun.

the universal quantifier, conditionals, and the universe

Quantifiers are most interesting when they interact with other logical connectives. For example, consider the following (true) statement:

Every multiple of $4$ is even.

We could choose to take our universe to be all multiples of $4$ , and consider the open sentence

$E(n)=$ n is even

and translate the statement as $\forall n,E(n)$ . But that isn't very interesting. A much more natural universe for the sentence $n$ is even is the integers. But then we have to do something clever, because if our universe for $n$ is the integers, then $\forall n,E(n)$ is false. The solution is to create another open sentence

$F(k)=$ k is a multiple of 4

How do we use $F$ and $E$ to translate our true statement? We can think of an open sentence as a test--if we plug in a value for its variable(s), we see whether that variable passes the test. Here we have two tests: $E$ , a test for evenness, and $F$ , a test for multiple-of- $4$ -ness. The statement we are trying to translate says that passing the $F$ test is enough to guarantee passing the $E$ test. That sounds like a conditional. Indeed the correct translation for Every multiple of $4$ is even is:

$\forall n,F(n)\Rightarrow E(n)$

Try translating this statement back into English using some of the various translations for $\Rightarrow$ to see that it really does mean the same thing as Every multiple of $4$ is even.

Exercise. Translate $\forall n, F(n)\wedge E(n)$ and $\forall n, F(n)\vee E(n)$ into English into English. Explain why these are false statements. Assume the universe for both $E$ and $F$ is the integers.

In fact, we can always expand the universe by putting in another conditional. If we let $Z(s)$ be the sentence $s$ is an integer and expand our universe to include all mathematical objects encountered in this course, we could translate Every multiple of 4 is even as $\forall s, \left(Z(s)\Rightarrow\left(F(s)\Rightarrow E(s)\right)\right)$ .

A Note about Notation. It's important to keep in mind that, just as for the functions you've encountered in calculus and before, the particular symbol we use for a variable is not relevant to the meaning of that variable. The statements

$\begin{equation*} \forall s,\left(Z(s)\Rightarrow\left(F(s)\Rightarrow E(s)\right)\right) \end{equation*}$

and

$\begin{equation*} \forall p,\left(Z(p)\Rightarrow\left(F(p)\Rightarrow E(p)\right)\right) \end{equation*}$

both say the same thing. namely, Every integer which is a multiple of 4 is even. The fact that we called the variable $s$ when we defined $Z$ and $n$ when we defined $E$ does not require us to always use those variables. Notice that in the English translation, no variables appear at all! We could equally well have written

$\begin{equation*} \forall \odot, \left(Z(\odot)\Rightarrow\left(F(\odot)\Rightarrow E(\odot)\right)\right) \end{equation*}$

except that that's a bit difficult to pronounce.

The existential quantifier and the universe

We just saw that generally speaking, a universal quantifier should be followed by a conditional. What should an existential quantifier be followed by? Consider the following true statement

There is a multiple of $7$ which is even.

How can we represent this symbolically? We could take the universe to be all multiples of $7$ and write $\exists n: E(n)$ . But as before, that's not very interesting. So let's keep our universe as it should be: the integers. As before, we'll need a test for multiple-of- $7$ -ness: denote by $S(k)$ the sentence $k$ is a multiple of $7$ .

Now think about what the statement There is a multiple of $7$ which is even means. What is the relationship between multiple-of- $7$ -ness and evenness? Just that some number happens to be both. Therefore we can translate:

$\exists n: S(n)\wedge E(n)$

Notice that because $\wedge$ is commutative, our symbolic statement is equivalent to $\exists n:E(n)\wedge S(n)$ . But this is just fine, because our statement and the statement

There is an even number which is a multiple of $7$

pretty clearly mean the same thing.

Let's lock in the connection between $\exists$ and $\wedge$ with another example. This time we'll use De Morgan's laws and consider the statement

Every multiple of $7$ is even.

which happens to be false. Therefore its negation is true. We compute that negation:

$\begin{equation*} \begin{aligned} \sim\left[\forall n,\left(S(n)\Rightarrow E(n)\right)\right]&\equiv \exists n:\sim\left(S(n)\Rightarrow E(n)\right)\\ &\equiv \exists n:\left(S(n)\wedge \sim E(n)\right) \end{aligned} \end{equation*}$

which we could phrase in English as There is an integer which is a multiple of $7$ and not even. Thus we see that the existential quantifier pairs naturally with the connective $\wedge$ .

Exercise. Let $E(k)$ stand for $k$ is even, $S(p)$ stand for $p$ is a multiple of $7$ , and $Z(m)$ stand for $m$ is an integer. Let the universe for all three sentences be the set of all mathematical objects encountered in this course. Write a symbolic translation of There is a multiple of $7$ which is even using these open sentences.

Exercise. Translate $\exists n: S(n)\Rightarrow E(n)$ into English. Explain why this is a true statement. Give a useful denial. Assume the universe for both $E$ and $S$ is the integers.

quantifier order

Many interesting open sentences have more than one variable, such as:

$A(r,t)$ = $r$ is $t$ years old

Since there are two variables, we are entitled to ask the question which one? twice. And we may have a different answer each time. There are eight possibilities, of which four are

$\forall r,\forall t, A(r,t)$ For any person $r$ , for any age $t$ , that person is that age.
$\forall t,\forall r, A(r,t)$ For any age $t$ , for any person $r$ , that person is that age.
$\exists r: \exists t: A(r,t)$ There is a person $r$ who is some age $t$ .
$\exists t: \exists r: A(r,t)$ There is an age $t$ so that some person $r$ is that age.

A moment's thought should make clear that statements 1 and 2 mean the same thing (in our universe, both are false), and statements 3 and 4 mean the same thing (in our universe, both are true if woefully uninformative). This says that we can move existential quantifiers past one another, and move universal quantifiers past one another.

The other four possibilities are

$\forall r,\exists t: A(r,t)$ For any person $r$ , there is an age $t$ so that that person is that age.
$\exists t: \forall r, A(r,t)$ There is an age $t$ so that every person $r$ is that age.
$\forall t,\exists r: A(r,t)$ For any age $t$ , there is a person who is that age.
$\exists r: \forall t, A(r,t)$ There is a person $r$ who is every age.

Notice that statement 5 is true (in our universe): everyone has an age. But statement 6 says that everyone is the same age, which is false in our universe. So statement 5 and statement 6 mean different things. Similarly, statement 7 is likely true in our universe, whereas statement 8 is false. The lesson is that quantifiers of different flavors do not commute!