0

Problem: Let $A$ be a non-countable set and let $B\subseteq A$ be a countable set. Prove that $A\setminus B$ is non-countable.

Where, $(X \text{ is non-countable})\;\iff (|X|>|\mathbb{N}|)$.

Of course, a way to prove this would be by finding a function $f:A\to A\setminus B$ that's injective to show that $|A|\leq |A\setminus B|$ thus finishing the proof. I can´t seem to be able to find shuch a function.

My guess would be that a function like that should exist due to the following special case:

$$\big|\mathbb{R}\setminus\big(\;]-\infty,-\pi/2]\cup [\pi/2,\infty[\;\big)\big|=\big|(-\pi/2,\pi/2)\big|=\big|\mathbb{R}\big|$$ Thanks to the existence of the function $\tan:(-\pi/2,\pi/2)\to\mathbb{R}$ which is bijective.

How could I find an appropriate function to prove Problem?

Please help adding or removing tags if necessary. Thanks in advance.

Sebastián P. Pincheira
  • 2,527
  • 2
    Do you already know the fact that if $X$ and $Y$ are both numerable (I think it's more common to say "denumerable" or "countable") then $X\cup Y$ is also numerable? What happens if you apply that fact with $X=A\setminus B$ and $Y=A\cap B$? – Greg Martin Jul 10 '20 at 21:19

1 Answers1

2

Since $B$ is countable, there exists an injection $f : B \rightarrow \mathbb N$

Suppose $A \setminus B$ is countable. Then there exists an injection $g : A \setminus B \rightarrow \mathbb N $.

Now let $h : A \rightarrow \mathbb N$ be defined by

$$ h(x) = \left \{ \begin{array}{l} 2f(x) \quad &\text{if} \quad x \in B \\ 2g(x) + 1 \quad &\text{if} \quad x \in A \setminus B \end{array} \right. $$

$h : A \rightarrow \mathbb N$ is an injection so $A$ is countable, which is a contradiction.

DodoDuQuercy
  • 1,760