Proving Cardinality of $\mathbb{N}$ Subsets

[bomba923]

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

 

[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.

 

[JasonRox]

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.

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.

 

[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.

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.

 

[matt grime]

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.

That was my method 1. I gave two methods.

 

[matt grime]

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

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)

 

[JasonRox]

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)

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

 

[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.

 

[sauravbhaumik]

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

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|$$