\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}