%Bits of this need to be mvoed to other places, eg basic operations
%should probably be moved to intro/datatypes.tex

\section{Sets}

\emph{This section was not covered in lecture, but summarized material
  from your background reading}


\subsection{Russell's paradox}

We might think that set theory is obvious, but this is not the case\.
Consider the set $S = \{x \given \mbox{$x$ 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 \in S \given \mbox{$x$ is a set and $x
  \notin x$}\}$\.  If $S$ is a set, then so is~$Q$ by standard axioms
like comprehension\.  Note: $Q \subseteq S$.

Now note that some sets are in $Q$ and some aren't\.
For example,
the set $A = \{1,2,3\}$ is not an element of itself, so $A \in Q$\.
On the other hand,
The set 
$P = \{\mbox{all infinite sets}\}$ is a set (by comprehension from $S$)\.
Therefore, $P \in P$ as the set $P$ itself is infinite\.
So $P \notin Q$\.

The troublesome question is: is $Q\in Q$? 
\begin{enumerate}
\item If $Q \in Q$ then $Q \notin Q$, a contradiction.
\item If $Q \notin Q$ then $Q \in Q$ also a contradiction.
\end{enumerate} 

This is clearly a paradox\.  In fact, this paradox, at the time it was
discovered by Russell 1901, was a blow to the then current
attempts to formalize all of mathematics axiomatically\.
Mathematicians had to work very hard to find a consistent set of
axioms (note that 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 without referring to a starting set, as we did
for~$S$ above\.  Axiomatic set theory has a specific set of rules for
how you can form sets---rules that don't allow the set~$S$ above to be
specified, and therefore avoid the paradox\.

Fortunately, we'll be working naively, so this is a matter of only
theoretical interest.



\subsection{Basic set operations}

There are several standard operations on sets\.  In axiomatic set
theory, the claims that these operations yield new sets are axioms.
\begin{description}
\item[Union:] $A\cup B=\{x\given x\in A \lor x\in B\}$.
\item[Intersection:] $A\cap B=\{x\given x\in A \land x\in B\}$.
\item[Difference:] $A-B = \{x\given x\in A \land x \notin B\}$.
  This is also written as $A\setminus B$.
\item[Complement:] $A^c = \{x\given x\notin A\}$.
  This is also written as $\bar A$.
\item[Symmetric difference:] $A \oplus B = A \cup B - A\cap B$.
  This is also written as $A \mathop{\triangle} B$.
\end{description}
Sets and operations on sets can be represented using Venn diagrams
(see Rosen, sections 1.4, 1.5)\.
Union and intersection can be extended to apply to more than two sets\.  
Given a finite 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$, and  
\[
\bigcap_{i=1}^n A_i
\]
is the set of elements in all of the $A_i$\.
Both of these make sense if $i=1$---they reduce to just $A_1$\.
In fact, for $i = 0$, the appropriate thing is to  say the union of no
sets is $\emptyset$ and 
intersection of no sets is universal set\.
This definition of union and intersection of no sets might seem
arbitrary, but in fact it can be motivated in several ways\.
For example, if we want to define the union of a finite 
family of sets $A_1,A_2,\ldots, A_n$, we can define
$\bigcup_{i=1}^{1} A_1 = A_1$ and 
$\bigcup_{i=1}^{n+1}A_i = (\bigcup_{i=1}^{n} A_i)\cup A_{n+1}$.
If we want this recursive definition to work also for base case 
$n=0$ we must set $\bigcup \emptyset = \bigcup_{i=1}^0 A_i = \emptyset$\.
The analogue holds for intersection\. The recursive definition 
of  $\bigcap_{i=1}^{n+1}A_i = (\bigcap_{i=1}^{n} A_i)\cap A_{n+1}$
must have base case 
$\bigcap \emptyset = \bigcap_{i=1}^0 A_i = U$
if we want $\bigcap \{A_1\} = (\bigcap \emptyset)\cap A_{1} = A_1$\.

Instead of using an explicit index, we can just consider a set of sets\.
If $\mathcal{S}$ is a \emph{set of sets}, then 
\[
\bigcup \mathcal{S}
\] 
denotes the union of all the sets in $\mathcal{S}$, in any order\.
(One can prove that the order doesn't matter.) 
Likewise, 
\[
\bigcap \mathcal{S} 
\]
denotes the intersection of all the sets in $\mathcal{S}$\.

Complement is different from all the other operations, because it
assumes some universe $U$ from which we extract the things not in
$A$\.  All sets in question are supposed to be subsets of $U$\.  Given
a universal set $U$, the complement operation can be expressed as $A^c
= U - A$\.  The universe $U$ is often implicit, where there seems to
be little chance of confusion\.

There is a close correspondence between set operations and logical
operations: consider sets $A$, $B$ and $C$ defined by $A=\{x\mid
P(x)\}$, $B=\{x\mid Q(x)\}$, $C=\{x\mid R(x)\}$, where $P,Q,R$ are
predicates\.
\begin{description}
\item[set union vs. predicate or:]
 $A\cup B =  C$ if and only if 
 $P(x)\vee  Q(x) \equiv  R(x)$ 
\item[set intersection vs. predicate and:]
 $A\cap B =  C$ if and only if 
 $P(x) \wedge Q(x)\equiv R(x)$ 
\item[set difference vs. predicate ``non implication'':]
 $A - B = C$ if and only if 
 $\neg (P(x)\rightarrow Q(x)) \equiv R(x)$
\item[set complement vs. predicate not:]
 $A^c=B$ if and only if $\neg P(x) \equiv Q(x)$
\item[set symmetric difference vs. predicate exclusive or:]
 $A\oplus B = C$ if and only if $P(x)\oplus Q(x)\equiv R(x)$.
\end{description}
Predicates and sets often form alternative ways of looking at the same
notions\.
Given predicates $p$ and $q$, define 
\begin{align*}
P &= \{ x \mid p(x) \} \\
Q &= \{ x \mid q(x) \}
\end{align*}
Then $P \cup Q = \{ x \mid p(x) \vee q(x) \}$, and so on.



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

Another very important operation on sets is that of the \emph{power
set} of a given set $A$\.
It is denoted by $\power(A)$ and consists of the set of all subsets
of $A$\.
In other words, $\power(A) = \{x\given x\subseteq A\}$\.
Note that for any set $A$,
$\emptyset\in\power(A)$ and $A\in \power(A)$.
\begin{example}
If $A=\{1,2\}$ then $\power(A)=\{\emptyset,\{1\},\{2\},\{1,2\}\}$.
\end{example}
\begin{theorem}
If $A$ has $n$ elements, then $P(A)$ has $2^n$ elements.
\end{theorem}
\begin{proof}
Ordinary Induction on $n$. 
Base case:  $n = 0$.  Then $P(A)$ has one element, $\emptyset$\.
Inductive step: We assume the theorem for $n$ and prove it for $n+1$\.
Pick one element, $a \in A$\.
The subsets can be divided into two groups---those containing $a$ and
those not containing $a$\.
Moreover, the set of subsets of $A$ not containing $a$ is 
$\power(A-\{a\})$, and the set of subsets of $A$ containing $a$
is the set $\{\{a\}\cup B \mid B\in \power(A-\{a\})$ which has 
the same number of elements as $\power(A-\{a\})$\.
By our induction hypothesis $\power(A-\{a\})$ has $2^{n-1}$
elements,
so the total is $2^{n-1} + 2^{n-1} = 2^n$.
\end{proof}
I did a base case of~$0$ here.  Does the inductive step from $0$
to~$1$ work correctly\?
Yes, it corresponds to the sets $\{\emptyset\}$ and $\{ a \}$\.

Because of this cardinality relationship, $\power(A)$ is sometimes
denoted by $2^A$.



\subsection{Set identities}

There are a large number of set identities involving relationships
among sets built using various operations\.
See p.~49 of Rosen\.
Here we just list some sample properties, and show how they can be
proved.
\begin{theorem}
[Distributivity:  Union distributes over intersection]
$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$
\end{theorem}
\begin{proof}
  We show the two sets are equal by proving that each is contained in the
  other.

  $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, which is the RHS.

  On the other hand, if $x \in (B \cap C)$, then $x \in B$ and $x \in
  C$\.  Then by definition of union, $x \in A \cup B$ and $x \in A
  \cup C$\.  It again follows that $x$ is in the intersection.

  $A \cup (B \cap C) \supseteq (A \cup B) \cap (A \cup 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)$\.  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)$.
\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$. 
  
  $(A\cup B)^c\subseteq A^c\cap B^c$: Let $x\in (A\cup B)^c$\.  Then
  by definition of complement, $x \notin A \cup B$\.  It follows
  (proof by contradiction) that $x \notin A$ and $x \notin B$\.
  Therefore, again 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$.
  
  $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{proof} 
The above two theorems have \emph{dual theorems} produced by swapping
$\cap$ and $\cup$\.  This is a general phenomenon---in Rosen, the
theorems are arranged in pairs\.  Duality can be applied to any
theorem that is true for \emph{all} sets\.  Each theorem in a pair can
be obtained from the other by swapping the operations $\cap$ and
$\cup$, and the sets $\emptyset$ and $U$\.  Notice that the complement
operations are not changed.
\begin{theorem}
  $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$.
\end{theorem}
\begin{theorem}
  $(A\cap B)^c=A^c\cup B^c.$
\end{theorem}

