# 2.7: Quantiﬁers

- Page ID
- 23241

## Propositional Function

The expression \[x>5\] is neither true nor false. In fact, we cannot even determine its truth value unless we know the value of \(x\). This is an example of a ** propositional function**, because it behaves like a function of \(x\), it becomes a proposition when a specific value is assigned to \(x\). Propositional functions are also called

**.**

*predicates*Example \(\PageIndex{1}\)

Denote the propositional function “\(x > 5\)” by \(p(x)\). We often write \[p(x): \quad x>5.\] It is not a proposition because its truth value is undecidable, but \(p(6)\), \(p(3)\) and \(p(-1)\) are propositions.

Example \(\PageIndex{2}\label{eg:quant-02}\)

Define \[q(x,y): \quad x+y=1.\] Which of the following are propositions; which are not?

- \(q(x,y)\)
- \(q(x,3)\)
- \(q(1,1)\)
- \(q(5,-4)\)

For those that are, determine their truth values.

**Answer**-
Both (a) and (b) are not propositions, because they contain at least one variable. Both (c) and (d) are propositions; \(q(1,1)\) is false, and \(q(5,-4)\) is true.

hands-on Exercise \(\PageIndex{1}\label{he:quant-01}\)

Determine the truth values of these statements, where \(q(x,y)\) is defined in Example \(\PageIndex{2}\).

- \(q(5,-7)\)
- \(q(-6,7)\)
- \(q(x+1,-x)\)

Although a propositional function is not a proposition, we can form a proposition by means of ** quantification**. The idea is to specify whether the propositional function is true for all or for some values that the underlying variables can take on.

## Universal Quantifier

Definition

The ** universal quantification** of \(p(x)\) is the proposition in any of the following forms:

- \(p(x)\) is true for all values of \(x\).
- For all \(x\), \(p(x)\).
- For each \(x\), \(p(x)\).
- For every \(x\), \(p(x)\).
- Given any \(x\), \(p(x)\).

All of them are symbolically denoted by \[\forall x \, p(x),\] which is pronounced as

“for all \(x\), \(p(x)\)”.

The symbol \(\forall\) is called the ** universal quantifier**, and can be extended to several variables.

Example \(\PageIndex{3}\label{eg:quant-03}\)

The statement

“For any real number \(x\), we always have \(x^2\geq0\)”

is true. Symbolically, we can write

\[\forall x \in \mathbb{R} \, (x^2 \geq 0), \qquad\mbox{or}\qquad \forall x \, (x \in \mathbb{R} \Rightarrow x^2 \geq 0).\label{eg:forallx}\]

The second form is a bit wordy, but could be useful in some situations.

Example \(\PageIndex{4}\label{eg:quant-04}\)

The statement \[\forall x\in\mathbb{R}\, (x > 5)\] is false because \(x\) is not always greater than 5. To disprove a claim, it suffices to provide only one counterexample. We can use \(x=4\) as a counterexample.

However, examples cannot be used to prove a universally quantified statement. Consider the statement \[\forall x\in\mathbb{R}\, (x^2\geq0).\] By direct calculations, one may demonstrate that \(x^2\geq0\) is true for many \(x\)-values. But it does not *prove* that it is true for *every* \(x\), because there may be a counterexample that we have not found yet. We have to use mathematical and logical argument to prove a statement of the form “\(\forall x \, p(x)\).”

Example \(\PageIndex{5}\label{eg:quant-05}\)

The statement

“Every Discrete Mathematics student has taken Calculus I and Calculus II”

is clearly a universally quantified proposition. To express it in a logical formula, we can use an implication: \[\forall x \, (x \mbox{ is a Discrete Mathematics student} \Rightarrow x \mbox{ has taken Calculus I and Calculus II})\] An alternative is to say \[\forall x \in S \, (x \mbox{ has taken Calculus I and Calculus II})\] where \(S\) represents the set of all Discrete Mathematics students. Although the second form looks simpler, we must define what \(S\) stands for.

## Existential Quantifier

Definition

The ** existential quantification** of \(p(x)\) takes one of these forms:

- There exists an \(x\) such that \(p(x)\).
- For some \(x\), \(p(x)\).
- There is some \(x\) such that \(p(x)\).

We write, in symbol, \[\exists x \, p(x),\] which is pronounced as

