# Uncountable minus countable set is uncountable

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?

TIA.

-
Do you know that $\aleph_0 + K=K$ where $K$ is infinite cardinality ? – 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.

-
Thank you very much. It's a nice proof by contradiction. – Pampero Sep 1 '12 at 14:43
@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)." – J. Loreaux Sep 1 '12 at 14:47
@J.Loreaux: I did not know that. Thank you for the clarification. :) – Pampero Sep 1 '12 at 14:51
Doesn't this answer use the continuum hypothesis? – Exterior Sep 10 '15 at 10:56
@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). – Thomas Sep 10 '15 at 11:53

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.

-
Thank you for the clue. :) – Pampero Sep 1 '12 at 14:43

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.

-
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. – Pampero Sep 1 '12 at 14:56
Also, why do you assume that $A = (A \setminus B) \cup B$? I think you meant $A \subseteq (A\setminus B)\cup B$. – Pampero Sep 1 '12 at 15:08
@Pampero I made little corrections and I think that now everything is clear :) Why the minus vote? – Godot Sep 1 '12 at 16:41
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$). – Godot Sep 1 '12 at 16:47
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. :) – Pampero Sep 1 '12 at 17:04