\documentclass[11pt,twoside]{article}
\input{../handouts/macros-course}
\usepackage{graphics}

\textwidth=6.5in
%\topmargin=-.15in
%\evensidemargin=0.75in
%\oddsidemargin=0.7pt
%\newcommand {\pindent} {\hspace*{20pt}}
\textheight=9.5in
\parskip=12pt plus 2pt minus 2pt
\pagestyle{empty}
\setlength{\parindent}{0in}
\newcommand{\pagetitle}[1]{\newpage {\bf #1} \hfill
L4$-$P. \thepage \\ \vspace{-0.5cm} \hrule \vspace{12mm}}
\newcommand{\doublespace}{\addtolength{\baselineskip}{.35\baselineskip}}
%\newcommand{\remove}[1]{}

\begin{document}

\renewcommand{\thepage}{\arabic{page}}


\Huge

\remove{
\pagetitle{Strong induction}

\noindent
Ordinary induction:

\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXX\=    \kill
Prove: $\forall n \geq 0 (P(n))$ \\
1. (Base) $P(0)$ \\
2. (Inductive step) $\forall n \geq 0 (P(n) \Rightarrow P(n+1))$ \\
3. QED
\> \> \> \> \> Induction
\end{tabbing}

\noindent
Strong induction:

\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXX\=    \kill
Prove: $\forall n \geq 0 (P(n))$ \\
1. (Base) $P(0)$ \\
2. (Inductive step)
$\forall n \geq 0 [(\forall i, 0 \leq i \leq n (P(n)))$\\
 $\Rightarrow P(n+1)]$ \\
3. QED
\> \> \> \> \> Strong induction
\end{tabbing}

\noindent
Observation: to prove $P(n+1)$, we can
assume $P(0),P(1),P(2),\ldots,P(n)$

\pagetitle{Strong Induction\\ Blocks and Towers}

\noindent
Given an unlimited number of blocks of heights 3 and 7,
what height towers can be built?

\noindent
Observation: if we can build towers of height $n$,$n+1$,$n+2$
then we will be able to build a tower of height $y \geq n+3$,\\
we have a $3$ block.

\noindent
Base for the strong induction will be $n=12$ (3+3+3+3), $n+1=13$
(7+3+3), $n+2=14$ (7+7). Cannot build a tower of e.g. 5,8,11.

\noindent
Step assuming it is correct for all $12 \leq i \leq n$, where $n \geq 14$,
(strong induction)\\
and proving for $n+1$.

\noindent
Use the observation

\pagetitle{Strong Induction -- Nim }

\noindent
Some positive number of sticks are place on the ground.
Two players take turns removing 1, 2, or 3 sticks.
The player to remove the last stick loses.

\noindent
Theorem --- the first player loses if the number of sticks, $n$,
is $4k+1$ for some $k$, and wins (if plays optimally) otherwise.

\noindent
$n=1$ the first losses\\
$n=2$, $n=3$, $n=4$ the first wins

\noindent
if $n=4k+1$ the first loses\\
$n=4k$, $n=4k+1$, $n=4k+2$ and $n=4k+3$ the first player wins.

\pagetitle{Strong Induction -- Nim }

\noindent
Suppose the theorem is true for all numbers $<n$, show for $n$

\noindent
Base: $n=1$ the first losses

Step:\\
$n=4k+1$ --- the first player can remove only $1 \leq x < 4$ letting the 
second player remove $4-x$...\\
\\
$n=4k$ --- the first player can remove $3$ reaching $n=4(k-1)+1$.\\
\\
$n=4k+2$ --- the first player can remove $1$ reaching $n=4k+1$.\\
\\
$n=4k+3$ --- the first player can remove $2$ reaching $n=4k+1$.\\


\pagetitle{Strong Induction -- Fibonacci }

$F_0=0$, \\
$F_{n+1}=F_{n-1}+F_n$\\
\\
All Fibonacci numbers are even:
\\
Base: $F_0$\\
(Strong) Induction step: true for all $0 \leq i \leq n$ therefore
true for $n+1$\\
\\
WRONG\\
The base case does not include information for $F_1$\\
(which cannot be a function of $F_{-1}$ and $F_0$).\\

\pagetitle{Strong Induction -- Fibonacci }

\noindent
Lemma $\forall n \geq 2$ it holds that $(F_n \geq (\frac{3}{2})^{n-2})$

\noindent
Use strong induction

\noindent
Base: $F_2=1\geq (3/2)^0$, $F_3=2 \geq (3/2)$.\\
\\
Induction step: prove $F_{n+1}\geq (3/2)^{n-1}$ given $F_{i} \geq (3/2)^{i-2}$
for all $1 \leq i<n+1$.
\\
$F_{n+1}=F_{n-1}+F_{n}$\\
$F_{n-1}+F{n} \geq (3/2)^{n-3}+(3/2)^{n-2} \geq (3/2)^{n-1}$\\
(for $x>0$ $(3/2)x+x \geq (3/2)^2x$, \\
choose $x=(3/2)^{n-3}$)\\
$F_{n+1} \geq (3/2)^{n-1}$\\

\pagetitle{Strong Induction --\\ Prime Factorization}

\noindent
Theorem: Every natural number $\geq 2$ can be written as the product of one or
more primes.

\noindent
Strong induction: \\
\\
Base: $n=2$\\
Step: assume for all $2 \leq i \leq n$ and\\
prove for $n+1$.\\
if $n+1$ is not a prime then we can write $n+1=a \times b$,
where $a$ and $b$ are smaller than $n+1$. \\
By the induction hypothesis both $a$ and $b$ can be factored
into primes.


\pagetitle{Tournaments}

\noindent
Every player plays with every other player exactly once (no ties)

\noindent
A beats B,C,D\\
B beats D\\
C beats B\\
D beats C

\noindent
Theorem: Any tournament that contains an $n-$cycle, 
contains a cycle of length $3$ ($3$-cycle).

\noindent
(ordinary induction) assume for $n$ and prove for $n+1$

\noindent
Base: $n=3$

\noindent
Step: Let $p_1 \rightarrow p_2 \rightarrow p_3 \rightarrow
\cdots \rightarrow p_{n+1} \rightarrow p_1$ be the $n+1$-cycle.\\
\\
Examine the arrow between $p_1$ and $p_3$\\
if $p_3 \rightarrow p_1$ we are done\\
otherwise, we have a $n$-cycle $p_1 \rightarrow p_3 \rightarrow \cdots
\rightarrow p_{n+1} \rightarrow p_1$\\
Use the induction hypothesis.

\pagetitle{Tournaments --\\ Locally Fair Ranking}

Cycles, but at least the right neighbors in ranking...

\noindent
Theorem Any n-player tournament has a locally fair ranking

\noindent
Base: n=1\\
Induction step: choose a player $x$,\\
$B$ the set of players that beat $x$\\
and $L$ the set of players that lose to $x$\\

\noindent
Use induction assumption for $B$ and $L$\\
then define a ranking of all players: $B$ ranking, then $x$, then $L$ ranking.
}%end remove


\pagetitle{Lecture Overview}

\noindent
Induction, Strong Induction, and Well-Ordering\\
\\
Structural induction\\
\\
Induction and Recursive Algorithms\\
\\
Sets\\

\pagetitle{Induction, Strong Induction,\\ and Well-Ordering}

\noindent
You may state the predicate of the Induction such that
it includes all $i$'s

\noindent
$Q(n)$ $\forall i$, $2 \leq i \leq n$ $i$ can be factored,
and prove $Q(n)$ using ordinary induction.

\noindent 
The induction and strong induction have ``identical power''

\pagetitle{Induction, Strong Induction,\\ and Well-Ordering}

\noindent
Well-ordering: 

\noindent
Axiom: Every nonempty subset $S \subseteq N$ has a smallest element

\noindent
Theorem: Any tournament that contains a cycle contains a 3-cycle.

\noindent
Let $n$ be the smallest cycle length in a tournament. \\
$n$ must be at least $3$.\\
Suppose $n \geq 4$.\\
Consider the arrow between $p_1$ and $p_3$.\\
Either close a 3-cycle\\
or yields a shorter cycle contradicting
the assumption that $n$ is smallest...

\pagetitle{Structural induction}

\noindent
Not only induction over $N$,\\
Proofs for data types that are defined recursively\\

\noindent
{\bf Fully parenthesized Boolean algebra}

\noindent
Definition: the set of fully parenthesized boolean expressions $F$\\
1. 0 and 1\\
2. if $e,e' \in F$ then $(e \wedge e') \in F$.\\
3. if $e,e' \in F$ then $(e \vee e') \in F$.\\
4. if $e \in F$ then $(\neg e) \in F$.\\
5. $F$ contains nothing else.

