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

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

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

\hidesolutions
%\showsolutions

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

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


\begin{problem}
Use proof by contradiction to show that $\log_{5} 8$ is irrational.

\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.}
\end{problem}


\begin{problem}
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*}


\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.
}
\end{problem}




\begin{problem}
Translate the following sentence into a predicate formula:
\begin{quote}
There is a student who has e-mailed at most 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 
\begin{itemize}
\item equality, and
\item $E(x,y)$, meaning that ``$x$ has sent e-mail to $y$.''
\end{itemize}


\solution{
A good way to begin tackling this problem is by trying to translate parts
of the sentence. First of all, our formula must be of the form
\[
\exists x. P(x)
\]
where $P(x)$ should be a formula that says that ``student $x$ has
e-mailed at most two other people in the class, besides possibly
herself''.

One way to write $P(x)$ is to write that ``whenever we meet a student
that has been e-mailed by $x$, this student is either $x$ herself or
$y$ or $z$, where $y$ and $z$ are two students in the class.''

To write the part ``whenever we meet a student that has been e-mailed
by $x$, this student is either $x$ herself or $y$ or $z$'' we write
\[
\forall s.
E(x,s) 
\implies
s=x \vee
s=y \vee
s=z.
\]
The part ``where $y$ and $z$ are two students in the class'' simply
means that there exist two such students; so by adding the appropriate
existential quantifiers, we get
\[
P(x)::=\quad
\exists y.
\exists z.\;\;
\forall s.
E(x,s) 
\implies
s=x \vee
s=y \vee
s=z
\]
At this point you may be thinking that $P(x)$ says that ``$x$ has
e-mailed \emph{exactly} two students besides possibly
herself''. However, note that we did not require that $y$ and $z$ be
distinct, or that they be different from $x$.  So, our formula 
describes all possibilities: 
\begin{itemize}
\item $x$ and exactly 2 other students: $x\neq y$, $x\neq z$, $y\neq z$.
\item $x$ and exactly 1 other student: $x\neq y$ $x\neq z$, $y=z$.
\item $x$ and no other student: $x=y=z$.
\end{itemize}
Overall the full formula is:
\[
\exists x.\;\;
\exists y.
\exists z.\;\;
\forall s.
E(x,s) 
\implies
s=x \vee
s=y \vee
s=z.
\]
}

\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$. Moreover, 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) and no \emph{exponentiation} (like $x^y$).  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 two cubes (a cube is a number equal to $k^3$ for some
integer $k$).

