# Proving Cardinality of $\mathbb{N}$ Subsets

• bomba923
In summary, using the Axiom of Choice, it can be proven that the set of all finite subsets of an infinite set has the same cardinality as the set itself. This is because the set of all finite subsets can be shown to have a cardinality equal to the sum of infinite copies of the cardinality of the original set, which is equal to the cardinality of the set itself.

#### bomba923

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

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.

matt grime said:
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 said:
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.

JasonRox said:
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.

JasonRox said:
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)

matt grime said:
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.

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.

bomba923 said:
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|$$