# How to prove a set is countably infinite

The problem states that A is countably infinite and element b is not in A. It then asks to show that A union {b} is countable infinite.

I'm pretty sure I need to find a bijection between the union and the set of all positive natural numbers, I'm just having trouble figuring out where to go after introducing said function, or how to prove such a function is one to one and onto. Any pointers?

• Since A is countable, there is a bijection tween A and N. Call it f so f (0) is the first element of A, f (1) is the second and so on. Define g:N->A +b as g (0) = b; g (n)=f (n-1) in n>1. g is a bijection. – fleablood Mar 7 '16 at 3:19

## 2 Answers

Let $a_1, a_2, a_3,\ldots$ be a sequence containing all members of the set $A$.

Then $b, a_1, a_2, a_3,\ldots$ is a sequence containing all members of the set $A\cup\{b\}$. $$\begin{array}{cccccccccc} 1 & 2 & 3 & 4 & 5 & \cdots \\ \updownarrow & \updownarrow & \updownarrow & \updownarrow & \updownarrow & \cdots \\ b & a_1 & a_2 & a_3 & a_4 & \cdots \end{array}$$

HINT: It might help to first do a concrete example - can you find a bijection between $\mathbb{N}$ and $\mathbb{N}_{>1}$?

If you can do this, then the general argument is similar:

• Since $A$ is countably infinite, we have a bijection $f$ between $A$ and $\mathbb{N}$.

• By the above exercise, we also have a bijection $g$ between $\mathbb{N}$ and $\mathbb{N}_{>1}$.

• Do you see how to build a bijection between $\mathbb{N}$ and $\mathbb{N}_{>1}\cup\{b\}$? If so, do you see how this helps finish the problem?