Problem Set 9

\dbox{{\bf Deliverable:} Submit your responses as a single, readable PDF file on the collab site before {\bf 6:29pm} on {\bf Wednesday, 23 November}.}

Deliverable: Submit your responses as a single, readable PDF file on the collab site before 6:29pm on Wednesday, 23 November.

Collaboration Policy - Read Carefully

The collaboration policy is identical to that for PS7: you should work in groups of one to four students of your choice with no restrictions, and follow the rest of the collaboration policy from PS3.

Preparation

This problem set focuses on infinite sets — Chapter 8 of the MCS book, and Class 18, Class 19, Class 21 and Class 22.

Download PDF for Problems.

Your response should be submitted as a single PDF file using collab. Please read and follow the Generating PDFs advice on the course site.

Directions

Solve all 8 problems. Your answers should be clear, consise, and convincing.

Countable Sets

For each set defined below, prove that the set described is countable.

$\text{\em Evens} = { 2n \, | \, n \in \mathbb{N} }$
$\mathbb{N} \cup { \pi, \tau }$ (where $\pi$ is the ratio of a circle’s circumference to its diameter and $\tau$ is the ratio of a circle’s circumference to its radius)
The set of all finite state machines, $M = (S, G, q_0)$ where $S$ is a finite set, and $G \subseteq S \times S$ and $q_0 \in S$ are otherwise unrestricted.

Possibly Countable Sets

For each set defined below, determine if the set is countable or uncountable and support your answer with a convincing proof.

The set of all stree objects, defined by: \begin{itemize} \item Base object: $\text{\bf null}$ is an {\em stree}.
\item Constructor: for any {\em stree} objects $q_1, q_2$, $\text{combine}(q_1, q_2)$ is an {\em stree}. \end{itemize}
$\mathbb{R} - \mathbb{Q}$.
($\star$) The set of all infinite state machines, $M = (S, G, q_0)$ where $S = \mathbb{N}$, and $G \subseteq S \times S$ and $q_0 \in S$ are otherwise unrestricted.

Properties of Infinite Sets

(MCS Problem 8.11, with typesetting problem fixed) (a) Prove that if a nonempty set, $C$, is countable, then there is a total surjective function, $$f: \mathbb{N} \rightarrow C.$$ (b) Conversely, suppose that $\mathbb{N}\ \text{surj}\ D$, that is, there is a surjective function that is not necessarily total, $f: \mathbb{N} \rightarrow D$. Prove that $D$ is countable.
MCS Problem 8.17.