# 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.

-

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

## 3 Answers

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

4
@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

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
show 1 more comment
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 40, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9576089978218079, "perplexity_flag": "head"}