<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\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}
</pre></body></html>