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

\addtolength{\topmargin}{-1in}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9in}

\raggedbottom

\input{macros-course}

\iffalse
\setlength{\topmargin}{-0.50in}
\setlength{\textheight}{8.5in}
\setlength{\oddsidemargin}{0.0in}
\setlength{\evensidemargin}{-0.0in}
\setlength{\textwidth}{6.5in}
\addtolength{\parskip}{2pt}
\addtolength{\itemsep}{0.1in}
\newtheorem{theorem}{Theorem}
\newtheorem{definition}{Definition}
\newtheorem{claim}{Claim}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newcommand{\qed}{\mbox{\ \ \ }\rule{6pt}{7pt} \bigskip}
\fi
\newtheorem{fact}{Fact}
\begin{document}

\handout{rec1}{Notes for Recitation 1 (2/6/98)}{February 12, 1998}


\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''.
Another way to say the same thing is to let the universe of discourse be
all objects and let $C$ be the set of clouds.  Now we write:
\[\forall x \in C: \mbox{SL}(x)\]
which is shorthand for
\[\forall x: x \in C \implies \mbox{SL}(x).\]

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 always 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 the same person wins every tournament whereas all the 
earlier version meant was 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).\]

\section{Proofs about sets}

In this section we carefully prove the following identity. Below
$A,B,C$ are finite sets.
\begin{lemma}
$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.

