Quantifiers

Section 2.2 Quantifiers

As we move into proving mathematical statements, we need to better understand the statements themselves. In your previous work with mathematics, you've often used variables and equations.

Think of some examples of variables you've seen in other math classes. What do these variables represent? Probably, the first example that comes to mind is something from an algebra class, such as \(y=x^2\) or \(f(x)=3x+2\text{.}\) You may also think of examples such as solving for \(x\) in an expression such as \(x^2=4\text{.}\) We use variables in mathematical statements to represent quantities that can vary. But we also use them to be more precise. Think of how much more confusing the first statement would be if we had to write it as "a number squared equals another number;" or the second statement, "the function which multiplies a number by 3 and adds 2." When you first learned varables, you probably WERE introduced to them in terms of sentences, but eventually, you got used to what the symbols mean.

In this class, we will rarely be interested in mathematical equations. We want to move to the common format of mathematical statements often found when describing mathematical defintions or theorems.

Common forms of mathematical statements:

Universal Statements.
We use these statements when a property is true for all things in a set.

Example: Every math student takes Calculus.
Conditional Statements.
These statements usually have the form “if...then...”.

Example: If a student majors in Computer Science, then she takes Discrete Math.
Existential Statements.
We use these statements when somthing exists with a particular property.

Example: There exists a Linfield class that meets at 9am on Mondays.

Many mathematical statements use variables. For example, \(x+3/2=4\) is not a statement since it has no truth value. However, if we say, “there exists \(x\) such that \(x+3/2=4\)” or “for all \(x\text{,}\) \(x+3/2=4\)”, and we know what set \(x\) belongs to, then we can decide whether these statements are true or false.

Activity 2.2.1. Each Type.

Give an additional example of each type of statement.

Subsection 2.2.1 Quantified Statements

We want to be able to work with generic statements, like \(p\) and \(q\text{,}\) but also with variables. So instead of \(p\text{,}\) we will use \(P(x)\text{.}\) An expression, \(P(x)\text{,}\) represents some property or expression about \(x\text{.}\) We call \(P(x)\) the predicate.

Example 2.2.1. Statements with Variables.

Let \(D=\mathbb{Z}\text{.}\) Determine whether the statement “for all \(x\in D\text{,}\) \(x+3/2=4\)” is true or false.

Answer 1.

Since \(x=5/2\) is the only value satisfying the equation, certainly every integer does not satisfy the equation. The statement is false.

Let \(D=\mathbb{R}\text{.}\) Determine whether the statement “for all \(x\in D\text{,}\) \(x+3/2=4\)” is true or false.

Answer 2.

Since \(x=5/2\) is the only value satisfying the equation, certainly every real number does not satisfy the equation. The statement is false.

Let \(D=\{5/2\}\text{.}\) Determine whether the statement “for all \(x\in D\text{,}\) \(x+3/2=4\)” is true or false.

Answer 3.

Since \(x=5/2\) satisfies the equation, and is the only value in \(D\text{,}\) the statement is true.

In these examples, \(P(x)\) is \(x+3/2=4\text{.}\)

Our properties don't just need to be mathematical, though. For example we could have a predicate such as \(P(x)\) is “\(x\) is a math major.” In this case the set of possible values for \(x\) could be the set of students at Linfield, or the set of students in Introduction to Proofs. As we saw in Example 2.2.1, it is important that we define our set of interest, as changing the set can change whether the statement is true or false.

Notation for Quantifiers.

Universal Quantifier.
\(\forall\), read as “for all” or “for every.”
Existential Quantifier.
\(\exists\), read as “there exists” or “for some.”

A universal statement has the form \(\forall x\in D, P(x)\text{.}\)

To show a universal statement is true, you need to show all values in \(D\) make \(P(x)\) true. If your set is small, you can do this just by showing \(P(x)\) is true for each \(x\text{.}\) If \(D\) is infinite, however, we will need more general techniques.

To show a universal statement is false, you just need to find one value in \(D\) which makes \(P(x)\) false.

An existential statement has the form \(\exists x\in D, P(x)\text{.}\)

To show an existential statement is true, you just need to find one value in \(D\) which makes \(P(x)\) true.

