\documentstyle[12pt,twoside,amssymb]{article}
\input{/a/class/6.042/spring95/macros-course}

\input{mk-macros}

\begin{document}

\lecnotes{February 14, 1995}{4-6}



\medskip

{\bf Reading:} Sections 2.1, 2.2.1-2.2.2, 2.3, 2.4, 5.1  of Truss.

\section{Sets}

A {\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{examples}
\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{examples} 

The {\em cardinality} of a set $A$ is defined as the number of elements it
contains and it is denoted by $|A|$. For example, the cardinalities of the 5
sets described above are 3, 0, 1, 2, $\infty$ (more on infinite sets later).

The {\em axiom of extensionality} says that two sets are equal iff they have
the same elements. 

\exm
$\{n\in \naturals  \given n \hbox{ is even }\}=\{2,4,6,8,\cdots\}$.
\eexm

The {\em axiom of comprehension} says that we can form a new set by including
all objects that share a common property. For example,

\exm
$\{x \given P(x)\} \hbox{  where  } P(x)=\hbox{ ``x is rational''}$
\eexm

We say that $a\in A$ (``$a$ is in $A$'') if $a$ is an element of $A$. Also, we
say that $A\subseteq B$ (``$A$ is a subset of $B$'') if every element of $A$ is
also an element of $B$. We say that $A$ is a {\em proper} subset of $B$
($A\subset B$) if $A\subseteq B$ and $A\neq B$. It is clear that $A=B$ iff both
$A\subseteq B$ and $B\subseteq A$. This trivial observation is very important
as it provides a simple way to prove that 2 sets are equal.

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


\section{Russell's paradox}

Consider the set $Q=\{x \given x \hbox{  is a set and  }x\not\in x\}$.
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 that
study axiomatic set theory deal with this paradox by constructing sets from
scratch and modifying the axiom of comprehension so that we can form new sets
that include all elements {\em of a previously constructed set} and which
share a common property. In this way, we cannot talk about the set of all
sets and therefore the set $Q$ as defined is ``illegal''.

\section{Set operations}

It is now natural to define operation on sets. The traditional ones are:

\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^c=\{x\given x\not\in A\}$. {\em complement}. Also $\bar A$.
\item $A-B=\{x\given x\in A \hbox{  and  } x\not\in B\}$. {\em difference}.
Also $A\setminus B$.
\item $A\bigtriangleup B=(A-B)\cup(B-A)$. {\em symmetric difference}
\end{enumerate} 

Usually, when we talk about sets we have a {\em universe} in mind, say
$\Omega$. In this way, all sets in consideration are supposed to be subsets of
$\Omega$. For example, $A^c=\Omega-A$.
It is easy to prove that both $\cup$ and $\cap$ are associative. The
following facts are also easy to show:

\begin{enumerate}
\item Distributivity: $A\cup(B\cap C)=(A\cup B)\cap(A\cup C)$.
\item De Morgan's rule: $(A\cup B)^c=A^c\cap B^c$.
\end{enumerate} 

In addition, there is a nice {\em duality} between $\cap$ and $\cup$ in that in
any equality statement as those described above, we can interchange $\cap$ with
$\cup$ and $\Omega$ with $\phi$ and get a valid statement. For example, the
dual statement to De Morgan's rule is $(A\cap B)^c=A^c\cup B^c$ which is also
true. Similarly, the dual of $A\cup A^c=\Omega$ is $A\cap A^c=\phi$.

As an illustration of how to prove such statements, lets prove De Morgan's rule:

\pf[De Morgan's rule]
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 $x$
is in neither $A$ or $B$. Therefore, $x$ is in both $A^c$ and $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} 
\epf 

The distributivity law is left as an exercise. Another way of proving such
facts is by using Venn diagrams. (see text, pages 52-53).

\exr
Prove that for finite sets, $|A\cup B|=|A|+|B|-|A\cap B|$.
\eexr

The definition of $\cup$ and $\cap$ can be extended to apply to more than 2
sets. For example, if $\{A_i\given i\in \naturals \}=\{A_1,A_2,\cdots\}$ is a collection
of sets then we can define their union $\cup_{i\in \naturals }A_i$ in the natural way.

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)$.

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

What is the cardinality of the power set of a finite set? We answer this
question with the next theorem:

\thm
For any finite set $A$, $|{\cal P}(A)|=2^{|A|}$.
\ethm

\pf
By induction on $|A|$.

{\em Base case}: If $|A|=0$ then $A=\phi$ and ${\cal P}(A)=\{\phi\}$ which
has $1=2^0$ element.

{\em Inductive step}: Assume that the theorem is true for sets of cardinality
less than $|A|$. Let $a$ be any element of $A$. The subsets of $A$ can be
divided according to whether they contain $a$ or not. Let $B=A-\{a\}$. The
sets not containing $a$ are exactly those in ${\cal P}(B)$ and by the inductive
assumption there are $2^{|B|}=2^{|A|-1}$. The sets containing $a$ are in one
to one correspondence with the sets in ${\cal P}(B)$. This is because any set
containing $a$ can be transformed into a set in ${\cal P}(B)$ by removing $a$
and conversely, any set in ${\cal P}(B)$ can be transformed into a set
containing $a$ by including $a$ in it. Therefore the number of sets containing
$a$ is also $2^{|A|-1}$. Finally, the cardinality of ${\cal P}(A)$ is
$2^{|A|-1}+2^{|A|-1}=2^{|A|}$. 
\epf 

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

\exm
If $A=\{1,2\}$ then $|{\cal P}(A)|=4$.
\eexm


\section{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)$.

\exm
If $A=\{0,1\}$ and $B=\{a,b\}$ then $A\times
B=\{(0,a),(0,b),(1,a),(1,b)\}$. Note that $(a,0)\not\in A\times B$.
\eexm

Note that the order is important so that $A\times B\neq B\times A$. We can
generalize this construction 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\}$. Also, we write $A^k$ for $\times_{i=1}^k A$.

