\documentclass{article}
\input{preamble.tex}
\usepackage{url}
\title{Day 10}
\date{Tuesday June 5, 2012}
\newcommand{\df}{\textbf}
% \def\Display{\@empty}
\newcommand{\Hide}[2]{\ifx \Display\undefined \strut \\ \vspace{#1} \\ \strut \else {\color{blue} #2} \fi }
\begin{document}
\maketitle
\section{Set Theory}
\subsection{Russell's Paradox}
Thus far we have defined several ways to make new sets:
\begin{itemize}
\item Union: The union of two (or more) sets is the set of elements which are in at least one of the sets.
\item Intersection: The intersection of two (or more) sets is the set of elements which are in all of the sets.
\item Relative Complement: The relative compliment of two sets $A\minus B$ is the set of things in $A$ and not in $B$.
\item Set Builder: The set $\s{ x\in A \mid P(x) }$ is the set of elements in the set $A$ that is not in the set $B$.
\end{itemize}
Notice that these all have the quality that they make a new set out of an existing set. The last way is actually quite powerful, and can capture the middle two:
\begin{align*}
A\cap B &= \set{ x\in A \mid x\in B} \\
A\minus B &= \set{x\in A \mid x\notin B}
\end{align*}
A natural question to ask is what are the ``atomic sets'' that is the sets that we begin with, that we can do the above with to make new sets. We have thus far conjectured the existence of the following sets: $\emptyset$, $\N$, $\Z$, $\Q$, $\R$, $\mathbb{C}$. Mathematics is sometimes very philosophical and, likewise, scientific. Those sets are not concrete objects, therefore we have no choice but to just claim that they exist.
So, can we just claim any set exists? Or are they some sets which cannot on principle exist if we expect to be able to perform the above operations to form new sets.
This natural question leads to one particular instance: Is there a set of all sets?
\begin{thm}[Bertrand Russell 1901]
If one is able to do comprehension (set builder notation) to form new sets, there cannot be a set of all sets.
\end{thm}
\begin{proof}
\Hide{3in}{
For sake of contradiction, let us suppose that this theorem is false. Then we know that there is a set of all sets, and we are able to do comprehension. Let $\Omega$ be the set of all set.
Now, we want to get a contradiction, and we suspect (given the way the theorem was stated) it has something to do with comprehension. So define a set $B$ as follows:
\[
B = \set{x \in \Omega \mid x\notin x}
\]
That is, $B$ is the set of all sets which do not contain themselves as members. We don't know much about $B$; maybe it is empty, maybe it is very large. But as $B$ is a set, we are allowed to ask questions to $B$ about who are its members. $B$ itself is either a member of $B$, or not.
\begin{quotation}
Case 1: $B\in B$.
We defined $B$ by comprehension, so something gets inside of $B$ only when it satifies the above formula. Therefore, we know $B\notin B$, which is a contradiction.
Case 2: $B\notin B$.
Look at the definition of $B$. We put a set $x$ in $B$ exactly when $x\notin x$. As $B\notin B$ we know therefore that $B\in B$, which of course is a contradiction.
\end{quotation}
As $B$ is a set, one of these two cases must hold, but they both lead to contradictions. Therefore, we can conclude that our initial assumption was incorrect: $\Omega$ is not a set.
}
\end{proof}
Therefore, we can conclude that the set of all sets is not a set. Russell's result was important because it showed that the lax rules of set theory at the time (the turn of the 20th century) did not suffice for a formal system. It was riddled with paradoxes.
To solve the problem, during the early 20th century, a program was started to write down what people believed were the rules for set theory. These are rules that you can understand (for the most part): $\emptyset$ and $\N$ are sets, one can take unions and use comprehension. Over the decades, more had to be added to make the system more powerful, but the spirit was always the same.
The idea of Russell's Paradox is an important one. The underlying principle of \df{self-reference}; we define $B$, and then as whether $B$ satisfies the very property that defines it. This idea will be re-explored next week when we talk about Cantor's Theorem. To see another interpretation of Russell's Paradox, we have the following story:
\begin{eg}[Barber's Paradox]
Consider a town in which every man is clean-shaven. There is one male barber, and the barber shaves every man who does not shave himself.
Who shaves the barber?
\end{eg}
\subsection{Powersets}
We learn a new way to make a set out of another set. This is another way to form sets which is simply conjectured by the rules of set theory.
\begin{dfn}
The \df{powerset} of a set $A$, denoted $\wp(A)$, is the set of all subsets of $A$.
\end{dfn}
\begin{eg}
Let $A = \s{ 1,2,3 }$. Then
\[
\wp(A) = \set{ \emptyset, \s{1},\s{2},\s{3},\s{1,2},\s{1,3},\s{1,2},\s{1,2,3} }
\]
\end{eg}
\begin{thm}
For any set $A$, we have $\wp(A)\neq \emptyset$.
\end{thm}
\begin{proof}
\Hide{2cm}{
To show $\wp(A)\neq\emptyset$, we need only show that $\wp(A)$ has a member. In other words, we need to show that $A$ has a subset. Well, as stated, $\emptyset\sbs X$ for any set $X$, therefore $\emptyset\sbs A$. So $\emptyset\in \wp(A)$, so $\wp(A)$ is nonempty.
}
\end{proof}
\begin{thm}
\[\wp(A\cap B) = \wp(A) \cap \wp(B)\]
\end{thm}
\begin{proof}
\Hide{.5in}{
($\sbs$) Take $X\in \wp(A\cap B)$. Then $X\sbs A\cap B$. As $X\sbs A\cap B$ we know ever member of $X$ is in $A$, so $X\sbs A$; similar ever member of $X$ is in $B$ so $X\sbs B$. Therefore $X\in \wp(A)$ and $X\in \wp(B)$, so $X\in \wp(A)\cap \wp(B)$.
($\sps$) Take $X\in \wp(A)\cap\wp(B)$. Then $X\in \wp(A)$ and $X\in \wp(B)$. Thus $X\sbs A$ and $X\sbs B$. We want to show that $X\in \wp(A\cap B)$, ie. $X\sbs A\cap B$. So, take $x\in X$ arbitrary. As $X\sbs A$ we know $x\in A$, and similar as $X\sbs B$ we know $x\in B$. Therefore, $x\in A\cap B$, which is what we wanted.
}
\end{proof}
For the homework, you'll be asked the prove an analogous result for $\cup$.
\begin{thm}
For every $n\in \N$, we have $[n]\in \wp(\N)$.
\end{thm}
\begin{proof}
\Hide{1cm}{
Suffices to show that for every $n$, we have $[n]\sbs \N$. But this is obvious, as if $x\in [n]$ then as $[n] = \set{1,2,3,\ldots, n}$ we have $x = i$ for some $0< i \leq n$ in the naturals.
}
\end{proof}
\begin{question}
If a set $A$ has $n$ members, then how many members does $\wp(A)$ have?
\end{question}
\begin{ans}
\Hide{1in}{
$2^n$; you can prove this with induction.
If $A$ has $0$ members, then $A=\emptyset$, and the only subset of $A$ is $\emptyset$. Therefore $\wp(A)$ has $1$ member.
Assume any set of size $n$ has $2^n$ subsets. Look at an arbitrary set of size $n+1$; call it $A$. Want to show that $A$ as $2^{n+1}$ subsets. Well, take $x\in A$. And look at $A\minus \s{x}$. This is a set with $n$ members. Thus it has $2^n$ subsets. For each one of these subsets there is another subset in which $x$ is added.
One must argue that every subset can be formed this way, but that is straightforward as every subset either has $x$ or does not, and if it does have $x$ in it, then it is still a subset when $x$ is removed.
}
\end{ans}
\subsection{Cartesian Product}
So far, we have looked at sets. Sets have absolutely no structure or order. Most of math, however, has structure. The natural numbers have lots of structure; there is an ordering, there is arithmetic, etc.
In order to solve this problem we introduce the Cartesian product (named after Ren\'e Descartes). You have really already seen the concept before.
\begin{rmk}
Recall the \df{Cartesian Plane} is the set of ordered pairs $(x,y)$ where $x$ and $y$ are reals. These make a plane in geometry.
\end{rmk}
\begin{dfn}
The \df{Cartesian Product} or sets $A$ and $B$, denoted $A\times B$ (spoken as $A$ cross $B$) is the set of ordered pairs, where the first coordinate comes from $A$ and the second from $B$. That is, if $x\in A$ and $y\in B$ then
\[
(x,y) \in A\times B
\]
\end{dfn}
\begin{eg}
\[
[3]\times [2] = \set{ (1,1),(2,1),(3,1),(1,2),(2,2),(3,2) }
\]
\end{eg}
Therefore the notation for the Cartesian Plane is $\R \times \R$.
This is the first bit of structure we have put on a set. If we have an ordered pair, we can ``recover'' which is the first element, and which is the second. This simple idea is very, very powerful and will be the backbone of defining all complicate structures on sets.
\begin{rmk}
Ordered pairs can be compared; $(a,b) = (c,d)$ if and only if $a=c$ and $b=d$.
\end{rmk}
\section{Relations}
With the Cartesian product allowing us to make structures, we talk about our first structure: Relations.
\begin{eg}
We have many natural relations in our day to day life. ``Sibling of'' is one. $A$ is a sibling of $B$ if they have the same parents. This relation has a number of interesting properties:
\begin{itemize}
\item $A$ is a sibling of $B$ means that $B$ is a sibling of $A$.
\item $A$ is a sibling of $B$ and $B$ is a sibling of $C$ means that $A$ is a sibling of $C$.
\end{itemize}
There is another relation ``ancestor of''. This relation fails on the first property above (if $A$ is my ancestor, that does not make me the ancestor of $A$) but does pass on the second.
\end{eg}
\begin{dfn}
If $A$ and $B$ are sets then a \df{relation $R$ relating $A$ to $B$} is a subset of $A\times B$.
If $(a,b)\in R$ for $a\in A$ and $b\in B$ then we say \df{ $a$ is $R$-related to $b$}. We typically write $R$ in either infix or prefix notation. Therefore the following are all equivalent (although context dependent)
\begin{itemize}
\item $(a,b)\in R$
\item $aRb$
\item $Rab$
\end{itemize}
Notice, they are all atomic statements which are either true or false and can be verified just by checking membership in R.
If $A=B$ (as is frequently the case) then we say \df{$R$ is a relation on $A$}
\end{dfn}
\begin{eg}
A natural example is $<$ on the natural numbers $\N$. Then we have $(a,b)\in <$ if and only if $a$ is smaller than $b$ with respect to the usual ordering on the natural numbers. We typically write this in infix notation: $a