I am going over my professors answer to the following problem and to be honest I am quite confused :/ Help would be greatly appreciated!

Let $A$ be any uncountable set, and let $B$ be a countable subset of $A$. Prove that $|A| = |A - B|$

The answer key that I am reading right now follows this idea:

It says that $A-B$ is infinite and proceeds to define a new denumerable subset $A-B$ as $C$. Of course since $C$ is countably infinite then we can write $C$ as ${c1,c2,c3...}$

Once we have a set $C$, we know that the union of $C$ and $B$ must be denumerable (from another proof) since $B$ is countable and $C$ is denumerable.

This is where I start to have trouble. The rest of the solution goes like this...

Since the union of $C$ and $B$ is denumerable, there is a bijective function $f$ that maps the union of $C$ and $B$ to $C$ again. The solution then proceeds to define another function $h$ that maps $A$ to $A-B$.

I am just so lost. The thing is I don't even understand the point of constructing a new subset $C$ or defining functions like $f$ or $h$.

So I suppose my question is in general, how would one approach this problem? I am not mathematically inclined unfortunately, and a lot of the steps in almost all of these problems seems arbitrary and random. Help would be really appreciated on this problem and some general ideas on how to solve problems like these!!!

Thank you so very much!


4 Answers 4


You have the uncountable set $A$ and its countable subset $B$. You want to show that $|A\setminus B|=|A|$, i.e., that there is a bijection between $A$ and $A\setminus B$. To see what that would mean, let’s imagine for a moment that we already have such a bijection $h:A\to A\setminus B$. $A$ is the union of the disjoint sets $B$ and $A\setminus B$, and $h$ is a bijection, so $h[A]$, which is $A\setminus B$, is the union of the disjoint sets $h[B]$ and $h[A\setminus B]$, as in the sketch below. And because $h$ is a bijection, we know that $B$ and $h[B]$ have the same cardinality; in particular, $h[B]$ is countable. In other words, if we’re to have this bijection $h$, we need to have some countable subset $h[B]$ of $A\setminus B$ that $h$ matches up with the subset $B$ of $A$. The set $C$ of your proof is going to be that set.

enter image description here

We know that $A\setminus B$ has a countably infinite subset $C$, and we know from an earlier result that $B\cup C$ is countably infinite. This means that $|B\cup C|=|C|$: there is a bijection $f:B\cup C\to C$. We can now use $f$ to build the desired bijection $h:A\to A\setminus B$ quite easily. We’ll split $A$ into two pieces, $B\cup C$ and the rest, which is $A\setminus(B\cup C)=(A\setminus B)\setminus C$; these are shown in red and white, respectively, in the lefthand set in the picture below. We’ll use the bijection $f$ to map $B\cup C$ to $C$, and we’ll use the identity map $\mathrm{id}$ to send $(A\setminus B)\setminus C$ to itself. Combining these two bijections gives us a bijection, which I’ll call $h$, from $A$ to $A\setminus $B$, as in the picture below.

enter image description here

Formally we define $h:A\to A\setminus B$ by

$$h(a)=\begin{cases} f(a),&\text{if }a\in B\cup C\\\\ a,&\text{if }a\in(A\setminus B)\setminus C\;. \end{cases}$$

The key idea is simply that all countably infinite sets are the same size, so we can find a bijection between any two of them. We use that fact to find the bijection $f$ that ‘collapses’ $B\cup C$ into $C$; then we leave all of the other elements of $A$ alone (i.e., those in $(A\setminus B)\setminus C$), and the net effect is to collapse $A$ into $A\setminus B$ with the bijection $h$.

  • 1
    $\begingroup$ Wow! What an explanation!! The diagram helped tremendously! Thank you so much! However, I am still not convinced why we need the set $C$. Could we have not just said, well $|B|$ must be equal to $|h[b]|$ and the $|A-B|$ must be equal to $|h[A-B]|$? Could we have not constructed our function $h$ like that? I understand how the solution works with the set $C$ but feel as though it would also work only with set $B$. $\endgroup$
    – nicefella
    Apr 9, 2013 at 0:06
  • 1
    $\begingroup$ @nicefella: You’re welcome! The idea is to build $h$ so that it leaves most of $A\setminus B$ alone. But we need to set aside a bit of $A\setminus B$ into which we collapse $B$. The easiest way to do this is to reserve a countably infinite amount of space $-$ that’s $C$ $-$ and then collapse $B$ and $C$ into that reserved space. I don’t see any nice way to do this without $C$. $\endgroup$ Apr 9, 2013 at 0:16
  • $\begingroup$ Ah yes! That makes sense! Excellent and thanks again :) $\endgroup$
    – nicefella
    Apr 9, 2013 at 0:20
  • $\begingroup$ @nicefella: Glad to have helped. $\endgroup$ Apr 9, 2013 at 0:21
  • $\begingroup$ Reading this more closely, don't you mean "We’ll use the bijection $f$ to map B∪C to C." [ Paragraph between the two diagrams.] @BrianM.Scott $\endgroup$ Nov 13, 2016 at 16:56

