\dbox{{\bf Deliverable:} Submit your responses as a single PDF file on the collab site before {\bf 6:29pm} on {\bf Friday, 23 September}. Follow the directions on \hyperlink{https://uvacs2102.github.io/pdfs/}{Generating PDFs} posted on the course site. }

Directions

Solve as many of the 9 problems as you can. For maximum credit, your answers should be correct, clear, well-written, and convincing. The problems marked with $(\star)$ are believed to be challenging enough that it is not necessary to solve them well to get a ``green-star level” grade on this assignment (although we certainly hope you will try and some will succeed!)

Sets

1. For each set $S$ defined below, indicate whether or not it is equivalent to $A$, where $A$ and $B$ are any sets. Support your answer with a brief explanation.

\begin{quote} \begin{enumerate}[a.] \item $S = A \cup \emptyset$. \item $S ::= { x | x \in A \wedge x \in \overline{B} }$ \item $S ::= { x | x \in A \wedge x \notin \overline{A} }$ \item $S ::= A \cap (B \cup A)$. \item $S ::= A - (B \cap \overline{B})$. \end{enumerate} \end{quote}

1. Use the definitions of the set operations to prove that for all sets $A$ and $B$, $$A = (A \cap B) \cup (A - B).$$

2. In Class 7, we defined set difference as: $$\forall x. x \in A - B \iff x \in A \wedge x \notin B.$$ Provide an alternate (but equivalent in meaning) definition of set difference using only the other defined set operations (you may use any of the union ($\cup$), intersection ($\cap$), and complement ($\overline{S}$) operations in your definition, but no other operations or qualifiers). A good answer will include a proof that shows your definition is equivalent to the original set difference definition.

Functions and Relations

1. For each function described below, identify a domain and codomain that make the function total. For example, for $f(x) ::= 1/x$ you could correctly answer that the domain is $\mathbb{R} - { 0 }$ and codomain is $\mathbb{R}$.

\begin{quote} \begin{enumerate}[a.] \item $f(x) ::= x + 1$

\item $f(x) ::= \frac{x}{(x - 1)}$

\item $f(S) ::= \textrm{ minimum}{<}(S \cap \mathbb{N})$ where $\textrm{ minimum}{<}$ is defined for all sets $A$ that are well-ordered by $<$ as: $$ \textrm{minimum}_{<}(A) = x \in A \textrm{ such that } \forall a \in A - { x } \ldotp x < a. $$ and $<$ is a binary relation on the real numbers. \end{enumerate} \end{quote}

1. Consider the relation, $<$, with the domain set, ${ 1, 2, 3 }$ and codomain set, ${ 0, 1, 2 }$.

   \begin{enumerate}[a.] \item Describe the graph of the relation. Your description can be a picture showing the graph, or some other clear way of defining that graph. \item Which of these properties does the relation have: {\em function}, {\em total}, {\em injective}, {\em surjective}, {\em bijective}. (You do not need to provide a detailed proof, but should support your answer with a very brief explanation.) \end{enumerate}

2. Consider the relation, $\le$, with the domain set, $\mathbb{N}$ and codomain set $\mathbb{N}$.

   \begin{enumerate}[a.] \item Describe the graph of the relation. (For this one, you won’t be able to draw a complete picture since the domain set is infinite. Instead, your description can be a picture illustrating the graph in a clear way, or some other clear way of defining that graph.) \item Which of these properties does the relation have: {\em function}, {\em total}, {\em injective}, {\em surjective}, {\em bijective}. (You do not need to provide a detailed proof, but should support your answer with a very brief explanation.) \end{enumerate}

3. Give an example of a relation $R: A \rightarrow \overline{A}$ that is bijective, for any set $A$. (You should specify carefully the domain of discourse, needed for $\overline{A}$ to be meaningfully defined.)

1. (Extracted from MCS Problem 4.23) Five basic properties of binary relations $R : A \rightarrow B$ are: \begin{quote} \begin{enumerate}[(1)] \item $R$ is a surjection [$\ge 1$ in] \item $R$ is an injection [$\le 1$ in] \item $R$ is a function [$\le 1$ out] \item $R$ is total [$\ge 1$ out] \item $R$ is empty [$= 0$ out] \end{enumerate} \end{quote} Below are some assertions about a relation $R$. For each assertion, write the numbers (1, 2, 3, 4, 5 from above) of all properties above that the relation $R$ must have (that is, the properties that are implied by the stated assertion); write ``none” if $R$ might not have any of these properties.

   Variables $a, a_1, a_2, \cdots$ are elements of $A$, and $b, b_1, b_2, \cdots$ are elements of $B$.

   The first answer is provided as an example. \begin{quote} \begin{enumerate}[a.] \item $\forall a \ldotp \forall b \ldotp a R b.$ \qquad\qquad Answer: (1), (4) \item $\neg(\forall a \ldotp \forall b \ldotp a R b).$ \item $\forall a \ldotp \exists b \ldotp a R b.$ \item $\forall b \ldotp \exists a \ldotp a R b.$ \item $R$ is a bijection. \item $\forall a_1, a_2, b \ldotp (a_1 R b \wedge a_2 R b) \implies a_1 = a_2.$ \item $\forall a_1, a_2, b_1, b_2 \ldotp (a_1 R b_1 \wedge a_2 R b_2 \wedge b_1 \neq b_2) \implies a_1 \neq a_2.$ \end{enumerate} \end{quote}

2. ($\star$) Consider the sets $A$ and $B$ where $|A| = n$ and $|B| = m$.

\begin{quote} \begin{enumerate}[a.]

\item Assuming $n = m$ (just for this sub-part), how many {\em bijective} relations are there $R: A \rightarrow B$.

\item How many {\em total} functions are there $f: A \rightarrow B$.

\item How many {\em partial} functions are there $f: A \rightarrow B$. (Note that the set of {\em partial} functions includes all {\em total} functions; partial means there {\em may} be domain elements with no associated codomain element.)

\item How many {\em injective} relations are there $R: A \rightarrow B$. \end{enumerate} \end{quote}