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.


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.

  • 2
    $\begingroup$ Can't you just use the fact that subsets of denumerable sets are denumerable? $\endgroup$ – Don Thousand Mar 12 '19 at 4:03
  • 1
    $\begingroup$ Note that $A = (A\setminus B)\cup B$. What happens if $A\setminus B$ is not denumerable? $\endgroup$ – Corrêa Mar 12 '19 at 4:06
  • $\begingroup$ Other approach is to use the Hilbert's Hotel Problem. I think that the idea works fine. $\endgroup$ – 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}<n_{2}< \dots <n_{k}$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.