# denumerability

• Dec 6th 2005, 10:49 AM
mathkid
denumerability
Prove that if A is denumerable and B is a finite subset of A, then A \ B is denumerable.
• Dec 6th 2005, 08:37 PM
CaptainBlack
Quote:

Originally Posted by mathkid
Prove that if A is denumerable and B is a finite subset of A, then A \ B is denumerable.

Lets assume you are using the definition of denumerable as meaning
countably infinite.

Let \$\displaystyle a_1,\ a_2,\ ...,\ a_n,\ ...\$ be an enumeration of \$\displaystyle A\$.
We can rearrange this enumeration so that <you may need to prove that this can be done>:

\$\displaystyle B\ =\ \{a_1,\ a_2,\ ...,\ a_{N_B}\}\$

(\$\displaystyle N_B\$ is the number of elements of \$\displaystyle B\$)

Then:

\$\displaystyle A \backslash B\ =\ \{a_{N_B+1},\ a_{N_B+2},\ ...\}\$.

So \$\displaystyle c_1,\ c_2,\ ...,\ c_N,\ ...\$ where \$\displaystyle c_n\ =\ a_{N_B+n}\$ is an enumeration of \$\displaystyle A \backslash B\$

RonL
• Dec 9th 2005, 11:17 AM
rgep
I like to use the definition of "countable" as "can be injected into the natural numbers". It is then immediate that a subset of a countable set is countable. "Denumerable" is countable and not finite, where "finite" means every injection of the set to itself is also a surjection. All that remains is to prove that the union of two finite sets is finite; use the lemma that a finite set injects into {1..n} for some natural number n.