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!
Best Answer
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.
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.
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$.