\noindent
Theorem Every Boolean expression has the same number of left and right parentheses.

\noindent
Base: 0 and 1

\noindent 
Inductive step: \\
steps 1-4 preserve the assertion (if $e$ and $e'$ satisfy the assertion
so does the result).

\pagetitle{Structural induction,\\ Binary trees}

\noindent
Definition: the set of binary trees $T$\\
1. A single node is in $T$\\
2. if $t$ is in $T$, then an addition of a root node $r$ and an arrow
connecting $t$ to be the
left child (subtree) of the root is also in $T$\\
3. if $t$ is in $T$, then an addition of a root node $r$ and an arrow
connecting $t$ to be the 
right child (subtree) of the root is also in $T$\\
4. if $t$ and $t'$ are in $T$, then an addition of a root node $r$  
and two arrows, where
$t$ is the left child and $t'$ is the right child is also in $T$\\

\pagetitle{Structural induction,\\ Binary trees}

\noindent
Theorem: The number of edges in any binary tree is exactly
one fewer than the number of nodes.

\noindent
Base: a single-node tree

\noindent 
Inductive step: \\
Steps 2 and 3 of the construction preserves the assertion:\\
 ---- $t$ has $n-1$ edges and a node and an edge are added.\\
Steps 4 of the construction preserves the assertion:\\
 ---- $t$ and $t'$ has $n-1$ and $n'-1$ edges, respectively.
1 node is added (total $n+n'+1$) and 2 edges are added
(total $(n-1)+(n'-1)+2=n+n'$ edges).\\

\pagetitle{Structural induction,\\ Strings over alphabet A}

\noindent
Definition: the set $S$ of (finite length) strings over alphabet $A$:\\
1. $\lambda$, the empty string, is in $S$.\\
2. If $s$ is in the set $S$ and $a\in A$, then $sa$ is in $S$.\\
3. $S$ contains nothing else.

\noindent
To prove a property $P(s)$ for strings over alphabet $A = \{ 0,1 \}$:

\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXX\=    \kill
Prove: $\forall s \in S (P(s))$ \\
1. (Base) $P(\lambda)$ \\
2. (Inductive step) $\forall s \in S~~ (P(s) \Rightarrow P(s 0))$ \\
3. (Inductive step) $\forall s \in S~~ (P(s) \Rightarrow P(s 1))$ \\
4. QED
\> \> \> Structural induction on strings.
\end{tabbing}

\pagetitle{Structural induction,\\ Strings over alphabet A}

\noindent
Theorem: In a string of 0s and 1s, the number of occurrence of the
pattern 01 $num(01,s)$ is less than or equal to the number of occurrence 
of 10 $num(10,s)$, plus one.

\noindent
It turned out that it is better to have a stronger induction predicate.\\
(Adding 1 at the end may increase $num(01,s)$)

\noindent
$num(01,s)\leq num(10,s)+1$, and\\
If $s$ ends in 0 then $num(01,s) \leq num(10,s)$\\
(Thus, addition of 1 at the end will not violate our main predicate).

\noindent 
Base: $\lambda$\\
Step: \\
1. (*(Inductive step) $\forall s \in S~~ (P(s) \Rightarrow P(s0))$*) \\
\\
1a. if $s$ ends in $0$ then $num(01,s0)=num(01,s)$ and $num(10,s0)=num(10,s)$\\
o.k.\\
\\
1b. if $s$ ends in $1$ then $num(01,s0)=num(01,s)$ and $num(10,s0)=num(10,s)+1$\\
We should show that $num(01,s0) \leq num(10,s0)$ given\\
$num(01,s)\leq num(10,s)+1$, replacing terms we get\\
$num(01,s0)\leq num(10,s0)$ as needed.\\
\\
2. (*(Inductive step) $\forall s \in S~~ (P(s) \Rightarrow P(s1))$*) \\
\\
2a. if $s$ ends in $0$ then $num(01,s1)=num(01,s)+1$ and $num(10,s1)=num(10,s)$\\
We should show that $num(01,s1)\leq num(10,s1)+1$ given\\
$num(01,s) \leq num(10,s)$, replacing terms we get\\
$num(01,s1) - 1 \leq num(10,s1)$ as required\\
\\
2b. if $s$ ends in $1$ then $num(01,s1)=num(01,s)$ and $num(10,s1)=num(10,s)$\\
o.k.

\pagetitle{Induction and Recursive\\ Algorithms}

\noindent 
Why use induction?\\
Induction and computation is one step at a time.\\

\noindent
Can any $2^n$ by $2^n$ board be tiled with Ls ?\\
the inductive proof is actually a {\it procedure}:\\
break the board to four, tile each piece, and merge the tiling.\\

\noindent
This is a {\it recursive} algorithm --- it calls itself on smaller
subproblems.

\noindent
The ranking $B$, $L$ and $x$ is similar.

\pagetitle{Induction and Recursive Algorithms --\\ RSA and Exponentiation}

\noindent
RSA is used in secure communication protocols SSH, SSL, etc.

\noindent
Computes remainder $r$ of $x^a$ on division by $b$, where $a$ and $b$ are
specially constructed {\it large} numbers.

\noindent
If you know the right secret about the origin of $a$ and $b$ then you get $x$.

\noindent 
We will try to calculate the Exponentiation:

\noindent
$x^0=1$\\
$x^n=x\cdot x^{n-1}$

\noindent
\begin{tabbing}
\= xxx \= xxx \= xxx \kill
Procedure ${Exp}(x,n)$\\
\\
{\bf if} $n=0$\\
\> return 1\\
{\bf else}\\
\> return $x*Exp(x,n-1)$
\end{tabbing}

\pagetitle{Induction and Recursive Algorithms --\\ Exponentiation}

\noindent
Theorem:
For all $x,n \in N$, a call to $Exp(x,n)$ returns $x^n$

\noindent 
We should prove that the algorithm does not run forever\\
\\
The algorithm returns the right value\\

\noindent
By induction on $n$\\
Base: $Exp(x,0)=x^0=1$\\
Step: Assume $Exp(x,n)$ returns $x^n$ and prove for $Exp(x,n+1)$\\
the {\bf else} is chosen calling $Exp(x,n)$, which returns $x^n$,\\
thus we return $x^{n+1}$.

\noindent
$n$ has 128 bits, we should call the procedure $2^{128}$ times........ 

\pagetitle{Induction and Recursive Algorithms --\\ Fast Exponentiation}

\noindent
if $x^a=x^{2c}$ ($a$ is even)\\
then compute $y=x^c$ and then $y^2$.\\
\\
Otherwise, ($a$ is odd)\\
then compute $y=x^{a-1}$ and then $y\cdot x$.

\begin{tabbing}
\= xxx \= xxx \= xxx \= \kill
Procedure $FastExp(x,n)$\\
\\
{\bf if} $n=0$\\
\> return 1\\
{\bf else}\\
\> {\bf if} $n$ is even\\
\> \> let $y=FastExp(x,n/2)$\\
\> \> return $y^2$\\
\> {\bf else}\\
\> \> let $y=FastExp(x,(n-1)/2)$\\
\> \> return $x*y^2$
\end{tabbing}

\pagetitle{Induction and Recursive Algorithms --\\ Fast Exponentiation}

\noindent
Theorem: For all $x,n \in N$, a call to $FastExp(x,n)$ returns $x^n$

\noindent
Base: $n=0$\\
Step: (strong induction) true for every $k<n$ and prove for $n$\\
$n$ is even, say $n=2m$ then we call $FastExp(x,m)$, by strong
induction $y=x^m$, thus we return $(x^m)^2=x^n$ as required.\\
$n$ is odd, say $n=2m+1$ then we call $FastExp(x,m)$, by strong
induction $y=x^m$, thus we return $x \cdot (x^m)^2=x^{2m+1}$\\
Proof works for all cases.

\pagetitle{Induction and Recursive Algorithms --\\ Fast Exponentiation Cont.}

\noindent
no more than 256 multiplications ...

\noindent
Theorem: If $n>1$ has $b$ bits, then $FastExp(x,n)$ performs at most
$2b$ multiplications.

\noindent
Base: $b=2$ then $n=0$, $n=1$, $n=2$, $n=3$ \\
if $n=0$ then we do not multiply\\
if $n=1$ we multiply $3<4$ times ($x\cdot 1^2$)\\
if $n=2$ we multiply $2<4$ times ($y^2$)\\
if $n=3$ we multiply $3<4$ times ($x \cdot x^2$)\\
\\
Step: we assume $b$ and prove for $b+1$\\
We execute recursive call with $n/2$ or $(n-1)/2$\\
both have $b$ bits, by induction $2b$ multiplications.\\
Then we do either 1 (even case) or 2 more (odd case) multiplications.\\
Thus overall at most $2b+2$\\

\pagetitle{Induction and Recursive Algorithms --\\ Greatest Common Divisor}

\noindent
Given 2 positive natural numbers, $a,b \in N^+$, their 
{\it greatest common divisor} (GCD) is the largest number that
divides both without remainder.

\noindent
Euclid's algorithm

\noindent
Lemma: Given $x>y$, let $r=x-y$.  Then any common divisor of $x$ and $y$ is
also a common divisor of $y$ and $r$, and vice versa.

\noindent
Proof: Suppose $d|x$ and $d|y$. So $x=zd$ and $y=wd$. Thus, $r=x-y=d(z-w)$.\\
Suppose $d|y$ and $d|r$ then $x=y+r=wd+ud=(w+u)d$.

\noindent
Corollary: GCD$(x,y)=$GCD$(y,r)$

\noindent
Proof: Since $(x,y)$ and $(y,r)$ have exactly the same set of divisors,
the biggest number in each set is identical.

\pagetitle{Induction and Recursive Algorithms --\\ Greatest Common Divisor}

\noindent
So?

\begin{tabbing}
Procedure $Euclid(x,y)$\\
\\
{\bf if} $x=0$ return $y$\\
{\bf else if} $y=0$ return $x$\\
{\bf else if} $x > y$ return $Euclid(y,x-y)$\\
{\bf else} return $Euclid(x,y-x))$
\end{tabbing}

Example: \\
Find $GCD(112, 84)$ = ? \\
Step 1: $112 - 84 = 28$, reduce to $(28,84)$. \\
Step 2: $84 - 28 = 56$, reduce to $(28,56)$. \\
Step 3: $56 - 28 = 28$, reduce to $(28,28)$. \\
Step 4: $28 - 28 = 0$, reduce to $28,0$\\
Now done, answer is $28$. 

\pagetitle{Induction and Recursive Algorithms --\\ Greatest Common Divisor}

\noindent
First prove that the algorithm terminates

\noindent
Lemma For any natural number inputs $x$ and $y$, $Euclid(x,y)$ returns
a value.

\noindent
Induction on $x+y$\\

\noindent
if $x+y=0$ then we return immediately\\
Assume for $x+y<n$ and prove for $x+y=n$\\
We either return (when $x$ or $y$ equal 0) or call
with smaller $x+y$.


\noindent
Lemma For any natural number inputs $x$ and $y$, $Euclid(x,y)$ returns
GCD$(x,y)$.

\noindent
Induction on $x+y$

\noindent
Base: GCD(0,0)=0 (*in fact we need GCD(x,0)=x*)\\
Step: $x+y=n>0$, assume without loss of generality $x \geq y$.
Return the result on $Euclid(y,x-y)$ (strong induction)
and lemma complete the proof.


\pagetitle{Sets}

\noindent
A {\em set} is a collection of objects.\\
\\
Order is not important $\{1,2\}$ and $\{2,1\}$ are the same set.\\
\\
Element is included once $\{a,a,b\}$ and $\{a,b\}$ are the same set.\\
\\
Examples of sets:\\
\{1,2,3\}\\
$\emptyset$ the {\em empty set}.\\
\{ $\emptyset$ \} a set with one element, which is a set.\\
\{1,\{1,2\}\} an element is included only once\\
$\{n \in N|n$ is even\}, in general domain $D$ and predicate
$P$ over $D$, $\{x \in D | P(x)\}$ the set of all $x$ in $D$ that
satisfy $P$ \\
\\
$a \in A$ in words {\it $a$ is an element of $A$},\\
$(\forall x) x \not\in \emptyset$.\\

\pagetitle{Subsets}
$A\subseteq B$ (``$A$ is a subset of $B$'' or
``$A$ is contained in $B$'') if every
element of $A$ is also an element of $B$\\
$(\forall x)(x\in A \rightarrow x \in B)$).
\\
$A$ is a {\em proper} subset of $B$
($A\subset B$) if $A\subseteq B$ and $A\neq B$.\\
\\
Note $(\forall X) \emptyset \subseteq X$, i.e. the empty set
is contained in any other set. \\

