# Show that 2S = S for all infinite sets

I am a little ashamed to ask such a simple question here, but how can I prove that for any infinite set, 2S (two copies of the same set) has the same cardinality as S? I can do this for the naturals and reals but do not know how to extend this to higher cardinalities.

• What is your definition of an “infinite set”? – Michael Hoppe Oct 8 '13 at 12:54
• A set with infinitely many members? Is there something else I should have considered? – Si Chen Oct 8 '13 at 12:55
• @MichaelHoppe, it depends. You could define a finite set to be a set which can be put into bijection with $\{1, \ldots n\}$ for some $n \in \mathbb N$. Then an infinite set would be a set that is not finite. I suppose you could also define an infinite set to be one that can be put into bijection with a proper subset of itself. You could also probably get away with defining an infinite set to be one that surjects onto $\mathbb N$. I'm sure Asaf can be more helpful here. – Dylan Yott Oct 8 '13 at 13:01
• @Dylan: You can also define an infinite set as a set which satisfy many many other axioms about self injections, self surjections, or injections or surjection with $\Bbb N$. If we assume the axiom of [countable] choice, then all these become equivalent whereas if we don't assume it then they might be different. – Asaf Karagila Oct 8 '13 at 13:03
• By the way, Si Chen, there's nothing to be ashamed for in this question. It's a nontrivial question from the naive point of view. – Asaf Karagila Oct 8 '13 at 13:14

If you wish to prove that for "known" infinite sets, e.g. $\Bbb R$, then this can be done without the axiom of choice indeed.
Using the axiom of choice, $S$ can be put in bijection with an ordinal $\delta$ - which we will only require to be a limit ordinal. Now we can easily define the map from $2\times\delta$ into $\delta$ by the following injection, for $\beta$ limit ordinal, $n\in\omega$ and $i\in\{0,1\}$ we define $$(i,\beta+n)\mapsto\beta+2n+i.$$ This is an injection, since given $(i,\beta+n)$ and $(i',\beta'+n')$ if $i\neq i'$ then clearly the results differ, if $i=i'$ and $n\neq n'$ the result must again differ, and similarly for $\beta\neq\beta'$. So two pairs are mapped to two different pairs.
The above map is in fact a bijection (given $\gamma<\delta$ we can "decode" the pair that was mapped to it), but if one finds the proof of surjectivity any less than immediate, then we can define an injection from $\delta$ into $2\times\delta$ simply by $\alpha\mapsto(0,\alpha)$. Using the Cantor-Bernstein theorem we have that $|\delta|=2|\delta|$, and since $\delta$ and $S$ have the same cardinality we finish.
• I don't understand your first injection---is there a typo perhaps? Anyway I think it would be easier to do this by applying the usual bijection $\omega \cong 2 \times \omega$ to each interval $[\lambda, \lambda + \omega) \subset \delta$ where $\lambda < \delta$ is limit. – Trevor Wilson Oct 8 '13 at 16:41
• I think your map is still wrong. For example, now $(0,3n+1)$ and $(1,n)$ both map to $3n+1$. If you just make it $\beta + 2n + i$ will be a bijection and you won't need Cantor-Bernstein. – Trevor Wilson Oct 8 '13 at 17:09