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

% add not exists = forall not

%\hidesolutions
\showsolutions

\newcommand{\card}[1]{\left|#1\right|}

\newcommand{\C}{\textit{incabal}}

\begin{document}

\recitation{1}{September 10, 2004}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\insolutions{
\section{Logic}

How can one discuss mathematics with logical precision, when the
English language is itself riddled with ambiguities?  For example,
what exactly does this sentence mean?
%
\begin{center}
You may have cake or ice cream.
\end{center}
%
Does this mean that you may have \textit{both} cake and ice cream?  Or
must you choose just one?

To cope with such ambiguities, mathematicians have defined precise
meanings for some key words and phrases.  Furthermore, they have
devised symbols to represent those words.  For example, if $P$ is a
proposition then ``not $P$'' is a new proposition that is true
whenever $P$ is false and vice versa.  The symbolic representation for
``not $P$'' is $\neg P$ or $\overline{P}$.

Two propositions, $P$ and $Q$, can be joined by ``and'', ``or'',
``implies'', or ``if and only if'' to form a new proposition.  The
truth of this new proposition is determined by the truth of $P$ and
$Q$ according to the table below.  Symbolic equivalents are given in
parentheses.

\begin{center}
\begin{tabular}{cc|cccc}
 & & & & ``$P$ implies $Q$'' or & ``$P$ if and only if $Q$'' or \\
 & & ``$P$ and $Q$'' & ``$P$ or $Q$'' & ``if $P$, then $Q$'' &  ``$P$ iff $Q$'' \\
$P$ & $Q$ & $(P \wedge Q)$ & $(P \vee Q)$ & $(P \implies Q)$ & $(P \iff Q)$ \\ \hline
F & F & F & F & T & T \\
F & T & F & T & T & F \\
T & F & F & T & F & F \\
T & T & T & T & T & T
\end{tabular}
\end{center}

There are a couple notable features hidden in this table:

\begin{itemize}

\item The phrase ``$P$ or $Q$'' is true if $P$ is true, $Q$ is true,
or both.  Thus, you can have your cake and ice cream too.

\item The phrase ``$P$ implies $Q$'' (equivalently, ``if $P$, then
$Q$'') is true when \textit{$P$ is false or $Q$ is true}.  Thus, ``if
the moon is made of green cheese, then there will be no final in
6.042'' is a true statement.

\end{itemize}

There are two more important phrases in mathematical writing: ``for
all'' (symbolized by $\forall$) and ``there exists'' (symbolized by
$\exists$).  These are called \term{quantifiers}.  A quantifier is
always followed by a variable (and perhaps an indication of the range
of that variable) and then a predicate, which typically involves that
variable.  Here are two examples:
%
\begin{gather*}
\forall\ x \in \mathbb{R}^+ \quad e^x < (1+x)^{1+x} \\
\exists\ n \in \mathbb{N} \quad 2^n > (100 n)^{100}
\end{gather*}

The first statement says that $e^x$ is less than $(1+x)^{1+x}$ for
every positive real number $x$.  The second statement says that there
exists a natural number $n$ such that $2^n > (100 n)^{100}$.

The special symbols such as $\forall$, $\exists$, $\neg$, and $\vee$
are useful to logicians trying to express mathematical ideas without
resorting to English at all.  And other mathematicians often use these
symbols as a shorthand.  We recommend using them sparingly, however,
because decrypting statements written in this symbolic language can be
challenging!

\section{Proving an Implication}

Let's try to prove the following theorem.

\begin{theorem}
\label{th:quantifier-swap}
Let $P(a, b)$ be any predicate defined for all $a \in {\cal A}$ and $b
\in {\cal B}$.  Then:
\[
\bigl(\exists\ a \in {\cal A} \quad \forall\ b \in {\cal B} \quad P(a, b)\bigr)
\quad \implies \quad
\bigl(\forall\ b \in {\cal B} \quad \exists\ a \in {\cal A} \quad P(a, b)\bigr)
\]
\end{theorem}

Yuck! Now you \textit{know} you're in a math class!  Let's impose a
specific interpretation in order to give concrete meaning to this
claim.  Define:
%
\begin{align*}
{\cal A} & = \set{\text{6.042 students}} \\
{\cal B} & = \set{\text{6.042 lectures}} \\
P(a, b) & = \text{``student $a$ falls asleep during lecture $b$''}
\end{align*}

Interpreting the left side in these terms gives:
%
\[
\exists\ a \in {\cal A} \quad \forall\ b \in {\cal B} \quad P(a, b)
= \text{``there exists a student that falls a sleep in every lecture''}
\]
%
So this side asserts that some particular student--- let's call him
Snoozer--- always falls asleep.  Now on the right side, we have:
%
\[
\forall\ b \in {\cal B} \quad \exists\ a \in {\cal A} \quad P(a, b)
= \text{``in every lecture, some student falls asleep''}
\]
%
This is a slightly different assertion, because there might be a
different sleeper in each lecture.  Intuitively, the left side should
imply the right; if Snoozer sleeps in every lecture, then in every
lecture some student is surely asleep.

The implication in Theorem~\ref{th:quantifier-swap} is actually true for
\textit{every} predicate $P$ and choice of sets ${\cal A}$ and ${\cal B}$.
A universally-true statement, like this one, is called a \term{validity}.
(Every tautology (\emph{cf.} Lecture Notes 9/9. p.6) is a validity, but
validities may also involve quantifiers.)  The \term{converse} of an
implication $P \implies Q$ is the reverse implication $Q \implies P$.  In
this case, the converse is:
%
\[
\bigl(\forall\ b \in {\cal B} \quad \exists\ a \in {\cal A} \quad P(a, b)\bigr)
\quad \implies \quad
\bigl(\exists\ a \in {\cal A} \quad \forall\ b \in {\cal B} \quad P(a, b)\bigr)
\]
%
Under our interpretation, this says, ``If in every lecture some student
falls asleep, then there is some student who falls asleep in every
lecture.''  This is not \emph{necessarily} true, although it might be true
for certain choices of predicate and sets. \iffalse would be true if every
student but one dropped the class.\fi But since the truth of this converse
proposition depends on the particular choice of predicate and sets, it is
\textit{not} a validity.

Anyway, let's prove the theorem.

\begin{proof}
We consider two cases.

\begin{tabular}{rp{5.2in}}

Case 1: & Suppose that the left side of the implication is
false.  Then the claim as a whole is true by default. \\
\\
Case 2: & \framebox{\begin{minipage}[t]{4.8in} Suppose that the left
side of the implication is true.  Then there exists some element $a_0
\in {\cal A}$ such that $P(a_0, b)$ is true for all $b \in {\cal B}$.
Thus, for all $b \in {\cal B}$ there exists an $a \in {\cal A}$
(namely, $a_0$) such that $P(a, b)$ is true.  Therefore, the right
side of the implication is also true.\end{minipage}}

\end{tabular}

In both cases, the left side implies the right side, and so the
theorem holds.
\end{proof}

Broadly speaking, we just proved that $P \implies Q$ for some
nasty-looking propositions $P$ and $Q$.  When $P$ was false (case 1),
the implication held trivially.  When $P$ was true (case 2), we had to
do some work to show that $Q$ was also true.  Every implication proof
has this same structure: all the substance is in case 2.  Thus,
ordinarily no one even bothers to write down case 1 or even to
identify two cases!  Instead, when proving an implication, you may
dispense with everything except for the body of case 2; the boxed text
alone is considered a valid proof of the theorem.  In summary,
\textit{in order to prove that $P$ implies $Q$, you should assume that
$P$ is true and prove that $Q$ is also true subject to that
assumption.}
\newpage
}

\section{Team Problem:  A Mystery}

A certain cabal within the 6.042 course staff is plotting to make the
final exam \textit{ridiculously hard}.  (``Problem 1.  Prove that the
axioms of mathematics are complete and consistent.  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{\text{Nick}, \text{Edmond}, \text{Claire}, \text{Florent},
\text{Albert}, \text{Tom}, \text{Eric}}
\]
%
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{Flo 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 Flo 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 Flo, 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 $\card{A} = 3$, so $A$ satisfies~\eqref{eee}.
\item Claire is not in $A$, so $A$ satisfies~\eqref{nNC} and~\eqref{CN}.
\item Flo 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*}}

\end{document}
