\documentclass{article}
\input{preamble.tex}
\usepackage{url}
\title{Day 9}
\date{Friday June 1, 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{Containment Proofs}
	
	It is often necessary to prove that one set is contained in another. These are call containment proofs. This amount to proving 
	\[
		\A x \in A \stt x\in B
	\]
	That is, if $x$ is in $A$ then $x$ is in $B$. 
	\begin{question}
	What do you think the first line and last lines of such a proof should be?
	\end{question}
	\begin{ans}
	\Hide{1cm}{
		Take $x\in A$ arbitrary	
		
		\ldots
		
		Then $x\in B$.
	}
	\end{ans}
	
	Recall we have defined the following operations so far:
	
	\begin{itemize}
		\item $A\cup B$ is the set of all elements that are in $A$ or in $B$. That is:
		\[
			\A x \st x\in A\cup B \bimp (x \in A \oor x\in B)
		\]
		Therefore, how do you think you use the information that $x\in A\cup B$?
		
		\Hide{1cm}{
			You do cases on whether $x\in A$ or $x\in B$.
		}
		\item $A\cap B$ is the set of all elements that are in both $A$ and $B$. That is:
		\[
			\A x \st x\in A\cap B \bimp (x\in A \oand x\in B)
		\]
		How do we use the information that $x\in A\cap B$?
		
		\Hide{1cm}{
			You know that $x\in A$ and $x\in B$
		}
	\end{itemize}

	\begin{eg}
		For any set $A$ and $B$ we have
		\[
			A \cap B \sbs A\cup B
		\]
		\begin{proof}
			\Hide{1cm}{
				Take $x\in A \cap B$ arbitrary. So $x\in A$ and $x\in B$. In particular, $x\in A$, so $x\in A\cup B$.
			}
		\end{proof}
	\end{eg}
	
	For equality remember
	\[
		(A = B) \iff A\sbs B \mbox{ and } B\sbs A
	\]
	Therefore, there are two directions to $A=B$; one when you take an element of $A$ and show it is in $B$, and the other when you take one in $B$ and show it's in $A$. We will see more example of this soon, but we need a few more ways to build sets.
	\begin{question}
	What would it take to show that $\neg (A\sbs B)$?
	\end{question}
	\begin{ans}
		You would have to show an $x$ that is in $A$ but is not in $B$. We will see some examples later. 
	\end{ans}

		\subsection{Comprehension}
	
	Say we have some logical stuff, and we wish to form a new set by taking all thing things that satisfy this. For instance, maybe I want to take all the natural numbers $n$ that are even, ie. satisfy $\E m\in\N \stt 2m = n$. 
	
	This is called \df{comphrension}, \df{seperation}, or \df{specification} depending on who you talk to. The notation that we use for this is called \df{set builder notation}. In this instance, we would write
	\[
		\set{ x \in \N \mid \E m\in \N \stt 2m = n }
	\]
	We read this as ``the set of all natural numbers such that there exists an $m$ in the naturals such that $2m$ equal $n$.'' 
	
	Note, in this case we are carving a smaller set out of a larger set. When doing this comphrension, as with relative complements, it doesn't make sense without specifying a larger set. 
	
	In general, set builder notation looks like
	\[
		B = \set{ x \in A \mid P(x) }
	\]
	where $P(x)$ is some formula with only $x$ free. Then, to check membership in this set, one ``loops through'' the member of $A$, 
	
\begin{verbatim}
New Set B = \emptyset;
foreach(x in A) {
   if ( P(x) ) {
      Put x in B;
      next;
   }
   else {
      next;
   }
}
\end{verbatim}

\begin{question}
	If $P(x)$ is always false, what would $B$ be?
\end{question}
\begin{ans}
	\Hide{1cm}{
		The emptyset!	
	}
\end{ans}

\begin{eg}
	\begin{itemize}
		\item $\set{n\in \N \mid \E m\in \N \st 2m = n} = $ even naturals
		\item $\set{n\in \Z \mid n\geq 0} = \N$
		\item $\set{n\in \R \mid n = \left\lceil n \right\rceil} = \Z$
		\item $\set{n\in \N \mid (n\neq 1) \oand \A p_1,p_2 \stt n=p_1\cdot p_2 \to ((p_1=1)\oor(p_2=1))} = $ set of primes.
	\end{itemize}

\end{eg}


\subsection{Relative Complements}

	So, one may ask the question: What is the compliment of a set, ie. the set of all elements not in that set? What is the problem with asking this?
	
	\Hide{1in}{
		Well, the color blue is an object, and it is not a natural number, so would the color blue be in the complement on $\N$? It's hard to peg down exactly the larger universe we are dealing with here, so it's not natural to take a compliment of a set. 	
	}
	
	To fix this problem we talk about the \df{relative complement} or \df{set difference}. The set difference, which we say $A$ take away $B$ or $A$ minus $B$, is the things which are in $A$ but not in $B$. We write this is 
	\[
		A \minus B
	\]
	(in \LaTeX, this is \textbackslash setminus)
	
	Logically, we write
	\[
		\A x \st (x\in A\minus B) \bimp ( (x\in A) \oand (x\notin B))
	\]
	
	Note: I used some `slang' notation here. If $\neg(x\in B)$ we usually write $x\notin B$. 
	


\subsection{Examples of Containment Proofs}

\begin{eg}
	\begin{enumerate}
		\item $(A\minus B)\cup (C\minus B) = (A\cup C) \minus B$
		\begin{proof}
			\Hide{1.5in}{
				($\sbs$) First, take $x\in (A\minus B)\cup(C\minus B)$. We do cases on whether $x\in A\minus B$ or $x\in C\minus B$. 
				
				Case 1: $x\in A\minus B$. then $x\in A$ and $x\notin B$. So, as $x\in A$ we know $x\in A\cup C$ as this is a larger set. So $x\in (A\cup C)\minus B$ as $x\notin B$, which is what we want.
				
				Case 2: $x\in C\minus B$, then $x\in C$ and $x\notin B$. So as $x\in C$ we know $x\in A\cup C$ as this is a larger set. So $x\in (A\cup C\minus B$ as $x\notin B$, which is what we want.
				
				($\supseteq$) Take $x\in (A\cup C)\minus B$. Then $x\in (A\cup C)$ and $x\notin B$. Do cases on whether $x\in A$ or $x\in C$. 
				
				Case 1: $x\in A$. Then $x\in A$ and $x\notin B$, so $x\in A\minus B$. so $x\in (A\minus B)\cup (C\minus B)$. 
				
				Case 2: $x\in C$. Then $x\in C$ and $x\notin B$, so $x\in C\minus B$. So $x\in (A\minus B\cup (C\minus B)$. 
				
			}
		\end{proof}
		\item $(A\minus B) \cap C = (A\cap C)\minus B$.
		\begin{proof}
		\Hide{1in}{
			($\supseteq$) First take $x\in (A\cap C)\minus B$. Then $x\in A\cap C$ and $x\notin B$. So $x\in A$ and $x\in C$ and $x\notin B$. So, $x\in A\minus B$, so we are done as $x$ is also in $C$ so $x\in (A\minus B)\cap C$
			
			($\subseteq$) Take $x\in (A\minus B)\cap C$. then $x\in A\minus B$ and $x\in C$. So $x\in A$ and $x\in C$ but $x\notin B$. So $x\in A\cap C$. So $x\in (A\cap C)\minus B$
		}
		\end{proof}
		\item $A \minus ( B\cup C) \sbs A\minus B$ but equality need not hold.
		\begin{proof}
		\Hide{1in}{
			Take $x\in A\minus (B\cup C)$. Then $x\in A$ and $x\notin B\cup C$. Then $x\notin B$, as otherwise $x$ would be in $B\cup C$. So $x\in A\minus B$. 
			
			Equality need not hold; For instance, if $A=\s{1}$ $B=\emptyset$ and $C=A$, the lefthand side is empty, but the righthand side is $\s{1}$. 
		}
		\end{proof}
		\item $\set{n\in \R \mid n = \left\lceil n \right\rceil} = \Z$
		\begin{proof}
			\Hide{1in}{
				Take $x$ in the left hand side. Then $x = \left\lceil x \right\rceil$. As $ \left\lceil x \right\rceil$ is an integer by definition, $x\in \Z$. 
				
				Take $x$ in the right hand side. $x$ is an integer, so $x\in  \left\lceil x \right\rceil$. So $x$ is the left hand side.
			}
		\end{proof}
	\end{enumerate}	

\end{eg}

\section{Indexed Families}

Let $\Lambda$ be a set. We can talk about a family of sets $X_\alpha$ where each $\alpha\in \Lambda$. That is to say, that there are a bunch of sets $X_\alpha$ one for each $\alpha\in\Lambda$. Then, we can take the union of all of these sets by 
\[
	\bigcup_{\alpha\in\Lambda} X_\alpha
\]
And similarly the intersection
\[
	\bigcap_{\alpha\in\Lambda} X_\alpha
\]

Think of these a lot like summations. For instance, if $\Lambda = [5]$ then really
\[
	\bigcup_{\alpha\in[5]} X_\alpha = X_1\cup X_2\cup X_3 \cup X_4 \cup X_5
\]

If you know $x\in \bigcup_{\alpha\in\Lambda} X_\alpha$ then you know there is some $\alpha\in\Lambda$ such that $x\in X_\alpha$. Similarly, if you know $x\in \bigcap_{\alpha\in\Lambda} X_\alpha$ then you know that for every $\alpha\in\Lambda$, $x\in X_\alpha$.

Does this seem familiar?

\[\A x \stt ((x\in\bigcup_{\alpha\in\Lambda} X_\alpha) \bimp (\E \alpha\in \Lambda \st x\in X_\alpha))\]

And 
\[\A x \stt ((x\in\bigcap_{\alpha\in\Lambda} X_\alpha) \bimp (\A \alpha\in \Lambda \st x\in X_\alpha))\]


\begin{eg}
	\[
		\mbox{Primes} \sbs \bigcup{p\in \mbox{Primes}} \set{n\in \N \mid n=p^k\mbox{ for some }k\in \N}
	\]
	\begin{proof}
		Take $x$ a prime number. Then $p = p^1$. Therefore $x \in \set{n\in \N \mid n=x^k\mbox{ for some }k\in \N}$
	\end{proof}
\end{eg}

\begin{eg}
	\[
		\s{1} = \bigcap_{i\in \N; i> 1} \set{n\in \N \mid \neg(i\mid n)}
	\]
	\begin{proof}
		($\sbs$) Take $x$ in the left hand side. It must be $1$. We want to show that $1$ is in the right hand side; so it suffices to show for every $i\in \N$ $i>1$ that $1\in \set{n\in \N \mid \neg(i\mid 1)}$. Let $i$ be arbitrary natural larger than $1$. Then $i$ does not divide 1, so $1$ is in that set. 
		
		($\sps$) Take $x\in \bigcap_{i\in \N; i> 1} \set{n\in \N \mid \neg(i\mid n)}$. Well, $x$ is a natural, and we we know that for every $i\in \N$ where $i>1$ that $\neg(i\mid x)$. Suppose that $x$ is natural and not equal to $1$ for contradiction. If $x=0$ then we get an immediate contradiction because every $i$ in $\N$ divides $0$, in particular, $2$ does.
		
		Otherwise, $x>1$. Then, as we know for every $i\in \N$ where $i>1$ that $\neg(i\mid x)$, we know in particular $\neg (x\mid x)$. But this is a contradiction. 
	\end{proof}


\end{eg}





	
	
\end{document}
