\documentclass[12pt]{article}   
\usepackage{latex-macros/course}% !! Use the macros

%\backwardscompatibility        % !! use for backwards compatibility
%\showsolutions                 % !! use to force solutions & skip query
%\hidesolutions                  % !! use to force no solutions & skip
                                 % query 

\renewcommand{\reading}{Notes for
  \href{http://theory.csail.mit.edu/classes/6.042/fall05/ln1.pdf}{Week1} and
  \href{http://theory.csail.mit.edu/classes/6.042/fall05/ln2.pdf}{Week 2}}

\newcommand{\isprime}{\text{\sc{is-prime}}}

\begin{document}
\problemset{1}                 % !! Start the problem set with its number

%S01 Karger
\begin{problem}A real number $r$ is called {\em sensible} if there
exist positive integers $a$ and $b$ such that $\sqrt{a / b} = r$.  For
example, setting $a = 2$ and $b = 1$ shows that $\sqrt{2}$ is
sensible.  Prove that $\sqrt[3]{2}$ is not sensible.  (Consider only
positive real roots in this problem)
\solution{
The proof is by contradiction.  Assume for the purpose of
contradiction that $\sqrt[3]{2}$ is sensible.  Then there exist
positive integers $a$ and $b$ such that $\sqrt{a / b} = \sqrt[3]{2}$.
Squaring both sides of this equation gives $a / b = \sqrt[3]{4}$,
which implies that $\sqrt[3]{4}$ is rational.

Since $\sqrt[3]{4}$ is rational, we can write it as a fraction $x / y$
in lowest-terms, where $x$ is an integer and $y$ is a positive
integer.  Therefore, we have:

\begin{eqnarray*}
\sqrt[3]{4} & = &   x / y \\
4       & = &   x^3 / y^3 \\
4 y^3       & = &   x^3
\end{eqnarray*}

In the last equation, the left side is even, and so the right side
must be even.  Since $x^3$ is even, $x$ itself must be even.  This
implies that the right side is actually divisible by 8, and so the
left side must also be divisible by 8.  Therefore, $y^3$ is even, and
so $y$ itself must be even.

The fact that both $x$ and $y$ are even contradicts the fact that $x /
y$ is a fraction in lowest terms.  Therefore, $\sqrt[3]{2}$ is not
sensible.  
}
\end{problem}


\begin{problem}
Translate the following sentence into a predicate formula:
\begin{quote}
There is a student who has e-mailed exactly two other people in the class,
besides possibly herself.
\end{quote}

The domain of discourse should be the set of students in the class; in
addition, the only predicates that you may use are equality and
$E(x,y)$, meaning that ``$x$ has sent e-mail to $y$.''


\solution{
A good way to begin tackling this problem is by trying to translate parts
of the sentance. Begin by trying to assert that student $x$ has emailed
students $y$ and $z$:
\[
E(x, y) \land E(x, z).
\]

Now we want to say that $y$ and $z$ not the same student, and neither of
them is $x$ either:
\[
x\neq y \land x \neq z \land y \neq z,
\]
where $x \neq y$ abbreviates $\neq(x = y)$.

Now, we must think of a way to say that the only people $x$ might have
e-mailed are $x$, $y$ and $z$:
\[
\forall s,\; E(x, s) \implies s = x \lor s = y \lor s = z.
\]

Finally, we can say there is some student who emailed exactly two other two
students by existentially quantifying $x,y$ and $z$.  So the complete
translation is
\begin{align}
\lefteqn{\exists x \exists y \exists z.\; E(x, y) \land E(x, z) \land}\\
& x \neq y \land x \neq z \land y \neq z \land\\
& \forall s,\; E(x, s) \implies s = x \lor s = y \lor s = z.
\end{align}}

\end{problem}


\begin{problem}
Express each of the following predicates and propositions in formal logic
notation.  The domain of discourse is the nonnegative integers,
$\naturals$.

In addition to the propositional operators, variables and quantifiers, you
may define predicates using addition, multiplication, and equality symbols,
but no \emph{constants} (like 0, 1, \dots).  For example, the proposition
``n is an even number'' could be written
\[
\exists m.\; (m + m = n).
\]

\begin{problemparts}
\problempart 
$n$ is the sum of three perfect squares.

\solution{
\[
\exists x \exists y \exists z.\; (x \cdot x + y \cdot y + z \cdot z = n)
\]
}
\end{problemparts}

Since the constant 0 is not allowed to appear explicitly, the predicate
``$x = 0$'' can't be written directly, but note that it could be expressed
in a simple way as:
\[
x + x = x.
\]
Then the predicate $x > y$ could be expressed
\[
\exists w.\; (y + w = x) \land (w \neq 0).
\]
Note that we've used ``$w \neq 0$'' in this formula, even though it's
technically not allowed.  But since ``$w \neq 0$'' is equivalent to the
allowed formula ``$\neg(w+w= w)$,'' we can use ``$w \neq 0$'' with the
understanding that it abbreviates the real thing.  And now that we've shown
how to express ``$x>y$'', it's ok to use it too.

\begin{problemparts}
\problempart $x > 1$.

\solution{
The straightforward approach is to define $x = 1$ as $\forall
y.\; xy=y$ and then express $x > 1$ as $\exists y.\; (y =1) \land (x >
y)$.
\iffalse
Another cute formula for $x > 1$ is $\neg (x \cdot x) = x$.  This works
because 0 and 1 are the only nonnegative integers equal to their own
squares.  But this formula doesn't generalize to, for example, defining $x
> 2$, while the straightforward approach does (see part~\eqref{G} below).
\fi
}

\problempart 
$n$ is a prime number.

\solution{
\[
\isprime(n) \eqdef (n > 1) \conj \neg (\exists x \exists y.\; (x > 1) \conj (y > 1) \conj (x \cdot y = n))
\]
}

\problempart 
$n$ is a product of two distinct primes.

\solution{
\[
\exists x \exists y.\; \neg (x = y) \land (n = x \cdot y) \land
\isprime(x)
\land \isprime(y).
\]
}

\problempart There is no largest prime number.

\solution{Of course this is a true statement, so it could be expressed by
the logically equivalent formula ``$1=1$,'' but even if we didn't know
this, we could transcribe the statement directly as:
\[
\neg \paren{\exists p.\; \isprime(p) \conj (\forall q.\; \isprime(q)
\implies p \geq q)}
\]
}

\problempart\label{G} (Goldbach Conjecture) Every even natural number $n > 2$ can
be expressed as the sum of two primes.

\solution{ We can define $n > 2$ with the formula $\exists y.\; (y =1)
\land (x > y + y)$.  Likewise, $n = 2k$ can be expressed as $n = k+k$.
Then we can express the Conjecture with:
\[
\forall n.\; \paren{(n > 2 \conj \exists k.\; n = 2k) \implies \exists p
\exists q.\; \isprime(p) \conj \isprime(q) \conj (n = p + q))}
\]
}

\problempart (Bertrand's Postulate) If $n > 1$, then there is always
at least one prime $p$ such that $n < p < 2n$.

\solution{
\[
\forall n.\;
\paren{(n > 1) \implies (\exists p.\; \isprime(p)  \conj (n < p) \conj (p < 2n))}
\]
}

\end{problemparts}
\end{problem}


\begin{problem}
If a set, $A$, is finite, then $\card{A} < 2^{\card{A}} =
\card{\power(A)}$, and so there is no surjection from set $A$ to its
powerset.  Show that this is still true if $A$ is infinite.  \hint Remember
Russell's paradox and consider $\set{x \in A \suchthat x
\notin f(x)}$ where $f$ is such a surjection.

\solution{ We prove there is no surjection by contradiction: suppose there
was a surjection $f:A \to \power(A)$ for some set $A$.  Let $W \eqdef
\set{x \in A \suchthat x \notin f(x)}$.  So by definition,
\begin{equation}\label{xw}
(x \in W) \iff (x \notin f(x))
\end{equation}
for all $x \in A$.  But $W \subseteq A$ by definition and hence is a member
of $\power(A)$.  This means $W = f(a)$ for some $a \in A$, since $f$ is a
surjection to $\power(A)$.  So we have from~\eqref{xw}, that
\begin{equation}\label{xf}
(x \in f(a)) \iff (x \notin f(x))
\end{equation}
for all $x \in A$.  Substituting $a$ for $x$ in~\eqref{xf} yields a
contradiction, proving that there cannot be such an $f$.}

\end{problem}

\begin{problem}
\bparts

\ppart Prove that
\begin{equation}\label{v}
\exists z.\; [P(z) \land Q(z)] \implies [\exists x.\; P(x) \land \exists
y.\; Q(y)]
\end{equation}
is valid.  (Use the proof in the subsection on Validity in Week 2 Notes as
a guide to writing your own proof here.)

\solution{
\begin{proof}
Assume
\begin{equation}\label{hyp}
\exists z.\; [P(z) \land Q(z)].
\end{equation}
That is, $P(z) \land Q(z)$ holds for some element, $z$, of the domain.
Let $c$ be this element; that is, we have $P(c) \land Q(c)$.

In particular, $P(c)$ holds by itself.  So we conclude (by Existential
Generalization)$\exists x\ P(x)$.  We conclude $\exists y\ Q(y)$
similarly.  Hence,
\begin{equation}\label{conc}
\exists x.\; P(x) \land \exists y.\; Q(y)
\end{equation}
holds.  

This shows that~(\ref{conc}) holds in any interpretation in
which~(\ref{hyp}) holds.  Therefore,~(\ref{hyp}) implies~(\ref{conc}) in
all interpretations, that is,~(\ref{v}) is valid.
\end{proof}}

\ppart Prove that the converse of~(\ref{v}) is not valid by describing a
counter model as in Week 2 Notes.

\solution{
\begin{proof}
We describe a counter model in which,~(\ref{conc}) is true and~(\ref{hyp})
is false.  Namely, let the domain, $D$, be $\set{\pi, e}$, $P(x)$ mean
``$x = \pi$,'' and $Q(y)$ mean ``$y = e$.''  Then, $\exists x.\; P(x)$ is
true (let $x$ be $\pi$) and likewise $\exists y.\; Q(y)$ is true (let $y$
be $e$), so~(\ref{conc}) holds.

On the other hand, $Q(\pi)$ is not true, so $P(\pi) \land Q(\pi)$ is not
true.  Likewise $P(e) \land Q(e)$ is not true.  Since these are the only
elements of $D$, it is not true that there is an element, $z$, of $D$,
such that $P(z) \land Q(z)$,  That is,~(\ref{hyp}) is not true.
\end{proof}}
\eparts

\end{problem}

\begin{problem}

\bparts
\ppart Give an example where the following result fails:

\begin{falsethm*}
For sets $A$, $B$, $C$, and $D$, let
\begin{align*}
L \eqdef (A \union C) \times (B \union D),\\
R \eqdef (A \times B) \union (C \times D).
\end{align*}
Then $L=R$.
\end{falsethm*}

\solution{
If $A=D=\emptyset$ and $B$ and $C$ are both nonempty, then $L = C \times B
\neq \emptyset$, but $R = \emptyset$.
}

\ppart Identify the mistake in the following proof of the False Theorem.

\begin{bogusproof}
Since $L$ and $R$ are both sets of pairs, it's sufficient to prove that
$(x,y) \in L \iff (x,y) \in R$ for all $x,y$.

The proof will be a chain of iff implications:

\begin{tabular}{lc}
$(x, y) \in L$ & iff \\
$x \in A \union C$ and $y \in B \union D$, & iff \\
either $x \in A$ or $x \in C$, and either $y \in B$ or $y \in D$, & iff \\
($x \in A$ and $y \in B$) or else ($x \in C$ and $y \in D$), & iff\\
$(x,y) \in A \times B$, or $(x,y) \in C \times D$, & iff \\
$(x,y) \in (A \times B) \union (C \times D) = R$.
\end{tabular}

\end{bogusproof}

\solution{The mistake is in the third ``iff.''  If [$x \in A$ or $x \in
C$, and either $y \in B$ or $y \in D$], it does not necessarily follow
that $(x,y) \in (A \times B) \union (C \times D)$.  It might be that
$(x,y)$ is in $A \times D$ instead.  This happens, for example, if $A =
\set{1}, B = \set{2}, C = \set{3}, D = \set{4}$, and $(x,y) = (1, 4)$.}

\ppart Fix the proof to show that $R \subseteq L$.

\solution{
Replacing the third ``iff'' by ``which will be true when,'' yields a
correct proof that $(x,y) \in L$ will be true when $(x,y) \in R$, which
implies that $R \subseteq L$.
}

\eparts

\end{problem}

\end{document}
