\Question{Miscellaneous Logic}
\begin{Parts}
\Part
Let the statement, $(\forall x \in \mathbb{R})(\exists y \in \mathbb{R}) \ G(x,y)$, be
true for predicate $G(x,y)$.
For each of the following statements, decide if the statement is certainly true, certainly false, or possibly true, and justify your solution. (If possibly true, provide a specific example where the statement is false and a specific example where the statement is true.)
\begin{enumerate}[(i)]
\item
$G(3,4)$
\item
$(\forall x \in \mathbb{R})$ $G(x,3)$
\item
$\exists y$ $G(3,y)$
\item
$\forall y$ $\neg G(3,y)$
\item
$\exists x$ $G(x,4)$
\end{enumerate}
% \Part True or False? \\
% $\forall x \exists y (P(x,y) \land \neg Q(x,y)) \equiv \neg \exists x \forall y (P(x,y) \implies Q(x,y))$
% \Part True or False? \\
% $\exists x ((\forall y P(x,y)) \land (\forall z Q(x,z))) \equiv (\exists x \forall y P(x,y)) \land (\exists x \forall z Q(x,z))$
\Part
Give an expression using terms involving $\lor,\land$ and $\neg$ which is true if and only if
exactly one of $X,Y$, and $Z$ is true.
% (Just to remind you: $(X \land Y \land Z)$ means
% all three of $X$,$Y$,$Z$ are true, $(X \lor Y \lor Z)$ means at least one of $X$,$Y$
% and $Z$ is true.)
\end{Parts}
\Question{Propositional Practice}
Convert the following English sentences into propositional logic and the following propositions into English. State whether or not each statement is true with brief justification.
\begin{Parts}
\Part There is a real number which is not rational.
\Part All integers are natural numbers or are negative, but not both.
\Part If a natural number is divisible by 6, it is divisible by 2 or it is divisible by 3.
\Part $(\forall x \in \mathbb{R})\ (x \in \mathbb{C})$
\Part $(\forall x \in \mathbb{Z})\ (((2 \mid x) \lor (3 \mid x)) \implies (6 \mid x))$
\Part $(\forall x \in \mathbb{N})\ ((x > 7) \implies ((\exists a, b \in \mathbb{N})\ (a + b = x)))$
\end{Parts}
\Question{Prove or Disprove}
\begin{Parts}
\Part $(\forall n \in \mathbb{N})$ if $n$ is odd then $n^2 + 2n$ is odd.
\Part $(\forall x, y \in \mathbb{R})$ $\min(x, y) = (x + y - |x - y|)/2$.
\Part $(\forall a, b \in \mathbb{R})$ if $a + b \le 10$ then $a \le 7$ or $b \le 3$.
\Part $(\forall r \in \mathbb{R})$ if $r$ is irrational then $r + 1$ is irrational.
\Part $(\forall n \in \mathbb{Z}^+)$ $10n^2 > n!$.
\end{Parts}
\Question{Preserving Set Operations}
For a function $f$, define the image of a set $X$ to be the set $f(X) = \{y~|~y = f(x) \text{ for some } x \in X\}$. Define the inverse image or preimage of a set $Y$ to be the set $f^{-1}(Y) = \{x~|~f(x) \in Y\}$. Prove the following statements, in which $A$ and $B$ are sets. By doing so, you will show that inverse images preserve set operations, but images typically do not.
\textit{Hint: For sets $X$ and $Y$, $X=Y$ if and only if $X \subseteq Y \text{ and } Y \subseteq X$. To prove that $X \subseteq Y$, it is sufficient to show that $(\forall x)~((x \in X) \implies (x \in Y))$.}
\begin{Parts}
\Part $f^{-1}(A \cup B) = f^{-1}(A) \cup f^{-1}(B)$.
\Part $f^{-1}(A \cap B) = f^{-1}(A) \cap f^{-1}(B)$.
\Part $f^{-1}(A \setminus B) = f^{-1}(A) \setminus f^{-1}(B)$.
\Part $f(A \cup B) = f(A) \cup f(B)$.
\Part $f(A \cap B) \subseteq f(A) \cap f(B)$, and give an example where equality does not hold.
\Part $f(A \setminus B) \supseteq f(A) \setminus f(B)$, and give an example where equality does not hold.
\end{Parts}
\Question{Hit or Miss?}
State which of the proofs below is correct or incorrect.
For the incorrect ones, please explain clearly where the logical error in the proof lies.
Simply saying that the claim or the induction hypothesis is false is \emph{not} a valid explanation of what is wrong with the proof.
You do not need to elaborate if you think the proof is correct.
\begin{Parts}
\Part
\textbf{Claim:} For all positive numbers $n \in \mathbb{R}$, $n^2 \ge n$.
\begin{proof}
The proof will be by induction on $n$. \\
\emph{Base Case:} $1^2 \ge 1$. It is true for $n=1$. \\
\emph{Inductive Hypothesis:} Assume that $n^2 \ge n$. \\
\emph{Inductive Step:} We must prove that $(n+1)^2 \ge n+1$.
Starting from the left hand side,
\begin{align*}
(n+1)^2 &= n^2+2n+1 \\
&\ge n+1.
\end{align*}
Therefore, the statement is true.
\end{proof}
\Part
\textbf{Claim:} For all negative integers $n$, $(-1) + (-3) + \cdots + (2n+1) = -n^2$.
\begin{proof}
The proof will be by induction on $n$. \\
\emph{Base Case:} $-1 = -(-1)^2$. It is true for $n=-1$. \\
\emph{Inductive Hypothesis:} Assume that $(-1) + (-3) + \cdots + (2n+1) = -n^2$. \\
\emph{Inductive Step:} We need to prove that the statement is also true for $n-1$ if it is true for $n$, that is,
$(-1) + (-3) + \cdots + (2(n-1)+1) = -(n-1)^2$. Starting from the left hand side,
\begin{align*}
(-1) + (-3) + \cdots + (2(n-1)+1)
&= ((-1) + (-3) + \cdots + (2n+1))+(2(n-1)+1) \\
&= -n^2 + (2(n-1)+1) \quad \text{(Inductive Hypothesis)}\\
&= -n^2 + 2n - 1 \\
&= -(n^2 - 2n + 1) \\
&= -(n-1)^2.
\end{align*}
Therefore, the statement is true.
\end{proof}
% \Part
% \textbf{Claim:} For all positive integers $n$, $\sum\limits_{i=0}^n 2^{-i} \le 2$.
% \begin{proof}
% We will prove a stronger statement, that is, $\sum\limits_{i=0}^n 2^{-i} = 2-2^{-n}$, by induction on $n$. \\
% \emph{Base Case:} $n=1 \le 2-1$. It is true for $n=1$. \\
% \emph{Inductive Hypothesis:} Assume that $\sum\limits_{i=0}^n 2^{-i} = 2-2^{-n}$. \\
% \emph{Inductive Step:} We must show that $\sum\limits_{i=0}^{n+1} 2^{-i} = 2-2^{-(n+1)}$. Starting from the left hand side,
% \begin{align*}
% \sum\limits_{i=0}^{n+1} 2^{-i}
% &= \sum\limits_{i=0}^{n} 2^{-i} + 2^{-(n+1)} \\
% &= (2-2^{-n})+2^{-(n+1)} \quad\text{(Inductive Hypothesis)} \\
% &= 2-2^{-(n+1)}.
% \end{align*}
% Since $\sum\limits_{i=0}^n 2^{-i} = 2-2^{-n} \le 2$, the claim is true.
% \end{proof}
\Part
\textbf{Claim:} For all nonnegative integers $n$, $2n=0$.
\begin{proof}
We will prove by strong induction on $n$. \\
\emph{Base Case:} $2 \times 0 = 0$. It is true for $n=0$. \\
\emph{Inductive Hypothesis:} Assume that $2k=0$ for all $0 \le k \le n$. \\
\emph{Inductive Step:} We must show that $2(n+1)=0$. Write $n+1 = a+b$ where $0 < a,b \le n$.
From the inductive hypothesis, we know $2a = 0$ and $2b=0$, therefore,
\begin{align*}
2(n+1) = 2(a+b) = 2a + 2b = 0+0 =0.
\end{align*}
The statement is true.
\end{proof}
% \Part
% \textbf{Claim:} Every positive integer $n\ge2$ has a unique prime factorization. \\
% In other words, let $2 \le p_1, p_2, \hdots, p_i \le n$ be all prime numbers that divide $n$,
% there is only one unique way to write $n$ as a product of primes,
% \begin{align*}
% n = p_1^{d_1} \cdot p_2^{d_2} \dotsm p_i^{d_i},
% \end{align*}
% where $d_1, d_2, \hdots, d_i \in \mathbb{N}$.
% \begin{proof}
% We will prove by strong induction on $n$. \\
% \emph{Base Case:} 2 is a prime itself. It is true for $n=2$. \\
% \emph{Inductive Hypothesis:} Assume that the statement is true for all $2 \le k \le n$. \\
% \emph{Inductive Step:} We must prove that the statement is true for $n+1$.
% If $n+1$ is prime, then it itself is a unique prime factorization.
% Otherwise, $n+1$ can be written as $x \times y$ where $2 \le x,y \le n$.
% From the inductive hypothesis, both $x$ and $y$ have unique prime factorizations.
% The product of unique prime factorizations is unique, therefore, $n+1$ has a unique prime factorization.
% \end{proof}
\end{Parts}
\Question{Badminton Ranking}
A team of $n$ ($n \geq 2$) badminton players held a tournament, where every person plays with every other person exactly once, and there are no ties. Prove by induction that after the tournament, we can arrange the $n$ players in a sequence, so that every player in the sequence has won against the person immediately to the right of him.