# Quick Question

1. Mar 13, 2007

### bomba923

How can I prove that
$$\left| {\left\{ {A \subset \mathbb{N}:\left| A \right| \in \mathbb{N}} \right\}} \right| = \left| \mathbb{N} \right|$$
?

2. Mar 13, 2007

### matt grime

By counting them. How many subsets of size n are there in N? So how many subsets do you have unioning over all n?

Or just enumerate them directly - a subset is the same as an indicator function. A finite subset is just an indicator function that is 1 finitely many times, that is a sequence such as

{0,..,0,1,0,..,0,1,0....,0,1,0,.......}

The place where you put the 1s corresponds to the elements in the set. eg the set {1,2,4} is the indicator/sequence

{1,1,0,1,0,0,0,.....}

It is easy to put these in bijection with N. In fact these are usually put in bijection with N by crackpots in an attempt to disprove the uncountability of the reals since they mistakenly believe that N all subsets of N have finitely many elements.

3. Mar 13, 2007

### JasonRox

I prefer to just create an injective map into the rationals.

Say for example A is the set {1,2,5,6}, then map it to 0.1256. And so on.

We can see it's one-to-one into the rationals. Since the rationals are countable, then is the collection of all the finite subsets of N.

4. Mar 13, 2007

### JasonRox

Nevermind, this is wrong. I'll leave it here just so readers and understand why.

Anyways, if you can prove that the countable union of a collection of countable sets is countable then all you must do is show that...

All sets of cardinality n is countable.

So, that you have all finite sets of cardinality 1, 2, 3, ..., n,... and union them all to get the collection of all finite sets of N. Since it is a countable union of a collection of countable sets then the collection of all finite sets of N is countable.

Note: matt_grime's method is definitely solid. I just like thinking of different ways to go about it. There's no doubt a lot of ways to do this.

5. Mar 13, 2007

### matt grime

That was my method 1. I gave two methods.

6. Mar 13, 2007

### matt grime

A method like that will almost always be wrong. There is a way to correct it, though, that is very useful. The problem is that in general the lack of uniqueness of decompositions (here 1256 decomposes as 1|2|5|6, and 12|56 amongst many other options). But we know something where we do have uniqueness - prime decomposition, and there are infinitely many primes. So send {1,2,5,6} to

p_1*p_2*p_5*p_6

for p_i the i'th prime (i.e. 2*3*11*13)

7. Mar 13, 2007

### JasonRox

Nice. I was thinking of a different approach to make it work, such as primes. You beat me to it.

8. Mar 13, 2007

### ZioX

What is confusing you? Is it that the power set of N is uncountable? Note how here we have a further restriction that all the sets we are considering have finite cardinality.

9. Mar 23, 2007

### sauravbhaumik

Indeed, if Axiom of Choice is assumed, the set of all finite subsets of an infinite set $$\alpha$$ has the same cardinality as $$\alpha$$.
This is seen in this way: Call the set of all finite subsets $$F(\alpha)$$.
$$|F(\alpha)|=\displaystyle \sum_{n\in\mathbb N}|\alpha^n|\\ = \displaystyle \sum_{n\in\mathbb N}|\alpha| = \aleph_0\cdot|\alpha|=|\alpha|$$

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook