Problem 1: Zig-Zag (Interleaving)

1. In the reading you proved that the negative integers are countable. The positive integers are clearly countable, since they are the natural numbers. So taken altogether, we could expect that the set of all integers is countable. Prove that this is the case. (Hint: the idea from the infinite hotel might help you here.)

2. It turns out that we can more generally state that the union of two countable sets is also countable. Since \(\mathbb{Z} = \mathbb{Z}^+\cup\{0\}\cup\mathbb{Z}^-\), this fact would tell us that the integers are countable. Prove the following claim by listing the elements of the union of two countable sets

   Claim (Union of Two Countable Sets): if \(A\) and \(B\) are both countable sets, then their union \(A\cup B\) is also countable.

Problem 2: Rational Diagonals

The positive rational numbers are defined as \(\mathbb{Q}^+ = \{\frac{m}{n} | m,n\in\mathbb{N}\}\), i.e., the set of all numbers that can be written as the ratio of two natural numbers, following the instructions below to prove this set is countable.

1. Our goal is to prove that the rational numbers are countable. One good way to get started is to try writing down a few rational numbers as we think about how to count/list them systematically. Notice that the rational numbers are all numbers that take the form \(m/n\), where \(m\) and \(n\) are both natural numbers. So one way we can visually represent these numbers is to put them into a table. Let \(m\) be the rows and \(n\) be the columns, then fill the table with the corresponding entries. Try actually filling out a 5x5 table as an example.
2. Now that we have a table filled with the rational numbers, all we have to do is find a way to count them. Try to think up several strategies for counting/listing the contents of the table. For now, don’t worry about whether the approaches will work, just try to propose a few possible counting strategies.
3. Two simple approaches to listing the contents of the table would be to count across each row one at a time, or down each column one at a time. But it turns out that these approaches both have the same critical flaw. Why will these approaches fail to prove that the rational numbers are countable? (Hint: A properly formed list must be able to tell you the index of each element. What is the index of \(2/1\) or \(1/2\) in your list if you use these strategies?)
4. Identify a counting strategy that will work to prove that the natural numbers are countable. Be reasonably precise when describing your specific counting algorithm. (Note: there are actually a number of reasonable approaches here, though one is a particular classic.)
5. Now complete the proof by arguing that your counting algorithm will produce a list of the rational numbers that is both complete and unique. Be careful, there are a few subtle details to watch out for in your table of rational numbers.

Problem 3: Cross Products

1. Prove that the set of all pairs of natural numbers is countable: \(\{(m,n) | m,n\in\mathbb{N}\}\).

2. Let’s generalize this to pairs of any two countable sets. Prove the following claim

   Claim (Cross Product of Two Countable Sets): if \(A\) and \(B\) are both countable sets, then their cross product \(A\times B\) is also countable.