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
up vote 2 down vote accepted

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? – Intuition 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
  • 1
    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? – Intuition 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

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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