\documentclass[11pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}

\usepackage[margin=1in]{geometry}
\usepackage{microtype}
\usepackage[parfill]{parskip}

\usepackage{graphicx,grffile}
\graphicspath{ {./img/} }
\usepackage{xcolor}
\usepackage{pgf,tikz,pgfplots}
\pgfplotsset{compat=1.15}
\usetikzlibrary{cd}
\usepackage{caption}

\usepackage{hyperref}

\usepackage{amsmath,amssymb,amsthm,mathtools,mathrsfs,esdiff,stmaryrd,mathabx,dsfont}

\usepackage[inline]{enumitem}
\setlist[enumerate]{label=(\alph*),ref=(\alph*)}

\usepackage{cleveref}

% \usepackage{suffix}
\usepackage{ragged2e}
\usepackage{framed}

\makeatletter

\newcommand*{\CC}{\mathbb{C}}
\newcommand*{\RR}{\mathbb{R}}
\newcommand*{\QQ}{\mathbb{Q}}
\newcommand*{\ZZ}{\mathbb{Z}}
\newcommand*{\NN}{\mathbb{N}}
\newcommand*{\FF}{\mathbb{F}}
\renewcommand*{\AA}{\mathbb{A}} % Replace Ã…
\newcommand*{\PP}{\mathbb{P}}
\newcommand*{\GG}{\mathbb{G}}
\renewcommand*{\SS}{\mathbb{S}}
\newcommand*{\TT}{\mathbb{T}}
\newcommand*{\VV}{\mathbb{V}}

\newcommand*{\kA}{\mathfrak{A}}
\newcommand*{\km}{\mathfrak{m}}
\newcommand*{\kp}{\mathfrak{p}}
\newcommand*{\kq}{\mathfrak{q}}

\newcommand*{\sA}{\mathscr{A}}
\newcommand*{\sC}{\mathscr{C}}
\newcommand*{\sE}{\mathscr{E}}
\newcommand*{\sF}{\mathscr{F}}
\newcommand*{\sG}{\mathscr{G}}
\newcommand*{\sH}{\mathscr{H}}
\newcommand*{\sI}{\mathscr{I}}
\newcommand*{\sK}{\mathscr{K}}
\newcommand*{\sO}{\mathscr{O}}
\newcommand*{\sP}{\mathscr{P}}
\newcommand*{\sQ}{\mathscr{Q}}
\newcommand*{\sX}{\mathscr{X}}

\newcommand*{\cM}{\mathcal{M}}
\newcommand*{\cP}{\mathcal{P}}

\newcommand*{\nth}{^{\mathrm{th}}}

