Uncoutable set minus a countable subset is uncountable without axiom of choice or continuum hypothesis

Question

Is there a way of proving that if $|X|=2^{\aleph_0}$ and $Y\subseteq X$ such that $|Y|=\aleph_0$ then $|X-Y|=2^{\aleph_0}$ without using axiom of choice or continuum hypothesis. Most of the proofs I've seen for this rely on the fact that if $X-Y$ does not have the cardinality of $\mathbb{R}$, then it must be countable (because it is clearly infinite). I was wondering if there is any way around this.

Answer 1

Yes, it is possible to prove this in just ZF. Let us identify our set $X$ with $\mathbb{R}^2$ (via some bijection, since we know $|X|=|\mathbb{R}^2|=2^{\aleph_0}$). Consider the first projection map $p:Y\to\mathbb{R}$ defined by $p(x,y)=x$. Since $Y$ is countable, $p$ cannot be surjective, so there exists some $x\in\mathbb{R}$ such that $(x,y)\not\in Y$ for all $y\in\mathbb{R}$. That is, $\{x\}\times\mathbb{R}\subseteq X-Y$. Thus $|X-Y|\geq |\{x\}\times\mathbb{R}|=2^{\aleph_0}$ and $|X-Y|\leq|X|=2^{\aleph_0}$, so $|X-Y|=2^{\aleph_0}$.

More generally, a similar argument shows that if $X$ is a set such that $|X\times X|=|X|$, then for any $Y\subseteq X$ such that there is no surjection from $Y$ to $X$, we must have $|X-Y|=|X|$.

Answer 2

If $X\setminus Y$ contains a countably infinite subset, you can use the trick described in this question to show that $|X\setminus Y|=|X|$. That’s automatic if every Dedekind infinite is infinite, something that follows from but is strictly weaker than the countable axiom of choice, which is a rather weak form of the axiom of choice. It can also be a consequence of the reason for which you know that $|X|=2^{\aleph_0}$. For instance, if you know this because you have a bijection between $X$ and $\Bbb R$ or $\wp(\omega)$, then you have access to many countably infinite subsets of $X$ via the bijection.