Finite Subsets of N: Proving Countability

[kingtaf]

Prove that the collection F(N) of all fi nite subsets of N (natural numbers) is countable.

 

[hochs]

Countable union of countable sets is countable.
For each n > 0, the number of subsets having cardinality n is countable. There's the empty set for n = 0 also.

 

[Outlined]

you have to look at the maximal element in an S in F(N). After that consider there are 2^{max(S) - 1} sets in F(N) which have max(S) as a maximum. Hope this helps.

 

[willem2]

It's easy to construct a bijection from this set to N, by mapping the set to a string of 1's and 0's and so construct a binary number.

 

[blue_raver22]

To prove that the collection F(N) of all finite subsets of N is countable, we must show that there exists a one-to-one correspondence between the elements of F(N) and the set of natural numbers, N.

First, we can list out all the possible finite subsets of N in a systematic way. For example, we can start with the empty set, then list all subsets with one element, then all subsets with two elements, and so on. This way, we can create a list of all the finite subsets of N.

Next, we can assign each subset in the list a unique number based on its position in the list. For example, the empty set would be assigned the number 1, the subsets with one element would be assigned numbers 2, 3, 4, and so on, and the subsets with two elements would be assigned numbers 5, 6, 7, and so on.

This way, we have created a one-to-one correspondence between the elements of F(N) and the set of natural numbers, N. Therefore, F(N) is countable.

Furthermore, we can use the fact that the union of countably many countable sets is also countable to strengthen our proof. Since each subset in F(N) has a finite number of elements, we can consider each element as a separate countable set. Therefore, the union of all these countable sets (i.e. the collection F(N)) is also countable.

In conclusion, we have proven that the collection F(N) of all finite subsets of N is countable by showing a one-to-one correspondence between its elements and the set of natural numbers, and by using the property that the union of countably many countable sets is countable.