“There exists \(x\) such that \(p(x)\).”

The symbol \(\exists\) is called the ** existential quantifier**. It can be extended to several variables.

Notice the pronouciation includes the phrase "such that". Don't forget to say that phrase as part of the verbalization of a symbolic existential statement.

Example \(\PageIndex{6}\label{eg:quant-06}\)

To prove that a statement of the form “\(\exists x \, p(x)\)” is true, it suffices to find an example of \(x\) such that \(p(x)\) is true. Using this guideline, can you determine whether these two propositions

- \(\exists x\in\mathbb{R}\,(x>5)\)
- \(\exists x\in\mathbb{R}\,(\sqrt{x}=0)\)

are true?

**Answer**-
- True. For example: \(x=6\).
- True. For example: \(x=0\).

Example \(\PageIndex{7}\label{eg:quant-07}\)

The proposition

“There exists a prime number \(x\) such that \(x+2\) is also prime”

is true. We call such a pair of primes ** twin primes**.

hands-on Exercise \(\PageIndex{2}\label{he:quant-02}\)

Name a few more examples of twin primes.

Example \(\PageIndex{8}\label{eg:quant-08}\)

The proposition

“There exists a real number \(x\) such that \(x>5\)”

can be expressed, symbolically, as \[\exists x\in\mathbb{R}\, (x>5), \qquad\mbox{or}\qquad \exists x\, (x\in\mathbb{R}\, \wedge x>5).\] Notice that in an existential quantification, we use \(\wedge\) instead of \(\Rightarrow\) to specify that \(x\) is a real number.

hands-on Exercise \(\PageIndex{3}\label{he:quant-03}\)

Determine the truth value of each of the following propositions:

- For any prime number \(x\), the number \(x+1\) is composite.
- For any prime number \(x>2\), the number \(x+1\) is composite.
- There exists an integer \(k\) such that \(2k+1\) is even.
- For all integers \(k\), the integer \(2k\) is even.
- For any real number \(x\), if \(x^2\) is an integer, then \(x\) is also an integer.

hands-on Exercise \(\PageIndex{4}\label{he:quant-04}\)

The proposition

“The square of any real number is positive”

is a universal quantification

“For any real number \(x\), \(x^2>0\).”

Is it true or false?

## Negation with Quantifiers

To negate that a proposition always happens, is to say there exists an instance where it does not happen.

To negate that a proposition exists, is to say the proposition always does not happen.

Symbolically:

\(\overline {\forall x P(x)} \equiv \exists x \overline{P(x)}\)

and

\(\overline {\exists x P(x)} \equiv \forall x \overline{P(x)}\)

hands-on Exercise \(\PageIndex{5}\label{he:quant-06}\)

Negate the propositions in Hands-On Exercise \(\PageIndex{3}\)

Example \(\PageIndex{9}\label{eg:quant-12}\)

The statement

“All real numbers \(x\) satisfy \(x^2\geq0\)”

can be written as, symbolically, \(\forall x\in\mathbb{R} \, (x^2 \geq 0)\). Its negation is \(\exists x\in\mathbb{R} \, (x^2 < 0)\). In words, it says “There exists a real number \(x\) that satisfies \(x^2<0\).”

hands-on Exercise \(\PageIndex{6}\label{he:quant-07}\)

Negate the statement

“Every Discrete Mathematics student has taken Calculus I and Calculus II.”

## Summary and Review

- There are two ways to quantify a propositional function: universal quantification and existential quantification.
- They are written in the form of “\(\forall x\,p(x)\)” and “\(\exists x\,p(x)\)” respectively.
- To negate a quantified statement, change \(\forall\) to \(\exists\), and \(\exists\) to \(\forall\), and then negate the statement.

## Exercises \(\PageIndex{}\)

Exercise \(\PageIndex{1}\label{ex:quant-01}\)

Consider these propositional functions:

\(p(n)\): | \(n\) is prime |

\(q(n)\): | \(n\) is even |

\(r(n)\): | \(n>2\) |

Express these formulas in words:

- \(\exists n\in\mathbb{Z}\,(p(n)\wedge q(n))\)
- \(\forall n\in\mathbb{Z}\,[r(n)\Rightarrow p(n)\vee q(n)]\)
- \(\exists n\in\mathbb{Z}\,[p(n)\wedge(q(n)\vee r(n))]\)
- \(\forall n\in\mathbb{Z}\,[(p(n)\wedge q(n)) \Rightarrow\overline{r(n)}]\)

