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

\input{macros-course}

\def\given{\mid}

\setcounter{section}{??}

\parskip1.5ex
\parindent0pt

\begin{document}
\handout{notes5}{Notes 6}{September 26, 1995}

\section{Functions}

A {\em function} $f:A\arrow B$ is a way of relating {\em every} item
in a set $A$ with {\em precisely one} item in a set $B$.

$A$ is called the {\em domain} of the function and $B$ is called the
{\em range}.

The {\em image} of $f$ is denoted by $f(A)$ and is the set of items
$b\in B$ such that there is an item $a\in A$ such that $f(a)=b$.

For example, $f:R\arrow R$ where $f(x)= |x|$ is the absolute value
function.  The square root function is trickier to define though since
we must handle square roots of negative numbers and since we must be
sure that there is only one root specified.

We can define functions recursively as with the factorial function:
$f:N\arrow N$, $f(0)=1$, and $f(n)=nf(n-1)$ for $n>0$.

\subsection(Injections, Surjections, and Bijections}

A function $f:A\arrow B$ is a {\em surjection} (aka is {\em onto}) if
for all $b\in B$, there exists an $ a\in A$ such that $f(a)=b$.

A function $f:A\arrow B$ is an {\em injection} (aka is {\em
one-to-one}) if for all $a, a^{\prime}\in A, (a\ne a^{\prime})\arrow
(f(a)\ne f(a^{\prime})).  In other words $f$ is an injection if it
maps different items in $A$ to different items in $B$.

A function is a {\em bijection} if it is both an injection and a
surjection.

For example, $f:N\arrow N$, $f(x)=2x$ is an injection but not a
surjection.  To prove that $f$ is an injection we observe that
$f(x)=f(x^{\prime})\arrow 2x=2x^{\prime}\arrow x=x^{\prime}.  To prove
that $f$ is not a surjection, we observe that there is no $x$ such
that $f(x)=1$.  We could make $f$ be a bijection if we altered the
domain or the range appropriately.


























 {\em set} is a collection of objects. The order of elements is not important
and including the same object more than once is redundant.

\begin{itemize}
\item $\{1,2,3\}$.
\item $\phi$ the {\em empty set}.
\item $\{\phi\}$.
\item $\{1,\{1,2\}\}$.
\item $\{n\in \naturals  \given n \hbox{ is even }\}$.
\end{itemize} 

We say that $a\in A$ (``$a$ is in $A$'' or ``$a$ is an element of
$A$'') if $a$ is an object in the set $A$. The empty set satisfies
the proposition $(\forall x) x \notin \emptyset$.

