Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

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

3 Answers 3

up vote 10 down vote accepted

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.

share|improve this answer
    
Thank you very much. It's a nice proof by contradiction. –  Pampero Sep 1 '12 at 14:43
5  
@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.

share|improve this answer
    
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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.