Problem Set 8

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

## 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 $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.

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

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

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.MCS Problem 8.23.