\documentstyle[12pt,twoside,amstex]{article}

\input{macros-course}

\begin{document}

\tutn{1}{2/5/98}{February 5, 1999}

\section{Predicate logic}

Consider the statement, ``Every cloud has a silver lining''.  To say this
more formally, let the variable $x$ range over a {\em universe of
discourse} which is the set of all clouds and let $\mbox{SL}(x)$ stand for
the proposition ``$x$ has a silver lining.''  Then we can write:
\[\forall x : \mbox{SL}(x)\]
Here the symbol $\forall$ means ``for every'' or ``for all''.

Often we have variables ranging over different sets, and it's clearer if
we explicitly indicate the intended range of each variable.
If we let $C$ be the set of clouds, then
another way to express ``Every cloud has a silver lining'' as a logical
formula is
\[\forall x \in C: \mbox{SL}(x)\]
which is shorthand for
\[\forall x: x \in C \implies \mbox{SL}(x).\]
In this last version, the domain of discourse of $x$ need not be mentioned
--- as long as it is understood to include all the clouds.

Other examples: Let $D$ be the set of children.  Then ``Every child is a
boy or a girl,'' can be restated as
\[\forall x \in D : \mbox{Boy}(x) \vee \mbox{Girl}(x).\]

The symbol $\exists$ means ``there exists'' or ``there is at least
one''.  So, e.g., ``There is an easy way out'' can be expressed:
\[\exists x : \mbox{Easy}(x) \wedge \mbox{Way-out}(x).\]

These symbols, $\exists$ and $\forall$, are called {\em quantifiers}.
They can be used together (and also repeatedly), e.g., ``There is a tallest
man'' can be written as
\[\exists x \forall y : \mbox{Man}(x) \wedge
[\mbox{Man}(y) \implies \mbox{Taller}(x,y).]\]

``Every tennis tournament has a winner'' is
\[\forall x \in \mbox{tournaments} \exists y \in \mbox{player}: y \mbox{
wins } x.\]

Notice that the order of the quantifiers can change the meaning of the
statement.  For example the above statement with quantifiers reversed is
\[\exists y \in \mbox{player}\forall x \in \mbox{tournaments} : y \mbox{
wins } x.\]
which means that there is a champion who wins all the tournaments, whereas the 
earlier version only meant that each tournament has a winner, not necessarily
the same person.

For proposition $P$, we represent ``not $P$'' as $\neg P$ or
$\overline{P}$.  What happens to quantifiers when they are negated?  To
express the fact that no element $x$ satisfies proposition $P$, we write
$\neg \exists x : P$.  This is the same as saying that every element does
not satisfy $P$, written $\forall x : \neg P$.  Similarly, $\neg \forall
x: P$ is equivalent to $\exists x: \neg P$.

What is the negation of the statement ``Every dog has its day''?  
We can express the negation as
$\neg \forall x \in \mbox{dogs}: \mbox{Has-a-day}(x).$
Then using the rule above, this is the same as
\[\exists x \in \mbox{dogs}: \neg\mbox{Has-a-day}(x).\]
In other words, there is a dog that does not have its day.

