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

21

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.

  • 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
    @Pampero: No problem :) Yes now I believe :)2012-09-01