# Bijection between an infinite set and its union of a countably infinite set

I have $A$ as an infinite set and $S$ as a countably infinite set, (so that means there exists a one-to-one correspondence between $S$ and $\mathbb{N}$).

How do I show that there always exists a bijection between $A$ and $A\cup S$? Can it be done by showing that there is a bijection from $A$ to $S$ or from $A$ to itself? I am lost on this one.

Oh, and can it be possible that there is no bijection if it is between $S$ and $A\cup S$? What about a map that maps $\mathbb{N}\to \mathbb{N}\cup\mathbb{R}$?

• You are talking about “bijection between an infinite set and its union with a countably infinite set”. $\Bbb N\to\Bbb N\cup \Bbb R$ isn't an example, because $\Bbb R$ isn't countably infinite. $\Bbb R\to \Bbb R\cup\Bbb N$ is an example, and there is a bijection. – MJD Aug 25 '14 at 14:37

## 2 Answers

Take a countably infinite sequence from $A$ which includes $S\cap A$, denoted by $(a_n)_{n\geq 1}$. And denote also $S\cup \{a_n, n = 1,2,\cdots\} = \{b_n, n = 1,2,\cdots\}$, since the union of two countable sets are still countable.

Then one explicit bijection between $A$ and $A\cup S$ is the following $f$:

$f(x) = x$ if $x \not\in \{a_n, n = 1,2,\cdots\}$, $f(a_{k}) = b_k$

Clearly it's a surjection. The fact that it's an injection is implied by the way we pick $(a_n)_{n\geq 1}$.

There can't be a bijection between $\mathbb{N}$ and $\mathbb{N}\cup \mathbb{R}$

• Could u tell us the intuition behind your choice of the function? – Emptymind Apr 10 '17 at 16:36

Let $S=\{s_n\}_{n\in\mathbb N}$. As $A$ is infinite, then it has an infinite countable subset $\{a_n\}_{n\in\mathbb N}$.

Define now the following bejection $f:A\to A\cup S$:

$$f(x)=\left\{\begin{array}{llll} x & \text{if} & x\in A\smallsetminus \{a_n\}_{n\in\mathbb N},\\ a_{n} & \text{if} & x=a_{2n-1},\\ s_{n} & \text{if} & x=a_{2n}. \end{array} \right.$$

There is no bijection between $\mathbb N$ and $\mathbb R\cup\mathbb N$, as there is no bijection between $\mathbb N$ and $(0,1)$. This is done using a standard (Cantor's) diagonal argument.

• It's possible that some $x$ in $A-\{a_n, n=1,\cdots,\}$ is equal to some $s_n$ – Petite Etincelle Aug 25 '14 at 15:01
• I have assumed that $A\cap S=\varnothing$ – Yiorgos S. Smyrlis Aug 25 '14 at 15:08
• Yeah, I guess so, why not mention it explicitly in the answer – Petite Etincelle Aug 25 '14 at 15:10
• Could u tell us the intuition behind your choice of the function? – Emptymind Apr 10 '17 at 16:36
• @YiorgosS.Smyrlis Could u tell us the intuition behind your choice of the function? – user426277 Apr 11 '17 at 9:10