\documentclass[noanswers,addpoints,12pt]{exam}
\usepackage{graphicx}
\usepackage{datetime}
\usepackage{amssymb}
\usepackage{listings}
\usepackage{soul}
\usepackage{tikz}
\usetikzlibrary{arrows,automata,decorations.pathmorphing,backgrounds,positioning,fit}
\usepackage{enumerate}
\usepackage{multicol}
\usepackage{fontspec}
\defaultfontfeatures{Scale=MatchLowercase,Mapping=tex-text}
\setmainfont{Gentium Book Basic}
\setmonofont{DejaVu Sans Mono}
\newfontfamily\lstlistingfamily{DejaVu Sans Mono}
\setsansfont{Trebuchet MS}
\lstset{
  basicstyle=\lstlistingfamily,
}

% classname
\newcommand\examNumber{Old [Exam 1]}
\newcommand\semester{From Spring 2018}
\newcommand\className{Foundatinos of Computing}
\newcommand\classNumber{CIS~300}
\newcommand\classFullName{\classNumber~\className}
\renewcommand{\dateseparator}{-}
\yyyymmdddate

% /classname

\pagestyle{headandfoot}
\firstpageheader{\classFullName\\\semester}{\examNumber\\~}{\today\\~}
\runningheader{\examNumber}{}{\today}
\firstpagefooter{Page \thepage\ of \numpages}
              {}
              {Points earned: \makebox[.5in]{\hrulefill}\\
                 out of a possible \pointsonpage{\thepage} points}
\runningfooter{Page \thepage\ of \numpages}
              {}
              {Points earned: \makebox[.5in]{\hrulefill}\\
                 out of a possible \pointsonpage{\thepage} points}



\begin{document}
\pointsinrightmargin{}
\begin{center}
  \fbox{\fbox{\parbox{6in}{
        The following test is \emph{closed book}; you may neither
        give nor receive assistance during this exam. Do not discuss
        the content of this exam until it is turned back in class.

        Read each question \emph{carefully} and answer it in the space
        provided. If you require more room, continue on the back of
        the page after clearly labeling what question the answer goes
        with.
      }}}
\end{center}
\vspace{0.1in}
\makebox[\textwidth]{Name:\enspace\hrulefill}

\textbf{Set-builder notation}: The definition of \emph{union}, in
set-builder notation would be: $A \cup B = \{x | x \in A \lor x \in
B\}$; it rewrites set operations into logic statements.

\begin{questions}
\question[5] Describe, in simple English, what the set $\mathbb{Z}
  \times \mathbb{Z}$ is.
  \begin{solution}[0.10in]
  \end{solution}

\question[5] Is the set $\mathbb{Z}^{>7} \times \mathbb{Z}^{>7}$
  countable? Justify your answer.
  \begin{solution}[0.10in]
  \end{solution}

\question[5] Give the \emph{set-builder notation} defining
  $A \subset B$.
  \begin{solution}[0.10in]
  \end{solution}

\question[10] Using the \emph{set builder notation}, prove DeMorgan's
  Law for taking the compliment of the union of two sets.
  \begin{solution}[1.0in]
  \end{solution}

\question[5] Consider $3\mathbb{Z} = \{z | z$ is a multiple of
    $3.\}$. \emph{Prove} that $|3\mathbb{Z}| = |\mathbb{Z}|$.
  \begin{solution}[1.0in]
  \end{solution}

\question[5]{} Give an example of two sets, $A$ and $B$, such that
  $|A| = |B|$ and $A$ is a \emph{proper} subset of $B$.
  \begin{solution}[0.25in]
  \end{solution}

\question[5]{} Give an example of two sets, $A$ and $B$, such that
  $|A| < |B|$ and $A$ is a \emph{proper} subset of $B$.
  \begin{solution}[0.25in]
  \end{solution}

\question{} Give a function from $\mathbb{Z^+}$ to $odd(\mathbb{Z}^+)$
  that has \textbf{exactly} the given property \emph{or} explain why
  no such function is possible.