\begin{examples}
\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{examples} 

What is the cardinality of $A\times B$? The following theorem answers this
question:

\thm
For any two finite sets $A$ and $B$, $|A\times B|=|A|\times|B|$.
\ethm

\exr
Prove that for any $k$ finite sets $A_1,\cdots A_k$, $|\times_{i=1}^k
A_i|=\prod_{i=1}^k|A_i|$.
\eexr

\exm
$|\{0,1\}^n|=2^n$.
\eexm

Note that $|\{0,1\}^n|=|{\cal P}(\{1,\cdots,n\})|=2^n$. This is not a
coincidence. Why not?

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

\begin{examples}
\item Let $A=\nats$ and define $a\sim_R b$ iff $a\le b$.
\item let $A={\cal P}(\naturals)$ and define $a\sim_R b$ iff $|a\bigtriangleup b|$ is finite.
\item Let $A=\Re^2$ and define $a\sim_R b$ iff $d(a,b)=1$.
\item Let $A={\cal P}(\{1,\cdots,n\})$ and let $a\sim_R b$ if $a\subseteq b$.
\end{examples} 

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

\exr
If $|A|=n$, how many different $k$-ary relations on $A$ are
there?
\eexr

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$ implies
$b\not\sim_R a$ unless $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} 

\begin{examples}
\item The second relation above is reflexive, symmetric and transitive.
\item The third relation is only symmetric.
\item The fourth relation is reflexive, antisymmetric and transitive.
\end{examples} 

\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]=\{b\in
A \given a\sim_R b\}$. We claim that the sets $[a]$ for $a\in A$ constitute a
partition of $A$.

\lm
For every $a,b\in A$, either $[a]=[b]$
or $[a]\cap [b]=\phi$.
\elm

