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

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

• Let $S$ be our set of positive multiples of $5$. You are supposed to come up with an explicit bijection $f$ from $\mathbb{N}$ to $S$. – André Nicolas Nov 15 '15 at 23:35
• Did you understand what is meant by a countable infinite set? – Crostul Nov 15 '15 at 23:37
• Are you familiar with all terms involved? Do you know what a bijection is? Do you know why having a bijection between two sets implies that they have the same cardinality? An example of such a bijection for showing that $\Bbb N$ and $\Bbb Z$ have the same cardinality would be something like $f:\Bbb N\to\Bbb Z$ where $f(n)=\begin{cases} \frac{n}{2}&\text{if}~n~\text{is even}\\ \frac{-n-1}{2}&\text{if}~n~\text{is odd}\end{cases}$. – JMoravitz Nov 15 '15 at 23:37
• My understanding is: A countably Infinite set is such that every unique item of the set can be listed in an infinite list. Uncountable sets cannot have their items listed one-to-one in an infinite list. I believe my confusion is coming from the bijection and what that implies. – Hani Al-shafei Nov 15 '15 at 23:40
• A bijection is a function which is both surjective (onto) and injective (one-to-one) implying that every element in the codomain is mapped to by exactly one element in the domain. For example, the function from $\Bbb R\to\Bbb R$ given by $f(x)=2x$ is a bijection (since if $f(x_1)=f(x_2)$ then $2x_1=2x_2$ and so $x_1=x_2$ so all elements in codomain are mapped to by at most one preimage, and since any $y$ in the codomain has an $x$ (namely $\frac{y}{2}$) such that $f(x)=y$, so all elements in codomain have at least one preimage). See wiki. – JMoravitz Nov 15 '15 at 23:52

## 2 Answers

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

• So, for the first set: The set of positive integers divisible by 5. We have: f(n) = 5n. I have to show that this is onto and one-to-one with Z+? – Hani Al-shafei Nov 15 '15 at 23:58
• That's the bijection. So yes, show it is onto and one-to-one with Z+. Which is easy. – fleablood Nov 16 '15 at 0:08
• So, since it is true that $f(a) \neq f(b)$ for any distinct numbers $a$ and $b$ in Z+, we have 5a - 5b = a - b \neq 0 therefore, $f(a) \neq f(b)$ so the function is one-to-one? Little confused on the onto property. – Hani Al-shafei Nov 16 '15 at 0:17
• Be careful writing equalities: $5a-5b = 5(a-b)$. Also remember that for "one-to-one" you are usually start with $a\neq b$ and try to show that this implies $f(a)\neq f(b)$. – David K Nov 16 '15 at 1:30

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