\pagetitle{Sets -- Definitions}

\noindent
$A=B$ if and only if $A \subseteq B$ and $B \subseteq A$.\\
\\
To prove that the sets $\{n \in N | 2~divides~n\}$ and $\{2n | n \in N\}$ are
equal we show containment in both ways:

\noindent
$\subseteq$: \\
Assume $x \in N$ and 2 divides $x$ and show that $\exists y \in N$ s.t.
$x=2y$.\\
$\supseteq$:\\
Assume $x=2y$ then $x$ is divisible by 2.\\

\noindent
The {\it size} of a set $A$ --- the number of elements in $A$ is $|A|$.\\
$|\{a,b,c\}|=3$, $|\emptyset|=0$, the size of an infinite set is $\infty$.\\

\noindent
$|A\cup B| \leq |A|+|B|$ (equal when $A\cap B=\emptyset$)\\
holds for infinite sets when $x+\infty=\infty$.

\pagetitle{Basic set operations}

\noindent
Union ---
$A\cup B=\{x | x\in A \hbox{  or  } x\in B\}$.

\noindent
$\cup_{i=1}^n A_i$\\
$i=0$ results in $\emptyset$


\noindent
Intersection ---
$A\cap B=\{x | x\in A \hbox{  and  } x\in B\}$.

