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

Question

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!

Answer 1

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

Answer 2

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

Answer 3

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!

Answer 4

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