\documentclass[twoside,12pt]{article}
\usepackage{light}

%\hidesolutions
\showsolutions

\begin{document}

\problemset{1}{September 10, 2004}{Monday, September 13}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}[15 points]
Prove the following statement by proving its contrapositive: if $r$ is
irrational, then $\sqrt{r}$ is also irrational.  (Be sure to
\textit{state} the contrapositive explicitly.)
\end{problem}

\solution{We prove the contrapositive: if $\sqrt{r}$ is rational, then
$r$ is rational.  If $\sqrt{r}$ is rational, then there exists an
integer $a$ and a positive integer $b$ such that:
%
\[
\sqrt{r} = \frac{a}{b}
\]
%
Squaring both sides gives:
%
\begin{align*}
r & = \frac{a^2}{b^2}
\end{align*}
%
Since $a^2$ and $b^2$ are integers, this implies that $r$ is also
rational.  (Note that $b^2 \neq 0$, since $b$ is positive.)}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}[25 points]
Let $A$, $B$, and $C$ be sets such that $A \cap B \cap C = \emptyset$.
Prove that:
%
\[
A \cup B \cup C = (A - B) \cup (B - C) \cup (C - A)
\]
%
You are welcome to use a diagram to aid your own reasoning, but your
proof must be text.  (For guidance on structuring the proof, see pages
64-71 in Cupillari.)
\end{problem}

\solution{We prove that the left side is contained in the right and
the right side is contained in the left.

First, we show that the left side is contained in the right.  Let $x$
be an element of $A \cup B \cup C$.  Then $x$ is an element of at
least one of the sets $A$, $B$, or $C$.  However, by the assumption $A
\cap B \cap C = \emptyset$, we know $x$ is also \textit{not} an
element of at least one of $A$, $B$, or $C$.  Now we use a case
analysis to show that $x$ is in either $A - B$, $B - C$, or $C - A$:

\begin{itemize}

\item If $x \in A$, then there are two possibilities:

\begin{itemize}

\item If $x \not\in B$, then $x \in A - B$.

\item If $x \in B$, then $x \not\in C$, since $x$ can not be in all of
$A$, $B$, and $C$.  Thus, $x \in B - C$.

\end{itemize}

\item If $x \not\in A$, then there are again two possibilities:

\begin{itemize}

\item If $x \in C$, then $x \in C - A$.

\item If $x \not\in C$, then $x \in B$, since $x$ is in at least one
of $A$, $B$, or $C$.  Therefore, $x \in B - C$.

\end{itemize}

\end{itemize}

\noindent Since $x$ is an element of either $A - B$, $B - C$, or $C -
A$, we know that $x$ is an element of $(A - B) \cup (B - C) \cup (C -
A)$.  Therefore, the set on the left is contained in the set on the
right.

Next, we show that the right side is contained in the left.  Let $x$
be an element of $(A - B) \cup (B - C) \cup (C - A)$.  Then $x$ is
element of either $A - B$, $B - C$, or $C - A$.  This implies that $x$
is an element of either $A$, $B$ or $C$, respectively.  Thus, $x$ is
an element of $A \cup B \cup C$.  Therefore, the set on the right is
contained in the set on the left.

Since the set on the right contains the set on the left and
vice-versa, the two sets are equal.}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}[20 points]
Use proof by contradiction to show that $\log_{5} 8$ is irrational.
\end{problem}

\solution{
We use proof by contradiction.  Suppose that $\log_5 8$ is rational.
Then there exists an integer $a$ and a positive integer $b$ such that:
%
\[
\log_{5} 8 = \frac{a}{b}
\]
%
This implies that:
%
\begin{align*}
8 & = 5^{a/b} \\
8^b & = 5^a
\end{align*}
%
(Raising the first equation to the $b$-th power gives the second.)
Now the left side of the last equation is even and the right side is
odd.  This is a contradiction.  Therefore, our supposition was wrong,
and $\log_{5} 8$ is irrational.}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}[20 points]
The three logical expressions below are nearly equivalent.  However,
for one particular setting of $x$, $y$, and $z$, one of the
expressions is not like the others.  Write out \textit{complete truth
tables for all three}, and determine which one of these expressions
just doesn't belong.
%
\begin{align*}
1. & \qquad (x \rightarrow y) \wedge (y \rightarrow z) \wedge (z \rightarrow x) \\
2. & \qquad (\neg x) \wedge (\neg y) \wedge (\neg z) \\
3. & \qquad (\neg x \vee (y \wedge z)) \wedge (x \vee (\neg y \wedge \neg z))
\end{align*}
\end{problem}

\solution{
\[
\begin{array}{c|c|c|c|c|c}
x & y & z & (1) & (2) & (3) \\ \hline
F & F & F & T & T & T \\
F & F & T & F & F & F \\
F & T & F & F & F & F \\
F & T & T & F & F & F \\
T & F & F & F & F & F \\
T & F & T & F & F & F \\
T & T & F & F & F & F \\
T & T & T & T & \textbf{F} & T
\end{array}
\]

Expression 2 just doesn't belong.
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}[20 points]

\term{Universal generalization} is an inference rule so natural that
you've probably used it many times without a second thought.  It says
that if you can prove that $P(x)$ is true for some arbitrary,
unspecified $x \in S$, then you can conclude that $P(x)$ is true for
all $x \in S$.  Use universal generalization to prove that:
%
\[
\forall \ x \in [-1,1] \quad 1 - x^2 \leq 1 - x^2 + x^4 - x^6
\]
%
Here [-1,1] denotes the set of all real numbers between -1 and 1,
including -1 and 1.  (If you prove this claim any old way, you'll
probably discover in retrospect that you implicitly relied on
universal generalization.)
\end{problem}

\solution{Let $x$ be an arbitrary, unspecified element of $[-1,1]$.
Then $x^2 \leq 1$, which means $1 - x^2$ is nonnegative.  We also know
%
\[
1 \leq 1 + x^4
\]
%
since $x^4$ is nonnegative.  Multiplying both sides of this inequality
by $1 - x^2$ does not reverse its direction, since we showed that $1 -
x^2$ is nonnegative.  Thus, we have:
%
\begin{align*}
1 - x^2
    & \leq (1 + x^4) (1 - x^2) \\
    & = 1 - x^2 + x^4 - x^6
\end{align*}
%
Since we proved the inequality for an arbitrary, unspecified element
$x \in [-1,1]$, universal generalization implies that the inequality
holds for all $x \in [-1,1]$.

\textbf{Note:} This may be the last you'll ever hear of universal
generalization.  We'll continue to use it all the time, but just won't
mention it explicitly.}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{document}
