\documentclass[10pt,letterpaper,unboxed,cm]{hmcpset}
\usepackage[margin=1in]{geometry}
\usepackage{graphicx, hyperref,varwidth}
\pagestyle{empty}
\newcommand{\st}{~\mid~}
\newcommand{\bAlg}[1]{\begin{center}\begin{varwidth}{\textwidth}
#1
\begin{enumerate}\setlength{\itemsep}{-3pt}}
\newcommand{\eAlg}{\end{enumerate}\end{varwidth}\end{center}}
%\name{}
\assignment{CSE 20 Homework 4}
\duedate{Due: Sunday February 12, 2017 at noon}
\begin{document}
\begin{center}
\begin{minipage}[t]{6in}
\rule{\linewidth}{2pt}
{\sc Topics} Quantifiers and paradoxes
\newline
{\sc Reading} Rosen Sections 1.4-1.8, 2.1-2.2.
\newline
{\sc Key Concepts} Predicates, domain of discourse / universe,
existential quantifier, universal quantifier, restricting the domain,
negated quantifiers, nested quantifiers, proof strategies,
counterexample, (constructive) example, direct proof, contrapositive
proof, proof by contradictions, sets, element, subset, empty set, power set,
paradox.
\newline
\rule{\linewidth}{2pt}
\end{minipage} \hfill
\end{center}
\problemlist{}
\begin{problem}[1.] ({\bf 9 points})
In each of the parts from this question, build your counterexample with universe (domain)
$\{1,2,3,4\}$. You can define the predicate $P(x,y)$ differently for each part. To define the predicate,
you can either use known predicates on numbers (e.g.\ ``$x$ and $y$ are both even" or ``$x > y$", etc.)
or by defining explicitly for which $x,y$ values $P(x,y)$ evaluates to $T$ and for which values it evaluates
to $F$ (to do this, you must consider {\bf all} possible domain values).
\begin{itemize}
\item[(a)] Give a counterexample which proves that
\[
\exists x \forall y P(x,y) \qquad \qquad
\exists y \forall x P(x,y)
\]
are not logically equivalent. Justify your answer.
\item[(b)] Give a counterexample which proves that
\[
\forall x \exists y P(x,y) \qquad \qquad
\forall y \exists x P(x,y)
\]
are not logically equivalent. Justify your answer.
\item[(c)] Give a counterexample which proves that
\[
\forall x \exists y P(x,y) \qquad \qquad
\exists x \forall y P(x,y)
\]
are not logically equivalent. Justify your answer.
\end{itemize}
\end{problem}
\begin{problem}[2.] ({\bf 12 points})
Determine the truth value of each of these
statements when the domain consists of all real numbers.
Justify your answers. Note that in grading
this question, we will check whether you correctly determined the truth value
for \textbf{each} statement, but we may not grade all three proofs.
\begin{itemize}
\item[(a)] $\forall y \exists x (xy \neq 0)$.
\item[(b)] $\forall x \forall y \forall z ( x + y =z )$.
\item[(c)] $\exists x \forall y ( y \neq 0 \to xy = 1)$.
\end{itemize}
({\it Similar to Rosen 1.5 \# 28})
\end{problem}
\begin{problem}[3.] ({\bf 10 points})
Asymptotic analysis is foundational in many disciplines in Computer Science. At the heart
of asymptotic analysis is big-O notation. Definition 1 on page 205 of big O notation
can be written formally using quantifiers in the following way.
\begin{quote}
Let $f$ and $g$
be functions from the set of integers to the set of real numbers. We say that
$f(x)$ is $O(g(x))$ if
\[
\exists C \exists k \forall x~\left ( x > k ~\to~ |f(x)| \leq C |g(x)| \right)
\]
\end{quote}
\begin{itemize}
\item[(a)] Using this definition and our proof strategies for quantified
statements, prove that $x+1$ is $O(x^2)$. That is, show that the proposition above
evaluates to true when $f(x) = x+1$ and $g(x) = x^2$.
\item[(b)] Using this definition and our proof strategies for quantified
statements, prove that $x^2$ is {\bf not} $O(x+1)$. That is, show that the proposition above
evaluates to false when $f(x) = x^2$ and $g(x) = x+1$.
\end{itemize}
\end{problem}
\begin{problem}[4.] ({\bf 10 points})
For each of the following, determine whether it is true or false and then
prove it (if it true) or disprove it (if it is false). Note that in grading
this question, we will check whether you correctly determined the truth value
for \textbf{each} statement, but we may not grade all three proofs.
\begin{itemize}
\item[(a)] $n^2 - n + 17$ is prime for every non-negative integer $n$.
{\it As a reminder, the definition for prime numbers is on page 257.}
\item[(b)] The ratio (result of division) of any two positive rational numbers is rational.
{\it As a reminder, the definition for rational numbers is on page 85.}
\item[(c)] Let $f$ be a real-valued function over the real numbers. (For
example, $f(x) = x^2$ or $f(x) = \log_2(|x|+1)$.) $f(x)$ is irrational if and
only if $x$ is irrational.
\end{itemize}
\end{problem}
\begin{problem}[5.] ({\bf 9 points})
(The Russell Paradox) Define the set $R$ to be $\{x : x ~\text{is a set and $x$ is not a member of $x$}\}$.
\begin{itemize}
\item[(a)] Explain why $\emptyset$, $\{1\}$, and $\{1,\{1\}\}$ are elements of $R$.
\item[(b)] Assume that the data type \texttt{CSE20Data} were defined so that every set of \texttt{CSE20Data} elements was itself another
element of type \texttt{CSE20Data}. Explain why the set of all \texttt{CSE20Data} elements, given our assumption, is not an element of $R$.
\item[(c)] Is $R$ a member of $R$? Explain why both a ``yes" and a ``no" answer to this question are impossible.
\end{itemize}
\end{problem}
\end{document}