# Prove $A$ countable and $B$ a finite subset of A $\implies (A-B)$ is countable.

Can someone verify this. I am confused because I am not sure if I am being asked to strictly construct a bijection or not, although that is probably the case. The thing that confuses me is that I am not sure what "countable" means-- even on StackExchange people will say different things. Is countable a bijection from a set to the natural numbers? Is it an injection from the natural numbers to a set?

Am I supposed to talk about cardinality? Functions? What about the theorem that subsets of a countable set are countable?

Let us assume $A$ is countable and $B$ is a finite subset of $A$.

$A$ is countable which means it is either finite, or countably infinite.

If $A$ is finite, then $(A-B)$ is clearly finite (and countable) since the difference of two finite sets is finite.

If $B = \emptyset$, then $(A-B) = A$, which is countable so $(A-B)$ is countable.

Let us consider the case where $A$ is countably infinite.

Consider an arbitrary element $x \in (A-B).$

$\implies x \in A \land x \notin B$.

So $x\in A$.

It follows that $\forall x \in (A-B), x \in A \implies (A-B) \subseteq A$.

We can assume $(A-B) \neq A$ because $A$ is countably infinite and $(A-B)$ is finite, so $(A-B) \subset A$.

Suppose we define an injection $f$ as $f:A \rightarrow \mathbb{N}$.

Since $(A-B) \subset A$ we can from that derive an injective function $g: (A-B) \rightarrow A$.

We can compose these two injective functions as $g \circ f: (A-B) \rightarrow \mathbb{N}$.

• Note that $|A-B|\le |A|,$ and hence $\le \omega$, i.e., it is countable. – Paul May 20 '16 at 3:32

Conceptually, I think you have the idea. Just note "$A$ is countable" does not mean $\# A = \# \mathbb{N}$, but that $A$ admits a bijection to a subset of $\mathbb{N}$, so $\# A \leq \# \mathbb{N}$. Now to actually prove the claim, simply take your bijection and construct new one out of it by removing the elements of $B$.

• I thought that $\#A \leq \#B$ for two sets $A$ and $B$ meant that there was an injection from $A \rightarrow B$? (which may or may not be a bijection). – J00S May 20 '16 at 4:26
• I also thought that $\#A < \#B$ meant there was strictly an injection (not a bijection). – J00S May 20 '16 at 4:27
• you are correct. But the two definitions are equivalent. An injection from $A$ to $B$ means one can construct to a bijection from $A$ to a subset of $B$ (this subset is just the image). – GiantTortoise1729 May 20 '16 at 15:44
• How about this? $g$ as $g: (A-B) \rightarrow (\mathbb{N}-\{f(b):$ for some $b \in B\})$ – J00S May 21 '16 at 21:49
• exactly. just make sure you're rigorous about defining everything. – GiantTortoise1729 May 21 '16 at 22:47

If $f:A \to \mathbb{N}$ is injective, $f:S\to \mathbb{N}$ is injective where $S \subset A$. Can you see why?

• Well, $B$ being a finite subset of another set $A$ means there is an injection from $B$ to that set $A$, right? – J00S May 20 '16 at 4:28
• Is there something like a set $A \approx \mathbb{N}$, $(A-B) = A - \{b \in B\}$, $(A-B) \approx (\mathbb{N} - \{n \in \mathbb{N}\}$, $\mathbb{N} \approx (\mathbb{N} - \{n \in \mathbb{N}\})$ $\implies (A-B) \approx \mathbb{N}$ – J00S May 20 '16 at 4:32
• Is this because there is an injection from $S$ to $A$, and you can compose the two functions to create an injection from $S$ to $\mathbb{N}$? The thing that confuses me here is that there are conflicting definitions of "countable" I am getting. Some say it is a bijection to the natural numbers others tell me it is the other way around, or that it is an injection to the natural numbers...? – J00S May 21 '16 at 20:29

Hint: Since $A$ is countable, there is a bijection from $A$ to $\mathbb N$.

Using this, show that there is a way to enumerate $A$ as $(a_n)_{n < \omega}$ such that $B = (a_n)_{n < m}$ for some finite $m$.

This then gives a fairly natural bijection of $A \setminus B$ to $\mathbb N$.