Infinities are weird

The answer is B ; we always have $|A| = |A \setminus B|$ .

First, the union of two countable sets is countable. There are many proofs on the internet , and hence I'll skip it. (The idea is to enumerate the elements of $X, Y$ as $x_1, x_2, \ldots$ and $y_1, y_2, \ldots$ , and see $x_1, y_1, x_2, y_2, \ldots$ .)

Next, with this, if $A \setminus B$ is countable then $A = B \cup (A \setminus B)$ will also be countable (since it's the union of two countable sets), contradicting the hypothesis in the problem. Thus $A \setminus B$ is uncountable. However, it is not enough to show that $A, A \setminus B$ are both uncountable, since there are infinitely many uncountable cardinal numbers. Thus we must proceed further.

Since Axiom of Choice holds, we know that $|A \setminus B| > |B|$ (since $A \setminus B$ is uncountable while $B$ is countable, and Axiom of Choice implies that any countable cardinal is strictly smaller than any uncountable cardinal). By definition, there exists an injective function $f$ from $B$ to $A \setminus B$ ; let the image be $C$ . By definition of image, $f$ is a bijection from $B$ to $C$ and is thus $C$ is a countable subset of $A \setminus B$ .

Enumerate the elements of $B = \{b_1, b_2, \ldots\}$ and $C = \{c_1, c_2, \ldots\}$ . Since $C \subset A \setminus B$ , we know that $B \cap C = \emptyset$ ; elements of $C$ are taken from elements not in $B$ .

Now define another function $g : A \to (A \setminus B)$ :

$g(x) = \begin{cases} x & \text{if } x \notin B, C \\ c_{2i-1} & \text{if } x = b_i \in B \\ c_{2i} & \text{if } x = c_i \in C \end{cases}$

It's easy to see that $g$ is a bijection. Any element not in either $B$ or $C$ is mapped identically (which is trivially a bijection), while $g$ provides a bijection from the countable set $B \cup C$ to the countable set $C$ . The existence of a bijection proves that both sets have equal cardinality; that is, $\boxed{|A| = |A \setminus B|}$ .