1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – MJD
    Aug 25, 2014 at 14:37

2 Answers 2

2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Could u tell us the intuition behind your choice of the function? $\endgroup$
    – Emptymind
    Apr 10, 2017 at 16:36
1
$\begingroup$

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.

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

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.