\noindent
$\cap_{i=1}^n A_i$\\
$i=0$ results in $U$ the universal set.

\noindent
Difference ---
$A-B=\{x | x\in A \hbox{  and  } x\not\in B\}$.\\
(or $A\setminus B$)

\noindent
Complement ---
$A^c=\{x | x\not\in A\}$.\\
(or $\bar A$).\\
$A^c=U-A$.

\noindent
Symmetric difference ---
$A \oplus B= A \cup B - A\cap B$.

\noindent
Venn diagrams

\pagetitle{Predicates and sets}

\noindent
Given predicates $p$ and $q$,\\
$P = \{ x \mid p(x) \}$, \\
$Q = \{ x \mid q(x) \}$. \\
Then $P \cup Q = \{ x \mid p(x) \vee q(x) \}$. \\
$P \cap Q =  \{ x \mid p(x) \wedge q(x) \}$.\\
Etc.

\pagetitle{Power set (set of all subsets)}

${\cal P}(A)$ the set of all subsets of $A$. \\
In other words, ${\cal P}(A) = \{x | x\subseteq A\}$. \\

\noindent
$\emptyset\in{\cal P}(A)$ and $A\in {\cal P}(A)$.

\noindent
If $A=\{1,2\}$ then ${\cal P}(A)=\{\emptyset,\{1\},\{2\},\{1,2\}\}$.

