\documentclass[10pt,letterpaper,unboxed,cm]{hmcpset}
\usepackage[margin=1in]{geometry}
\usepackage{graphicx, hyperref,varwidth}
\pagestyle{empty}
\newcommand{\st}{~\mid~}
\newcommand{\powerset}{\ensuremath{\mathcal{P}}}
\newcommand{\bAlg}[1]{\begin{center}\begin{varwidth}{\textwidth}
#1
\begin{enumerate}\setlength{\itemsep}{-3pt}}
\newcommand{\eAlg}{\end{enumerate}\end{varwidth}\end{center}}
%\name{}
\assignment{CSE 20 Homework 7}
\duedate{Due: Sunday March 12, 2017 at noon}
\begin{document}
\begin{center}
\begin{minipage}[t]{6in}
\rule{\linewidth}{2pt}
{\sc Topics} Sets and Induction.
\newline
{\sc Reading} Rosen Sections 5.2, 5.3, 2.3, 2.5
\newline
{\sc Key Concepts} Recursive definitions, strong induction, structural
induction, basis step, induction hypothesis, induction step, strings,
functions, one-to-one, onto, bijection, invertible, size / cardinality,
finite sets, countably infinite sets, countable sets, uncountable sets.\newline
\rule{\linewidth}{2pt}
\end{minipage} \hfill
\end{center}
\problemlist{}
\begin{problem}[1.] ({\bf 10 points})
Consider the statement \[ \text{For every nonnegative integer}~n,~ 3 | n. \]
The next paragraph claims to prove this statement. Is this proof correct? Explain why or why not,
making specific reference to each step of the proof if it is correct or to specific errors if it is not.
If you find errors in the proof, explain how you would correct them or whether that would be impossible
(and why).
\begin{quote}
``Proof": We proceed by strong mathematical induction.
{\it Basis step:} Indeed, $3 | 0$ because there is an integer, namely $0$ such that $0 = 3\cdot 0$.
{\it Induction step:} Let $k$ be arbitrary. Assume, as the strong induction hypothesis,
that for all nonnegative integers $j$ with $0 \leq j \leq k$, that $3 | j$. Write $k+1 = m + n$, where
$m,n$ are integers less than $k+1$. By the induction hypothesis, $3 | m$ and $3 | n$. That is, there
are integers $a,b$ such that $m = 3a$ and $n=3b$. Therefore, $k+1 = (3a) + (3b) = 3 (a+b)$.
Since the set of integers is closed under multiplication, $a +b \in \mathbb{Z}$ and $3 | (k+1)$, as
required.
\end{quote}
\end{problem}
\begin{problem}[2.] ({\bf 10 points}) A set is defined to be {\bf countably infinite} if
it has the same cardinality as $\mathbb{Z}^+$.
\begin{itemize}
\item[(a)] Prove that if $A$ and $B$ are disjoint and countably infinite, then $A\cup B$ is countably infinite.
\item[(b)] Prove that, for every nonnegative integer $n \geq 2$, if $A_1, \ldots, A_n$ are
all countably infinite and each set is disjoint from all others,
then $\bigcup_{i=1}^n A_i$ is countably infinite.
{\it Hint: use mathematical induction and your work in part (a).}
\end{itemize}
{\it To develop some intuition, let's look at specific sets $A$ and $B$ to start:
suppose $A = \{ x \in\mathbb{Z}^+ ~|~ x~\text{is even} \}$ and
$B = \{ x \in \mathbb{Z}^+ ~|~|x~\text{is odd}\}$. These sets are both countably infinite:
to prove that $A$ is countably infinite, see that $f: \mathbb{Z}^+ \to A$ defined
as $f(x) = 2x$ is a bijection
between $\mathbb{Z}^+$ and $A$; to prove that $B$ is countably infinite, see that
$g: \mathbb{Z}^+ \to B$ defined
as $f(x) = 2x-1$ is a bijection between $\mathbb{Z}^+$ and $B$. Moreover,
$A \cap B = \emptyset$ because no integers is both even and odd. In other words, $A$
and $B$ are disjoint. By definition,
\[
A \cup B = \{ x ~|~ x \in A \vee x \in B \} = \{ x ~|~(\text{$x \in \mathbb{Z}^+$ and $x$ is even})
\vee (\text{$x \in \mathbb{Z}^+$ and $x$ is odd}) \} = \{ x ~|~ x \in \mathbb{Z}^+ \} =
\mathbb{Z}^+
\]
because every nonnegative integer is either even or odd. Since $\mathbb{Z}^+$
is the same cardinality as itself, we see that $A \cup B$ is
countably infinite.
}
\end{problem}
\vspace{10pt}
\noindent {\it Bonus problem - not for credit}: what would change if we remove the assumption
that $A$ and $B$ are disjoint?
\begin{problem}[3.] ({\bf 15 points})
To extend the notion of {\bf size} to infinite sets, we've established the following definitions:
for nonempty sets $X, Y$
\begin{description}
\item[$|X| \leq |Y|$] means there's a function $f: X \to Y$ which is one-to-one.
\item[$|X| \geq |Y|$] means there's a function $f: X \to Y$ which is onto.
\item[$|X| = |Y|$] means there's a function $f: X \to Y$ which is a bijection.
\end{description}
In Week 9's discussion section, you will prove that, for any (nonempty) sets $A, B, C$ and any functions
$f: A \to B$ and $g: B \to C$,
if $f$ and $g$ are one-to-one, then $g \circ f$ is also one-to-one. You
will then use this lemma to prove that if $|A| \leq |B|$ and $|B| \leq |C|$ then $|A| \leq |C|$.
\begin{itemize}
\item[(a)] Show that for any (nonempty) sets $A, B, C$ and any functions $f: A \to B$ and $g: B \to C$,
if $f$ and $g$ are onto, then $g \circ f$ is also onto.
\item[(b)] Use the lemma in part (a) to prove that, for any nonempty sets $A, B,C$, if $|A| \geq |B|$ and $|B| \geq |C|$ then $|A| \geq |C|$.
\item[(c)] Prove that, for any nonempty sets $A, B, C$, if $|A| = |B|$ and $|B| = |C|$ then $|A| = |C|$. {\it Hint: use what you already know from discussion and from
parts (a) and (b). The proof for part (c) should be very short.}
\end{itemize}
\end{problem}
\begin{problem}[4.] ({\bf 15 points}) Classify each of these sets
as (exactly one of) {\bf finite}, {\bf countably infinite}, or {\bf uncountable}.
Very briefly justify your answers.
\begin{itemize}
\item[(a)] The set of all bit strings that start with $1$, $\{ 1w ~|~ w\in \{0,1\}^* \}$
\item[(b)] The empty set, $\emptyset$
\item[(c)] The set of all functions whose domain is $\mathbb{N}$ and whose
codomain is $\{0,1\}$
\item[(d)] $\mathbb{Z} \times \mathbb{Z}$
\item[(e)] The set of of all bit strings whose length is an even prime,
$\{ u \in \{0,1\}^*~|~l(u)~\text{is an even prime} \}$
\item[(f)] The set of all logically inequivalent compound propositions with
propositional variables $p_1, \ldots, p_{17}$
\item[(g)] The set of prime numbers
\item[(h)] $\mathcal{P}(\{0,1\}^*)$
\item[(i)] $\mathcal{P}(\mathbb{R})$
\item[(j)] The set of all (one-file) Java programs
\end{itemize}
\end{problem}
\end{document}