Foundations of Computer Science: Honors
Homework 3A
Problem 2 Show that every subset of N is countable.
Problem 3 Show that the set of all integers (Z) is countable.
Problem 4 Show that the set of all finite subsets of a countable set is countable.
Problem 5 Show that the following statements are equivalent and true (Statement P and Q are equivalent if P ⇐⇒ Q): • N x N is countable. • Union of countably many countable sets is countable. • Q is countable.
Problem 6 A submarine is moving along the integer number line at a constant speed s so that at each hour it is on an integer number. It started moving at time 0 at some position b. If t is the (whole) number of hours elapsed since the submarine started moving, then its position is given by the equation x = st + b, where x,s, and b are integers.
You are working at Rocket Pizza delivery and you are to deliver pizza to the submarine. At each hour you can drop pizza on any number on the integer line. If the submarine is there at that time, then you have delivered the pizza and your job is done (you will be notified as soon as it happens).
The problem is that you don’t know where the submarine is, you cannot see it, you don’t know where it started and how fast it is moving (i.e., you don’t know values of s and b classified top secret data). The upside is that you have infinite number of pizzas.
Show that you can deliver pizza in a finite amount of time
Problem 7 The goal of this quiz/question is to make sure you will have no problems with countability in the future. In the following table, F stands for Finite, I for Infinitely Countable, C
for Countable, U for uncountable. Put a checkmark next to the strongest statement you can make about the resulting set (i.e. correct answer for F ∪F is finite, even though it is countable as well). Check ? whenever there’s not enough information to decide, i.e. there can be different cases with no ‘strongest’ answer.