\noindent
If $A$ has $n$ elements, then ${\cal P}(A)$ has $2^n$ elements.

\noindent
Induction on $n$\\
Base: $n=0$ ${\cal P}(A)=\{\emptyset\}$.\\
Step: let $a$ be the ``new'' element\\
${\cal P}(A)$ contains all subsets without $a$
which are $2^{n-1}$ subsets\\
for each such subset
a subset that includes $a$.\\
$2^{n-1} \cdot 2$.\\
(the number of binary words with $n$ bits).

\noindent
${\cal P}(A)$ can be denoted $2^A$.

\pagetitle{Set identities}

(Distributivity:  Union distributes over intersection) \\
$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$

\noindent
We show that each is contained in the other

1. $A \cup (B \cap C) \subseteq (A \cup B) \cap (A \cup C)$.

\noindent
Suppose $x \in A \cup (B \cap C)$.  \\
Then, $x \in A$ or $x \in (B \cap C)$.  \\
We argue by cases.  \\
\\
If $x \in A$, then $x \in A \cup B$ and similarly $x \in
A \cup C$.  \\
By definition of intersection $x$ is in the intersection
of these two sets.\\
%, which is the RHS. \\
\\
On the other hand, if $x \in (B \cap C)$, then $x \in B$ and $x \in C$. \\
By definition of union, $x \in A \cup B$ and $x \in A \cup C$. \\
It again follows that $x$ is in the intersection.
\\
2. 
$A \cup (B \cap C) \supseteq (A \cup B) \cap (A \cup C)$. \\

