8
$\begingroup$

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.

  • 2
    Do you know that $\aleph_0 + K=K$ where $K$ is infinite cardinality ?2012-09-01

3 Answers 3

19

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.

  • 0
    Thank you very much. It's a nice proof by contradiction.2012-09-01
  • 9
    @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)."2012-09-01
  • 0
    @J.Loreaux: I did not know that. Thank you for the clarification. :)2012-09-01
  • 0
    Doesn't this answer use the continuum hypothesis?2015-09-10
  • 1
    @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).2015-09-10
  • 0
    @Thomas you assumed by contradiction $A$ is countable, which may not be the negation of $A$ is uncountable, no?2015-09-10
  • 1
    @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$.2015-09-10
4

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.

3

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.

  • 0
    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.2012-09-01
  • 0
    Also, why do you assume that $A = (A \setminus B) \cup B$? I think you meant $A \subseteq (A\setminus B)\cup B$.2012-09-01
  • 0
    @Pampero I made little corrections and I think that now everything is clear :) Why the minus vote?2012-09-01
  • 0
    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$).2012-09-01
  • 0
    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. :)2012-09-01
  • 0
    @Pampero: No problem :) Yes now I believe :)2012-09-01