$|A-B|\leq |A|$ is obvious.

For the reverse inequality, Use $|A|=|A\times A|$. Denote the bijection $A\rightarrow A\times A$ by $\phi$, then $\phi(B)$ embeds into a countable subset of $A\times A$.

Then consider the projection $\pi_1$ onto the first coordinate, of the set $\phi(B)$. Namely $\pi_1 \phi(B)$.

Since $|\pi_1\phi(B)|\leq |B|$, and $|B|<|A|$, we see that $A-\pi_1\phi(B)$ is nonempty. Pick any element $x \in A-\pi_1\phi(B)$, then we see that $\{x\}\times A$ embeds into $(A\times A)-\phi(B)$.

This gives the reverse inequality $|A|\leq |A-B|$.

  • $\begingroup$ This short argument, unfortunately, implicitly uses the Cantor-Bernstein theorem, whereas the accepted answer does not! $\endgroup$
    – murray
    Jul 6, 2021 at 21:07

Your answer key is right, but I think it can be describe more simply.

We have $A$ uncountable and $B$ countable. Since $A-B$ is infinite, it contain another countable set $C$. So there is a bijection $C\rightarrow B\cup C$ as you note. Now let $D=(A-B)-C$, so $A-B=C\cup D$, and therefore $A=B\cup C\cup D$, all three of which are disjoint from one another. Since you have the bijection $C\rightarrow B\cup C$, you clearly have another bijection $(C)\cup D\rightarrow (B\cup C)\cup D$, but by construction that is the bijection $A-B\rightarrow A$.

But why is it done this way? It's kind of a trick. The key is realizing that you needed to separate both $A$ and $A-B$ into a countable piece, and another piece whose cardinality may not be countable. Further, you need that questionable piece to be the same set on both sides of the bijection: that's $D$ in my example. The trick is that the countable piece is different on each side of the bijection ($C$ vs. $B\cup C$), but since both are countable you get a bijection anyway!


EDIT: I just realised that this solution is exactly the same as the trb456's answer. I will leave it anyway, because it is explained slightly differently.

Brian's answer is very elegant and nicely explained. I believe I solved it in a different manner using the theorem for the existence of at least one uncountable subset. I am a novice with set theory however, so there might be mistakes, redundancies and unnecessarily complicated reasoning.

First off, for later clarity let $\hat A :=A\backslash B$. We know we may find a countable subset $C = \{c_1, c_3,...,c_{2n-1},...\}$ in $\hat{A}$. As has already been discussed, it follows that there exists a bijection between $C$ and $B$, i.e. an equivalence $C\sim B$. The following paragraph is trying to show how we may then find an uncountable subset $D$ such that $D\cap C = \emptyset$ (i.e. have no elements in common), which will have a very useful second property.

Consider a second countable subset $E = \{c_2, c_4,...,c_{2n},...\}$. As the union of two countable sets is countable there is an equivalence $E\cup C \sim E$. We may extend this equivalence so that $(E\cup C)\cup (\hat{A}\backslash (E\cup C)) \sim E \cup (\hat{A}\backslash (E\cup C))$, by transforming $x\in \hat{A}\backslash (E\cup C)$ to itself. But this is the same as $\hat{A} \sim \hat{A}\backslash C$. Thus we have found the uncountable subset $D=\hat{A}\backslash C$ that I mentioned previously.

Now for the kicker. We have because of the above that $D\cup C \sim \hat{A}\cup B$, by sending $x\in D$ to $\hat{A}$ and $x\in C$ to $B$. But $D\cup C = \hat{A}$ and $\hat{A}\cup B = A$. Thus $A\backslash B \sim A$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .