% This is a TeX file
% It is essentially a programming language for mathematics documents
% You can ignore this first portion of the file, as it is essentially a bunch of "include" statements.
\documentclass[10pt]{article}

\usepackage{pictex, latexsym, graphicx,amsmath,amssymb,amsbsy,amsfonts,amsthm,verbatim}
\usepackage{graphics}
\usepackage{fullpage}
\usepackage{fancyhdr}
\usepackage{hyperref}

\usepackage{algorithm,algorithmic}
\usepackage{multirow}

\setlength{\voffset}{-0.25in}
\setlength{\headsep}{0.25in}
\setlength{\parskip}{1em}
\setlength{\parindent}{0em}

% The following denotes a counter for the problems.
\newcounter{problem}
\newcommand{\problem}{\textbf{\refstepcounter{problem}Problem \theproblem.} }

% These are macro shortcuts! Helpful!
\def\vu{\mathbf{u}}
\def\vx{\mathbf{x}}
\def\vb{\mathbf{b}}
\def\vv{\mathbf{v}}
\def\vw{\mathbf{w}}

\renewcommand{\implies}{\rightarrow}
%\newcommand{\lnot}{\neg}
\renewcommand{\lor}{\vee}
\renewcommand{\land}{\wedge}
\newcommand{\xor}{\oplus}
\newcommand{\symmdiff}{\triangle}
\renewcommand{\iff}{\leftrightarrow}
\newcommand{\TRUE}{\mathbf{T}}
\newcommand{\FALSE}{\mathbf{F}}
\newcommand{\universe}{\mathcal{U}}


\def\N{\mathbb{N}}
\def\Q{\mathbb{Q}}
\def\C{\mathbb{C}}
\def\Z{\mathbb{Z}}
\def\R{\mathbb{R}}
\def\cP{\mathcal{P}}


\begin{document}
\pagestyle{fancyplain}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% NOW you can start typing your text that will appear in the PDF!!!

% Note that anything after a '%' is a comment!

% Anything immediately after a '\' is a command. 
% Some denote formatting, some are for special characters.
% The '$' symbol starts and ends "math mode". Use this only for mathematical statements
% In math mode, any sequence of letters is meant to be a list of variables, so use "\sin x" for the sine of x, which will look much different from "sin x"
\chead{COM S 330 --- Homework 05 --- Solutions}

\textit{Type your answers to the following questions and submit a PDF file to Blackboard. 
One page per problem.}


% Problems about Sets!
\problem [5pts] Consider our definitions of $\Z$, $\Q$, $\R$, and $\C$. Recall that $A \subseteq B$ means ``$A$ is a subset of $B$'' and $A \not \subseteq B$ means ``$A$ is not a subset of $B$.''

Prove that 

(a) $\Z \subseteq \Q$, 

\begin{proof}
Let $i \in \Z$ be an arbitrary integer. Then $\frac{i}{1}$ is a rational number in $\Q$, and $i = \frac{i}{1}$.
\end{proof}

(b) $\Q \not \subseteq \Z$, 

\begin{proof}
$\frac{1}{2}$ is a rational number in $\Q$, but it is not an integer, so $\frac{1}{2} \notin \Z$.
\end{proof}

(c) $\R \not \subseteq \Q$, 

\begin{proof}
$\sqrt{2}$ is a real number, but as we know from class it is irrational.
\end{proof}

(d) $\R \subseteq \C$, 

\begin{proof}
Let $x$ be a real number. Then $x + 0i$ is a complex number in $\C$, and $x = x + 0i$.
\end{proof}

and (e) $\C \not \subseteq \R$.

\begin{proof}
$i$ is a complex number in $\C$, but $i = \sqrt{-1}$ and for every real number $x \in \R$, $x^2 \geq 0$, so since $i^2 < 0$, $i$ is not a real number.
\end{proof}

(We would also accept that we know $i$ is imaginary and not a real number, but giving a reason is always nice.)

