Set of all finite subsets of N (real analysis)

[KevinL]

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 a₁ to be the set of all finite one-element subsets of N. And then perhaps expand that idea to a_n+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.

 

[mynameisfunk]

Try thinking about how you should go about showing your bijection onto N. How would you make sure you didnt miss any elements?

 

[JonF]

Are you familiar with the Cantor-Schroeder-Bernstein theorem? If so this isn’t so bad. Let’s call N'
your set of all finite subsets of N.

N->N'should be trivial

Hint for N’->N. Consider the set Nb' the set of N' in binary format. So {1,3,5} -> {1,11, 101}. Clearly Nb' and N' are bijective.

Is there an easy way to uniquely map every element of Nb' into N by using digits other than “0” and “1”

 

[KevinL]

Im trying it with induction.

Let A be the set of all finite subsets of N

Let a_n , n>=1 be a set of subsets of N each with cardinality of n.

Claim: Any a_n is countable, so the union from n=0 to infinity of a_n is countable, and thus A would be countable. Prove by induction.

basis: n=1, a₁: N: 1 2 3...
a₁: {1}{2}{3}... and we have an obvious bijection.

Inductive hypothesis: Assume a_n is countable. Show a_n+1 is countable.

For any set S is an element of a_n+1, remove an arbitrary element K. The resulting sets are T and P such that T is an element of a_n, and K is an element of P is an element of a₁.

By inductive hypothesis, T is countable. By basis step we know a₁ is countable. So the union of T and P is countable, so a_n+1 is countable. Therefore A is countable.

Does this look right?

 

[JonF]

this step doesn't follow:
So the union of T and P is countable, so an+1 is countable. Therefore A is countable.

The union of T and P is your S, not your an+1