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

Printable View

- December 6th 2005, 11:49 AMmathkiddenumerability
Prove that if A is denumerable and B is a finite subset of A, then A \ B is denumerable.

- December 6th 2005, 09:37 PMCaptainBlackQuote:

Originally Posted by**mathkid**

countably infinite.

Let be an enumeration of .

We can rearrange this enumeration so that:**<you may need to prove that this can be done>**

( is the number of elements of )

Then:

.

So where is an enumeration of

RonL - December 9th 2005, 12:17 PMrgep
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.