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