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.

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!

share|improve this question

3 Answers 3

up vote 5 down vote accepted

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 $B$, 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$.

share|improve this answer
1  
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$. –  nicefella Apr 9 '13 at 0:06
1  
@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$. –  Brian M. Scott Apr 9 '13 at 0:16
    
Ah yes! That makes sense! Excellent and thanks again :) –  nicefella Apr 9 '13 at 0:20
    
@nicefella: Glad to have helped. –  Brian M. Scott Apr 9 '13 at 0:21

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

share|improve this answer

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!

share|improve this answer

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.