This comes from Exercise 11 of Section 2.1 of Kaplansky's "Set Theory and Metric Spaces".

Let $A$ be an uncountable set. Let $B \subseteq A$ be a countable set and let $B^c$ be its complement in $A$. Prove that there exists a bijection between $A$ and $B^c$.

I've found some related questions here: removing a countable subset from an infinite set doesn't change cardinality, and here: Altering an Infinite Set does not change cardinality, but none seems to be exactly the one I'm looking for.

Suposedly this problem can be solved without the axiom of choice, due to it being proposed before the axiom's introduction in the book.

It is quite easy to show that $B^c$ must be uncountable, but moreover I need to prove that it has the same cardinality as $A$. That doesn't look so simple. Here are some thoughts I've been considering:

  • Since $B^c$ can be split into some countable $C$ and uncountable $C^c$, and the same for $C^c$, this problem is equivalent to partitioning $A$ into a countable number of countable sets and its complement, which must be uncountable. And if we prove that it has indeed the same cardinality as $A$, we would've proved that any partition of $A$ must include a proper subset. It is a fact that proper subsets exist in $A$ due to it being infinite, but I don't think that's enough to say that it will be present on every partition. ¿Is there a way to prove this?

  • As a particular case, we obtain from this result that irrationals and trascendents have both the same cardinality as $\mathbb{R}$.


So, following Berci's answer, I wrote this proof.

Since $B$ is countable and $A = B \cup B^c$ is uncountable it follows that $B^c$ is uncountable. Then it contains an uncountable infinite subset; call it $B_1$. By the same argument $B^c \backslash B_1$ must be uncountable. On the other hand, we have that $B \cup B_1$ is countable, so there exists a one to one correspondence between $B$, $B_1$ and $B \cup B_1$. And since $A \backslash B \cup B_1$ and $B \backslash B_1$ both have the same elements, it follows that there must exist a bijection between $A$ and $B^c$.

I think that's how it is suposed to be solved. I have some doubts about the conclusion though.

  • 3
    $\begingroup$ This can't be shown without the axiom of choice. For instance, let $A$ be the disjoint union of a countably infinite set and an infinite Dedekind-finite set. (But as Berci's answer shows, if every infinite set is Dedekind-infinite, then it holds. So the proposition is equivalent over ZF to the proposition that every infinite set is Dedekind-infinite.) $\endgroup$ – spaceisdarkgreen Jan 26 at 1:08
  • $\begingroup$ @spaceisdarkgreen. I posted my A before I read your comment. $\endgroup$ – DanielWainfleet Jan 26 at 5:22

Since $B^\complement$ is uncountable, it contains a countably infinite subset $C$.

Now simply apply a bijection between $B\cup C$ and $C$, and extend it identically on $B^\complement\setminus C$.

  • $\begingroup$ +1...........As I showed in my A, it is necessary to assume $C$ exists, which can't be done in ZF. $\endgroup$ – DanielWainfleet Jan 26 at 5:20
  • $\begingroup$ Got it. Still, since the 'assumption' is stated in Kaplansky's book before, I believe Berci's answer is the way the author wanted it to be done. $\endgroup$ – Gabriel Pena Jan 26 at 23:52
  • $\begingroup$ @GabrielPena I thought you said choice was stated after... what "assumption" are you referring to? $\endgroup$ – spaceisdarkgreen Jan 27 at 0:47
  • 1
    $\begingroup$ The book states that 'any uncountable infinite set contains a countable infinite subset', without a proper proof. Which now seems obvious because this fact is stated in Chatper 2 and choice is not introduced until Chapter 3. $\endgroup$ – Gabriel Pena Jan 27 at 1:20
  • 1
    $\begingroup$ @Gabriel Got it, sorry, should have been clear what you were referring to. In attempt to make my interjection useful I’ll add that this choice principle is pretty weak... strictly weaker than countable choice in fact, though the most obvious proof uses dependent choice. $\endgroup$ – spaceisdarkgreen Jan 27 at 1:44

It cannot be done in ZF. It has been shown to be consistent with ZF that there exists $x$ which is not Tarski-finite but is not Dedekind-infinite. That is, $x$ is not a bijective image of any bounded subset of $\Bbb N$ and $x$ has no countably-infinite subset.

If such an $x$ exists, let $A=(x\times \{0\})\cup (\Bbb N\times \{1\})$ and let $B=\Bbb N\times \{1\}$. Now if $f:A\to B^c=x\times \{0\}$ were a bijection then the image $f[B]$ would be a countably infinite subset of $x\times \{0\}$ which would imply that $\{y\in x: (y,0)\in f[B]\}$ is a countably infinite subset of $x$, a contradiction



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.