\begin{parts}
  \part[3] Only \emph{injective}
  \begin{solution}[0.10in]
  \end{solution}
  \part[3] Only \emph{surjective}
  \begin{solution}[0.10in]
  \end{solution}
  \part[4] \emph{bijective}
  \begin{solution}[0.10in]
  \end{solution}
\end{parts}

\question{} Consider the \emph{predicate} $prime$ for integers.
  \begin{parts}
  \begin{solution}[0.0in]
  \end{solution}
  \part[3] What is the \emph{domain} of the function?
  \begin{solution}[0.0in]
  \end{solution}
  \part[3] What is the \emph{codomain} of the function?
  \begin{solution}[0.0in]
  \end{solution}
  \part[3] What is the \emph{signature} of $prime$?
  \begin{solution}[0.0in]
  \end{solution}
  \part[3] What is the \emph{range} of the function? Justify your answer.
  \begin{solution}[0.0in]
  \end{solution}
  \part[3] Is this function \emph{injective}, \emph{surjective},
    \emph{bijective}, or none of these? Justify your answer.
  \begin{solution}[0.0in]
  \end{solution}
  \end{parts}
\question[10]{} Define an \emph{algorithm} that returns \lstinline|true| if the
function, \lstinline{f}, is \emph{onto} from finite set \lstinline{A}
to finite set \lstinline{B} and \lstinline|false| otherwise. This is
an \emph{algorithm} so you can define your own notation for things
like the cardinality of a set if you need to; make sure your
notation's meaning is clear.

\begin{lstlisting}[mathescape=true,emph={boolean,set,A,B},emphstyle={\textbf}]
  boolean isOnto(set A = $a_1$, $a_2$, ..., $a_m$,
                 set B = $b_1$, $b_2$, ..., $b_n$,
                 B f(A a)) {
\end{lstlisting}
\begin{solution}[1.25in]
\end{solution}
\begin{lstlisting}
  }
\end{lstlisting}
\question[12] Prove that the union of any two \emph{countable} sets is
  \emph{countable}.
  \begin{solution}[1.25in]
    Prove that for sets $A$ and $B$,
    $countable(A) \land countable(B) \rightarrow countable(A \cup B)$.
  \end{solution}

\question[13] Consider the set of ordered pairs of positive integers,
  $\mathbb{Z}^+ \times \mathbb{Z}^+$. Prove that $\mathbb{Z}^+ \times
  \mathbb{Z}^+$ is \emph{countable}.

  \begin{solution}[1.25in]
    Prove: $\mathbb{Z}^+ \times \mathbb{Z}^+$ is \emph{countable}.

    Prove: $|\mathbb{Z}^+ \times \mathbb{Z}^+| = |\mathbb{Z}^+|$.

    Any sets, $A$, $B$, $|A| = |B|$ if and only if $\exists
    f:A \rightarrow B$ such that $f$ is a bijection.

    Find bijection $f: \mathbb{Z}^+ \rightarrow \mathbb{Z}^+ \times
    \mathbb{Z}^+$

    \[
      \begin{array}{rrrrr}
        (1,1)&(1,2)&(1,3)&(1,4)&\ldots\\
        (2,1)&(2,2)&(2,3)&(2,4)&\ldots\\
        (3,1)&(3,2)&(3,3)&(3,4)&\ldots\\
        (4,1)&(4,2)&(4,3)&(4,4)&\ldots\\
        \vdots&\vdots&\vdots&\vdots&\\
      \end{array}
    \]

    Take the pairs in order by the sum of the elements (starting with
    2 in the upper-left corner of the table) and, within any value, in
    order by the first element. This would order the pairs as (1, 1),
    (1, 2), (2, 1), (1, 3), (2, 2), \ldots. This represents following
    the diagonals down and to the left, starting again in the first
    row as the diagonal moves off the left column.

    This sequence represents a mapping from positive integers to the
    ordered pairs.

    Any given pair appears in the sequence exactly once so the mapping
    is one-to-one (any pair has at most one integer mapping to it)
    \emph{and} every pair appears in the sequence because a pair's
    values have a sum and then an order by first element within that
    sum, so every pair will be mapped onto eventually (every pair has
    at least one integer mapping to it). The mapping represented by
    the sequence is a bijection.
  \end{solution}

\end{questions}
\end{document}

%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End:
