2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – fleablood Mar 7 '16 at 3:19
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.