Skip to main content

Discrete Mathematics: An Active Approach to Mathematical Reasoning

Jennifer Firkins Nordstrom

Section 3.1 Quantifiers

We want to be able to use variables in statements. 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\text{,}\)” and we know what set \(x\) belongs to, then we can decide whether these statements are true or false.

Definition 3.1.1.

The domain for a quantified statement is the set of possible values for a variable in a quantified statement.
In order to determine whether a statement is true of false, we first need to know the domain.

Example 3.1.2. Domain and Existential Statements.

Let \(D=\mathbb{Z}\text{.}\) Determine whether the statement “there exists \(x\in D\) such that \(x+3/2=4\)” is true or false.
Answer 1.
Since \(x=5/2\) is the only value satisfying the equation, but \(x\notin \mathbb{Z}\text{,}\) the statement is false.
Let \(D=\mathbb{R}\text{.}\) Determine whether the statement “there exists \(x\in D\) such that \(x+3/2=4\)” is true or false.
Answer 2.
Since \(x=5/2\) is the only value satisfying the equation, and \(x\in \mathbb{R}\text{,}\) the statement is true.
Let \(D=\{5/2\}\text{.}\) Determine whether the statement “there exists \(x\in D\) such that \(x+3/2=4\)” is true or false.
Answer 3.
Since \(x=5/2\) is the only value satisfying the equation, and \(x\in D\text{,}\) the statement is true.

Example 3.1.3. Domain and Universal Statements.

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.
We want to be able to work with generic statements, like \(p\) and \(q\text{,}\) but also with variables. Instead of \(p\) 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.
In our above 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 our domain could be the set of students at Linfield or the set of students in Discrete Math.
One goal with quantified statements is to be able to for which values in the domain they are true.

Definition 3.1.4.

The truth set for a predicate, \(P(x)\text{,}\) is the set of values for \(x\) that make \(P(x)\) true.

Example 3.1.5. Finding Truth Sets.

Find the truth set for \(P(x)\) given by \(x+3/2=4\text{.}\)
Answer 1.
Since \(x=5/2\) is the only value satisfying the equation, the tuth set is \(\{5/2\}\text{.}\)
Find the truth set for \(P(x)\) given by \(x\) is even.
Answer 2.
The truth set is the set of all even numbers.

Quantifiers.

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

Definition 3.1.6.

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\) (method of exhaustion). 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 (counterexample).

Activity 3.1.1.

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

Activity 3.1.2.

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

Definition 3.1.7.

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 3.1.3.

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

Activity 3.1.4.

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

Example 3.1.8. 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 3.1.5.

Write the following statement formally using quantifiers and variables: Every differentiable function is continuous.
Recall universal conditional statements from Section 1.1.

Definition 3.1.9.

A universal conditional statement has the form \(\forall x\in D\text{,}\) if \(P(x)\) then \(Q(x)\text{.}\) In symbols, we can write a universal conditional as \(\forall x\in D, P(x)\rightarrow Q(x).\)

Example 3.1.10. Universal Conditional Statement.

Translate the statement using quantifiers and variables, “If an integer is even then it is divisible by 2.”
Answer.
Let \(P(x)\) be “\(x\) is even” and \(Q(x)\) be “\(x\) is divisible by 2.” \(\forall x\in \mathbb{Z}, P(x)\rightarrow Q(x)\text{.}\)

Activity 3.1.6.

Write the following statement formally as a universal conditional: Every differentiable function is continuous.

Activity 3.1.7.

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.

Reading Questions Check Your Understanding

1.

    Let \(D=\mathbb{Z}\text{.}\) Let \(P(x)\) be “\(x^2\) is even.”
    True or False: \(\forall x\in D, P(x).\)

  • True.

  • It is not true that every square is even. For example, \(3^2=9\) is odd.

  • False.

  • It is not true that every square is even. For example, \(3^2=9\) is odd.

2.

    Let \(D=\mathbb{Z}\text{.}\) Let \(P(x)\) be “\(x^2\) is even.”
    True or False: \(\exists x\in D, P(x).\)

  • True.

  • For example, \(2^2=4\) is even.

  • False.

  • For example, \(2^2=4\) is even.

3.

    Let \(D=\mathbb{Z}\text{.}\) Let \(P(x)\) be “\(x^2\) is even.”
    True or False: \(\forall x\in D, \sim P(x).\)

  • True.

  • It is not true that every square is not even.

  • False.

  • It is not true that every square is not even.

4.

    Let \(D=\mathbb{Z}\text{.}\) Let \(P(x)\) be “\(x^2\) is even.”
    True or False: \(\exists x\in D, \sim P(x).\)

  • True.

  • There exists a square which is not even.

  • False.

  • There exists a square which is not even.

