Showing that a set is countably infinite by defining a bijection between $\Bbb N$ and that set.

Question

I'm a little confused on what is being asked here:

Show that the following sets are countably infinite, by defining a bijection between $\Bbb N$ (or $\Bbb Z^+$) and that set.

• The set of positive integers divisible by $5$.

• $\{1,2,3\} \times \Bbb Z$.

Answer 1

The problem is asking you to precisely describe a function from $\mathbb Z^+$, that is, from the set $\{1,2,3,\ldots\}$, to another set, and to prove that the function you have described is one-to-one and onto.

When you have done that, by doing this you will have shown that the other set is countably infinite.

For example, suppose the "other" set were the set all integers greater than $3$, namely, $\{4,5,6,\ldots\}$. Let $f$ be the function given by $f(n) = n + 3$.

The "one-to-one" property requires that for any distinct numbers $a$ and $b$ in $\mathbb Z^+$, it will always be true that $f(a) \neq f(b)$. So let $a$ and $b$ be any distinct numbers in $\mathbb Z^+$; then $$f(a) - f(b) = (a + 3) - (b + 3) = a - b \neq 0,$$ therefore $f(a) \neq f(b)$. Hence the function is one-to one.

The "onto" property requires that for any $b$ in the $\{4,5,6,\ldots\}$, there must be an $a$ in $\mathbb Z^+$ such that $f(a) = b$. So let $b$ be any number in $\{4,5,6,\ldots\}$, and let $a = b - 3$, treating these numbers as integers. But $b \geq 4$, therefore $a = b - 3 \geq 4 - 3 = 1$, hence $a$ is a positive integer, that is, $a \in \mathbb Z^+$ and $f(a) = b$, so $f$ is an onto function.

There are actually two problems in the problem statement, because you have to do all this for the positive integers divisible by $5$, and then do it all over again (with a new function) for the set $\{1,2,3\} \times \Bbb Z$.

Answer 2

Hint for the second item: Every element in $\mathbb N$ can be written uniquely as $3q+r$, with $r \in \{1,2,3\}$.