Set theory is perhaps the most fundamental part of mathematics: almost
everything else (such as the Peano axioms) can be formulated as
theorems within set theory.  Set theory can be done in an {\em
extremely} formal way, starting with a collection of axioms that seem
ridiculously obvious (but aren't):

\begin{itemize}
\item
The {\em axiom of extensionality} says that two sets are equal iff they have
the same elements. 
\begin{itemize}
\item $\{n\in \naturals  \mid 2 \mbox{ divides } n\}=\{2n \mid n \in \naturals\}$.
\end{itemize}

\item
The {\em axiom of comprehension} says that we can form a new set by including
all objects of a given set that share a common property. For example,
\begin{itemize}
\item $\{x \in {\Bbb R} \given P(x)\} \hbox{  where  } P(x)=\hbox{ ``x is
rational''}$ denotes the set of all rational numbers.
\end{itemize}
Set builder notation above may implicitly use a universe of discourse,
like our predicate quantifiers.
\end{itemize}

\begin{defn}
We say that $A\subseteq B$ (``$A$ is a subset of $B$'') if every
element of $A$ is also an element of $B$ (that is, $(\forall x)(x\in
A \implies x \in B)$).
\end{defn}

\begin{defn}
 We say that $A$ is a {\em proper} subset of $B$
($A\subset B$) if $A\subseteq B$ and $A\neq B$.
\end{defn}

Note $(\forall X) \emptyset \subseteq X$

Can we have both $A\in B$ and $A\subseteq B$?

\begin{theorem}
$A=B$ if and only if $A \subseteq B$ and $B \subseteq A$.
\end{theorem}

This observation is very important as it provides a simple way to
prove that 2 sets are equal.

The size of a set $A$ (the number of elements it contains) is written
$|A|$.  

\subsection{Set operations}

There are several standard operations on sets.  In axiomatic set
theory, the claim that these operation yield new sets is an axiom.

\begin{enumerate}
\item $A\cup B=\{x\given x\in A \hbox{  or  } x\in B\}$. {\em union}
\item $A\cap B=\{x\given x\in A \hbox{  and  } x\in B\}$. {\em intersection}
\item $A-B=\{x\given x\in A \hbox{  and  } x\not\in B\}$. {\em difference}.
Also $A\setminus B$.
\item $A^c=\{x\given x\not\in A\}$. {\em complement}. Also $\bar A$.
\item $A \oplus B= A \cup B - A\cap B$. {\em symmetric difference}
\end{enumerate} 

Union and intersection can be applied to more than two sets.  Given a
collection of sets $A_i$, $i=1,\ldots,n$,
\[
\bigcup_{i=1}^n A_i
\]
is the set of elements in at least one of the $A_i$.  Intersection for
multiple sets is defined similarly.  If ${\cal S}$ is a {\em set of
sets}, then 
\[
\bigcap {\cal S} 
\]
denotes the intersection of all the sets in ${\cal S}$.



Complement is different from all the other operations, because it
assumes some universe where we can find the things not in $A$.  This
universe is often implicit, like the universe of discourse for
predicate logic.  In this way, all sets in consideration are supposed
to be subsets of $\Omega$. For example, $A^c=\Omega-A$.

Correspondence between set operations and logical operations; sets and
predicates.  

\subsubsection{Power Set}

Another very important operation on sets is that of the {\em power
set} of a given set $A$. It is denoted by ${\cal P}(A)$ and consists
of the set of all subsets of $A$. In other words, ${\cal
P}(A)=\{x\given x\subseteq A\}$. In particular, for any set $A$,
$\phi\in{\cal P}(A)$ and $A\in {\cal P}(A)$.

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

\begin{theorem}
If $A$ has $n$ elements, then $P(A)$ has $2^n$ elements.
\end{theorem}
\begin{proof}
Induction.
\end{proof}

In fact, ${\cal P}(A)$ is sometimes denoted $2^A$.

\subsection{Proving Set Identities}

\begin{theorem}
$A \cup (B \cap C) = (A \cap B) \cup (A \cap C)$
\end{theorem}
\begin{proof}
We show equality by proving each is contained in the other.
\begin{itemize}
\item $A \cup (B \cap C) \subseteq (A \cup B) \cap (A \cup C)$.
Suppose $x \in A \cup (B \cap C)$.  Then by definition, $x \in A$ or
$x \in (B \cap C)$.  We argue by cases.  If $x \in A$, then by
definition $x \in A \cup B$ and similarly $x \in A \cup C$.  It
follows by definition of intersection that $x$ is in the intersection
of these two sets. 
\item $A \cup (B \cap C) \supseteq (A \cap B) \cup (A \cap C)$.
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)$.  So suppose $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)$.
\end{itemize}
\end{proof}


\begin{theorem}
De Morgan's rule: $(A\cup B)^c=A^c\cap B^c$.
\end{theorem} 
\begin{proof}
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$. 

\begin{enumerate}
\item
$(A\cup B)^c\subseteq A^c\cap B^c$: Let $x\in (A\cup B)^c$. Then 
by definition $x \notin A \cup B$.  It follows (proof by
contradiction) that $x \notin A$ and $x \notin B$.  In other words, $x
\in A^c$ and $x \in B^c$.  Therefore, by definition, $x \in A^c \cap B^c$.

\item
$A^c\cap B^c\subseteq (A\cup B)^c$: 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$.
\end{enumerate} 
\end{proof} 

The above two theorems have {\em dual theorems} produced by swapping
$\cap$ and $\cup$.
\begin{theorem}
$A \cap (B \cup C) = (A \cup B) \cap (A \cup C)$
\end{theorem}

\begin{theorem}
 $(A\cap B)^c=A^c\cup B^c.$
\end{theorem}

