\input{config}
% \input{preambles/preamble}
% \input{preambles/definitions}
% \input{preambles/environments}

\title{Problem Set 7}
\author[Daniel Gonzalez Cedre]{Discrete Mathematics}
\publisher{University of Notre Dame}
\date{Due on the \red{27\textsuperscript{th} of March, 2024}}

\begin{document}

\maketitle

\begin{enumerate}
  \item[(10 pts) \quad 1.]
    Let $X$ be a set.
    Show that $\left(\forall Y \in \power{X}\right)\left(\card*{Y} \leq \card*{X}\right)$.

  \item[(15 pts) \quad 2.]
    Show that $\forall X \forall Y \left(\card*{X} \leq  \card*{Y} \implies \exists Z \left(Z \subseteq Y \land \card*{X} = \card*{Z}\right)\right)$.

  \item[(15 pts) \quad 3.]
    Let $X, Y, Z$ be sets and consider
    $f: X \to Y$ and $g: Y \to Z$.%
    \marginnote{Since the codomain of $f$ and the domain of $g$ are the same, they are \emph{compatible}, and their composition is sensibly defined.}
    We define the \ered{composition} of $f$ with $g$ to be the function
    $g \comp f: X \to Z$ given by
    $(g \comp f)(x) \defeq g(f(x))$
    for all $x \in X$.
    \begin{enumerate}
      \item
        Show that, if $f$ and $g$ are both injections, then $g \comp f$ is injective.%
        \marginnote{These are called \defn{monomorphisms}\emph{.}}
      \item
        Show that, if $f$ and $g$ are both surjections, then $g \comp f$ is surjective.%
        \marginnote{These are called \defn{epimorphisms}\emph{.}}
      \item
        Show that, if $f$ and $g$ are both bijections, then $g \comp f$ is bijective.
        \marginnote{These are called \defn{isomorphisms}\emph{.}}
    \end{enumerate}

  \item[(30 pts) \quad 4.]
    For this problem, let $X$ and $Y$ be nonempty sets and let $f: X \to Y$.
    \begin{enumerate}
      \item
        % Suppose $f: X \inject Y$ is injective.
        If $f$ is injective, show there exists $g: Y \to X$ where $g \comp f = \id_X$.
      \item
        If $f$ is surjective, show there exists $g: Y \to X$ where $f \comp g = \id_Y$.
      \item
        If $f$ is a bijection, then show that there exists a \sout{\emph{unique}} function $g: Y \to X$ such that $g \comp f = \id_X$ and $f \comp g = \id_Y$.
    \end{enumerate}

  \item[(30 pts) \quad 5.]
    \defn{Euler's totient function} is the function $\varphi_e: \naturals \to \naturals$ that counts how many positive integers are \emph{coprime} with each $n \in \naturals$, defined below.
    \begin{equation*}
      \varphi_e(n)
      \defeq \cardinality*{\set*{z \in \naturals \suchthat 1 \leq z \leq n \land \gcd(z, n) = 1}}
    \end{equation*}
    % $\varphi_e(n)$ counts how many positive integers are \emph{coprime} with $n \in \naturals$.
    \begin{enumerate}
      \item
        % If $p, k, m \in \naturals$ such that $p$ is prime and $m \leq p$, then prove that $\gcd(p^k, m) \in \set{p^\ell \suchthat (0 \leq \ell \leq k) \land \ell \in \naturals}$.
        % If $p, k, m \in \naturals_+$ are \emph{positive} naturals such that $p$ is prime and $m \leq p$, then prove $\gcd(p^k, m) \neq 1 \iff m \in \set{\ell p \suchthat (1 \leq \ell \leq p^{k - 1}) \land \ell \in \naturals}$.
        If $p, k, m \in \naturals_+$ are \emph{positive} naturals with $p$ prime and $m \leq p^k$, then prove that $\gcd(p^k, m) \neq 1 \iff p \divides m$.
      \item
        If $p$ is prime, then prove that $\varphi_e(p) = p - 1$.
      \item
        % Show that, if $p \in \naturals$ is prime and $k \in \naturals_+$, then $\varphi_e(p^k) = p^k - p^{k - 1}$.
        % If $p$ is prime and $k \in \naturals_+$, then prove that $\varphi_e(p^k) = p^{k - 1}(p - 1)$.
        If $p$ is prime and $k \in \naturals_+$, then prove that $\varphi_e(p^k) = p^k - p^{k - 1}$.%
        \marginnote{\emph{Hint: count the multiples of $p$.}}
      % \item
        % If $p \neq q$ are distinct primes, then prove that $\varphi_e(pq) = \varphi_e(p)\varphi_e(q)$.
    \end{enumerate}
\end{enumerate}

\end{document}