% Be sure to use this \clearpage to make sure your problems are on separate pages!
\clearpage
\problem [5pts] Prove that if $A \subseteq B$, then $\cP(A) \subseteq \cP(B)$.

\begin{proof}
Let $S \in \cP(A)$ be an arbitrary element of $\cP(A)$.
By the definition of $\cP(A)$, $S$ is a subset of $A$.
Therefore, for every element $x \in S$, the element $x$ is also in $A$.
Since $A \subset B$, the element $x \in A$ is also an element $x \in B$.
Therefore, $S$ is also a subset of $B$.
Hence, $S$ is an element of $\cP(B)$ and $\cP(A) \subseteq \cP(B)$.
\end{proof}



% Be sure to use this \clearpage to make sure your problems are on separate pages!
\clearpage
\problem [5pts] Let $A$ and $B$ be sets. Prove that $|A\cup B|= |A| + |B| - |A \cap B|$, using the following steps:
\begin{enumerate}
\item Prove that if $E$ and $F$ are disjoint sets (i.e. $E \cap F = \varnothing$) then $|E \cup F| = |E| + |F|$.

\begin{proof}
Since $E \cap F= \varnothing$, each element of $E \cup F$ is in exactly one of $E$ or $F$ (not both).
There are $|E|$ such elements that are in $E$ and $|F|$ such elements that are in $F$.
Thus, there are $|E| + |F|$ elements total in $E \cup F$.
\end{proof}


\item Prove that $|A \cup B| = |A| + |B \setminus A|$.


\begin{proof}
Note that $A \cap (B \setminus A) = \varnothing$.
Therefore, by the previous part (with $E = A$ and $F = B \setminus A$), $|A \cup (B\setminus A)| = |A| + |B\setminus A|$.
It remains to show that $A \cup (B\setminus A) = A \cup B$, which holds since
\[
	A \cup (B \setminus A) = A \cup (B \cap \overline{A}) = (A\cup \overline{A}) \cap (A \cup B) = \universe \cap (A \cup B) = A \cup B.
\]
\end{proof}



\item Prove that $|B \setminus A| = |B| - |A \cap B|$.

\begin{proof}
Note that $|B \setminus A| = |B| - |A \cap B|$ if and only if $|B| = |B \cap A| + |B \setminus A|$.
Since $(B \cap A) \cap (B \setminus A) = \varnothing$, we can apply the first part with $E = B \cap A$ and $F = B \setminus A$ to find that $|(B \cap A) \cup (B \setminus A)| = |B\cap A| + |B \setminus A|$.
It remains to show that $B = (B \cap A) \cup (B \setminus A)$, but this holds since any element $x \in B$ is either in $A$ or not in $A$, so it is in $B \cap A$ or $B \setminus A$. (You can also use Set Identities, if you want.)
\end{proof}



\item Conclude that $|A \cup B| = |A| + |B| - |A \cap B|$.

\begin{proof}
From previous parts, we see that
\[
|A \cup B| = |A| + |B \setminus A| = |A| + |B| - |A\cap B|.
\]
\end{proof}


\end{enumerate}



% Problems about Set Operations!
% Be sure to use this \clearpage to make sure your problems are on separate pages!
\clearpage
\problem [5pts]  Let $\universe = \{1,2,3,4,5,6,7\}$, $A = \{ 1, 3, 5, 7\}$, $B = \{4,5,6,7\}$. Determine the following sets:

\begin{itemize}
\item $\overline{A} = \{ 2,4,6\}$
\item $A \cap B = \{ 5,7\}$
\item $A \cup B = \{1,3,4,5,6,7\}$
\item $A \setminus B = \{1,3\}$
\item $A \symmdiff B  = \{1,3,6\}$
\end{itemize}



% Be sure to use this \clearpage to make sure your problems are on separate pages!
\clearpage
\problem [5pts] Let $A$ and $B$ be sets. Prove that $\cP(A) \cap \cP(B) = \cP(A \cap B)$.


