Class 12: Review

Exam Review

Below are some notations you should understand. We use variables $P$ and $Q$ to represent logical propositions (with \T\ or \F\ value), $A$ and $B$ and $D$ (domain of discourse) to represent sets, and $x$ represents any mathematical object.

\begin{tabular}{cl} \multicolumn{2}{c}{\bf Logical Operators}
$P$ \smallcaps{implies} $Q$, $P \implies Q$ & Logical implication: when $P$ is \T, $Q$ must be \T
$P$ \smallcaps{iff} $Q$, $P \iff Q$ & Double implication: $P \implies Q \vee Q \implies P$
\smallcaps{not}$(P)$, $\neg P$, $\overline{P}$ & Logical negation
$P$ \smallcaps{and} $Q$, $P \wedge Q$ & Logical conjunction (\T\ when both $P$ and $Q$ are \T)
$P$ \smallcaps{or} $Q$, $P \vee Q$ & Logical disjunction (\T\ when $P$ or $Q$ is \T\ (or both)
$P$ \smallcaps{xor} $Q$, $P \oplus Q$ & Exlusive or (\T\ when either $P$ or $Q$ is \T, but not both
\multicolumn{2}{c}{\bf Quantifiers}
$\forall x \in A \ldotp P(x)$ & $P(x)$ for {\em every} element $x$ of the set $A$
$\exists x \in A \ldotp P(x)$ & $P(x)$ for {\em at least one} element $x$ of the set $A$
\multicolumn{2}{c}{\bf Set Operators}
$x \in A$ & Set membership, $A$ contains the element $x$
$x \notin A$ & Set non-membership, $A$ does not contain $x$
$A \subseteq B$ & $A$ is a subset of $B$: $\forall x \in A. x \in B.$
$A = B$ & set equality: $A \subseteq B \vee B subseteq A$
$A \cup B$ & Set Union: $\forall x. x \in A \cup B \iff x \in A \vee x \in B.$
$A \cap B$ & Set Intersection: $\forall x. x \in A \cup B \iff x \in A \wedge x \in B.$
$ A - B$ & Set Difference: $\forall x. x \in A - B \iff x \in A \wedge x \notin B.$
$ \overline{A}$ & Set Complement: $\forall x. x \in D. x \in \overline{A} \iff x \notin A.$
$ A \times B$ & Cartesian Product: $\forall a \in A, b \in B \ldotp (a, b) \in A \times B.$
$ \textrm{pow}(A)$ & Power Set: $S \in A \iff S \subseteq A$.
\end{tabular}

Well-Ordering Principle

Remember the well-ordering principle template from Class 3:

To prove that $P(n)$ is true for all $n \in \mathbb{N}$:

1. Define the set of counterexamples, $C ::= { n \in \mathbb{N} | NOT(P(n)) }$.
2. Assume for contradiction that $C$ is non-empty.
3. By the well-ordering principle, there must be some smallest element, $m \in C$.
4. Reach a contradiction (this is the creative part!). One way to reach a contradiction would be to show $P(m)$. Another way is to show there must be an element $m’ \in C$ where $m’ < m$.
5. Conclude that $C$ must be empty, hence there are no counter-examples and $P(n)$ always holds.

Since we didn’t finish the winning strategy proof in class, I’ve written it out fully here.

Theorem. Player 1 has a winning strategy in Take-Away if the number of sticks, $n$ is not divisible by 4.

For any induction proof, the first thing we need to do is write the theorem as a predicate on the natural numbers.

$$\forall n \in \mathbb{N} \ldotp P(n) ::= \textrm{ Player 1 has a winning strategy if }\exists a \in { 1, 2, 3 }, \exists k \in \mathbb{N} \textrm{ such that } n = 4k + a.$$

Base cases: $P(1)$, $P(2)$, $P(3)$.

$P(1)$: If there is $1$ stick remaining, Player 1 wins by taking 1 stick.
$P(2)$: If there are $2$ sticks remaining, Player 1 wins by taking 2 sticks.
$P(3)$: If there are $3$ sticks remaining, Player 1 wins by taking 3 sticks.

Inductive case: Using strong induction, $\forall m \in \mathbb{N}, m \ge 4 \ldotp (\forall k \in \mathbb{N}, k \le m. P(k)) \implies P(m + 1)$.

Since $m \ge 4$ we can write $m = 4k + b$ for some $k \in \mathbb{N}^{+}$ and $b \in {0, 1, 2, 3}$.

We consider four cases for each value of $b$.

Case 3: $b = 3$. Since $m = 4k + 3$, $m + 1 = 4k + 4 = 4(k + 1)$. Since $m + 1$ is divisible by 4, $P(m+ 1)$ holds because the predicate makes no claims when $n$ is divisible by 4.

Cases 0, 1, 2: Since $m = 4k + b$ for $b \in {0, 1, 2}$, we know $m + 1 = 4k + c$ for $c \in {1, 2, 3}$ (since $c = b + 1$ to produce $m + 1$). We need to show $P(m+1)$, which means showing that player 1 has a winning strategy for $n = 4k + c$, $c \in {1, 2, 3}$. Player 1 takes $c$ sticks, leaving $4k$ sticks.

For the next turn, Player 2 can remove 1, 2, or 3 sticks, leaving $4k - d$ sticks, $d \in {1, 2, 3}$. This can be simplified to $4(k - 1) + e$ sticks where $e = 4 - d$ since $4k - 4 + (4 - d) = 4k - d = 4(k - 1) + e$. Hence, after Player 2’s turn it will be Player 1’s turn with $4(k - 1) + e$ sticks, $e \in {1, 2, 3}$. We know $4(k - 1) + e < m$ and it is not divisible by 4. So, Player 1 has a winning strategy from $P(m + 1)$ since she has a move to make such that no matter what move player 2 makes, it leads to a number that is not divisible by 4 and is less than $m$, which we know is a position where Player 1 has a winning strategy but strong induction.

Note that $4(k - 1) + e$ is $m - 1$, $m - 2$ or $m - 3$, so we need to know $m \ge 4$ for this to be valid. That’s why we needed three base cases!