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.

  • $\begingroup$ What is your definition of an “infinite set”? $\endgroup$ – Michael Hoppe Oct 8 '13 at 12:54
  • $\begingroup$ A set with infinitely many members? Is there something else I should have considered? $\endgroup$ – Si Chen Oct 8 '13 at 12:55
  • $\begingroup$ @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. $\endgroup$ – Dylan Yott Oct 8 '13 at 13:01
  • $\begingroup$ @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. $\endgroup$ – Asaf Karagila Oct 8 '13 at 13:03
  • 3
    $\begingroup$ 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. $\endgroup$ – Asaf Karagila Oct 8 '13 at 13:14

In order to prove this is true for all infinite sets you have to use the axiom of choice in one way or another (or at least a fragment of it). And indeed we cannot prove that in naive set theory.

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.

  • $\begingroup$ 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. $\endgroup$ – Trevor Wilson Oct 8 '13 at 16:41
  • $\begingroup$ Trevor, it's a mental typo. :-) $\endgroup$ – Asaf Karagila Oct 8 '13 at 16:56
  • $\begingroup$ 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. $\endgroup$ – Trevor Wilson Oct 8 '13 at 17:09
  • $\begingroup$ Trevor, you're right again. $\endgroup$ – Asaf Karagila Oct 8 '13 at 17:24

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.