\begin{proof}
We prove both $\cP(A) \cap \cP(B) \subseteq \cP(A \cap B)$ and $\cP(A \cap B) \subseteq \cP(A) \cap \cP(B)$ to show equality.

($\cP(A) \cap \cP(B) \subseteq \cP(A \cap B)$) 
Let $S \in \cP(A) \cap \cP(B)$.
Thus $S \in \cP(A)$ and $S \in \cP(B)$.
By definition of the power set, $S$ is a subset of $A$ and $S$ is a subset of $B$.
Therefore, every element of $S$ is an element of $A$ and an element of $B$.
Hence $S$ is a subset of $A \cap B$ and by definition of the power set, $S \in \cP(A\cap B)$.

($\cP(A \cap B) \subseteq \cP(A) \cap \cP(B)$)
Let $S \in \cP(A\cap B)$.
By definition of the power set, $S$ is a subset of $A \cap B$.
So every element of $S$ is in both $A$ and $B$.
Then $S$ is a subset of $A$ and a subset of $B$.
By definition of the power set, $S$ is in $\cP(A)$ and in $\cP(B)$.
Therefore, $S \in \cP(A) \cap \cP(B)$.
\end{proof}


% Be sure to use this \clearpage to make sure your problems are on separate pages!
\clearpage
\problem [10pts] Let $A$, $B$, and $C$ be subsets of a universe $\universe$. Use definitions of set operations and set identities to prove the following equality of sets:
\[
	((B \cap A) \cup (B \cap C))\setminus (A \cap B \cap C) = (B \cap (A \symmdiff C))
\]

\begin{center}
\begin{tabular}[h]{rll}
&$((B \cap A) \cup (B \cap C))\setminus (A \cap B \cap C)$  &\\
&$= (B \cap (A \cup C))\setminus (A \cap B \cap C)$ & Distributive law\\
 &$= (B \cap (A \cup C)) \cap \overline{(A \cap B \cap C)}$ & Definition of set difference\\
 &$= (B \cap (A \cup C)) \cap (\overline{A} \cup \overline{B} \cup \overline{C})$ & DeMorgan's law\\
 &$= B \cap ((A \cup C) \cap (\overline{A} \cup \overline{B} \cup \overline{C}))$ & Associative law\\
 &$= B \cap ((A \cap (\overline{A} \cup \overline{B} \cup \overline{C})) \cup (C \cap (\overline{A} \cup \overline{B} \cup \overline{C})))$ & Distributive law\\
 &$= B \cap ((A \cap \overline{A}) \cup (A \cap\overline{B}) \cup (A \cap\overline{C})) \cup (C \cap \overline{A}) \cup (C \cap \overline{B}) \cup (C \cap\overline{C}))$ & Distributive law\\
 &$= B \cap (\varnothing \cup (A \cap\overline{B}) \cup (A \cap\overline{C}) \cup (C \cap \overline{A}) \cup (C \cap \overline{B}) \cup \varnothing)$ & Complementation law\\
 &$= B \cap ((A \cap\overline{B}) \cup (A \cap\overline{C}) \cup (C \cap \overline{A}) \cup (C \cap \overline{B}))$ & Identity law\\
 &$= B \cap ((A \cap\overline{B}) \cup (A \setminus {C}) \cup (C \setminus {A}) \cup (C \cap \overline{B}))$ & Definition of set difference\\
 &$= B \cap ((A \symmdiff C) \cup (A \cap\overline{B}) \cup (C \cap \overline{B}))$ & Definition of symm. diff. and comm. law\\
 &$= (B \cap (A \symmdiff C)) \cup (B \cap(A \cap\overline{B})) \cup ((B \cap(C \cap \overline{B})))$ & Distributive law\\
 &$= (B \cap (A \symmdiff C)) \cup (B \cap \overline{B} \cap A) \cup (B \cap \overline{B} \cap A)$ & Commutative and Associative laws\\
 &$= (B \cap (A \symmdiff C)) \cup (\varnothing \cap A) \cup (\varnothing \cap A)$ & Complementation laws\\
 &$= (B \cap (A \symmdiff C)) \cup \varnothing  \cup \varnothing$ & Domination law\\
 &$= B \cap (A \symmdiff C)$ & Identity law\\