To show an existential statement is false, you need to show all values in \(D\) make \(P(x)\) false, or no values make it true. If your set is small, you can do this just by showing \(P(x)\) is false for each \(x\text{.}\) If \(D\) is infinite, however, we will need more general techniques.

Activity 2.2.2. True Existential.

Show the following statement is true: \(\exists x\in \mathbb{R}, 2x^2+1=5\text{.}\)

Activity 2.2.3. False Existential.

Show the following statement is false: \(\exists x\in \mathbb{Z}, 3x+5=6\text{.}\)

Activity 2.2.4. True Universal.

Let \(D=\{2, 3, 4, 5\}\text{.}\) Show the following statement is true: \(\forall x\in {D}, x^2>2\text{.}\)

Activity 2.2.5. False Existential.

Let \(D=\{2, 3, 4, 5\}\text{.}\) Show the following statement is false: \(\forall x\in D, x^2 < 20\text{.}\)

Example 2.2.2. Translating Statements.

Translate the statement using quantifiers and variables, “All positive real numbers have square roots greater than zero.”

Answer 1.

\(\forall x\in \mathbb{R}^+, \sqrt{x}>0.\)

Translate the statement using quantifiers and variables, “Nobody's perfect.”

Answer 2.

\(\forall x\in \{\textrm{people}\}, x\) is not perfect.

Activity 2.2.6. Translating a Statement.

Write the following statement formally using quantifiers and variables: Every differentiable function is continuous.

Activity 2.2.7. More Translation.

Write the following statements formally using quantifiers and variables.

(a)

Some even integers are negative.

(b)

Everyone makes mistakes.

(c)

Someone will get an A.

Subsection 2.2.2 Negating Quantified Statements

In this section we will look at how to negate statements involving quantifiers.

Negations of Quantified Statements.

The negation of \(\forall x\in D, P(x)\) is \(\exists x\in D, \neg P(x)\text{;}\) or

\begin{equation*} \neg(\forall x\in D, P(x))\equiv \exists x\in D, \neg P(x). \end{equation*}
The negation of \(\exists x\in D, P(x)\) is \(\forall x\in D, \neg P(x)\text{;}\) or

\begin{equation*} \neg(\exists x\in D, P(x))\equiv \forall x\in D, \neg P(x). \end{equation*}

We can think of negation as switching the quantifier and negating \(P(x)\text{,}\) but it will be really helpful if we can understand WHY this is the negation. Thinking about negating a “for all” statement, we need the statement to not be true for all things, which means it must be false for something, Thus, there exists something making \(\neg P(x)\) true. Thinking about negating a “there exists” statement, we need there not to exist anything making \(P(x)\) true, which means \(P(x)\) must be false for everything. Thus, everything makes \(\neg P(x)\) true.

Example 2.2.3. Negating a Quantified Statement.

Negate the statement: For all primes \(p\text{,}\) \(p\) is odd. Is this statement true or false?

Answer 1.

There exist a prime \(p\) such that \(p\) is not odd. The original statement is false, since we can find an even prime (\(p=2\)).

Negate the statement: There exists a real number \(x\text{,}\) such that \(x^2< 0\text{.}\) Is this statement true or false?

Answer 2.

For all real numbers \(x\text{,}\) \(x^2\geq 0\text{.}\) The original statement is false, since the negation is true.

Activity 2.2.8. Writing Negations.

Write the negation of the following statements (in English).

(a)

For all integers \(n\text{,}\) \(\sqrt{n}\) is an integer.

(b)

There exists an integer \(n\text{,}\) such that \(n^2=5\text{.}\)

Many of our quantified statements may have predicates involving other logical connectives. So it is going to be important to remember how to negate "and"s, "or"s, and "if...then"s.

Reminder, keep in mind the rules we saw in Section 1.3 for negating logical statements.

Useful Negation Rules.

AND statements.
\(\neg(p\wedge q)\equiv \neg p\ \vee \neg q\text{.}\) This is DeMorgan's Law.
OR statements.
\(\neg(p\vee q)\equiv \neg p\ \wedge \neg q\text{.}\) This is DeMorgan's Law.
IF...THEN statements.
\(\neg(p\rightarrow q)\equiv p\ \wedge \neg q\text{.}\) The negation of a conditional is NOT a conditional.

Activity 2.2.9. More Writing Negations.

Write the negation of the following statements (in English).

(a)

