- #1
KevinL
- 37
- 0
Homework Statement
Show that the set of all finite subsets of N is a countable set.
The Attempt at a Solution
At first I thought this was really easy. I had A = {B1, B2, B3, ... }, where Bn is some finite subset of N. Since any B is finite and therefore countable, and since a union of finite sets is countable, then the set of all finite subsets is countable. But I'm pretty sure this is false because its sort of assuming that the set A is countable.
So I got to thinking that I could consider a1 to be the set of all finite one-element subsets of N. And then perhaps expand that idea to an+1 to be any of these such sets. From here though, I'm not sure how to prove that the set of all of these subsets is countable.
Im thinking induction, and the basis step is a pretty obvious bijection with N. But I don't know where to go from here.