% This is a TeX file
% It is essentially a programming language for mathematics documents
% You can ignore this first portion of the file, as it is essentially a bunch of "include" statements.
\documentclass[10pt]{article}

\usepackage{pictex, latexsym, graphicx,amsmath,amssymb,amsbsy,amsfonts,amsthm,verbatim}
\usepackage{graphics}
\usepackage{fullpage}
\usepackage{fancyhdr}
\usepackage{hyperref}

\usepackage{algorithm,algorithmic}
\usepackage{multirow}

\setlength{\voffset}{-0.25in}
\setlength{\headsep}{0.25in}
\setlength{\parskip}{1em}
\setlength{\parindent}{0em}

% The following denotes a counter for the problems.
\newcounter{problem}
\newcommand{\problem}{\textbf{\refstepcounter{problem}Problem \theproblem.} }

% These are macro shortcuts! Helpful!
\def\vu{\mathbf{u}}
\def\vx{\mathbf{x}}
\def\vb{\mathbf{b}}
\def\vv{\mathbf{v}}
\def\vw{\mathbf{w}}

\renewcommand{\implies}{\rightarrow}
%\newcommand{\lnot}{\neg}
\renewcommand{\lor}{\vee}
\renewcommand{\land}{\wedge}
\newcommand{\xor}{\oplus}
\newcommand{\symmdiff}{\triangle}
\renewcommand{\iff}{\leftrightarrow}
\newcommand{\TRUE}{\mathbf{T}}
\newcommand{\FALSE}{\mathbf{F}}
\newcommand{\universe}{\mathcal{U}}


\def\N{\mathbb{N}}
\def\Q{\mathbb{Q}}
\def\C{\mathbb{C}}
\def\Z{\mathbb{Z}}
\def\R{\mathbb{R}}
\def\cP{\mathcal{P}}


\begin{document}
\pagestyle{fancyplain}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% NOW you can start typing your text that will appear in the PDF!!!

% Note that anything after a '%' is a comment!

% Anything immediately after a '\' is a command. 
% Some denote formatting, some are for special characters.
% The '$' symbol starts and ends "math mode". Use this only for mathematical statements
% In math mode, any sequence of letters is meant to be a list of variables, so use "\sin x" for the sine of x, which will look much different from "sin x"
\chead{COM S 330 --- Homework 05 --- INSERT NAME HERE}

\textit{Type your answers to the following questions and submit a PDF file to Blackboard. 
One page per problem.}


% Problems about Sets!
\problem [5pts] Consider our definitions of $\Z$, $\Q$, $\R$, and $\C$. Recall that $A \subseteq B$ means ``$A$ is a subset of $B$'' and $A \not \subseteq B$ means ``$A$ is not a subset of $B$.''

Prove that (a) $\Z \subseteq \Q$, (b) $\Q \not \subseteq \Z$, (c) $\R \not \subseteq \Q$, (d) $\R \subseteq \C$, and (e) $\C \not \subseteq \R$.


% Be sure to use this \clearpage to make sure your problems are on separate pages!
%\clearpage
\problem [5pts] Prove that if $A \subseteq B$, then $\cP(A) \subseteq \cP(B)$.

% Be sure to use this \clearpage to make sure your problems are on separate pages!
%\clearpage
\problem [5pts] Let $A$ and $B$ be sets. Prove that $|A\cup B|= |A| + |B| - |A \cap B|$, using the following steps:
\begin{enumerate}
\item Prove that if $E$ and $F$ are disjoint sets (i.e. $E \cap F = \varnothing$) then $|E \cup F| = |E| + |F|$.
\item Prove that $|A \cup B| = |A| + |B \setminus A|$.
\item Prove that $|B \setminus A| = |B| - |A \cap B|$.
\item Conclude that $|A \cup B| = |A| + |B| - |A \cap B|$.
\end{enumerate}



% Problems about Set Operations!
% Be sure to use this \clearpage to make sure your problems are on separate pages!
%\clearpage
\problem [5pts]  Let $\universe = \{1,2,3,4,5,6,7\}$, $A = \{ 1, 3, 5, 7\}$, $B = \{4,5,6,7\}$. Determine the following sets:
\[ \overline{A}, \quad A \cap B, \quad A \cup B, \quad A \setminus B, \quad A \symmdiff B.\]



% Be sure to use this \clearpage to make sure your problems are on separate pages!
%\clearpage
\problem [5pts] Let $A$ and $B$ be sets. Prove that $\cP(A) \cap \cP(B) = \cP(A \cap B)$.


% Be sure to use this \clearpage to make sure your problems are on separate pages!
%\clearpage
\problem [10pts] Let $A$, $B$, and $C$ be subsets of a universe $\universe$. Use definitions of set operations and set identities to prove the following equality of sets:
\[
	((B \cap A) \cup (B \cap C))\setminus (A \cap B \cap C) = (B \cap (A \symmdiff C))
\]
[Hint: Show both sides are equal to the set $((B \cap A) \setminus C) \cup ((B\cap C) \setminus A)$.]


% Problems about Functions!

% Be sure to use this \clearpage to make sure your problems are on separate pages!
%\clearpage
\problem [5pts]  Let $A = \{a,b,c\}$, $B = \{1,2,3,4\}$, and $C = \{\pi, \phi, i\}$. Define functions $f : A \to B$ and $g : B \to C$ as
\[
	f(x) = \begin{cases} 2 & x = a\\3 & x = b\\ 4 & x = c\end{cases} \quad
	g(x) = \begin{cases} \pi & x = 1\\ \phi & x = 2 \\ i & x = 3 \\ \pi & x = 4 \end{cases}
\]
Consider each of the functions $f$, $g$, $g \circ f$ and determine if they are injective, surjective, or both.



% Be sure to use this \clearpage to make sure your problems are on separate pages!
%\clearpage
\problem [10pts]  Consider the following function $f : \N \to \Z$:
\[
	f(n) = (-1)^n\left(\frac{n}{2}+\frac{1}{4}\right)  - \frac{1}{4}.
\]
\begin{enumerate}
\item\ [1pt] Write out the elements $f(0)$, $f(1)$, $f(2)$, $f(3)$, $f(4)$, $f(5)$.
\item\ [4pts]  Prove that $f$ is injective. 
\item\ [5pts]  Prove that $f$ is surjective.
\item\ [+5pts] Describe a function $g : \Z \to \Q$ that is surjective (and prove it is surjective).
\end{enumerate}




\end{document} 