\end{tabular}
\end{center}


% Problems about Functions!

% Be sure to use this \clearpage to make sure your problems are on separate pages!
\clearpage
\problem [5pts]  Let $A = \{a,b,c\}$, $B = \{1,2,3,4\}$, and $C = \{\pi, \phi, i\}$. Define functions $f : A \to B$ and $g : B \to C$ as
\[
	f(x) = \begin{cases} 2 & x = a\\3 & x = b\\ 4 & x = c\end{cases} \quad
	g(x) = \begin{cases} \pi & x = 1\\ \phi & x = 2 \\ i & x = 3 \\ \pi & x = 4 \end{cases}
\]
Consider each of the functions $f$, $g$, $g \circ f$ and determine if they are injective, surjective, or both.

\begin{itemize}
\item $f$ : injective, not surjective.

Since $f(a) = 2$, $f(b) = 3$, and $f(c) = 4$, every element of the domain is mapped to a distinct element of the codomain, so $f$ is injective.

Since no element is mapped to $1 \in B$, $f$ is not surjective.

\item $g$ : surjective, not injective.

Since $g(1) = g(4) = \pi$, $g$ is not injective.

Since $g(2) = \phi$, $g(3) = i$, and $g(4) = \pi$, $g$ is surjective.

\item $g \circ f$ : injective and surjective.

Since $(g\circ f)(a) = g(2) = \phi$, $(g\circ f)(b) = g(3) = i$, and $(g\circ f)(c) = g(4) = \pi$,  every element of the domain is mapped to a distinct element of the codomain, and  every element of the codomain is the image of an element of the domain, $g \circ f$ is both injective and surjective.
\end{itemize}


% Be sure to use this \clearpage to make sure your problems are on separate pages!
\clearpage
\problem [10pts]  Consider the following function $f : \N \to \Z$:
\[
	f(n) = (-1)^n\left(\frac{n}{2}+\frac{1}{4}\right)  - \frac{1}{4}.
\]
\begin{enumerate}
\item\ [1pt] Write out the elements $f(0)$, $f(1)$, $f(2)$, $f(3)$, $f(4)$, $f(5)$.

\[ f(0) = 0, \quad f(1) = -1, \quad f(2) = 1, \quad f(3) = -2, \quad f(4) = 2, \quad f(5) = -3, \dots\]

\emph{From this part, you should notice that the output differs depending on if the input is even or odd.}

\item\ [4pts]  Prove that $f$ is injective. 

\begin{proof}
First, I claim that $f(n) < 0$ when $n$ is odd and $f(n) \geq 0$ when $n$ is even.
If $n = 2k$ for some integer $k \geq 0$, then $f(2k) = (-1)^{2k}(2k/2 + 1/4) - 1/4 = (k+1/4)-1/4 = k \geq 0$.
If $n = 2k+1$ for some integer $k \geq 0$, then $f(2k+1) = (-1)^{2k+1}((2k+1)/2+1/4)-1/4 = -k - 1/2 - 1/4 - 1/4 = -(k+1) < 0$.

Now, assume $n$ and $m$ are natural numbers such that $f(n) = f(m)$.

