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

\showsolutions

\begin{document}

\recitation{1}{February 2, 2005}

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

\section{Logic}

A \term{proposition} is a statement that is either true or false.
Propositions can be joined by ``and'', ``or'', ``not'', ``implies'',
or ``if and only if''.  For each of these connective, the definition
and notational shorthand are given in the table below.  Here $A$ and
$B$ denote arbitrary propositions.
%
\[
\begin{array}{cc|ccccc}
 &  & A \text{ and } B & A \text{ or } B & \text{not } A & A \text{ implies } B & A \text{ if and only if } B \\
A & B & A \wedge B & A \vee B & \neg A & A \implies B & A \iff B \\ \hline
\true & \true & \true & \true & \false & \true & \true \\
\true & \false & \false & \true & \false & \false & \false \\
\false & \true & \false & \true & \true & \true & \false \\
\false & \false & \false & \false & \true & \true & \true
\end{array}
\]
%
A \term{predicate} is a proposition whose truth depends on the value
of one or more variables.  If $P$ is a predicate, then
%
\[
\forall x \in S\ P(x)
\]
%
means that the predicate is true for every value of $x$ in the set $S$.
Similarly,
%
\[
\exists x \in S\ P(x)
\]
%
means that the predicate is true for at least one value of $x$ in the
set $S$.

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

\newpage

\section*{Team Problem:  A Mystery}

\newcommand{\C}{C}

% Define the course staff here.

\newcommand{\Eric}{\text{Eric }}
\newcommand{\Tom}{\text{Srini }}
\newcommand{\Albert}{\text{Christos }}
\newcommand{\Claire}{\text{Grant }}
\newcommand{\Edmond}{\text{Ishan }}
\newcommand{\Florent}{\text{Sally}}
\newcommand{\Nick}{\text{Theory Pig }}

A certain cabal within the 6.042 course staff is plotting to make the
final exam \textit{ridiculously hard}.  (``Problem 1.  Derive all of
known mathematics from first principles.  Express your answer in Mayan
hieroglypics.'')  The only way to stop their evil plan is to determine
exactly who is in the cabal.  The course staff consists of seven
people:
%
\[
\set{\Eric, \Tom, \Albert, \Claire, \Edmond, \Florent, \Nick }
\]
%
(\Florent is the course secretary and \Nick is our mascot.)
The cabal is a subset of these seven.  A membership roster has been
found and appears below, but it is deviously encrypted in logic
notation.  The predicate $\C$ indicates who is in the cabal; that is,
$\C(x)$ is true if and only if $x$ is a member.  Translate each
statement below into English and deduce who is in the cabal.

\begin{enumerate}[\upshape (i)]

\item\label{eee} $\exists x \ \exists y \ \exists z \
    (x \neq y \wedge
     x \neq z \wedge
     y \neq z \wedge
     \C(x) \wedge \C(y) \wedge \C(z))$

\solution[\vspace{0.3in}]{A direct English paraphrase would be ``There
exist people we'll call $x,y$, and $z$, who are all different, such that
$x,y$ and $z$ are each in the cabal.''  A better version would use the
fact that there's no need in this case to give names to the people.
Namely, a better paraphrase is ``There are 3 different people in the
cabal.''  Perhaps a simpler way to say this is: ``The cabal is of size at
least 3.''}

\item\label{nNC} $\neg (\C(\text{\Nick}) \wedge \C(\text{\Claire}))$

\solution[\vspace{0.3in}]{\Nick and \Claire are not both in the cabal.
Equivalently: at least one of \Nick and \Claire is not in the cabal.}

\item\label{Fall} $\C(\text{\Florent}) \rightarrow \forall x \ \C(x)$

\solution[\vspace{0.3in}]{If \Florent is in the cabal, then everyone is.}

\item\label{CN} $\C(\text{\Claire}) \rightarrow \C(\text{\Nick})$

\solution[\vspace{0.3in}]{If \Claire is in the cabal, then \Nick is also.}

\item\label{EAnT}
$(\C(\text{\Edmond}) \vee \C(\text{\Albert})) \rightarrow \neg \C(\text{\Tom})$

\solution[\vspace{0.3in}]{If either of \Edmond or \Albert is in the cabal,
then \Tom is not.  Equivalently, if \Tom \emph{is} in the cabal, the neither
\Albert nor \Edmond is.}

\item\label{ENnE}
$(\C(\text{\Edmond}) \vee \C(\text{\Nick})) \rightarrow \neg \C(\text{\Eric})$

\solution[\vspace{0.3in}]{If either of \Edmond or \Nick is in the cabal,
then \Eric is not.  Equivalently, if \Eric \emph{is} in the cabal, the
neither \Edmond nor \Nick is.  }
\end{enumerate}

