# Proving that if a set A is denumerable and a set B that is finite and a subset of A, then $A\setminus B$ is denumerable

Background: This comes from the book: INTRODUCTION TO MATHEMATICAL PROOFS Charles E. Roberts, Jr. Indiana State University Terre Haute, USA A Transition to Advanced Mathematics Second Edition

A set $$A$$ is denumerable if and only if $$A\sim \mathbb{N}$$.

$$A\sim B$$ if and only if there is a one-to-one correspondence (bijection) from $$A$$ to $$B$$.

Theorem 7.15 - If $$A$$ is a denumerable set and $$B$$ is a finite set, the $$A\cup B$$ is a denumerable set.

Question:

Prove that if $$A$$ is a denumerable set and $$B$$ is a finite subset of $$A$$, then $$A\setminus B$$ is denumerable.

Attempted proof - Note that

\begin{align*} A\setminus B &= A\cap B^c\\ &= (A\cup B)\cap B^c \end{align*}

Borrowing from the comments below. Since $$A\cup B$$ is denumerable by theorem 7.15, and any subset of a denumerable set is denumerable this implies that $$A\setminus B$$ is denumerable.

We know from theorem 7.15 that $$A \cup B$$ is denumerable. I am just not sure how to show that the complement of the finite set $$B$$ with $$A\cup B$$ is also denumerable.

• Can't you just use the fact that subsets of denumerable sets are denumerable? – Don Thousand Mar 12 '19 at 4:03
• Note that $A = (A\setminus B)\cup B$. What happens if $A\setminus B$ is not denumerable? – Corrêa Mar 12 '19 at 4:06
• Other approach is to use the Hilbert's Hotel Problem. I think that the idea works fine. – Corrêa Mar 12 '19 at 4:08

Try this:

We have that there exists a bijection $$f:A \to \mathbb{N}$$

Then $$g = f^{-1}:\mathbb{N} \to A$$ is a bijection too

And $$B = \{b_{1},...,b_{k}\} \subset A$$

So, we have that for every $$n \in \mathbb{N}$$, $$g(n) = a_{n} \in A$$

And $$g(n_{i}) = b_{i}$$ for some $$n_{i}$$ with $$1 \leq i \leq k$$

And suppose that $$n_{1}

We are going to create a bijection $$h:\mathbb{N} \to$$ $$A$$ \ $$B$$

Let $$d \in \mathbb{N}\cup\{0\}$$, $$d = n_{k} - k$$

We have a subset with $$d$$ elements $$\{1,2,...,n_{k}\}$$\ $$\{n_{1},...n_{k}\} = \{c_{1},...,c_{d}\}$$

Let $$h(n) = g(c_{n})$$ if $$1 \leq n \leq d$$, and $$h(n) = g(n + k)$$ if $$n>d$$

Then $$h$$ define a bijection between $$\mathbb{N}$$ and $$A$$ \ $$B$$

First, we observe that $$A \setminus B$$ is not finite, otherwise $$A = A \setminus B \cup B$$ would be finite. Now, $$A \setminus B$$ (being infinite) is either denumerable or non - denumerable. Since $$A \setminus B \subseteq A$$ and $$A$$ is denumerable, $$A \setminus B$$ cannot be non - denumerable (A subset cannot contain "more" elements than its superset). Hence, the only possibility is that $$A \setminus B$$ is denumerable.

• You mean $A$\ $B$ cannot be non-denumerable? – J. W. Tanner Mar 12 '19 at 4:11