There exists an integer \(n\text{,}\) such that \(1 < n < 2\text{.}\)

(b)

For all real numbers \(x\text{,}\) if \(x>2\) then \(x+5>7\text{.}\)

(c)

For all functions \(f\text{,}\) if \(f\) is continuous, then \(f\) is differentiable.

The relationship between “for all” and “there exists” can be used to show some surprising things. In particular, what happens if our domain, \(D\text{,}\) has nothing in it? Let \(D=\emptyset\text{,}\) the empty set. Is \(\forall x\in D, P(x)\) true or false? Well, let's look at the negation: \(\exists x\in D, \neg P(x)\text{.}\) Now the negation MUST be false since \(D\) has nothing in it, so there can't exist something in \(D\) making \(\neg P(x)\) true. Since the negation is false, the original statement is true! We say \(\forall x\in D, P(x)\) is vacuously true.

Example 2.2.4. Vacuously True Statement.

Consider the statement “For all turtles, \(T\text{,}\) in Intro to Proofs, \(T\) is getting an A.” The negation is “There exists a turtle, \(T\text{,}\) in Intro to Proofs, such that \(T\) is not getting an A.” Since no such turtle exists, the negation is false. Making the original true. So every turtle in Intro to Proofs is getting an A.

As one additional note, it can be helpful in deciding if your negation is correct to find the truth value of both the original and the negation. They should have opposite values. Similarly, if you need to determine the truth value of a complex statement, it might be easier to find the truth value of the negation.

Activity 2.2.10. True or False.

Determine if each of the following statements are true or false. It may be helpful to look at the negations you founds in the above activities, Activity 2.2.8, Activity 2.2.9, Activity 2.3.8, and Activity 2.3.9.

(a)

For all integers \(n\text{,}\) \(\sqrt{n}\) is an integer.

(b)

There exists an integer \(n\text{,}\) such that \(n^2=5\text{.}\)

(c)

There exists an integer \(n\text{,}\) such that \(1 < n < 2\text{.}\)

(d)

For all real numbers \(x\text{,}\) if \(x>2\) then \(x+5>7\text{.}\)

(e)

For all functions \(f\text{,}\) if \(f\) is continuous, then \(f\) is differentiable.

(f)

For all real numbers \(x\text{,}\) if \((x+1)(x-2)>0\) then \(x < -1\) or \(x>2\text{.}\)

(g)

For all integers \(n\text{,}\) if \(n\) has a factor of 15, then \(n\) has a factor of 3 and \(n\) has a factor of 5.

Subsection 2.2.3 Multiple Quantifiers

Many statements in mathematics involve multple quantifiers. For example, “For all real numbers \(x\text{,}\) there exists a real number \(y\) with \(x+y=0\text{.}\)” These statements, though frequent in math courses, represent some of the most complicated types of statements to understand. In this section we will try to understand the general structure of such statements.

Let's look at the various ways we could have statements with two quantifiers. Since we have two quantifiers, we will have two variables. Thus, our predicate will now involve both variables. We can use the notation \(P(x, y)\) to mean a statement about \(x\) and \(y\text{.}\)

\(\forall x\in D, \exists y\in E, P(x, y)\text{.}\)

This means we can find a \(y\) in \(E\) that makes \(P(x, y)\) true for each \(x\) in \(D\text{.}\) In such statements \(y\) will often depend on \(x\text{.}\)
\(\exists x\in D, \forall y\in E, P(x, y)\text{.}\)

The order of the quantifiers matters. This means we can find a SINGLE \(x\) in \(D\) that makes \(P(x, y)\) true for every \(y\) in \(E\text{.}\) In such statements \(x\) does not depend on \(y\text{.}\) The same \(x\) must work for all the \(y\)'s.
\(\forall x\in D, \forall y\in E, P(x, y)\text{.}\)

This means \(P(x, y)\) is true for all \(x\in D\) and for all \(y\in E\text{.}\)
\(\exists x\in D, \exists y\in E, P(x, y)\text{.}\)

This means \(P(x, y)\) is true for for at least one \(x\in D\) and at least one \(y\in E\text{.}\)

Example 2.2.5. Statements with Multiple Quantifiers.

Let \(x, y\in\mathbb{R}\text{.}\) Determine whether the following statements are true or false.

\begin{equation*} \forall x, \exists y, x+y=5. \end{equation*}

