Let the set S be infinite, and the set T countably infinite. Show that S and S U T have the same cardinality

Solution 1:

Let $A$ be a countably infinite subset of $S$.* The first thing we want to do is find a map $g : A \to A \cup T$.

Since $A$ is countable, there's some bijection $\alpha$ from $\mathbb{N}$ to $A$, and same with $T$ (with bijection $\beta$). Define $\gamma : \mathbb{N} \to A \cup T$ as follows: $$\gamma(n) = \begin{cases} \alpha(\frac{n}{2}) & n \textrm{ is even} \\ \beta(\frac{n+1}{2}) & n \textrm{ is odd} \\ \end{cases} $$

Since $\gamma$ is a bijection, this tells us that $A \cup T$ is countable. So there's some bijection $g : A \to A \cup T$. Define $f : S \to S \cup T$ as follows: $$f(s) = \begin{cases} s & s \notin A \\ g(s) & s \in A \\ \end{cases} $$

*I'm not sure how one proves such a set exists. It's easy if you have the well-ordering theorem, but I think you can get away with a weaker form of Choice. Not sure how weak though.