cs2102
Discrete Mathematics

Problem Set 8

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

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

Collaboration Policy - Collaboration Policy (identical to PS5)

For this assignment, you may work in groups of one to three students to write-up a solution together. If you work with teammates, exactly one of you should submit one assignment that represents your collective best work with all of your names and UVA ids clearly marked on it on it. Everyone on a team should understand everything you turn in for the assignment well enough to be able to produce it completely on your own. All teammates must review the submissions before it is submitted to make sure you understand everything on it and that your name and UVA id are clearly marked on it.

Preparation

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

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.

  1. $\text{\em Evens} = { 2n \, | \, n \in \mathbb{N} }$

  2. $\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)

  3. The set $X$ of all finite state machines, $M = (S, G, q_0)$ where $S = \mathbb{N}_k$ for some natural number $k>0$, and $G \subseteq S \times S$ and $q_0 \in S$ are otherwise unrestricted. (Note that here we are not working with a fixed $k$, and for example machines with $S = \mathbb{N}_2$ and machines with $S = \mathbb{N}_9$ are both counted in the set $X$).

Possibly Countable Sets

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

  1. 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}

  2. $\mathbb{R} - \mathbb{Q}$.

  3. 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

  1. In class 17 we defined a set $C$ to be countable, if there is a surjective function $f: \mathbb{N} \rightarrow C$. Prove that we get an equivalent definition if we call $C$ countable whenever then there is a total surjective function, $$f: \mathbb{N} \rightarrow C.$$ Note that you need to prove two directions, that whenever $C$ satisfies in the first definition of countable, it does satisfy in the second definition of countable, and vice versa.

  2. MCS Problem 8.23.