\solution{
\[
\exists x \exists y.\; (x \cdot x \cdot x + y \cdot y \cdot y = 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{
One formula is $\forall y.\; xy=y$.  Another is $(x \cdot x = x) \conj (x
\neq 0)$.
}

\ppart $m$ is a divisor of $n$ (notation: $m \divides n$)

\solution{\[
m \divides n 
\eqdef\quad 
\exists k.\; k \cdot m = n
\]}

\problempart 
$n$ is a prime number (hint: use the predicates from the previous parts)

\solution{
\[
\isprime(n)
\eqdef\quad 
(n\neq 1) 
\;\;\conj\;\;
\forall m.\; (m \divides n) \implies (m=1 \disj m=n).
\]
Note that the requirement $n\neq 1$ is necessary, or else our
predicate would be satisfied by 1, which is not considered to be a
prime number. Also note that $n\neq 1$ is given here as an
abbreviation of the formula $\neg(n=1)$; and thus of $\neg\forall y.yn=n$.

If we don't want to use the divisor predicate, we can write:
\[
\isprime(n) 
\eqdef\quad 
(n\neq 1) 
\;\;\conj\;\;
\neg\bigl(
\exists x 
\exists y.\; 
(x > 1) \conj 
(y > 1) \conj 
(x \cdot y = n)
\bigr).
\]
Do you agree this formula is also correct? If so, note that the
formulas $x>1$ and $y>1$ are not allowed. Can you express them in
terms of allowed formulas?  }

\problempart $n$ is a power of 2.

\solution{We can simply say that the only divisors of $n$ are 1 and 2:
\[
\forall m.\; m \divides n \implies m =1 \disj m=2
\]
Still, $m=2$ is not allowed, so we have to express it in terms of
allowed formulas. Here is one way to do this:
\[
m=2
\eqdef\quad
\exists z.
z=1
\;\conj\;
m= z + z
\]
}
\end{problemparts}
\end{problem}



\begin{problem}  Prove that
\[  %\begin{equation}\label{v}
[\forall x.\; \neg P(x)] \implies \neg \exists z.\; P(z).
\]  %\end{equation}
is valid.  (Use the validity proof from lecture 2W and from the subsection
on Validity in Week 2 Notes as guides to writing your proof.)

\solution{
\begin{proof}
Assume
\begin{equation}\label{eq:1}
\forall x.\; \neg P(x).
\end{equation}

Now we prove by contradiction that $ \neg \exists z.\; P(z)$ holds.
Namely, we assume $\exists z.\; P(z)$ and reach a contradiction.

So suppose $\exists z.\; P(z)$ holds.  So there is an element, $c$,
such that $P(c)$.  But from~\eqref{eq:1}, we know that $\neg P(c)$
holds, contradicting the fact that $P(c)$ holds.  Hence, the
assumption $\exists z.\; P(z)$ must be false, that is, $\neg \exists
z.\; P(z)$ is true.
\end{proof}}

\end{problem}


\begin{problem}  %verbatim from fall 05 ps1:

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$.  Consider the
set of all elements of $A$ that do \emph{not} belong to their image under $f$:
\[
W \eqdef \set{x \in A \suchthat x \notin f(x)} .
\]  
By the definition of this set, we know that for all $x \in A$:
\begin{equation}\label{xw}
(x \in W) \iff (x \notin f(x)) .
\end{equation}
But $W \subseteq A$ (by the definition of $W$), and hence $W$ is a member
of $\power(A)$.  Since $f$ is a surjection onto $\power(A)$,  
this means that $W = f(a)$ for some $a \in 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}
Let $A$, $B$, and $C$ be sets.
Prove that:
%
\[
A \cup B \cup C = (A - B) \cup (B - C) \cup (C - A) \cup (A \cap B \cap C).
\]
%
You are welcome to use a diagram to aid your own reasoning, but your
proof must be text.

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

First, we show that the left side is contained in the right side.  Let $x$
be any element of $A \cup B \cup C$.  Then $x$ belongs to at least 
one of $A$, $B$, and $C$.  We distinguish two cases.
\begin{itemize}
\item $x$ belongs to all three sets: Then $x$ belongs to the
intersection $A\cap B\cap C$. 

\item $x$ does \emph{not} belong to all three sets: Then at least one
of $A$, $B$, $C$ does not contain $x$.  So overall, at least one set
contains $x$ and at least one set doesn't. We distinguish cases:
\begin{itemize}
\item If $A$ contains $x$, then one of $B$ and $C$ must not contain
it. 
\begin{itemize}
\item If $B$ does not contain it, then $x\in A-B$. 
\item If $B$ contains it, then $C$ does not, therefore $x\in B-C$.
\end{itemize}

\item If $A$ does \emph{not} contain $x$, then one of $B$ and $C$ must  
contain it. 

\begin{itemize}
\item If $C$ does, then $x\in C-A$. 
\item If $C$ does not contain it, then $B$ does, therefore $x\in B-C$. 
\end{itemize}
\end{itemize}
\end{itemize}
In all cases, we end up with $x$ being a member of one of 
$A - B$, $B - C$, $C - A$, or $A\cap B\cap C$.  Therefore, it belongs
to the right side. Hence, 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.  This is
easier. Let $x$ belong to the right side. Then it belongs to one of $A
- B$, $B - C$, $C - A$, or $A\cap B\cap C$.  In the first case, we
clearly know $x\in A$. In the second case, $x\in B$. In the third
case, $x\in C$. In the last case, $x\in A$ again. So, in all cases,
$x$ belongs to one of $A$, $B$, or $C$. So $x$ belongs to the left
side. Therefore, the set on the right is contained in the set on the
left.

Since each set is contained in the other, they are equal.}

\end{problem}


\begin{problem} %verbatim form Fall 05

\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{center}
\begin{tabular}{ll}
    & $(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) $ \\
iff & $(x,y)\in R$.
\end{tabular}
\end{center}

\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}