{\em 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{enumerate}
\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 $Y \subseteq X$.

Let $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$.
\item $x$ is in $A\cap C$. Then $x \in A$ and $x\in C$.
\end{enumerate}

Therefore $x$ is in $A$, and $x$ is in $B\cup C$
That is $x$ is in $A \cap (B \cup C)$.

$x\in X$.
\end{enumerate}


\qed


\section{Proof by contradiction}

\iffalse  This was used as a problem on PS1

\begin{lemma}
For any integers $m$ and $n$, $^m\sqrt{n}$, the 
$m^{th}$ root of $n$ is either an integer or
irrational.
\end{lemma}

So for example the lemma tells us that $\sqrt{2}$, $4^{1/3}$, $10^{1/5}$ 
are all irrational numbers.\\

{\em Proof. } 
Every real number is either an integer, or a ratio of two integers with
the denominator greater than 1, or irrational. Let us assume for the
purpose of getting a contradiction that for some integers $m,n$ the 
number $n^{1/m}$ is of the second kind, i.e., it is the ratio of two 
integers with the denominator greater than 1.
$$ n^{1/m} = {a \over b}$$ 
for some integers $a,b$ which have no common divisors greater than $1$ 
and $b \not{=} 1.$

Rearranging terms, 
$$a^m - nb^m = 0$$
Let $p$ be a prime divisor of $b$ (such a prime divisor exists since 
$b >1$). 
Then $a^m$ must also be divisible
by the same prime. By the fundamental theorem of arithmetic (prime factorization theorem) this means that $p$ is a divisor of $a$. 
But then since we assumed that $a,b$ have no common divisors, this is a 
contradiction.
\qed

Using the same idea as above we can prove the following more general
statement.
\fi

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

{\em Proof.} 
Let $x$ be a root of the polynomial, that is,
\[a_0+a_1x+a_2x^2+\ldots+x^n = 0.\]
There are three cases in which to classify $x$: 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.

Let us assume for a contradiction that $x = s/t$
for integers $s$ and $t$ which have no common divisors and such that $t >1$.
Substituting $s/t$ for $x$ 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.\]
So
\[ 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 abov equation, and therefore also the rihgthand side, viz., $-s^n$.
Therefore $p$ divides $s$.  Since we assumed $s,t$ have no common divisors
this is a contradiction.  \qed

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

{\em 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 using one weighing of a physical 
balance?}

{\em Solution.}
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{enumerate}
\item Prove that 
\[\forall k \in \naturals\ :\ (\sqrt{2})^k \mbox{ is rational iff k is even.}\]

\item The {\em Gale game}\footnote{J. Daniel Christensen and Mark Tilford,
``David Gale's Subset Take-Away Game,'' American Mathematical Monthly v.105
(Jan.1998)} described in lecture is played on a finite set,
$A$, of size two or more, e.g., $A$ might be the set of integers from 1 to
$n\ge 2$.  Two players alternate moves.  A {\em move} is a choice of a
{\em proper} subset (that is, a nonempty subset of $A$ other than $A$
itself), subject to the constraint that no subset may be chosen which {\em
contains} a previously chosen subset.  The player who first gets stuck
without an allowed move loses.

For example, when $A = \{1, 2, 3, 4\}$, the moves might be:
\[
\begin{array}{ccccccccc}
player: & 1 &2 & 1 &2 & 1 &2 & 1 &2\\
move:   &\{1,2\} &\{3,4\} & \{1,3\} & \{2,4\} & \{1\} & \{2\} & \{3\} & \{4\}\\
\end{array}
\]
At this point, the first player has no valid move and therefore loses.

{\em Gale's Conjecture} is that the second player can always win.  Note
that this does not mean that the second player {\em will} win every game.
He can lose if he plays stupidly, but there always is a way for the second
to win no matter what moves the first player makes.  (This is like the
situation in tic-tac-toe, where the first player {\em can} lose by playing
stupidly, but has a simple {\em strategy} which guarantees that he will never
lose.)

(a) Prove Gale's Conjecture for the games with $n=2$ and 3.

{\bf Solution}:
When $n=2$, $A=\{1,2\}$.  The first player can only choose a singleton
set consisting of one of the two elements.  The second player just chooses
the other one and wins.

When $n=3$, the first player can have two choices: choosing a subset
containing 1 element or 2 elements.  Whatever the first player's choice
is, the second player simply picks the complement of the first player's
choice.  The game is then reduced to the case when $n=2$. Therefore,
Gale's Conjecture holds for $n=2,3$.

\medskip
(b) Must every Gale game end with a winner (remember, chess games don't)?
What is the length of the longest, and shortest, possible games on
$\{1,\dots,n\}$?  Explain.

{\bf Solution}:
The game will always end with a winner, because there are a finite number
of legal moves in any game, and no move can be reused.  Therefore the game
will come to an end after a number of steps at most equal to the number of
possible moves.

The set $A$ with $n$ elements has $2^n$ different subsets.  Since choosing
$\emptyset$ and $A$ itself is not allowed in the game, there are exactly
$2^n-2$ possible moves.  So the longest possible game would have at most
$2^n-2$ moves.  It is possible to have this many moves in a game: the
players could choose all the subsets of size of $n-1$ first, followed by
those with size of $n-2$, and so on, down to subsets with size of 1.  Such
a sequence of moves is allowed because all the moves prior to any given
move in the sequence are subsets at least as large as the given move, so
none of them is contained in the given move.

The shortest possible game would last for $n$ steps. In such a game the
players always choose subsets containing one element.  When all the $n$
such sets are chosen, no more valid moves remain.  It is not possible to go
below $n$ steps because the $n$ subsets with size 1 can always be picked
if they are not picked before.

\medskip
(c) Try to prove Gale's Conjecture for $n=4$.  Hint: you will be
overwhelmed with cases if you don't identify "symmetric" cases.  For
example, if player 1's first move is $\{1,2,3\}$, and you work out how
player 2 will win, then you can adapt your strategy to work against {\em
any} first move consisting of a set of size three, by permuting the roles
of 1, 2, 3, and 4.

{\bf Solution}: There are three cases for the move of the first player
when the game starts:

\begin{enumerate}
\item The first player chooses a subset of 1 element.  The second player
then should choose the complement of the first player's choice.  The game
then becomes the same as playing the $n=3$ game on the set just chosen by
the second player.

\item The first player chooses a subset of 3 elements.  The second player
should choose the complement of the first player's choice.  The game then
becomes the same as playing the $n=3$ game on the set just chosen by the
first player.

\item The first player chooses a subset of 2 elements $C_1=\{a,b\}$.  The
second player then picks the complement of the first player's choice,
$C_2=\{c,d\}$.  We then have the following cases:
\begin{enumerate}

\item If the first player choose a subset of one element contained in
$C_1$ or $C_2$, say, $\{a\}$, the second player can choose the subset containing
only the element which remains in the same set, i.e., $\{b\}$.  The game
is then reduced to the case when $n=2$.

\item
If the first player chooses a subset of two elements --- necessarily one
element from $C_1$ and the other from $C_2$, say, $\{a,c\}$.  The second
player chooses the complement of it, $\{b,d\}$.  We have two remaining
possible subcases:
\begin{enumerate}

\item If the first player chooses one of the remaining sets of size two,
say $\{a,d\}$, player two should choose its complement, $\{b,c\}$.  The
remaining possible moves are the four sets of size 1, where the second
player clearly wins after two more rounds.

\item If the first player chooses a set of 1 element in $C_1$ or $C_2$,
say, $\{a\}$, player two should choose the set containing only the element
remaining in the set, i.e., $\{b\}$.  The game is then reduced to the case
when $n=2$.
\end{enumerate}
\end{enumerate}
\end{enumerate}
Therefore, player also has a winning strategy in the Gale game for $n=4$. 


\iffalse

\item  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?
\fi

\end{enumerate}

\end{document}

