Let the set S be infinite, and the set T countably infinite. S and T are both subsets of R. Show that S and S U T have the same cardinality.

I know we can discuss whether S is countable or uncountable, but is it true that, for example like this, countable set's cardinality basically does not count in the union of itself and an uncountable set?


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.

  • $\begingroup$ Proof of this theorem must requires choice (at least, you assume that every Dedekind-finite set is finite). If $A$ is a Dedekind-finite infinite set and $A\cap\omega=0$, then $|A|<|A\cup\omega|$. $\endgroup$ – Hanul Jeon Sep 24 '14 at 23:55
  • $\begingroup$ The statement "every infinite set is Dedekind infinite" is strictly weaker than countable choice (over ZF), however I don't know whether there are more "choice-like" equivalent forms of this former axiom. So this basically is a hidden request to tell me about them. $\endgroup$ – Stefan Mesken Feb 6 '15 at 12:59

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.