For any \(x\) can you always find a corresponding \(y\) with \(x+y=5\text{?}\)
Answer.
Yes, for each \(x\) let \(y=5-x\text{.}\) So the statement is true.
\begin{equation*} \exists x, \forall y, x+y=5. \end{equation*}

Is there a single \(x\) that works for all \(y\text{?}\)
Answer.
No, no single \(x\) will always have \(x+y=5\text{.}\) So the statement is false.

Activity 2.2.11.

Let \(x, y\in \mathbb{Z}^{nonneg}\text{.}\) Determine if each statement is true or false. Give a reason for your answer.

(a)

\(\forall x\ \exists y, x < y\text{.}\)

(b)

\(\exists y\ \forall x, x < y\text{.}\)

(c)

\(\exists x\ \forall y, x < y\text{.}\)

(d)

\(\forall y\ \exists x, x < y\text{.}\)

(e)

\(\exists x\ \exists y, x < y\text{.}\)

(f)

\(\forall x\ \forall y, x < y\text{.}\)

Although we won't study the mathematical context of the following example in this class, it is a classic example in mathematics of a statement with multiple quantifiers and a conditional. It is so important that it is the subject of one set of math bike racks in front of Taylor Hall!

Example 2.2.6. Definition of a Limit.

The definition of the limit of a function: For every \(\epsilon>0\text{,}\) there exists a \(\delta>0\) such that if \(|x-a|<\delta\) then \(|f(x)-L|<\epsilon\text{.}\) Or in symbols,

\begin{equation*} \forall\epsilon>0, \exists\delta>0, |x-a|<\delta\rightarrow |f(x)-L|<\epsilon\text{.} \end{equation*}

Now, we want to be able to negate statements with multiple quantifiers. There is nothing really new here, we just negate our quantified statements as we did for single quantifiers.

Negating Statements with Multiple Quantifiers:.

The negation of \(\forall x\in D, \exists y\in E, P(x, y)\) is \(\exists x\in D, \forall y\in E, \neg P(x, y)\text{;}\)or

\begin{equation*} \neg(\forall x\in D, \exists y\in E, P(x, y))\equiv \exists x\in D, \forall y\in E, \neg P(x, y). \end{equation*}
The negation of \(\exists x\in D, \forall y\in E, P(x, y)\) is \(\forall x\in D, \exists y\in E, \neg P(x, y)\text{;}\) or

\begin{equation*} \neg(\exists x\in D, \forall y\in E, P(x, y))\equiv \forall x\in D, \exists y\in E, \neg P(x, y). \end{equation*}
The negation of \(\forall x\in D, \forall y\in E, P(x, y)\) is \(\exists x\in D, \exists y\in E, \neg P(x, y)\text{;}\) or

\begin{equation*} \neg(\forall x\in D, \forall y\in E, P(x, y))\equiv \exists x\in D, \exists y\in E, \neg P(x, y). \end{equation*}
The negation of \(\exists x\in D, \exists y\in E, P(x, y)\) is \(\forall x\in D, \forall y\in E, \neg P(x, y)\text{;}\) or

\begin{equation*} \neg(\exists x\in D, \exists y\in E, P(x, y))\equiv \forall x\in D, \forall y\in E, \neg P(x, y). \end{equation*}

Example 2.2.7. Negating the Definition of a Limit.

If you take Elementary Analysis, you will need to be able to negate the definition of the limit from Example 2.2.6. Negate “For every \(\epsilon>0\text{,}\) there exists a \(\delta>0\) such that if \(|x-a|<\delta\) then \(|f(x)-L|<\epsilon\)”. Our statement has the form \(\forall \epsilon, \exists \delta, P(\delta)\rightarrow Q(\epsilon)\text{,}\) so the negation has the form \(\exists \epsilon, \forall \delta, P(\delta)\wedge \neg Q(\epsilon).\)

Answer.

\(\exists\epsilon>0, \forall\delta>0, |x-a|<\delta\wedge |f(x)-L|\geq\epsilon\text{.}\)

Activity 2.2.12. Negating Statements with Multiple Quantifiers.

Write the negation of the following statements. Then determine whether the original statment is true or false.

(a)

There exists an integer \(n\) such that for all integers \(m,\ nm=0\text{.}\)

(b)

