\documentclass[]{article}

\usepackage{epsfig}
\usepackage{latexsym}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{graphicx}
\pagestyle{empty}
%\setlength{\topmargin}{-1in}
%\setlength{\oddsidemargin}{-.3in}
%\setlength{\textheight}{9.5in}
%\setlength{\textwidth}{7.2in}
\newcommand{\bZ}{\mathbb{Z}}
\newcommand{\bR}{\mathbb{R}}
\newcommand{\mcg}{\vspace{0.3cm}}
\newcommand{\blank}{\underline{\hspace{2cm}}}
\newcommand{\solution}[1]{\parbox{1cm}{} \hfill {#1}\parbox{3cm}{: \hrulefill} \\}
\begin{document}

\begin{center}
\Large Studyguide for Baby Exam
\end{center}

{\Large M366} \hfill {\Large Spring 2012} \\


\vspace{0.5cm}

\textit{The goal of this worksheet is to solidify concepts about sets, functions, equivalence relations and quotient sets. You are encouraged to work with others! Please pay especial attention to your exposition. Keep it simple and understandable!  English is strongly encouraged as the language to use :)}
\vspace{0.5cm}




\section{Sets}
\begin{enumerate}

\item Let
$$
A=\{1, 2, 3, 4, 5, Joe, apple\} , B=\{ 1, 2, Bob, Joe \}.
$$
Write down:
\begin{enumerate}
	\item $$ A\cup B. $$
         \item $$ A\cap B.$$
	\item $$ A \setminus B.$$
	\item $$ B \setminus A. $$
	\item $$ A \cap B^c.$$
\end{enumerate}
	\item \textsc{True or False} Let
$$
A=\{1, 2, 3, 4, 5\} , B=\{ 1, 2, 5 \}, C=\{10, 20, 30, 40, 50\}.
$$
\begin{enumerate}
         \item $$ 3\in A. $$
         \item $$ 3\in B.$$
         \item $$ 3\in B^c.$$
	\item $$ A \subseteq B .$$
	\item $$ B\subseteq A .$$
	\item $$ A = C.$$
	\item $$ B \subseteq C.$$
	\item $$ B \cap C \subseteq C.$$
\end{enumerate}	
 \item Prove that for every pair of sets $X$ and $Y$, 
 $$
 X \subseteq X \cup Y
 $$
\item Prove that two sets are equal if and only if they are each a subset of the other. In symbols:
$$
X = Y \  \ \mbox{ if and only if}\ \ \ X\subseteq Y \ \mbox{ and} \ Y \subseteq X.
$$
\item What is the set
$$ (A \cap B)\cup (A^c\cap B)= ?$$
\end{enumerate}

\section{Functions}

\begin{enumerate}
\item Give an example of:
\begin{enumerate}
\item a function.
\item a surjective function $f$ from the set of all integers $\mathbb{Z}$ to the set $Y=\{red, green\}$.
\item an injective function $g$ from the set $Y=\{red, green\}$ to  the set of all integers $\mathbb{Z}$.
\item a bijective function from  $Y$ to itself.
\item a function from $Y$ to itself which is neither injective nor surjective?
\end{enumerate}

\item Refer to the functions $f$ and $g$ that you defined in the previous problem. Describe $f\circ g$ and $g \circ f$.

\item Prove that the composition of two injective functions is an injective function, and that the composition of two surjective functions is surjective. Are the converse statements true: if $f\circ g$ is injective(resp. surjective), then $f$ and $g$ both have to be injective (resp. surjective)?

\item Write down a function $f: \mathbb{N} \to \mathbb{N}$ that is injective but not surjective.  Write down function $g: \mathbb{N} \to \mathbb{N}$ that is surjective but not injective. Can you do this if you replace $\mathbb{N}$ by a finite set? Why?

\item \textbf{Hilbert's Hotel.} You own Hilbert's hotel, a hotel with infinitely many rooms numbered by natural numbers. It is a dark and stormy night and a customer stops by looking for a room. Your hotel is full, but... can you find a way to accommodate the extra customer without having anyone share a room? 

Right after you have done this, an infinite bus breaks down right in front of your hotel, and now the infinite passengers (sitting in the bus seats indexed by natural numbers) all need a room. Can you accommodate them?

What is the relationship between this problem and the previous one? 

\item \textbf{Important.} Let $f:X\to Y$ and $g:Y\to X$. Prove that $f$ and $g$ are inverse functions of each other if and only if $g\circ f= Id_X$ and $f \circ g = Id_Y$. This theorem is used as follows: suppose you want to show that a function $f$ is bijective. If you can construct an inverse function $g$  (i.e. a $g$ such that $g\circ f= Id_X$ and $f \circ g = Id_Y$), then you win! (Why?)

\item Show that the function $f: \mathbb{R} \to \mathbb{R}$ defined by $f(x)= 3x$ is a bijective function. 

 
\end{enumerate}


\section{Equivalence Relations}



%\vspace{1cm}
%\begin{center}
 %\includegraphics[width=.7\textwidth]{1=2.pdf}
%\end{center}
%\vspace{1cm}
 
\begin{enumerate}
\item Give an example of an equivalence relation.
\item Let $X$ be the set of students of our class. Does the rule

\textit{x $\sim$ y if $x$ and $y$ are born in the same year}

define an equivalence relation?
\item Let $X=\{ 1,2,3,4,5,6,7\}$. Do the subsets:
$$Y_1= \{ 1,7\},Y_2= \{ 2,3,4\},Y_3= \{ 6\},
Y_4= \{5\}$$
define an equivalence relation on $X$? How many elements does the quotient set have? Is $[2] =[3]$? 

\item Let $X=\{Cat, Dog, Mouse, Sheep, Ram, Horse, Kangaroo\}$. \\
Define an equivalence relation on $X$ as follows:  two elements of $X$ are equivalent if they have the same number of letters.

\noindent
\textbf{Comments:}\\
You don't have to prove that this rule is an equivalence relation. You can assume I gave you a good one! Also, if you want to save some time in writing you can just use the first letter to indicate each animal.
\begin{enumerate}
\item How many elements does the quotient set $ X/\sim$ have?
\item Write down the equivalence classes for this equivalence relation.
\item Write down the partition that this equivalence relation determines for the set $X$.
\item Write down explicitly the projection function $p:X \to X/\sim$.

\end{enumerate}
\item Let $X= \mathbb{Z}$ and $Y= \{0,1,2,3,4\}$ and define a surjective function:
$$
rem: X  \to Y
$$ 
by $rem(x)$= the remainder of division of $x$ by $5$.
Describe the equivalence relation induced by $rem$ on the set $X$. Describe the natural bijection between $Y$ and the quotient set $X/\sim$.






\end{enumerate}

\end{document}