\noindent
Suppose $x \in (A \cup B) \cap (A \cup C)$. \\
It follows that $x \in A\cup B$ and $x \in A \cup C$. \\
We argue by cases. \\
\\
If $x \in A$, then certainly $x \in A \cup (B \cap C)$. \\
\\
If $x \notin A$, then since $x \in A \cup B$, we know $x \in B$. \\
Similarly, $x \in C$. \\
Therefore, $x \in B \cap C$. \\
It follows that $x \in A \cup (B \cap C)$.

\pagetitle{Set identities --\\ De Morgan's rule}

\noindent
$(A\cup B)^c=A^c\cap B^c$.

\noindent
We have to show that $(A\cup B)^c \subseteq A^c \cap B^c$
and that $A^c \cap B^c \subseteq (A\cup B)^c$.

\noindent
1. $(A\cup B)^c\subseteq A^c\cap B^c$.

\noindent
Let $x\in (A\cup B)^c$.\\
By definition of complement, $x \notin A \cup B$.\\
(proof by contradiction) $x \notin A$ and $x \notin B$.\\
By definition of complement, $x \in A^c$ and $x \in B^c$.  \\
Then by definition of intersection, $x \in A^c \cap B^c$.

\noindent
2. $A^c\cap B^c\subseteq (A\cup B)^c$.

\noindent
Let $x \in A^c \cap B^c$. \\
Then $x$ is in $A^c$ and in $B^c$. \\
Therefore, $x$ is in neither $A$ nor $B$ and therefore not in $A \cup B$. \\
We conclude that $x \in (A \cup B)^c$.


\noindent 
Dual holds,
swapping $\cup$ with $\cap$ and $\emptyset$ with $U$.

\pagetitle{Cartesian products}

\noindent
$A\times B =\{(a,b)|a\in A~and~b \in B\}$.\\
$(a,b)$ is an ordered pair $\neq$ $(b,a)$.

\noindent
$A=\{0,1\}$ and $B=\{x,y\}$ then $\{A \times B\}=\{(0,x),(0,y),(1,x),(1,y)\}$.

\noindent
Generalize Cartesian products\\ 
$A_1 \times \cdots \times A_n = \prod_{i=1}^n A_i
= \{(a_1,\cdots,a_n)  | a_i\in A_i \hbox{ for   }1\le i \le n\}$.\\
Also, $A^n$ is $\prod_{i=1}^n A$.

\noindent
Examples:\\
$\{0,1\}^n$ is the set of all $n$-tuples of 0's and 1's.
Or, length $n$ strings of $0$'s and $1$'s.\\
\\
$\Re^2 = \Re\times \Re$ is the real plane.

\end{document}