For every integer \(n\) there exists an integer \(m\) such that \(nm=0\text{.}\)

(c)

There exists an integer \(n\) such that for all integers \(m,\ n+m=0\text{.}\)

(d)

For every integer \(n\) there exists an integer \(m\) such that \(n+m=0\text{.}\)

Example 2.2.8. Translating Statements with Multiple Quantifiers.

Let \(L(x, y)\) be “\(x\) loves \(y\)”. Translate each of the following statements using quantifiers and variables.

Someone loves everyone.

Answer 1.

\(\exists x, \forall y, L(x, y).\)

Someone is loved by everyone.

Answer 2.

\(\exists x, \forall y, L(y, x).\)

Everyone loves someone.

Answer 3.

\(\forall x, \exists y, L(x, y).\)

Everyone is loved by someone.

Answer 4.

\(\forall x, \exists y, L(y, x).\)

Exercises Exercises

1.

Give an example to show the following statement is false.

\begin{equation*} \forall a \in \mathbb{Z}, (a-1)/a \text{ is not an integer.} \end{equation*}

2.

Give an example to show the following statement is false.

\begin{equation*} \forall a \text{ real numbers } x \text{ and } y, \sqrt{x+y}=\sqrt{x}+\sqrt{y} \end{equation*}

3.

Consider the statement

\begin{equation*} \exists x\in \mathbb{R} \text{ such that } x^2=2. \end{equation*}

Which of the following are equivalent ways of expressing this statement?

There is at least one real number whose square is 2.
The square of each real number is 2.
Some real numbers have square 2.
The number \(x\) has square 2, for some real number \(x\text{.}\)
If \(x\) is a real number, then \(x^2=2\text{.}\)
Some real number has square 2.

4.

Consider the statement

\begin{equation*} \forall n\in \mathbb{Z} \text{ if } n^2 \text{ is even then } n \text{ is even}. \end{equation*}

Which of the following are equivalent ways of expressing this statement?

If the square of an integer is even, then that integer is even
All integers have even squares and are even.
Given any integer whose square is even, that integer is itself even.
For all integers, there are some whose square is even.
Any integer with an even square is even.
All even integers have even squares.

5.

Rewrite the following statements using the form “\(\forall\)____\(x\text{,}\)____.”

Every real number is positive, negative, or zero.
No irrational numbers are integers.

6.

Rewrite the statement in English without using the symbols \(\forall\) or \(\exists\text{.}\) Express your answer as simply as possible. Then write a negation for the statement. Determine which statement is true, the original or the negation.

\(\exists\) a book \(b\text{,}\) \(\forall\) people \(p\text{,}\) \(p\) has read \(b\text{.}\)
\(\forall\) odd integers \(n\text{,}\) \(\exists\) an integer \(k\) such that \(n=2k+1\text{.}\)
\(\forall r \in \mathbb{Q}\text{,}\) \(\exists\) integers \(a\) and \(b\) such that \(r=a/b\text{.}\)
\(\forall x \in \mathbb{R}\text{,}\) \(\exists y\in \mathbb{R}\) such that \(x+y=0\text{.}\)
\(\exists x \in \mathbb{R}\text{,}\) \(\forall y\in \mathbb{R}\text{,}\) \(x+y=0\text{.}\)

7.

Rewrite the statement formally using quantifiers and variables. Write the negation of the statement.

Everybody trusts somebody.
Somebody trusts everybody.
Any even integer equals twice some other integer.
The number of rows in any truth-table is \(2^n\) for some integer \(n\text{.}\)
There is a prime number between every integer and its double.

8.

For each statement write a new statement by interchanging the symbols \(\forall\) and \(\exists\text{.}\) Which is true– the given statement, the interchanged version, neither, or both?

\(\forall x\in \mathbb{R}\text{,}\) \(\exists y\in \mathbb{R}\) such that \(x<y\text{.}\)
\(\exists x\in \mathbb{R}\text{,}\) \(\forall y \in \mathbb{R}^-\) (the set of negative real numbers), \(x<y\text{.}\)

9.

Consider the following sequence of digits: 2300204. A person claims that all of the 1’s in the sequence are to the left of all of the 0’s in the sequence. Is this true? Justify your answer.

Hint.

Write the claim formally and write a formal negation for it. Is the negation true or false?