\insolutions{So much for the translations.  We now argue that the only
cabal satisfying all six propositions above is one whose members are
exactly \Nick, \Edmond, and \Albert.

We first observe that by~\eqref{nNC}, there must be someone -- either \Nick
or \Claire -- who is not in the cabal.  But if Flo were in the cabal, then
by~\eqref{Fall}, everyone would be.  So we conclude by contradiction
that:

\begin{equation}\label{nF}
\text{\Florent is not in the cabal.}
\end{equation}

Next observe that if \Claire was in the cabal, then by~\eqref{CN}, \Nick would
be too, contradicting~\eqref{nNC}.  So by again contradiction, we conclude:
\begin{equation}\label{nC}
\text{\Claire is not in the cabal.}
\end{equation}

Now suppose \Tom is in the cabal.  Then by~\eqref{EAnT}, \Edmond and \Albert
are not, and we already know \Florent and \Claire are not, so only three remain
who could be in the cabal, namely, \Tom, \Nick, and \Eric.  But
by~\eqref{eee} the cabal must have at least three members, so it follows
that the cabal must consist of exactly these three.  This proves:
\begin{lemma}\label{TNE}
\text{If \Tom is in the cabal, then \Nick and \Eric are in the cabal.}
\end{lemma}

But by~\eqref{ENnE}, if \Nick is the cabal, then \Eric is not.  That is, 
\begin{lemma}\label{NnE}
\text{\Nick and \Eric cannot both be in the cabal.}
\end{lemma}
Now from Lemma~\ref{NnE} we conclude that the conclusion of
Lemma~\ref{TNE} is false.  So by contrapositive, the hypothesis of
Lemma~\ref{TNE} must also be false, namely,
\begin{equation}\label{nT}
\text{\Tom is not in the cabal.}
\end{equation}

Finally, suppose \Eric is in the cabal.  Then by~\eqref{ENnE}, \Edmond
and \Nick are not, and we already know \Florent, \Claire and \Tom are not. So
the cabel must consist of at most two people (\Albert and \Eric). This
contradicts~\eqref{eee}, and we conclude by contradiction that
\begin{equation}\label{nE}
\text{\Eric is not in the cabal.}
\end{equation}
So the only remaining people who could be in the cabal are \Albert, \Edmond,
and \Nick.  Since the cabal must have at least three members, we conclude
that
\begin{lemma}
The only possible cabal consists of \Albert, \Edmond, and \Nick.
\end{lemma}

But we're not done yet: we haven't shown that a cabal consisting of
\Albert, \Edmond, and \Nick actually does satisfy all six conditions.  So let
$\mathcal{A} =\set{\text{\Albert}, \text{\Edmond}, \text{\Nick}}$, and let's quickly
check that $\mathcal{A}$ satisfies~\eqref{eee}--\eqref{ENnE}:

\begin{itemize}

\item $\size{A} = 3$, so $A$ satisfies~\eqref{eee}.
\item \Claire is not in $A$, so $A$ satisfies~\eqref{nNC} and~\eqref{CN}.
\item \Florent is not in $A$, so the hypothesis of~\eqref{Fall} is false, which
means that $A$ satisfies~\eqref{Fall}.
\item Finally, \Tom and \Eric are not in $A$, so the conclusions of
both~\eqref{EAnT} and~\eqref{ENnE} are true, and so $A$
satisfies~\eqref{EAnT} and ~\eqref{ENnE}.

\end{itemize}

So now we have proved
\begin{proposition*}
$\set{\text{\Albert}, \text{\Edmond}, \text{\Nick}}$ is the \emph{unique} cabal
satisfying conditions~\eqref{eee}--\eqref{ENnE}.
\end{proposition*}}

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

\newpage

\section*{Team Problem:  Swapping Quantifiers}

Suppose $P$ is predicate that depends on two variables that take on
values in the set $S$.  Here are two propositions:
%
\begin{align}
\left(\forall x \in S\ \exists y \in S\ P(x, y)\right) \implies
\left(\exists y \in S\ \forall x \in S\ P(x, y)\right) \tag{1} \\
\left(\exists y \in S\ \forall x \in S\ P(x, y)\right) \implies
\left(\forall x \in S\ \exists y \in S\ P(x, y)\right) \tag{2}
\end{align}
%
\bparts

\ppart Give an example of a predicate $P$ and set $S$ that makes one
of these propositions false.  (The set $S$ can be anything you choose:
colors, animals, food, people, etc.).

\solution[\vspace{2in}]{Let $S$ be the set of all people who have ever
lived, and let $P(x, y)$ be the proposition that ``the mother of
person $x$ is person $y$''.

Then the left side of the first proposition is true; every person has
a mother.  However, the right side is not true; there is not a single
person who is everyone's mother.  Thus, the first proposition as a
whole is false.}

\ppart Explain why the other proposition is always true.

\solution{The left side of the second proposition asserts that there
exists a $y$--- call it $y_0$--- such that $P(x, y)$ is true regardless
of the value of $x$.  This implies that the right side of the
proposition is also true; for every $x$ there exists a $y$ (namely,
$y_0$) such that $P(x, y)$ is true.}

\eparts

\end{document}