If $f(n) \geq 0$, then both $n$ and $m$ are even.
Then $n = 2k$ and $m = 2\ell$ for nonnegative integers $k$ and $\ell$.
Thus,
\[
	(2k/2 + 1/4)-1/4 = f(2k) = f(n) = f(m) = f(2\ell) = (2\ell/2 + 1/4) - 1/4.
\]
However, this implies that $k = \ell$ by simple algebra ($1/4$'s cancel, $2/2 = 1$). So $n = m$.


If $f(n) < 0$, then both $n$ and $m$ are odd.
Then $n = 2k+1$ and $m = 2\ell+1$ for nonnegative integers $k$ and $\ell$.
Thus,
\[
	-(k+1) = -((2k+1)/2 + 1/4)-1/4 = f(2k) = f(n) = f(m) = f(2\ell+1) = -((2\ell+1)/2 + 1/4) - 1/4 = -(\ell+1).
\]
However, this implies that $k = \ell$, so $n = m$.
Therefore $f$ is injective.
\end{proof}

\item\ [5pts]  Prove that $f$ is surjective.

\begin{proof}
Let $y$ be an arbitrary integer.

If $y \geq 0$, then let $x = 2y$. Note that $f(2y) = (-1)^{2y}(2y/2+1/4)-1/4 = y$.

If $y < 0$, then let $x = 2|y|-1$. Note that $f(2|y|-1) = (-1)^{2|y|-1}((2|y|-1)/2+1/4)-1/4 = -|y| = y$.
\end{proof}

\clearpage
\item\ [+5pts] Describe a function $g : \Z \to \Q$ that is surjective (and prove it is surjective).

\emph{There are many ways to do this, and almost all of them are gross. This is the cleanest version I can think of.}

We will describe an algorithm that will take as input an integer $i$ and will output a rational number, and the output of this algorithm defines $g(i)$.

\vspace{1em}
\hrule

\textbf{Algorithm:} Input an integer $i$.

If $i = 0$, then output $0/1$.

If $i < 0$, then output $-g(-i)$, so we must only consider positive integers.

If $i > 0$, then consider the (unsigned) binary representation of $i$ as $i = \sum_{j=0}^k a_j2^j$ for some $(k+1)$-tuple $(a_k,a_{k-1},\dots,a_1,a_0)$.
Since $i > 0$, we can assume that $a_k = 1$ (by making $k = \lceil \log_2 i\rceil$).
Let $q$ be the minimum integer such that either $q > k$ or $a_{k-q} = 0$.
Thus, the binary representation of $i$ starts with $q$ 1-digits, then either stops, or has a 0-digit followed by $k-q-1$ more digits.
Let $p = \sum_{j=0}^{k-q} a_j2^j$.

Output $\frac{p}{q}$.

\hrule
\vspace{1em}

We claim that for every rational number $\frac{p}{q} \in \Q$, there exists an integer $i$ where the algorithm outputs a rational number equal to $\frac{p}{q}$ when given $i$.
We will assume that $q > 0$, since $q \neq 0$ and if $q < 0$ we can use the rational number $\frac{-p}{-q} = \frac{p}{q}$.

If $p = 0$, then the algorithm outputs $\frac{0}{1} = \frac{p}{q}$ when given 0.

If $p > 0$, then let $\sum_{j=0}^t a_j2^j$ be a binary representation of the integer $p$, defining a $(t+1)$-tuple $(a_t,a_{t-1},\dots,a_1,a_0)$.
We can further assume that $t = \lceil \log_2 p\rceil +1$, so $a_t = 0$.
Then, for $j \in \{t+1,\dots,t+q\}$, define $a_j = 1$.
Then, let $i = \sum_{j=0}^{t+q} a_j2^j$ and notice that this binary representation of $i$ starts with $q$ 1-digits, a zero digit, then the binary representation of $p$.
Therefore, the algorithm will output $\frac{p}{q}$ when given the input $i$ (in fact, it will output the fraction in this form, with exactly this $p$ and $q$ pair.)

If $p <0$, then consider the $i$ that outputs $\frac{-p}{q}$ and the algorithm given input $-i$ will output $\frac{p}{q}$.
\end{enumerate}




\end{document} 