{\em DeMorgan's Law} says that
\[\neg (P \wedge Q) \mbox{ is equivalent to } (\overline{P} \vee \overline{Q}).\]

Using DeMorgan's Law and the rules for negating quantifiers, we now know that
\[\neg\forall x,y\exists z \forall w \exists v : (P \wedge \overline{Q}) \vee
\neg(P \wedge R \wedge S)\]
is equivalent to
\[\exists x,y\forall z \exists w \forall v : (\overline{P} \vee Q) \wedge
(P \wedge R \wedge S).\]

How do we say there are \emph{at least} two boys in the class?
\[\exists x, y \in 6.042 : \mbox{Boy}(x) \wedge \mbox{Boy}(y) \wedge (x \neq y)\]

\textbf{Class exercise}: How do we say there are \emph{exactly} two boys
in the class?

\emph{Answer}:  Say that there are at least two, and that every boy in the
class equals one or the other of the two:
\[
\exists x, y \in 6.042 : \left[\mbox{Boy}(x) \wedge \mbox{Boy}(y)
\wedge (x \neq y)
\wedge [\forall z \in 6.042 : \mbox{Boy}(z) \implies (z = x \vee z = y)]\right]
\]

\section{Proofs about sets}

In this section we carefully prove the following identity.  
\begin{lemma}
For all sets $A,B,C$,
\[A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\]
\end{lemma}

This is known as the {\em distributive law of set intersection} and will
be useful later in the course.

\begin{proof}
Let $X = A \cap (B \cup C)$ and $Y = (A \cap B) \cup (A \cap C)$.
Then we will show that 
\begin{enumerate}
\item  $X \subseteq Y$ {\em and} 
\item  $Y \subseteq X$.
\end{enumerate}

This will show that $X$ and $Y$ must be the same set.

\begin{itemize}
\item   $X \subseteq Y$.

Let $x$ be any element of $X$. Then $x \in A$ and $x \in (B \cup C)$.

That is $x$ is in $A$ and also in $B$ or in $C$. 
Let us examine these cases separately:
 \begin{enumerate}
  \item $x$ is in $B$.  Then $x$ is in $A \cap B$.
  \item $x$ is in $C$. Then $x$ is in $A \cap C$. 
 \end{enumerate}

Therefore $x$ is in $A \cap B$ or in $A \cap C$.
That is, $x$ is always an element in their union, 
$x \in (A \cap B) \cup (A \cap C)$. 

\item \textbf{Class exercise}: Prove conversely, that $Y \subseteq X$.

\emph{Answer}:
Suppose $x\in Y$, i.e., $x \in (A \cap B) \cup (A \cap C)$.
There are two cases:
\begin{enumerate}

\item $x$ is in $A\cap B$. Then $x \in A$ and $x\in B$.  Since $x\in B$,
it is also in $B \cup C$.  So $x \in A$ and $x\in B\cup C$.  Therefore, $x
\in A \cap (B \cup C) = X$.

\item $x$ is in $A\cap C$.  By the same argument as the previous case with
$B$ and $C$ reversed, we conclude that $x \in A \cap (C \cup B) = A \cap
(B \cup C) = X$.
\end{enumerate}

So in either case $x \in X$.
\end{itemize}

\end{proof}

\section{Proof by contradiction}

Here's one of many generalizations of the proof from lecture that
$\sqrt{2}$ is irrational.

\begin{lemma}
Let the coefficients of the polynomial $a_0+a_1x+a_2x^2+\ldots+x^n$ 
be integers.  Then any root of the polynomial is either integral or 
irrational.
\end{lemma}

\textbf{Class exercise}: How does this Lemma imply that $\sqrt{2}$ is
irrational?

\emph{Answer}: $x^2 - 2$ has no integer root because neither 0, 1, -1 are
roots, and when $\abs{k} > 1$, then $k^2 > 2$, so $k^2 - 2 > 0$.  This
eliminates all the integers, so by the Lemma, the root must be irrational.

\begin{proof}

Let $y$ be a root of the polynomial, that is,
\[a_0+a_1y+a_2y^2+\ldots+y^n = 0.\]
There are three cases in which to classify $y$: it is either integral,
irrational, or the ratio of two integers with no common divisors where the
denominator is greater than one.  We want to eliminate the last case.

Assume that $y = s/t$
for integers $s$ and $t$ which have no common divisors and such that $t >1$.
Substituting $s/t$ for $y$ and multiplying both sides of the above
equation by $t^n$ yields: 
\[ a_0t^n+a_1st^{n-1}+a_2s^2t^{n-2}+\ldots+st^{n-1}+s^n = 0.\]

\[ a_0t^n+a_1st^{n-1}+a_2s^2t^{n-2}+\ldots+s^{n-1}t = -s^n.\]

Let $p$ be a prime divisor of $t$. Then $p$ divides the lefthand side of
the above equation, and therefore also the righthand side, viz., $p \mid
-s^n$.  But this means that $p$ must divide $s$.  Since we assumed $s$ and
$t$ have no common divisors this is a contradiction.

\end{proof}

Note that we are using an ``obvious'' fact about natural numbers: if a
prime $p$  divides $s^n$ for integer $n \geq 0$, then $p$ divides $s$.

\emph{Class exercise}: What's a quick counterexample if $p$ is not prime?
\emph{Answer}: $9 \mid 3^3$ but \emph{not} $9 \mid 3$.

Actually this fact is more ``familiar'' than completely obvious.

\emph{Class exercise}:  How would you justify this fact to a friend who
didn't see why it was true.

\begin{proof}
Write $s$ as a product of prime powers $p_1^{k_1} p_2^{k_2}~ \cdots
~p_t^{k_l}$.  So $s^n ~=~ p_1^{n k_1} p_2^{n k_2}~ \cdots ~p_t^{n k_l}$.
But factorization of a number into primes is unique (this is the
Fundamental Theorem of Arithmetic, which will be examined more fully next
week).  So if $p$ divides $s^n$, it has to equal one of the $p_j$'s, and
therefore, $p$ also divides $s$.
\end{proof}


\section{Proof by cases}

We have already seen proofs involving cases (e.g., the proof of the
distributive law).  Now we look at another problem that involves
cases. The key to such proofs is to make sure that we cover {\em all} the
cases.

\emph{Class Exercise} You are given 3 identical looking balls, and told
that one of them is heavier than the other two.  Can you find the heavy
ball in one weighing with a balance scale?

\emph{Answer}:
Place one ball on each pan of the balance. 
There are 3 possible outcomes:
\begin{enumerate}
\item The left pan is heavier. Then the ball in the left pan is the
answer.
\item The right pan is heavier. Then the ball in the right pan is the
answer.
\item The pans are equal. Then the third ball must be the heavy one!
\end{enumerate}

\section{Team problems}

%Now we'll work out some tougher problems.

\begin{problems}

\problem Scheme, and many other programming languages, allows procedures to
take themselves as arguments.  For example, in Scheme we can define
a \texttt{perverse} procedure:
\begin{verbatim}
    (define (perverse f)
       (if   (and (number? (f f)) (zero? (f f)))   1   0)))
