Skip to main content

Chapter 5 Quantifiers

Exercises Practice Problems

1. Sets and Logic.

For \(x \in \mathbb Z\text{,}\) consider the statements

\begin{equation*} P(x) = \mbox{" is even"} \qquad \qquad Q(x) = \mbox{" is positive"} \end{equation*}

and let \(A\) and \(B\) be the sets

\begin{equation*} A = \{ x \in \mathbb{Z} \mid P(x) \mbox{ is true} \} \qquad \qquad B = \{ x \in \mathbb{Z} \mid Q(x) \mbox{ is true} \} \end{equation*}

Fill in the blanks using the symbols \(A\text{,}\) \(B\text{,}\) \(\cup\) and \(\cap\text{.}\)

\begin{equation*} \begin{array}{rcl} \underline{\phantom{asdasdasd}} = \{ x \in \mathbb{Z} \mid P(x) \wedge Q(x) \mbox{ is true} \} \\ \underline{\phantom{asdasdasd}} = \{ x \in \mathbb{Z} \mid P(x) \vee Q(x) \mbox{ is true} \} \end{array} \end{equation*}

You have just turned an expression about mathematical statements into an expression about sets! Solution.

\begin{equation*} \begin{array}{rcl} A \cap B = \{ x \in \mathbb{Z} \mid P(x) \wedge Q(x) \mbox{ is true} \} \\ A \cup B = \{ x \in \mathbb{Z} \mid P(x) \vee Q(x) \mbox{ is true} \} \end{array} \end{equation*}

2. Quantifiers.

Let \(X\) be the set of people. Let \(P(x,y)\) be the statement "\(x\) loves \(y\text{.}\)" Rewrite each of the following statements using formal quantifiers and variables.

  1. Everybody loves somebody.

  2. Somebody loves everybody.

Solution.

Let \(X\) be the set of all people. Let \(P(x,y)\) be the statement "\(x\) loves \(y\text{.}\)"

  1. \(\displaystyle \forall x \in X, \exists y \in Y, P(x,y)\)

  2. \(\displaystyle \exists x \in X, \forall y \in Y, P(x,y)\)

3. Negating Quantifiers.

Negate the formal statements you made in the previous problem, then translate them into everyday English. Do these negations make sense, when compared to the original statements? Solution.

  1. \(\exists x \in X, \forall y \in Y, \neg P(x,y)\text{,}\) which means "Somebody hates everybody."

  2. \(\forall x \in X, \exists y \in Y, \neg P(x,y)\text{,}\) which means "Everybody hates somebody."

4. Negating an Implication.

Let \(P(x) =\) "\(x\) is an integer" and let \(Q(x)\) = "\(x\) is positive". Negate the statement "For all \(x \in \R\text{,}\) if \(x\) is an integer then \(x\) is positive," using the fact that \(P \Rightarrow Q\) is equivalent to \(\neg P \vee Q\text{.}\) Then explain why providing one counterexample is enough to disprove that \(\forall x \in \R, P(x) \Rightarrow Q(x)\text{.}\) Solution.

The negation is "There exists an integer that is not positive." Note that "not positive" isn't the same as "negative" because 0 is neither positive nor negative.

This uses the existential quantifiers (at least one), so we just need one example of a non-positive integer.

5. Fooling Around.

Negate the statement "You can fool all of the people all of the time" by first creating a formal statement using quantifiers. Hint: you are considering two sets: people and times. Solution.

Let \(X\) be the set of people and let \(T\) be the set of times. Let \(P(x,t)\) be the statement "you can fool person \(x\) at time \(t\text{.}\) The original statement is

\begin{equation*} \forall x \in X, \forall t \in T, P(x,t). \end{equation*}

The simple negation of the statement leads to the adage "You can't fool all of the people all of the time." What if we try to say this in precise mathematical language? We get

\begin{equation*} \exists x \in X, \exists t \in T, \neg P(x,t), \end{equation*}

which means there is a person and a time where you fail to fool them.

6. Order of Quantifiers.

In this problem, we will see that the order of our quantifiers matters

  1. Consider the statement

    \begin{equation*} \exists y \in \mathbb{R}, \forall x \in \mathbb{R}, x = y^3. \end{equation*}

    Restate the above in plain English (as well as you can). Is this statement true or false? Solution.

    The statement is: "There exists a \(y \in \R\text{,}\) such that for all \(x \in \R\text{,}\) we have \(x=y^3\text{.}\)" This is false since this statement says that there is a single number \(y\) that works for every \(x\) simultaneously.

  2. Now consider the statement

    \begin{equation*} \forall y \in \mathbb{R}, \exists x \in \mathbb{R}, x = y^3. \end{equation*}

    Restate the above in plain English (as well as you can). Is this statement true or false? Solution.

    The statement is: "For each \(y \in \R\text{,}\) there exists an \(x \in \R\text{,}\) such that \(x=y^3\text{.}\)" This statement is true. This time, the choice of \(x\) depends on the given \(y\text{.}\) In particular, we take \(x = \sqrt[3]{y}\text{.}\)