Skip to main content\( \newcommand{\identity}{\mathrm{id}}
\newcommand{\notdivide}{{\not{\mid}}}
\newcommand{\notsubset}{\not\subset}
\newcommand{\lcm}{\operatorname{lcm}}
\newcommand{\gf}{\operatorname{GF}}
\newcommand{\inn}{\operatorname{Inn}}
\newcommand{\aut}{\operatorname{Aut}}
\newcommand{\Hom}{\operatorname{Hom}}
\newcommand{\cis}{\operatorname{cis}}
\newcommand{\chr}{\operatorname{char}}
\newcommand{\Null}{\operatorname{Null}}
\def\Z{\mathbb Z}
\def\R{\mathbb R}
\def\Q{\mathbb Q}
\def\N{\mathbb N}
\def\C{\mathbb C}
\def\W{\mathbb W}
\def\ba{{\mathbf{a}}}
\def\bb{\mathbf{b}}
\def\bh{{\mathbf{h}}}
\def\bu{{\mathbf{u}}}
\def\bv{{\mathbf{v}}}
\def\bw{{\mathbf{w}}}
\def\bx{{\mathbf{x}}}
\def\by{\mathbf{y}}
\def\bone{{\mathbf{1}}}
\def\bzero{\mathbf{0}}
\def\var{{\mbox{var}}}
\def\P{{\mathbb{P}}}
\def\E{{\mathbb{E}}}
\def\cA{{\mathcal{A}}}
\def\cB{{\mathcal{B}}}
\def\cC{{\mathcal{C}}}
\def\cP{\mathcal P}
\def\cN{\mathcal N}
\def\cE{\mathcal E}
\def\cO{\mathcal O}
\def\cF{\mathcal F}
\def\cX{\mathcal X}
\def\nimsum{\, \oplus \,}
\def\mex{{\mathrm{mex}}}
\newcommand{\pile}[1]{\bullet{#1}}
\def\g{g}
\def\kin{k^{\mathrm{in}}}
\def\kout{k^{\mathrm{out}}}
\newcommand{\indeg}[1]{k^{\mathrm{in}}_{#1}}
\newcommand{\outdeg}[1]{k^{\mathrm{out}}_{#1}}
\tikzset{->-/.style={decoration={
markings,
mark=at position .5 with {\arrow{latex}}},postaction={decorate}}}
\newcommand{\nimbleboard}[1]{
\begin{scope}[shift={(.25, .4)}]
\draw (0,-.3) -- (#1,-.3) -- (#1+.45, .7) -- (#1+.45, 1);
\draw (0,0) -- (#1,0);
\draw (.45,1) -- (#1+.45,1);
\foreach \i in {0, ..., #1} {
\draw (\i, -.3) -- (\i, 0) -- (\i+.45,1);
}
\foreach \i in {1, ..., #1} {
\node[style={font=\sffamily\scriptsize}] at (\i - .5, -.15) {\i};
}
\end{scope}
}
\newcommand{\coin}[1]{
\begin{scope}[shift={#1}]
\draw[color=white, fill=white] (-.4, 0) -- (-.4, -.1) -- (.4,-.1) -- (.4,0) -- cycle;
\draw[thick, fill=white] (0,0) ellipse (0.4 and 0.10);
\draw[thick, fill=white] (.4,-.1) arc (0:-180:0.4 and 0.10);
\draw[thick] (0.4,0) -- (0.4, -.1);
\draw[thick] (-0.4,0) -- (-0.4, -.1);
\end{scope}
}
\newcommand{\bean}[2]{
\begin{scope}[shift={#1}, rotate={#2}]
\draw [very thick, fill=gray!50] plot [smooth cycle] coordinates {(-.2,0) (-.175, .07) (-.1,.1) (0,.075) (.1,.1) (.175, .07) (.2,0) (.15, -.07) (0,-.1) (-.15, -.07)};
\end{scope}
}
\newcommand{\heap}[2]{
\begin{scope}[shift={#1}]
\draw[very thick] (0,0) circle ({#2});
\end{scope}
}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\)
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!
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.
Everybody loves somebody.
Somebody loves everybody.
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?
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 \(P \vee \neg Q\text{.}\) Then explain why providing one counterexample is enough to disprove that \(\forall x \in \R, P(x) \Rightarrow Q(x)\text{.}\)
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.
6. Order of Quantifiers.
In this problem, we will see that the order of our quantifiers matters
-
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?
-
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?