\subsection{Russell's paradox}

We might think that set theory is obvious, but this is not the case.
Consider the set $S = \{X \mid X \mbox{ is a set}\}$.  This seems like a
perfectly reasonable set (well, maybe a bit strange---note $S \in S$).
If our set theory allows for such an entity, we get into trouble as follows.

Consider the set $Q=\{x \given x \hbox{ is a set and }x\not\in x\}$
(note $Q \subseteq S$).  Clearly, the set $A=\{1,2,3\}$ is not an
element of itself so that $A\in Q$.  Also, the set $P=\{\hbox{ all
infinite sets}\}$ is infinite and therefore $P\in P$ so that $P\not\in
Q$. The question is: is $Q\in Q$?

\begin{enumerate}
\item If $Q\in Q$ then $Q\not\in Q$, a contradiction.
\item If $Q\not\in Q$ then $Q\in Q$ also a contradiction.
\end{enumerate} 

This is clearly a paradox. In fact, this paradox was a blow to the
then current attempts to formalize all of mathematics ($\sim$1900).
Mathematicians had to work very hard to find a consistent set of axioms
(note a consistent set of axioms does not allow this paradox to
arise).  The problem with naive set theory is that you can form a set
by describing its members, as we did for $Q$ above.  Axiomatic set
theory has a specific set of rules for how you can form sets---rules
that don't allow the set $Q$ above to specified, and therefore avoid
the paradox.

\subsection{Cartesian products}

Another important set operation is the {\em Cartesian product}. For sets $A$
and $B$ define $A\times B=\{(a,b)\given a\in A\hbox{  and  }b\in B\}$. Here,
$(a,b)$ is considered an {\em ordered} pair so that $(a,b)\neq (b,a)$.

\begin{example}
If $A=\{0,1\}$ and $B=\{a,b\}$ then $A\times
B=\{(0,a),(0,b),(1,a),(1,b)\}$.
\end{example}

Order is important!  In the above example, $(a,0) \notin A \times B$,
though $(a,0) \in B \times A$.  We can generalize Cartesian products
to apply to more than 2 sets and define $A_1\times\cdots\times
A_k=\times_{i=1}^k A_i=\{(a_1,\cdots,a_k)\given a_i\in A_i \hbox{ for
  }1\le i \le k\}$ (note Cartesian product is associate {\em up to
  isomorphism}). Also, we write $A^k$ for $\times_{i=1}^k A$.

\begin{itemize}
\item $\{0,1\}^n$ is the set of all $n$-tuples of 0's and 1's. 
\item $\Re^2$ is the real plane.
\end{itemize} 

\section{Relations}

A {\em binary relation} from a set $A$ to a set $B$ is a subset $R\subseteq
A\times B$. A binary relation {\em on} a set $A$ is a subset $R\subseteq A^2$.
We can write $a\sim_R b$ or $aRb$ if $(a,b)\in R$.

We can also define a {\em ternary} relations as a subset $R\subseteq A^3$ or,
in general, a $k$-ary relation as a subset $R\subseteq A^k$.

\begin{enumerate}
\item flight schedules.
\item \label{classes} The relation ``is taking class'' as a subset of
  $\{$students at MIT$\}\times\{$classes at MIT$\}$.  extra info?
\item \label{roommates} The relation ``is living in the same room as'' is a subset of
 $\{$students at MIT$\}\times \{$students at
MIT$\}$
\item \label{reachable} The relation ``can drive from first to second
  city''
\item \label{wire} Relation ``are connected by a wire''
\item \label{meet} ``meet one another on a given day''
\item \label{likes}  ``likes''
\item \label{le} Let $A=\naturals$ and define $a\sim_R b$ iff $a\le b$.
\item \label{finite} let $A={\cal P}(\naturals)$ and define $a\sim_R b$ iff $|a \cap b|$ is finite.
\item \label{dist} Let $A=\Re^2$ and define $a\sim_R b$ iff $d(a,b)=1$.
\item \label{contain} Let $A={\cal P}(\{1,\cdots,n\})$ and let $a\sim_R b$ if
$a\subseteq b$.
\end{enumerate} 

\subsection{Properties of Relations}

A binary relation $R$ on $A$ is:
\begin{enumerate}
\item {\em reflexive} if for every $a\in A$, $a\sim_R a$.
\item {\em symmetric} if for every $a,b\in A$, $a\sim_R b$ implies $b\sim_R a$.
\item {\em antisymmetric} if for every $a,b\in A$, $a\sim_R b$ and
$b\sim_R a$ implies $a=b$.
\item {\em transitive} if for every $a,b,c\in A$, $a\sim_R b$ and $b\sim_R c$
implies $a\sim_R c$. 
\end{enumerate} 

Among out examples,
\begin{itemize}
\item Relation~\ref{wire} is symmetric but not transitive. Whether it
  is reflexive is open to interpretation.
\item Relation~\ref{roommates} above is reflexive, symmetric and transitive.
\item Relation~\ref{dist} is only symmetric.
\item Relation~\ref{contain} is reflexive, antisymmetric and transitive.
\end{itemize} 

\subsection{Representation}

Lists, Matrices, Graphs. 

Reflexivity, symmetry, transitivity in each representation.

Examples using divisibility relation.

\subsection{Composition}

A {\em composition} of relations $R_1 \subseteq A \times B$ and $R_2
\subseteq B \times C$ is the relation $R_1 \circ R_2 =\{(a,c) \mid
(\exists b) ((a,b) \in R_1) \wedge ((b,c) \in R_2)\}$.


Composition of relations is equivalent to matrix multiplication, with
$+$ replaced by $\vee$ (Boolean or) and $*$ replaced by $\wedge$.

Examples: composition of parent-of relation with itself gives
grandparent-of.  Composition of parent-of relation with child-of
relation gives sibling-of relation.

The composition $A \circ A$ of $A$ with itself is written $A^2$;
similarly $A^n$ denotes $A$ composed with itself $n$ times (recursive
definition: $A^n = A\circ A^{n-1}$).

\begin{lemma}
$A \circ (B \circ C) = (A \circ B) \circ C$
\end{lemma}

\begin{theorem}
For $n>1$, $R^n = R^{n-1} \circ R$
\end{theorem}
\begin{proof}
By induction on $n$.  Base case $n=2$ trivial.  Suppose $(a,b) \in R^n$.
Then $(\exists a') ((a,a') \in R) \wedge (a',b) \in R^{n-1}$.  By
induction, $(\exists b') ((a',b') \in R^{n-2}) \wedge ((b',b) \in R)$.
It follows that $(a,b') \in R^{n-1}$.  Therefore, $(a,b) \in R^{n-1}
\circ R$.
\end{proof}

\begin{theorem}
$R$ is transitive if and only if $R^n \subseteq R$ for all integers
$n$.
\end{theorem}
\begin{proof}
(If part) If $R^n \subseteq R$ for every $n$, then $R^2 \subseteq R$.
Follows that $R$ is transitive.

(Only if part) By induction.  Base case easy.  Suppose $R^n \subseteq
R$.  Show $R^{n+1} \subseteq R$.  Say $(a,b) \in R^{n+1}$.  Then
$(a,c) \in R^n$ and $(c,b) \in R$ for some $c$.  Then $(a,c) \in R$ by
induction.  This by transitivity $(a,b) \in R$.
\end{proof}

\section{Equivalence relations and partitions}

An {\em equivalence} relation is a relation which is reflexive,
symmetric and transitive. For example, the first relation above is an
equivalence relation.  A trivial example is the ``='' relation.  One
interesting fact about equivalence relations is that they partition
the universe in a very natural way. Given a set $A$, a {\em partition}
is a collection of subsets $\{A_1,\cdots,A_k\}$ such that any two of
them are disjoint (for any $i\neq j$, $A_i\cap A_j=\phi$) and such
that their union is $A$. That is, every element of $A$ is in exactly
one subset.

Fix an equivalence relation $R$ on $A$. For an element $a\in A$, let
$[a]$ denote the set $\{b\in A \given a\sim_R b\}$.  We call this set
the {\em equivalence class of $a$ under $R$}.  We claim that the sets
$[a]$ for $a\in A$ constitute a partition of $A$.

\begin{lemma}
  For every $a,b\in A$, either $[a]=[b]$ or $[a]\cap [b]=\phi$.
\end{lemma}

\begin{proof}
  Fix $a,b\in A$. If $[a]=[b]$ then we are done. Otherwise, suppose
  that $c$ is an element in only one set (suppose that $c\in
  [b]-[a]$). If $[a]\cap [b]=\phi$ then we are done. Otherwise,
  suppose that $d\in [a]\cap [b]$. We will get a contradiction by
  showing that $a\sim_R c$ and therefore that $c\in [a]$. First,
  $a\sim_R d$ because $d\in [a]$ (note that $d=a$ is a possibility but
  this is ok because $R$ is reflexive). Second, $d\sim_R b$ and
  $b\sim_R c$ because both $c,d\in [b]$ and $R$ is symmetric. This
  implies, by transitivity, that $d\sim_Rc$. Finally, by transitivity,
  $a\sim_R c$ because $a\sim_R d$ and $d\sim_R c$.
\end{proof}

Conversely, any partition $\{A_1,\cdots,A_k\}$ of $A$ defines an
equivalence relation by letting $a\sim_R b$ iff $a$ and $b$ are in the
same $A_i$.  Therefore, we can look at partitions and at equivalence
relations as different versions of each other.

\subsection{Integers modulo $m$}

In the previous lecture, we considered the modulo operation as a
function.  A cleaner way to think of it is as a definition of
equivalence classes of natural numbers.  Consider the following
definition.

\begin{defin}
We say $a=b \pmod m$ if $m \mid (a-b)$.  
\end{defin}

An equivalent formulation says that $a=b+km$ for some integer $k$.  

\begin{theorem}
Equality modulo $m$ is an equivalence relation.
\end{theorem}
\begin{proof}
We need to show the relation is reflexive, symmetric, and transitive.
\begin{description}
\item{reflexive} Clearly $m \mid 0=a-a$, so $a=a \pmod m$.
\item{symmetric} If $a=b+km$ then $b=a+(-k)m$.
\item{transitive} If $a=b \pmod m$ and $b = c \pmod m$, this means that
  $m \mid (a-b)$ and $m \mid (b-c)$.  It follows from a theorem in the
  previous lecture that $m \mid (a-c) = (a-b)+(b-c)$.
\end{description}
\end{proof}

The equivalence class of $a$ is simply the set $[a] = \{km+a \mid k
\in {\Bbb Z}$.

It turns out that we can perform a lot of standard arithmetic modulo
$m$.  That is, we can {\em extend} the standard notions of sum and
product to the equivalence classes mod $m$.  For example, we can
define $[a]+[b]$, given two equivalence classes mod $m$, to be the
equivalence class $[a+b]$.  This is not as obvious as it seems: notice
that the result is given in terms of $a$ and $b$, two selected
representative from the equivalence classes, but that it is supposed
to apply to the equivalence classes themselves.  To prove that this
works, we have to show that it doesn't matter which representative of
the equivalence class we choose.

\begin{lemma}
If $a=x \pmod m$ and $b=y \pmod m$ then $(a+b) = (x+y) \pmod m$.  
\end{lemma}
\begin{proof}
$m \mid (a-x)$ and $m \mid (b-y)$ so $m \mid ((a-x)+(b-y)) =
(a+b)-(x+y)$,  
\end{proof}

It follows that if we are interested only the result of the addition
modulo $m$, which is the case, for example, in the RSA cryptosystem,
that we can at any time replace a given number with a different number
equivalent to it, without changing the value (equivalence class) of
the final answer. 

The same fact can be proven for multiplication.  This is the basis of
the fast exponentiation algorithm presented in section.

\subsection{Fast Exponentiation}

Let's say that we want to compute $a^n \pmod b$.  Here's a crude
way to do it:

\begin{enumerate}
\item Compute $a^n$.
\item Divide by $b$ and take the remainder.
\end{enumerate}

There are actually two big problems with this.  First of all, $a^n$
could be a gigantic number; and secondly, we're using $n$ multiplications,
which could take a long time if $n$ is large.

Let's correct the first problem first.

\begin{enumerate}
\item Initialize $p = 1$.
\item Repeat $n$ times:
\begin{itemize}
\item[(i)] Set $p \leftarrow ap$.
\item[(ii)] Set $p \leftarrow p \pmod b$.
\end{itemize}
\item Return $p$.
\end{enumerate}

To see why this works, we have to use the fact that
$x \pmod b * y \pmod b = (x * y) \pmod b.$  This can be shown by
arguments as in the preceding section of the notes.

Now to reduce the number of multiplications, we try to use 
squaring whenever possible.

Algorithm {\tt fast-exp(a,n,b)}
\begin{enumerate}
\item If $n = 1$ then return $a \pmod b$.
\item Else if $n$ is odd return $a *$ {\tt fast-exp(a,n-1,b)} $\pmod b$.
\item Else ($n$ is even), set $p \leftarrow$ {\tt fast-exp(a,n/2,b)} and
return $p^2 \pmod b$.
\end{enumerate}

In recitation, we'll prove a few things about this algorithm ---
first, that it terminates with the correct answer for $n \geq 1$;
and second, that it uses at most $2 \log n$ multiplications
(a huge savings over $n$ multiplications even for moderate values of $n$).

\end{document}