\end{verbatim}
Then evaluating
\begin{verbatim}
    (perverse (lambda (proc) 0))
\end{verbatim}
returns 1, while evaluatng
\begin{verbatim}
    (perverse (lambda (proc) proc))
\end{verbatim}
returns 0.
\bparts

\ppart What happens when Scheme evaluates \texttt{(perverse +)}?

\emph{Answer}: Evaluation of \texttt{(perverse +)} will lead to an
evaluation of \texttt{(+ +)} which results in an error, at which point the
whole evaluation will abort wioth an error, since in Scheme, \texttt{+}
may only apply to numbers.

\ppart What happens when Scheme evaluates \texttt{(perverse perverse)}?

\emph{Answer}: Evaluation of \texttt{(perverse perverse)} will lead to an
evaluation of \texttt{(perverse perverse)} which will lead to an
evaluation of \texttt{(perverse perverse)} \dots.  That is, evaluation will
continue indefinitely with no output (other than heat \texttt{:-)}.

\ppart Now let's get away from Scheme procedures --- which are
mathematically a little murky --- and define a real \emph{mathematical}
function, $p$, which can be applied to any function of one variable.  The
function $p$ is defined as follows:
\[p(f) = \left\{\begin{array}{ll}
               1 & \mbox{if $f(f)$ is defined and it equals 0,}\\
               0 &  \mbox{otherwise.}
               \end{array} \right. \]

Now by this definition, $p(f)$ is defined to be either 1 or 0 for all
functions $f$.  Also, whenever $f(f)$ happens to be defined,
\[p(f) \neq f(f).\]

In particular, we can choose $f$ to be $p$, and reach the nonsensical
conclusion that 
\[p(p) \mbox{ is defined and } p(p) \neq p(p)!\]

Carefully explain where this argument goes wrong.
\eparts

\emph{Answer}: A mathematician would say that the argument went wrong at
the start with the implicit assumption that the rule given above actually
defined a mathematical function $p$.

We know from Russell's paradox why mathematicians forbid sets to be
members of themselves.  In fact, not only can't sets be members of
themselves, they can't be members of members of themselves, or members of
members of members, etc.  In mathematics functions can't apply to
themselves either, exactly to avoid the kind of contradiction illustrated
above.  This already follows from the set restriction on self-membership:
a function is represented as the set of all ordered pairs whose first
element, $d$, is in the domain of the function and whose second element is
the value of the function at $d$.  In order for $f$ to apply to itself,
one of the $d$'s would have to be $f$, so $f$ would be a member of an
ordered pair which is a member of itself.


\iffalse
\problem Prove that
\[\forall k \in \naturals\ :\ (\sqrt{2})^k \mbox{ is rational iff $k$ is even.}\]
\fi

\problem You are given 12 identical looking balls, and told that one of
them is of different weight from the other 11, but you don't know in
advance whether it is heavier or lighter.  Can you find the ball that is of
different weight using only 3 weighings on a balance scale?


{\bf Solution:} The answer is Yes.

Step 1. Divide into groups of 4 balls. Place two of these groups
on two pans.

Two possible outcomes: 
\begin{enumerate}
\item Equal. So the 8 balls that were weighed must be of the same weight,
label them N (for ``normal'') and one of the other 4 is of different weight,
call them D.  

  Step 2. Place 3 D balls on one side and 3 N balls on the other side for
the second weighing.
Three possible outcomes again:
\begin{enumerate}
 \item Equal. The remaining D must be the ball of different weight.
 \item DDD side is heavier. So the ball of different weight is among these
three and heavier. Now we can finish in one more weighing using
the approach done in the tutorial.
 \item DDD side is lighter. Similar to previous case.
\end{enumerate}

\item Not Equal.  Call the heavier side balls H and the lighter side balls L.
Then there are 4 H's , 4 L's and 4 N's (the 4 that we didn't weigh are of
the same weight).

  Step 2. Place 3 H's and 1 L on one side and 1 H and 3 N's on the other side
for the second weighing. There are 3 possible outcomes:

\begin{enumerate}
\item Equal. The ball of different weight is among the remaining 3 L's
and is lighter. We can find it in one more weighing.

\item 3 H's , 1 L side is heavier. Then one of the three H's must be
heavier than the rest. We can find it in one more weighing.

\item 3 H's , 1 L side is lighter. Then either the L on this side is
lighter than the rest or the H on the other side is heavier than the rest.
We can compare one of them with an N ball and find the ball of different
weight!
\end{enumerate}

\end{enumerate} %two cases for first weighing

\end{problems}

\end{document}


