\documentclass{2800hw}
\usepackage{amsmath,amssymb,latexsym}
\usepackage{utf8}
\topic{Functions}
\homework{5}
\begin{document}
\maketitle
\begin{exercises}
\item
Each of the following relations has domain $\{ x, y, z \}$ and codomain $\{ 1,
2, 3 \}$. For each, state whether it is a function or not. If it is a function,
state (i) its image, (ii) whether it is surjective or not, (iii) whether it is
injective or not. If it is not a function, state why not.
\begin{enumerate}
\item $\{ (x, 1), (y, 2), (x, 3), (z, 2) \}$
\item $\{ (x, 1), (y, 2) \}$
\item $\{ (x, 3), (y, 2), (z, 1) \}$
\item $\{ (x, 1), (y, 1), (z, 1) \}$
\end{enumerate}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item
Determine whether each of these functions from $\mathbb{Z}$ to $\mathbb{Z}$ is
injective (one-to-one) or not. If it is not injective, give a counterexample.
Note that $\mathbb{Z}$ is the set of all integers: negative, positive or zero.
\begin{enumerate}
\item $f(n) \ = \ n - 1$
\item $f(n) \ = \ n^2 + 1$
\item $f(n) \ = \ n^3$
\item $f(n) \ = \ \lceil n / 2 \rceil$ \hspace{0.25in} ($\lceil x \rceil$ denotes the smallest integer greater than or equal to $x$)
\end{enumerate}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item
Recall that $[X \rightarrow Y]$ denotes the set of all functions with domain $X$
and codomain $Y$.
\begin{enumerate}
\item Give a bijection from $[X → Y] \times [X → Z]$ to $[X → Y \times Z]$.
\item Give a bijection from $[X \rightarrow [Y \rightarrow Z]]$ to $[X \times Y \rightarrow Z]$.
\item Assuming there is a bijection between $X$ and $Y$, give a bijection from $[X \rightarrow Z]$ to $[Y \rightarrow Z]$.
\end{enumerate}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item
\begin{enumerate}
\item
A function $f : A \rightarrow A$ is called involutive if for all $x \in A$, $f(f(x)) = x$.
Prove or disprove: \begin{enumerate}
\item if $f$ is involutive, then it is injective.
\item if $f$ is involutive, then it is surjective.
\end{enumerate}
\item
A function $f : A \rightarrow A$ is called idempotent if for all $x \in A$, $f(f(x)) =
f(x)$. Prove or disprove:
\begin{enumerate}
\item if $f$ is idempotent, then it is injective.
\item if $f$ is idempotent, then it is surjective.
\end{enumerate}
\item
If $f : B \rightarrow C$ and $g : A \rightarrow B$ are functions, then $f \circ g$ is the function
from $A$ to $C$ defined by: $(f \circ g) : x ↦ f(g(x))$. Prove or disprove:
if $f$ and $f \circ g$ are one-to-one, then $g$ is one-to-one.
\end{enumerate}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item
In the first few homeworks, we asserted various facts about sets. We will now
prove two of them. Given two sets $A \subseteq S$ and $B \subseteq S$, show
that
\begin{enumerate}
\item $A \cup B = (A \setminus B) \cup (A \cap B) \cup (B \setminus A)$.
\item $(A \setminus B) \cap (A \cap B) = \emptyset$.
\end{enumerate}
Note that the formal definition of equality for sets is that $A = B$ if $A
\subseteq B$ and $B \subseteq A$, and the formal definition of subset is $A
\subseteq B$ if for all $x \in A$, $x \in B$. Definitions for $\cup$, $\cap$,
$\setminus$ and $\emptyset$ are on the lecture slides.
\end{exercises}
\end{document}