**Answer**-
(a) There exists an integer \(n\) such that \(n\) is prime and \(n\) is even.

(b) For all integers \(n\), if \(n>2\), then \(n\) is prime or \(n\) is even.

(c) There exists an integer \(n\) such that \(n\) is prime, and either \(n\) is even or \(n>2\).

(d) For all integers \(n\), if \(n\) is prime and \(n\) is even, then \(n\leq2\).

Exercise \(\PageIndex{2}\label{ex:quant-02}\)

Write each of the following statements in symbolic form:

- For every even integer \(n\) there exists an integer \(k\) such that \(n=2k\).
- There exists a right triangle \(T\) that is an isosceles triangle.
- Given any quadrilateral \(Q\), if \(Q\) is a parallelogram and \(Q\) has two adjacent sides that are perpendicular, then \(Q\) is a rectangle.

Exercise \(\PageIndex{3}\label{ex:quant-03}\)

Determine whether these statements are true or false:

- There exists an even prime integer.
- There exist integers \(s\) and \(t\) such that \(1<s<t<187\) and \(st=187\).
- Given any real numbers \(x\) and \(y\), \(x^2-2xy+y^2>0\).

**Answer**-
(a) true (b) true (c) false

Exercise \(\PageIndex{4}\label{ex:quant-04}\)

Determine whether these statements are true or false:

- There is a rational number \(x\) such that \(x^2\leq0\).
- For all \(x\in\mathbb{Z}\), either \(x\) is even, or \(x\) is odd.
- There exists a unique number \(x\) such that \(x^2=1\).

Exercise \(\PageIndex{5}\)

Negate this universal conditional statement (think about how a conditional statement is negated).

For all cats, if a cat eats 3 meals a day, then that cat weighs at least 10 lbs.

**Answer**-
There exists a cat that eats 3 meals a day and weighs less than 10 lbs.

Exercise \(\PageIndex{6}\)

Negate this universal conditional statement.

\(\forall x \in \mathbb{R} (x<0 \rightarrow x+1<0)\).

**Answer**-
\(\exists x \in \mathbb{R} (x<0 \wedge x+1\geq 0)\).

Exercise \(\PageIndex{7}\)

original: *No student wants a final exam on Saturday.*

a. Write the original statement symbolically.

b. Negate the original statement symbolically.

C. Negate the original statement informally (in English).

**Answer**-
a. \(\forall \;students \;x\; (x \mbox{ does not want a final exam on Saturday})\).

b. \(\exists \;a \;student \;x\; (x \mbox{ does want a final exam on Saturday})\).

c. Some student does want a final exam on Saturday.

Exercise \(\PageIndex{8}\label{ex:quant-08}\)

For this statement, (i) represent it in symbolic form, (ii) find the symbolic negation (in simplest form), and (iii) express the negation in words.

There exist rational numbers \(x_1\) and \(x_2\) such that \(x_1<x_2\) and \(x_1^3-x_1 > x_2^3-x_2\).

Exercise \(\PageIndex{9}\label{ex:quant-09}\)

The easiest way to negate the proposition

“A square must be a parallelogram”

is to say

“It is not true that a square must be a parallelogram.”

Yet, it is not the same as saying

“A square must not be a parallelogram.”

Can you explain why? What are other ways to express its negation in words?

**Answer**-
The statement “a square must be a parallelogram” means, symbolically, \[\forall PQRS\,(PQRS \mbox{ is a square} \Rightarrow PQRS \mbox{ is a parallelogram}),\] but the statement “a square must not be a parallelogram” means \[\forall PQRS\,(PQRS \mbox{ is a square} \Rightarrow PQRS \mbox{ is not a parallelogram}).\] The second statement is not the negation of the first. The correct negation, in symbol, is \[\exists PQRS\,(PQRS \mbox{ is a square} \wedge PQRS \mbox{ is a parallelogram}).\] In words, it means “there exists a square that is not a parallelogram.”

Exercise \(\PageIndex{10}\label{ex:quant-10}\)

Negate these statements:

- All squared numbers are positive.
- All basketball players are over 6 feet tall.
- No quarterback is under 6 feet tall.