\DeclarePairedDelimiter{\ceil}{\lceil}{\rceil}
\DeclarePairedDelimiter{\floor}{\lfloor}{\rfloor}
\DeclarePairedDelimiterX\innerp[2]{\langle}{\rangle}{#1,#2}
\DeclarePairedDelimiter{\norm}{\lVert}{\rVert}
\DeclarePairedDelimiter{\abs}{\lvert}{\rvert}
\DeclarePairedDelimiter{\order}{\lvert}{\rvert}
\DeclarePairedDelimiter{\ps}{\llbracket}{\rrbracket}
\DeclarePairedDelimiter{\angles}{\langle}{\rangle}

\DeclareMathOperator{\coker}{coker}
\DeclareMathOperator{\Span}{Span}
\DeclareMathOperator{\rank}{rk}
\DeclareMathOperator{\nullity}{null}
\DeclareMathOperator{\diag}{diag}
\DeclareMathOperator{\sgn}{sgn}
\DeclareMathOperator{\tr}{tr}
% \DeclareMathOperator{\degree}{deg}
\DeclareMathOperator{\fchar}{char}
\DeclareMathOperator{\trdeg}{tr.deg}
\DeclareMathOperator{\codim}{codim}
\DeclareMathOperator{\height}{ht}
\DeclareMathOperator{\pd}{pd}

\DeclareMathOperator{\Pl}{Pl}
\DeclareMathOperator{\Sec}{Sec}
\DeclareMathOperator{\Div}{Div}
\let\div\undefined
\DeclareMathOperator{\div}{div}
\DeclareMathOperator{\Cl}{Cl}
\DeclareMathOperator{\Spec}{Spec}

% \newcommand{\divides}{\mid}
% \newcommand{\notdivides}{\nmid}

\newcommand*{\close}{\overline}
\newcommand*{\interior}[1]{#1^\circ}
\newcommand*{\bound}[1]{\partial #1}

\newcommand*{\xto}[1]{\xrightarrow{#1}}
\newcommand*{\xfrom}[1]{\xleftarrow{#1}}
\newcommand*{\To}{\Rightarrow}
\newcommand*{\into}{\hookrightarrow}
\newcommand*{\onto}{\twoheadrightarrow}
\newcommand*{\isoto}{\xto{\sim}}

\newcommand*{\dirlim}{\lim\limits_{longrightarrow}}
\newcommand*{\dirlimarg}[1]{\lim\limits_{\substack{\longrightarrow\\#1}}}
\newcommand*{\invlim}{\lim\limits_{\longleftarrow}}
\newcommand*{\invlimarg}[1]{\lim\limits_{\substack{\longleftarrow\\#1}}}

\newcommand*{\wh}[1]{\widehat{#1}}
\newcommand*{\wt}[1]{\widetilde{#1}}
\newcommand*{\ol}[1]{\overline {#1}}
\newcommand*{\ul}[1]{\underline {#1}}

\DeclareMathOperator{\Aut}{Aut}
\DeclareMathOperator{\Syl}{Syl}
\DeclareMathOperator{\Gal}{Gal}
\DeclareMathOperator{\Frac}{Frac}
\DeclareMathOperator{\Ann}{Ann}
\DeclareMathOperator{\Hom}{Hom}
\DeclareMathOperator{\Ext}{Ext}
\DeclareMathOperator{\Tor}{Tor}
\DeclareMathOperator{\End}{End}
\DeclareMathOperator{\GL}{GL}
\DeclareMathOperator{\PGL}{PGL}
\DeclareMathOperator{\Mat}{Mat}
\DeclareMathOperator{\Gr}{Gr}
\DeclareMathOperator{\im}{im}
\DeclareMathOperator{\lcm}{lcm}

\newcommand*{\sep}{\mathrm{sep}}

\newcommand{\present}[2]{\langle{{#1} \: |  \: {#2}}\rangle}
\newcommand{\cyclic}[1]{\langle{#1}\rangle}

\newcommand*{\residue}[1]{\mkern 1.5mu\overline{\mkern-1.5mu#1\mkern-1.5mu}\mkern 1.5mu}
\newcommand*{\zmod}[1]{ \Z / #1 \Z }

\newcommand*{\lni}{\lim_{n \to \infty}}
\newcommand*{\lNi}{\lim_{N \to \infty}}
\newcommand*{\sni}{\sum_{n=1}^\infty}

\newcommand\restr[2]{{% we make the whole thing an ordinary symbol
  \left.\kern-\nulldelimiterspace % automatically resize the bar with \right
  #1 % the function
  \vphantom{\big|} % pretend it's a little taller at normal size
  \right|_{#2} % this is the delimiter
}}
\newcommand*{\st}{\ \vert\ }

\newcommand{\conj}[1]{\overline{#1}}

\newcommand{\catname}[1]{{\mathsf{#1}}}
\newcommand{\Set}{\mathsf{Set}}
\newcommand{\Alg}[1]{#1\!-\!\mathsf{Alg}}
\newcommand{\Vect}[1]{#1\!-\!\mathsf{Vect}}
\newcommand{\Mod}[1]{#1\!-\!\mathsf{Mod}}
\renewcommand{\mod}[1]{#1\!-\!\mathsf{mod}}
\newcommand{\CommAlg}[1]{#1\!-\!\mathsf{CommAlg}}
\newcommand{\Ring}{\mathsf{Rings}}
\newcommand{\CommRing}{\mathsf{CommRings}}
\newcommand{\Grp}{\mathsf{Grp}}
\newcommand{\Ab}{\mathsf{Ab}}
\newcommand{\Fun}{\mathsf{Fun}}
\newcommand{\For}{\mathsf{For}}
\newcommand{\Fld}{\mathsf{Fld}}
\newcommand{\Open}{\mathsf{Open}}
\newcommand{\Aff}[1]{#1\!-\!\mathsf{Aff}}
\newcommand{\aA}{\mathsf{A}}
\newcommand{\aB}{\mathsf{B}}
\newcommand{\aC}{\mathsf{C}}
\newcommand{\aD}{\mathsf{D}}
\newcommand{\aG}{\mathsf{G}}
\newcommand{\aK}{\mathsf{K}}
\newcommand{\aP}{\mathsf{P}}

\newcommand{\op}{\textnormal{op}}
\newcommand{\fd}{\textnormal{fd}}
\DeclareMathOperator{\Ob}{Ob}
\newcommand{\id}{\mathrm{id}}

\newcommand*{\dir}[2]{(#1) \( \Rightarrow \) (#2)}

% -------------------
% Heading Commands
% -------------------
\newcommand{\class}{Math 294}
\newcommand{\term}{Fall 2024}
\newcommand{\instructor}{Theo Sandstrom}
\newcommand{\head}[2]{%
\thispagestyle{empty}
\vspace*{-0.5in}
\noindent\begin{tabular*}{\textwidth}{l @{\extracolsep{\fill}} r @{\extracolsep{6pt}} l}
	\textbf{#1} & \textbf{Name:} & \makebox[8cm]{\hrulefill} \\
	\textbf{#2} & & \\
	\textbf{\class:\; \term} & & \\
	\textbf{Instructor: \instructor}
\end{tabular*} \\
\rule[2ex]{\textwidth}{2pt} %
}


% -------------------
% Commands
% -------------------
\newcounter{problem}
\newenvironment{problem}
{
  \begin{leftbar}
  \begin{justify}
    \stepcounter{problem}%
    \textbf{Problem \theproblem. }
}
{
\end{justify}
\end{leftbar}
}
\newenvironment{problem*}[1]
{
  \begin{leftbar}
  \begin{justify}
    \stepcounter{problem}%
    \textbf{Problem \theproblem\ (#1). }
}
{
\end{justify}
\end{leftbar}
}


% -------------------
% Header & Footer
% -------------------
\usepackage{fancyhdr}

\fancypagestyle{pages}{
	%Headers
	\fancyhead[L]{}
	\fancyhead[C]{}
	\fancyhead[R]{}
\renewcommand{\headrulewidth}{0pt}
	%Footers
	\fancyfoot[L]{}
	\fancyfoot[C]{}
	\fancyfoot[R]{}
\renewcommand{\footrulewidth}{0.0pt}
}
\headheight=0pt
\footskip=14pt

\pagestyle{pages}

\makeatother

\begin{document}

\head{Worksheet 8}{Week 8: 2024-10-15}

Let's keep plugging along with functions! I've also thrown some induction problems in here too, another proof technique to add to your toolbox. \vspace{5mm}

\begin{framed}
  Eugenia Cheng (1976-) is a British mathematician and concert pianist who, beyond her notable research in category theory, has made a career as a popularizer of mathematics. After teaching at both the University of Cambridge and the University of Chicago, she took up a position as scientist-in-residence at the School of the Art Institute of Chicago.

  In her book \textit{How to Bake Pi}, she presents an approachable view of category theory, via analogies to baking. ``Math is about taking ingredients, putting them together, seeing what you can make out of them, and then deciding whether it’s tasty or not.'' Dr. Cheng insists that the public has it all wrong about math being difficult, something that only the gifted mathletes among us can do. To the contrary, she says, math exists to make life smoother, to solve those problems that can be solved by applying math’s most powerful tool: logic.

  \noindent\makebox[\textwidth][c]{
  \begin{minipage}[t]{0.5\linewidth}
    \vspace{-2ex}
    \centering
    \includegraphics[width=4cm]{cheng}
  \end{minipage}}
\end{framed}

\begin{problem}
    A function \( f : X \to Y \) is called \textit{injective} if, for any \( x, x' \in X \), if \( f(x) = f(x') \) then \( x = x' \) (Note: some people call these functions \textit{one-to-one}, for reasons I cannot fathom. I will not use this terminology, because it is confusing). For each of the following, identify (with justification) whether they are injective.
    \begin{enumerate}
        \item \( f : \RR \to \RR \) given by \( f(x) = 3 x + 2 \).
        \item \( g : \ZZ \to \RR \) given by \( g(n) = e^n \).
        \item \( h : \RR \to \RR \) given by \( h(x) = x^2 + 3 \).
        \item \( F : [0, \pi] \to \RR \) given by \( F(\theta) = \cos \theta \).
    \end{enumerate}
\end{problem}

\vspace{4cm}

\begin{problem}
    A function \( f : X \to Y \) is called \textit{surjective} if, for each \( y \in Y \), there exists some \( x \in X \) such that \( f(x) = y \) (Note: those same folks who call injective functions \textit{one-to-one} call surjective functions \textit{onto}). For each of the functions in the previous problem, identify (with justification) whether they are surjective.
\end{problem}

\vspace{3cm}

\begin{problem}
    Let \( f : X \to Y \) and \( g : Y \to Z \) be two functions. We denote by \( g \circ f \) the \textit{composition} \( X \to Z \) given by \( (g \circ f)(x) = g(f(x)) \).
    \begin{enumerate}
        \item If \( f \) and \( g \) are both injections, is it always true that \( g \circ f \) is an injection? If so, are both conditions necessary? I.e., can you give an example where \( f \) is not injective, but the composition \( g \circ f \) is? What about where \( g \) is not injective, but the composition is?
        \item If \( f \) and \( g \) are both surjections, is it always true that \( g \circ f \) is a surjection? As in the previous problem, are both conditions necessary?
    \end{enumerate}
\end{problem}

\vspace{4cm}

\begin{problem}
    A function which is both injective and surjective is called \textit{bijective}. Give examples of bijections between the following sets, or argue that no such bijection exists:
    \begin{enumerate}
        \item \( \{ 1, 2, 3 \} \to \{ 1, 2, 3 \} \). (A bijection from a set to itself is sometimes called a \textit{permutation}. Challenge: given a finite set \( A \) with \( n \) elements, how many distinct permutations of \( A \) exist?)
        \item \( \{ 1, 2, 3 \} \to \{ A, B, C, D \} \).
        \item \( \ZZ \to \QQ \).
        \item \( \ZZ \to \RR \).
    \end{enumerate}
\end{problem}

\vspace{4cm}

\begin{problem}
    For every set \( A \), we have an \textit{identity function} \( \id_A : A \to A \) defined by \( \id_A(a) = a \). Given a function \( f : X \to Y \), we say that \( g : Y \to X \) is a \textit{left-inverse} for \( f \) if \( g \circ f = \id_X \). Similarly, \( g \) is a \textit{right-inverse} for \( f \) if \( f \circ g = \id_Y \), and \( g \) is a plain old \textit{inverse} for \( f \) if it is both a left- and a right-inverse.
    \begin{enumerate}
        \item Prove that \( f \) is injective if and only if it admits a left-inverse.
        \item Prove that \( f \) is surjective if and only if it admits a right-inverse.
        \item Conclude that \( f \) is bijective if and only if it admits an inverse.
    \end{enumerate}
\end{problem}

\vspace{4cm}

\begin{problem}
    Given a finite set \( A \), the \textit{cardinality} of \( A \), which I denote by \( \# A \), is the number of elements of \( A \). Show that, given finite sets \( A \) and \( B \), there exists a bijection \( A \to B \) if and only if \( \# A = \# B \).
\end{problem}

\vspace{3cm}

\begin{problem*}{Challenge}
    Let \( f : X \to Y \) be a function, and suppose that \( g : Y \to X \) is a left-inverse and \( h : Y \to X \) is a right-inverse. Prove that \( g = h \). (Easier case: assume \( X \) and \( Y \) are finite.)
\end{problem*}

\vspace{3cm}

\begin{problem}
    Consider the function \( f : \ZZ_{>0} \to \ZZ \) defined by \( f(n) = \frac{n^3 - n}{3} \). Verify that \( f \) is a well-defined function (what must you check?) and show that it is injective.
\end{problem}

\vspace{3cm}

\begin{problem}
    Below is a proof that every student in MATH 294 has the same name. Obviously this is false. Find the error.

    \textit{Proceed by induction on the number of students. If there is only one student, then it is certainly true that every student has the same name (there is only one name). Now assume that the claim is true for every number of students less than \( n \), and suppose that there are \( n + 1 \) students in the class. Line the students up in a random order. If you look at the first \( n \) of them, then they all must have the same name by the inductive hypothesis. Similarly, the last \( n \) of them must have the same name. But then all of the students have the same name.}
\end{problem}

\vspace{3cm}

\begin{problem}
    In calculus, you have learned the \textit{product rule} or \textit{Leibniz rule}, which states that given differentiable functions \( f, g : \RR \to \RR \),
    \[ \frac{d(f g)}{dx} = f(x) \frac{dg}{dx} + \frac{df}{dx} g(x). \]
    Using this formula, prove the \textit{power rule}; that is
    \[ \frac{d(x^n)}{dx} = n x^{n-1}. \]
\end{problem}

\end{document}