Problem statement

Prove that if $A$ is an uncountable set and $B$ is a countable set, then $A\setminus B$ must be uncountable.

What I think

The statement does not mention $A$ and $B$ relationship. I think there are two possibilities:

  • If $A \cap B = \emptyset $, then $A\setminus B$ is trivially uncountable
  • If $A \cap B = B$, then $B \subset A$ and as a bijection can not be made between $A\setminus B$ and $\mathbb{N}$, $A\setminus B$ is uncountable.

And there is where I'm stuck. How can I prove that a bijecton can't be made?


  • 2
    $\begingroup$ Do you know that $\aleph_0 + K=K$ where $K$ is infinite cardinality ? $\endgroup$ – Belgi Sep 1 '12 at 14:15

Maybe this is a way to see it. You can make it more precise yourself. Assume that $A\setminus B$ is countable. $B$ is countable, so that would mean that $(A \setminus B) \cup B$ is countable (finite union of countable sets is clearly countable). But then $A \subseteq (A\setminus B)\cup B$, so $A$ is contained in a countable set, so it must itself be countable.

  • $\begingroup$ Thank you very much. It's a nice proof by contradiction. $\endgroup$ – Pampero Sep 1 '12 at 14:43
  • 11
    $\begingroup$ @Pampero: Just fyi, this is actually a proof by contrapositive. That is, if the statement is of the form "if P, then Q," then this argument proves the equivalent statement "if not Q, then not P." A proof by contradiction would show that "if (P and not Q), then (R and not R)." $\endgroup$ – J. Loreaux Sep 1 '12 at 14:47
  • $\begingroup$ @J.Loreaux: I did not know that. Thank you for the clarification. :) $\endgroup$ – Pampero Sep 1 '12 at 14:51
  • 1
    $\begingroup$ @Exterior: how so? Since $A$ is contained in a countable set, it is itself countable. The continuum hypothesis is about sets that have cardinality greater than countable (I believe). $\endgroup$ – Thomas Sep 10 '15 at 11:53
  • 1
    $\begingroup$ @Exterior: No, not quite. To show that $A$ uncountable implies $A\setminus B$ uncountable, do the contrapositive. So we show that not $A\setminus B$ uncountable implies that not $A$ not uncountable. So, yes, we need the negation of uncountable. The definition of uncountable is not countable. So not uncountable is countable. Now, the continuum hypothesis is about the "different types of uncountable", but we are not concern about that. Uncountable means cardinality strictly greater than $\aleph_0$. $\endgroup$ – Thomas Sep 10 '15 at 16:14

First, the two cases you mention don't include all possibilities. For your question, note that the union of two countable sets is again countable.


Suppose that $A-B=A-A\cap B$ is countable. Then you have a bijection between $A-B$ and the set of even natural numbers. Since $B$ is countable then $A\cap B$ is also countable and you have a bijection between $A\cap B$ and the set of odd natural numbers. Now, taking the union of those bijections, you get the bijection between the set $A=(A-B)\cup (A\cap B)$ and the set of natural numbers, which is an absurd because $A$ is uncountable. Thus $A-B$ is uncountable. Q.E.D.

If $A\cap B$ is just finite countable then the proof goes similarly with obvious changes, see comments.

  • $\begingroup$ Thank you for the proof. It is very clear. When you say: "which is an absurd because $B$ is uncountable" Didn't you mean "$A$ is uncountable"? Thanks. $\endgroup$ – Pampero Sep 1 '12 at 14:56
  • $\begingroup$ Also, why do you assume that $A = (A \setminus B) \cup B$? I think you meant $A \subseteq (A\setminus B)\cup B$. $\endgroup$ – Pampero Sep 1 '12 at 15:08
  • $\begingroup$ @Pampero I made little corrections and I think that now everything is clear :) Why the minus vote? $\endgroup$ – Godot Sep 1 '12 at 16:41
  • $\begingroup$ One more detail: if some of the mentioned sets are finite countable ($A\cap B$ could be...) then argument still works with some minor changes (just make bijection between $\mathbb{N}-F$ and $A-B$ and between $F$ and $A\cap B$ where $F$ is a finite subset of $\mathbb{N}$ of the same cardinality as $A\cap B$). $\endgroup$ – Godot Sep 1 '12 at 16:47
  • $\begingroup$ thanks again for clarifying. :) It wasn't me the one who gave you the minus vote. To be able to vote you've to get 15 reputations points, and ATM I only have 13. Q.E.D., it wasn't me. :) $\endgroup$ – Pampero Sep 1 '12 at 17:04

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.