\bigskip
\textit{\textbf{Note:} This homework consists of two parts. The first part (questions 1-3) will be graded and will determine your score for this homework. The second part (questions 4-5) will be graded if you submit them, but will not affect your homework score in any way. You are strongly advised to attempt all the questions in the first part. You should attempt the problems in the second part only if you are interested and have time to spare.}
\rule{6in}{2px}
\section*{Part 1: Required Problems}
\bigskip
\Question{Unions and Intersections}
Given:
\begin{itemize}
\item $A$ is a countable, non-empty set. For all $i \in A$, $S_i$ is an uncountable set.
\item $B$ is an uncountable set. For all $i \in B$, $Q_i$ is a countable set.
\end{itemize}
For each of the following, decide if the expression is
"Always Countable", "Always Uncountable", "Sometimes Countable,
Sometimes Uncountable".
For the "Always" cases, prove your claim. For the "Sometimes" case, provide
two examples -- one where the expression is countable, and one where
the expression is uncountable.
\begin{Parts}
\Part $A \cap B$
\nosolspace{.5cm}
\Part $A \cup B$
\nosolspace{.5cm}
\Part $\bigcup_{i \in A} S_i$
\nosolspace{.5cm}
\Part $\bigcap_{i \in A} S_i$
\nosolspace{2cm}
\Part $\bigcup_{i \in B} Q_i$
\nosolspace{2cm}
\Part $\bigcap_{i \in B} Q_i$
\nosolspace{1cm}
\end{Parts}
\Question{Countability Practice}
\begin{Parts}
\Part Do $(0, 1)$ and $\R_+ = (0, \infty)$ have the same cardinality? If so, either give an explicit bijection (and prove that it is a bijection) or provide an injection from $(0,1)$ to $(0, \infty)$ and an injection from $(0, \infty)$ to $(0,1)$ (so that by Cantor-Bernstein theorem the two sets will have the same cardinality). If not, then prove that they have different cardinalities.
\Part Is the set of strings over the English alphabet countable?
(Note that the strings may be arbitrarily long, but each string has finite length. Also the strings need not be real English words.)
If so, then provide a method for enumerating the strings.
If not, then use a diagonalization argument to show that the set is uncountable.
\Part Consider the previous part, except now the strings are drawn from a countably infinite alphabet $\mathcal{A}$. Does your answer from before change? Make sure to justify your answer.
\end{Parts}
\Question{Counting Functions}
Are the following sets countable or uncountable? Prove your claims.
\begin{Parts}
%\Part $A \times B$, where $A$ and $B$ are both countable.
%\Part $\bigcup_{i\in A} B_i$, where $A, B_i$ are all countable.
\Part The set of all functions $f$ from $\N$ to $\N$ such that $f$ is
non-decreasing. That is, $f(x) \leq f(y)$ whenever $x \leq y$.
\Part The set of all functions $f$ from $\N$ to $\N$ such that $f$ is
non-increasing. That is, $f(x) \geq f(y)$ whenever $x \leq y$.
%\Part The set of all injective functions from $\N$ to $\N$.
%\Part The set of all surjective functions from $\N$ to $\N$.
\Part The set of all bijective functions from $\N$ to $\N$.
\end{Parts}
\bigskip
\textit{\textbf{Note:} This concludes the first part of the homework. The problems below are optional, will not affect your score, and should be attempted only if you have time to spare.}
\rule{6in}{2px}
\bigskip
\section*{Part 2: Optional Problems}
\bigskip
\Question{Counting Shapes}
Suppose scaled and shifted copies of a shape $S$ are embedded into the plane $\R^2$.
%Imagine that the $\R^2$ plane is embedded with scaled and shifted copies of a shape $S$.
%Assume somebody took a shape $S$ and placed scaled and shifted copies of it in
%the plane, such that no two copies intersect.
Let $\mathcal C$ denote the collection of all these copies.
Thus each element in $\mathcal C$ determines the scaling and the position of that copy.
Suppose further that the embedding is such that no two copies intersect.
For example in the case of filled squares, if there is any overlap between two squares, then they intersect.
In the case of the (non-filled) square, two copies intersect if and only if their boundaries intersect.
Similarly, in the case of the halved-square, if either the boundary or the middle line of one square intersects with either the boundary or the middle line of some other square, then these two squares intersect.
Can $\mathcal C$ be uncountable if $S$ is
\begin{Parts}
\Part the filled square: \tikz\draw[black, fill=black] (0,0) rectangle (.5,.5); ?
\Part the square: \tikz\draw[black] (0,0) rectangle (.5,.5); ?
\Part the halved square: \tikz\draw (0,.25) -- (0,.5) -- (.5,.5) -- (0.5,0) --
(0,0) -- (0,.25) -- (.5,.25); ?
\end{Parts}
If no uncountable $\mathcal C$ exists, prove that all $\mathcal C$ must be
countable.
\Question{Cantor Sums}
Show that every real number $x \in [0,1]$ can be written as the average of two numbers in the Cantor set.