Let A and B be countable infinite sets. Being both countable, a one-to-one correspondence between the set’s elements can be established. A new correspondence can also be established between A and the union of all elements in A and B, since this is another countable set.

Intuitively, it would seem even more obvious that the same would apply if A was uncountable. The larger set would still be uncountable. However, the countability is part of the proof in the first case, such as two car lanes merging into one. The same technique is not available in the second case.

(I note the question: An uncountable set minus a countable set is still uncountable, but is that equivalent to my question? - It would be if there is a one-to-one correspondence between all uncountable sets, but I don't think this is obvious)

How is such a proof delivered?

  • $\begingroup$ Could you be more clear about what correspondence you are looking for? $\endgroup$ – Karl Kronenfeld Sep 7 '13 at 19:43

We can see that an uncountable set minus a countable set is indeed uncountable.

Suppose for an uncountable set $A$ and a countable set $B$ that $A-B$ is countable. The union of countably many countable sets is countable; thus $(A-B) \cup B$ is countable. But then A is a subset of $(A-B) \cup B$ and thus must be countable itself, which is a contradiction.

It is however not true that there is a bijection between all uncountable sets. The cardinality of the continuum is one such cardinality of an uncountable set, but by Cantor's theorem, the power set of the reals has a cardinality strictly larger than that of the continuum. The power set of the power set of the reals has yet a larger cardinality. Thus there are infinitely many uncountable cardinalities, by extension.

Does this help?


EDIT: see this also.

  • $\begingroup$ Thanks, it confirms my suspicion – I believe in terms of cardinalities, that I would like to see proven that a an uncountable set of a certain cardinality + a countable set is a new set with the same cardinality, not only that it is still uncountable. $\endgroup$ – Mikael Jensen Sep 7 '13 at 20:26
  • $\begingroup$ This is also true. I will edit my answer with this proof. $\endgroup$ – Fernando Pessoa Sep 7 '13 at 21:15
  • $\begingroup$ I am afraid I will have to do this tonight though. :) $\endgroup$ – Fernando Pessoa Sep 7 '13 at 21:16

Let $A$ be an uncountable and $B$ a countable set. There is certainly an injection from $A$ into $A\cup B$; if we can show that there is an injection from $A\cup B$ into $A$, then we can apply the Schröder-Bernstein theorem to conclude that there is a bijection between $A$ and $A\cup B$.

There is no harm in assuming that $A\cap B=\varnothing$, as we can always replace $B$ by $B\setminus A$ if necessary. There is an injection $h:\Bbb N\to A$; let $A_0=\{h(n):n\in\Bbb N\}$. There is an injection $g:B\to\Bbb N$. Now define

$$f:A\cup B\to A:x\mapsto\begin{cases} x,&\text{if }x\in A\setminus A_0\\ h(2k),&\text{if }x=h(k)\text{ for some }k\in\Bbb N\\ h\big(2g(x)+1\big),&\text{if }x\in B\;, \end{cases}$$

and check that $f$ is injective. (The idea is that we’re fitting copies of both $A_0$ and $B$ into $A_0$ while leaving the rest of $A$ alone.)

  • $\begingroup$ +1, but it should probably be noted that it is not trivial that $h$ exists; this depends on having at least something like the Axiom of Dependent Choice available. $\endgroup$ – Henning Makholm Sep 7 '13 at 20:14
  • $\begingroup$ @Henning: It’s trivial for those of us who take AC for granted! (I thought about mentioning AC and decided that it was more likely to be confusing than helpful at the level suggested by the question.) $\endgroup$ – Brian M. Scott Sep 7 '13 at 20:20
  • $\begingroup$ Thanks, this may be what I need - but I am surprised that it seems much more complicated than I thought. $\endgroup$ – Mikael Jensen Sep 7 '13 at 20:28
  • $\begingroup$ @Mikael: Once you see clearly what it’s doing, I think that you’ll find that the complexity is merely technical: the idea is the ‘merging lanes’ notion that you mentioned in the question. By the way, with some adjustment in the case in which $B$ is finite you can arrange for $f$ to be a bijection and avoid the Schröder-Bernstein theorem altogether. $\endgroup$ – Brian M. Scott Sep 7 '13 at 20:31

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.