If A is a countable set, how can i show that A has countably many finite subsets?

Question

Lets say that A is a countable set. How would I go about showing that A has countably many finite subsets? I need to show that for every n ∈ N, the set Pn(A) of finite subsets - with exactly n elements - of A is countable. How would I then show how the union U(subscript'n∈N') P(hyperscript'n')(A) of all these sets is countable? Thanks in advance:)

Answer 1

Suppose that A is the set of natural numbers N. In order to show that the set of all finite subsets of N is countable it suffices to consider the following:

1) Suppose that p_{1}, p_{2}, p_{3}, ... , p_{n}, .... is an enumeration of the prime numbers in increasing order.

2) Suppose that {n_{1},n_{2},...,n_{k}} is a finite subset of N also in increasing order.

Then, the only thing you have to do is define a map f: {all finite subsets of N} \mapsto N

by the formula f({n_{1},n_{2},...,n_{k})=p_{n_{1}} p_{n_{2}} ... p_{n_{k}}.

You can show that this is a 1-1 map with target space N. Hence, the domain of f (which is the set of all finite subsets of N) must be countable.