5.

    Let \(D=\mathbb{Z}\text{.}\) Let \(P(x)\) be “\(x^2\) is even.”
    True or False: \(\sim(\forall x\in D, P(x)).\)

  • True.

  • This is the negation of \(\forall x\in D, P(x)\text{,}\) which was false, so it must be true.

  • False.

  • This is the negation of \(\forall x\in D, P(x)\text{,}\) which was false, so it must be true.

Exercises Exercises

1.

Let \(P(x)\) be the predicate “\(x>1/x\text{.}\)”
  1. Write \(P(2), P(1/2), P(-1), P(-1/2)\text{,}\) and \(P(-8)\text{.}\) Indicate which of these is true and which is false.
  2. Let the domain be the set \(\mathbb{R}\text{.}\) Find the truth set of \(P(x)\text{.}\)
  3. Let the domain be the set \(\mathbb{R}^+\) of all positive real numbers. Find the truth set of \(P(x)\text{.}\)

2.

Let \(Q(x, y)\) be the predicate “If \(x<y\) then \(x^2<y^2\)” with domain for both \(x\) and \(y\) being \(\mathbb{R}\text{.}\)
  1. Explain why \(Q(x, y)\) is false if \(x=-4\) and \(y=2\text{.}\)
  2. Give values different from those in part (a) for which \(Q(x, y)\) is false.
  3. Explain why \(Q(x, y)\) is true if \(x=2\) and \(y=4\text{.}\)
  4. Give values different from those in part (c) for which \(Q(x, y)\) is true.

3.

Give a counter 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*}

4.

Give a counter 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*}

5.

Which of the following are equivalent ways of expressing the statement
\begin{equation*} \exists x\in \mathbb{R} \text{ such that } x^2=2? \end{equation*}
  1. There is at least one real number whose square is 2.
  2. The square of each real number is 2.
  3. Some real numbers have square 2.
  4. The number \(x\) has square 2, for some real number \(x\text{.}\)
  5. If \(x\) is a real number, then \(x^2=2\text{.}\)
  6. Some real number has square 2.

6.

Which of the following are equivalent ways of expressing the statement
\begin{equation*} \forall n\in \mathbb{Z} \text{ if } n^2 \text{ is even then } n \text{ is even}? \end{equation*}
  1. If the square of an integer is even, then that integer is even
  2. All integers have even squares and are even.
  3. Given any integer whose square is even, that integer is itself even.
  4. For all integers, there are some whose square is even.
  5. Any integer with an even square is even.
  6. All even integers have even squares.

7.

Rewrite the following statements using the form “\(\forall\)____\(x\text{,}\)____.”
  1. Every real number is positive, negative, or zero.
  2. No irrational numbers are integers.

8.

Let \(D\) be the set of all students at Linfield University, and let \(M(s)\) be “\(s\) is a math major,” let \(C(s)\) be “\(s\) is a computer science major,” and let \(P(s)\) be “\(s\) is a physics major.” Express each of the following statements using quantifiers, variables, and the predicates \(M(s), C(s), P(s)\text{.}\)
  1. There is a physics major who is a math major.
  2. Every computer science major is a math major.
  3. No computer science majors are physics majors.
  4. Some computer science majors are also math majors.
  5. Some computer science majors are physics majors and some are not.

9.

Let \(\mathbb{R}\) be the domain of the predicate variable \(x\text{.}\) Which of the following are true and which are false? Give counter examples for the statements that are false.
  1. If \(x>2\) then \(x>1\text{.}\)
  2. If \(x>2\) then \(x^2>4\text{.}\)
  3. If \(x^2>4\) then \(x>2\text{.}\)
  4. If \(x^2>4\) then \(|x|>2\text{.}\)

10.

Let the domain of \(x\) be the set \(D\) of objects discussed in mathematics courses, and let Real(\(x\)) be “\(x\) is a real number,” Pos(\(x\)) be “\(x\) is a positive real number,” Neg(\(x\)) be “\(x\) is a negative real number,” and Int(\(x\)) be “\(x\) is an integer.” Rewrite each statement without using quantifiers or variables. Indicate which statements are true and which are false.
  1. Pos(0)
  2. \(\forall x\text{,}\) Real(\(x\)) \(\wedge\) Neg(\(x\)) \(\rightarrow\) Pos(\(-x\)).
  3. \(\forall x\text{,}\) Int(\(x\)) \(\rightarrow\) Real(\(x\)).
  4. \(\exists x\) such that Real(\(x\)) \(\wedge\) \(\sim\)Int(\(x\)).
You have attempted of activities on this page.
PrevTopNext