\input{config}

\title{Problem Set 10}
\author[Daniel Gonzalez Cedre]{Discrete Mathematics}
\publisher{University of Notre Dame}
\date{Due on the \red{22\textsuperscript{nd} of April, 2024}}

\begin{document}

\maketitle

\begin{enumerate}
  \item[(40 pts) \quad 1.]
    Construct---\emph{with proof}---the \emph{explicit} functions requested below.
    % \emph{No proof is required} to justify your answers to the following questions.
    \begin{enumerate}
      \item
        A bijection from $\set{x \in \reals \suchthat -1 < x < 1}$ to $\set{x \in \reals \suchthat -\pi < x < \pi}$.
      \item
        A surjection from $\naturals$ to $\set{p \suchthat p \text{ is prime}}$.
      \item
        An injection from $X$ to $\power{X}$ for \emph{every} set $X$.
      \item
        A surjection from $\power{X}$ to $X$ for \emph{every} set $X \neq \emptyset$.
        % \sidenote{Make sure your definition is \emph{explicit.}}
    \end{enumerate}

  % \item[(20 pts) \quad 2.]
    % Justify each answer below \emph{with proof.}
    % \begin{enumerate}
      % \item
        % How many infinite binary strings have digits whose sum is $2$?
      % \item
        % How many infinite decimal strings have \emph{finitely many} $7$s?
      % \item
        % How many infinite decimal strings have \emph{infinitely many} $7$s?
      % \item
        % Is there a set $x$ such that $\forall y \pn*{\cardinality*{x} \geq \cardinality*{y}}$?
    % \end{enumerate}

  \item[(30 pts) \quad 2.]
    Let $A$ be an arbitrary finite set of cardinality $\cardinality{A} = n$, where $n \in \naturals$.
    How many finite strings over $A$ are there?

  \item[(30 pts) \quad 3.]
    Imagine that, one day, you encounter a library.%
    \sidenote{This library is so massive and so complete a collection of literary works that it even contains books of \emph{infinite length.}}
    At the entrance of this library is an enormous tome $\mathscr{B}$ listing \emph{all} of the \emph{possible} sentences in the English language, indexed by natural numbers.

    Walking past the entrance, you see that the library has rows of bookshelves numbered $0, 1, 2, \dots$, so that there is exactly one row of books for each $n \in \naturals$.
    A great owl---perched on the pedestal that supports $\mathscr{B}$---informs you that, for each $n \in \naturals$, the $n^{th}$ row of bookshelves contains \emph{all} of the books that could possibly ever be that begin with the $n^{th}$ sentence in $\mathscr{B}$.
    With the sound of granite scraping against marble, the doors to the library close behind you.
    The owl makes you the following proposal: you will be free to go \emph{if and only if} you can read every book in the library \emph{in a countable amount of time.}

    Will you be set free?
    The owl demands a proof to justify your answer.
\end{enumerate}

\end{document}
