% 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[landscape]{geometry}

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

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

\setlength{\voffset}{-0.5in}
\setlength{\headsep}{0.25in}

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

% 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}
\renewcommand{\iff}{\leftrightarrow}
\newcommand{\TRUE}{\mathbf{T}}
\newcommand{\FALSE}{\mathbf{F}}
\newcommand{\universe}{\mathcal{U}}

\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"
 % no page number

\renewcommand{\arraystretch}{2}

\begin{center}
\textbf{COM S 330 --- Functions and Compositions}
\end{center}

Let $A$, $B$, and $C$ be sets (not necessarily the same, but also not necessarily different), and let $f : A \to B$ and $g : B \to C$ be functions. Recall the definitions of injective, surjective, and bijective.

\begin{center}
\begin{tabular}[h]{|p{3in}|p{3in}|p{3in}|}
\hline
$f : A \to B$ injective (one-to-one) & $f : A \to B$ surjective (onto) & $f : A \to B$ bijective (one-to-one and onto) \\
$\forall x,y\in A [(f(x) = f(y))\implies (x=y)]$ &
$\forall y \in B\exists x \in A (f(x) =y)$ &
$f$ is injective and surjective.\\
%$\forall x,y\in A [(x\neq y) \implies f(x) \neq f(y)]$ &
%$\lnot \exists y \in B \forall x\in A (f(x) \neq y)$&
%\\
If $f(x)=f(y)$ for any two values $x,y$ in the domain $A$, then $x$ and $y$ must be equal.
&
If $y$ is in the codomain $B$, then there exists an element $x$ from the domain $A$ such that $f(x) = y$.
&
There exists an inverse function $f^{-1} : B \to A$ such that $f^{-1}(y)=x$ if and only if $f(x) = y$.\\
\hline
\end{tabular}
\end{center}

The \emph{composition} function $g \circ f : A \to C$ is defined by $(g \circ f)(x) = g(f(x))$ for all $x \in A$.
In the table below, we have specified different options for $f$ and $g$ being injective, surjective, neither, or both. You should determine if the given situations imply that $g \circ f$ is injective, surjective, neither, or both. Is it ALWAYS one of these cases, or could it possibly change for different examples? If your answers is ``Always Yes'' or ``Always No'' then give a proof. If your answer is ``Sometimes Yes, Sometimes No'' then give an example for each situation.


\begin{center}
\begin{tabular}[h]{|c|c|c|c|c|}
\hline
& $g$ bijective & $g$ injective, not surjective & $g$ surjective, not injective & $g$ not injective or surjective \\
\hline
\multirow{2}{*}{$f$ bijective} 
& Is $g \circ f$ injective? \underline{\hspace{0.5in}}
& Is $g \circ f$ injective? \underline{\hspace{0.5in}}
& Is $g \circ f$ injective? \underline{\hspace{0.5in}}
& Is $g \circ f$ injective? \underline{\hspace{0.5in}}\\
\cline{2-5}
& Is $g \circ f$ surjective? \underline{\hspace{0.5in}}
& Is $g \circ f$ surjective? \underline{\hspace{0.5in}}
& Is $g \circ f$ surjective? \underline{\hspace{0.5in}}
& Is $g \circ f$ surjective? \underline{\hspace{0.5in}}\\
\hline
\multirow{2}{*}{$f$ injective, not surjective} 
& Is $g \circ f$ injective? \underline{\hspace{0.5in}}
& Is $g \circ f$ injective? \underline{\hspace{0.5in}}
& Is $g \circ f$ injective? \underline{\hspace{0.5in}}
& Is $g \circ f$ injective? \underline{\hspace{0.5in}}\\
\cline{2-5}
& Is $g \circ f$ surjective? \underline{\hspace{0.5in}}
& Is $g \circ f$ surjective? \underline{\hspace{0.5in}}
& Is $g \circ f$ surjective? \underline{\hspace{0.5in}}
& Is $g \circ f$ surjective? \underline{\hspace{0.5in}}\\
\hline
\multirow{2}{*}{$f$ surjective, not injective} 
& Is $g \circ f$ injective? \underline{\hspace{0.5in}}
& Is $g \circ f$ injective? \underline{\hspace{0.5in}}
& Is $g \circ f$ injective? \underline{\hspace{0.5in}}
& Is $g \circ f$ injective? \underline{\hspace{0.5in}}\\
\cline{2-5}
& Is $g \circ f$ surjective? \underline{\hspace{0.5in}}
& Is $g \circ f$ surjective? \underline{\hspace{0.5in}}
& Is $g \circ f$ surjective? \underline{\hspace{0.5in}}
& Is $g \circ f$ surjective? \underline{\hspace{0.5in}}\\
\hline
\multirow{2}{*}{$f$ not injective or surjective} 
& Is $g \circ f$ injective? \underline{\hspace{0.5in}}
& Is $g \circ f$ injective? \underline{\hspace{0.5in}}
& Is $g \circ f$ injective? \underline{\hspace{0.5in}}
& Is $g \circ f$ injective? \underline{\hspace{0.5in}}\\
\cline{2-5}
& Is $g \circ f$ surjective? \underline{\hspace{0.5in}}
& Is $g \circ f$ surjective? \underline{\hspace{0.5in}}
& Is $g \circ f$ surjective? \underline{\hspace{0.5in}}
& Is $g \circ f$ surjective? \underline{\hspace{0.5in}}\\
\hline
\end{tabular}
\end{center}





\end{document} 