\pf
Fix $a,b\in A$. If $[a]=[b]$ then we are done. Otherwise, suppose that $c$ is
an element in $[a]\bigtriangleup [b]$ (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$.
\epf

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.

\exm
The first relation above partitions ${\cal P}(\naturals)$ into equivalence classes.
\eexm

\section{Partially ordered sets}

A {\em partially ordered} relation is one which is reflexive, antisymmetric and
transitive. For example, relation 3 above is a P.O. relation. We usually write
$a \preceq b$ instead of $a\sim_R b$ if $R$ is a P.O. relation. A set $A$
together with a P.O. relation is called a {\em partially ordered set} and it is
denoted by $(A,\preceq)$. For
example, $({\cal P}(\naturals),\subseteq)$.

A {\em total order} of $A$  is a partially ordered relation on $A$ such that
for any $a,b\in A$, either $a\preceq b$ or $b\preceq a$. For example, the
relation defined by $\le$ is a total order of $N$.

P.O. sets occur everywhere in computer science. They can be pictured with the
aid of {\em Hasse diagrams}.

Given a P.O. set $(A,\preceq)$, a {\em chain} is a subset
$\{a_1,\cdots,a_k\}\subseteq A$ such that for every $i\neq j$, either
$a_i\preceq a_j$ or $a_j\preceq a_i$. An {\em antichain} is a subset
$\{a_1,\cdots,a_k\}\subseteq A$ such that for every $i\neq j$ $a_i\not\preceq
a_j$ and $a_j\not\preceq a_i$. A {\em maximal} element is an element $a\in A$
such that for every $b\in A$, $a\not\preceq b$. We can similarly define {\em
minimal} elements.

\exm
Consider $({\cal P}(\{1,\cdots,n\}),\subseteq)$. Then
$\{\{1\},\{1,2\},\{1,2,3\}\}$ is a chain of size 3. The set of all subsets of
cardinality 2 is an antichain of size $n(n-1)/2$. 
\eexm

\exr
Which are the maximal and minimal elements of $({\cal
P}(\{1,\cdots,n\}),\subseteq)$?
\eexr

The following is a very useful fact of P.O. sets and it is the dual to the so
called Dillworth's theorem.

\thm
Let $(A,\preceq)$ be a P.O. set. Suppose that the length of the longest chain is
$n$. Then $A$ can be partitioned into $n$ disjoint antichains.
\ethm

\exm
Again consider $({\cal P}(\{1,\cdots,n\}),\subseteq)$. It is clear that the
longest chain is of size $n+1$ (prove it!). It is also clear that ${\cal
P}(\{1,\cdots,n\})$ can be partitioned into $n+1$ antichains (how?).
\eexm

\pf
By induction on $n$.

{\em Base case}: $n=1$. Then no two elements of $A$ are related so $A$ itself is
an antichain.

{\em Inductive step}: Let $B\subseteq A$ be the set of maximal elements in $A$.
Clearly $B$ is an antichain. Consider the P.O. set $(A-B,\preceq)$. Clearly,
the length of the longest chain in this set is $n-1$ (why?). Therefore, by the
inductive assumption $A-B$ can be partitioned into $n-1$ antichains. These
$n-1$ antichains together with $B$ form a partition of $A$ into $n$ antichains.
\epf

\exr
Prove that if the longest chain is exactly $n$ then we cannot partition $A$
with fewer than $n$ antichains.
\eexr

The dual of the theorem is called Dillworth's theorem and it is harder to
prove. It says that if the size of the largest antichain is $n$, then we can
partition $A$ into $n$ chains.

We can now derive some very nice corollaries.

\cor
If  $(A,\preceq)$ is a P.O. set with $|A|\ge nm+1$ then either there is an
antichain of size $n+1$ or there is a chain of length $m+1$.
\ecor

\pf
Suppose that the length of the longest chain is $m$. Then by the theorem we can
partition $A$ into $m$ antichains. Therefore, we must have an antichain of size
at least $n+1$ (why?).
\epf

\exm
A point $(x,y)\in\Re^2$ in the positive quadrant defines a the rectangle with
corners $(0,0), (x,0), (0,y), (x,y)$. Then if we have $n^2+1$ such rectangles
then either there are $n+1$ rectangles one inside of the other, or there are
$n+1$ rectangles not one of which is contained in another. This follows by the
previous corollary by considering the P.O. on $\Re^2$ defined by rectangle
containment.
\eexm

\section{Functions and the pigeonhole principle}

A {\em function} from $A$ to $B$ is a subset $f$ of $A\times B$ such that for every
$a\in A$ there is a unique $b\in B$ such that $(a,b)\in f$. We denote this by
$f:A\mapsto B$. We write $f(a)=b$
instead of the more awkward $(a,b)\in f$. 

\begin{examples}
\item $f:(0,1]\mapsto [1,\infty)$ defined by $f(x)=1/x$.
\item $f:\nats\mapsto\nats$ defined by $f(n)=2n$.
\item $f:\nats\mapsto\{0,\cdots,6\}$ defined by $f(n)=n\bmod 7$.
\end{examples} 

\exr
If both $A$ and $B$ are finite, how many functions from $A$ to $B$ are there?
\eexr

The {\em range} of $f$ (Range($f$)) is the set $\{b\in B\given f(a)=b \hbox{
for some  }a\in A\}$.

\exr
What are the ranges of the 3 functions described above?
\eexr

A function $f$ is:

\begin{enumerate}
\item {\em onto} or {\em surjective} if its range equals $B$.
\item {\em 1-1} or {\em injective} if for $a_1\neq a_2$ we have that
$f(a_1)\neq f(a_2)$.
\item {\em bijective} if it is both onto and 1-1.
\end{enumerate} 

\begin{examples}
\item The first function above is bijective.
\item The second function is 1-1.
\item The third function is onto.
\end{examples} 

If $f$ is bijective then it has an {\em inverse} $f^{-1}$ so that if $f(a)=b$
then $f^{-1}(b)=a$.

The following theorem is called the {\em Pigeonhole principle} and it is
surprisingly helpful. It says that if we put $n$ pigeons into $n-1$ holes then
there is a hole with at least 2 pigeons.

\thm
If $A$ and $B$ are finite and $|A|>|B|$ then there is not a bijective function
$f:A\mapsto B$.
\ethm

We consider this theorem obvious and we will not provide a proof.

\exr
Prove the theorem. (by induction?)
\eexr

As a nontrivial application we have the following:

\exm
From the numbers $\{1,\cdots,200\}$, 101 are chosen arbitrarily. Then there are 2
numbers such that one divides the other.
\eexm

\pf
We will let the 101 numbers chosen be the pigeons. We have to define 100 holes
in such a way that if two numbers fall into the same hole then one divides the
other. The example would follow from the pidgeonhole principle. The holes will
be associated with the odd numbers in the range $1,\cdots,200$ (there are 100
of them). We will place a number $n$ into the hole associated with $k$ iff
$n=k2^l$ for some $l$. Note that if $n_1$ and $n_2$ are placed into the hole
associated with $k$ then $n_1=k2^{l_1}$ and $n_2=k2^{l_2}$. Let $l_1<l_2$ (why
can`t $l_1=l_2$?). It is clear that $n_1$ divides $n_2$.
\epf

Not bad! Functions are also very helpful for counting sets. Let $A$ and $B$ be
finite sets. Consider the following:

\begin{enumerate}
\item $|A|=|B|$ iff there is a bijection from $A$ to $B$.
\item $|A|\le|B|$ iff there is an injection from $A$ to $B$.
\item $|A|\ge|B|$ iff there is a surjection from $A$ to $B$.
\end{enumerate} 

\exm
Consider the set of palindromes of length $n$ over the alphabet $\{0,1\}$. That
is, the set of $n$-tuples in $\{0,1\}^n$ which read the same in both
directions. For example, if $n=4$ then $0110$ is a palindrome but $0111$ is not.
How many palindromes of length $n$ are there? We claim that if $n$ is even then
there are exactly $2^{n/2}$ palindromes.
\eexm

\pf
We will define a bijection from the set $\{0,1\}^{n/2}$ to the set of
palindromes of length $n$. This will imply that there are
$|\{0,1\}^{n/2}|=2^{n/2}$ palindromes. For a sequence $a=(a_1,\cdots,a_{n/2})$
define $f(a)=(a_1,\cdots,a_{n/2},a_{n/2},\cdots,a_1)$. Clearly, $f(a)$ is a
palindrome and $f$ is bijective.
\epf

Notice that we used this same idea when we proved that $|{\cal P}(A)|=2^{|A|}$.

\exr
How many palindromes of odd length are there?
\eexr

\section{Infinite sets}

If $A$ is finite and $B\subset A$ then there is no bijection from $A$
to $B$. However, consider the set $\nats$ and the proper subset
$M=\{2,4,6,\cdots\}$. Clearly, the function $f(n)=2n$ is a bijection from $\nats$
to $M$. In fact, it can be shown that a set is infinite iff it has a bijection
to a proper subset.

Which is larger, $N$ or $M$? To answer this question we can use the concept of
bijections to extend the concept of cardinality to apply to infinite sets. We
say that $|A|=|B|$ iff there is a bijection from $A$ to $B$.

\exm
$|\nats|=|M|$!
\eexm

\exr
Prove that this is an equivalence relation.
\eexr

Note that to show that $|A|=|B|$, we don't have to {\em count} the elements of
$A$ and $B$. Instead, it is sufficient to show the existence of a bijection.

The cardinality of $\nats$ is called $\aleph_0$ ({\em aleph zero}). We say that a set
is {\em countable} if it is either finite or of cardinality $\aleph_0$. That
is, a set is countable if we can {\em count} its element so that there is the
1st, the 2nd, the 3rd and so on.

\begin{examples}
\item $\nats\times\nats$ is countable.
\item $\cal Q$ is countable.
\item $\{0,1\}^*=\cup_{n=0}^\infty \{0,1\}^n$ is countable.
\end{examples} 

Not every set is countable as the following beautiful theorem shows. It was
proven by Cantor in the later years of last century.

\thm
${\cal P}(\naturals)$ is not countable.
\ethm

\pf
We will proceed by contradiction. Assume that ${\cal P}(\naturals)$ is
countable so that ${\cal P}(\naturals)=\{S_1,S_2,\cdots\}$. The idea is to
construct a set $S\subseteq \naturals$ which is not in the list. We will put 1
in $S$ iff 1 is not in $S_1$.  Similarly, we will put 2 in $S$ iff 2 is not in
$S_2$. In general, we will say that $i\in S$ iff $i\not\in S_i$. The set $S$ is
well defined in that for each natural $n$, we can decide if $n$ is in $S$ by
looking at whether $n\in S_n$ or not.

The claim is that $S$ is not in the list. If it were, then it would be equal to
$S_j$ for some $j$. But this cannot be as $j\in S$ iff $j\not\in S_j$.
\epf

This technique is called {\em diagonalization} and it is used again and again
in the study of computability.

Another example of an uncountable set is $[0,1]$. This proof will be covered in
recitation. The cardinality of $[0,1]$ is called the cardinality of the
continuum and it is denoted by {\bf c}. 

\exr
Show that $|[0,1]|=|\Re|$.
\eexr

As an application, we will show that there are some functions that cannot be
computed! We will look at functions from $\nats$ to $\{0,1\}$. It is easy to see
that the set of such functions is uncountable (why?). Also, it is easy to see
that the set of computer programs is countable (why?). Therefore, there are
functions that cannot be computed!

\end{document}
