- #1

- 759

- 0

[tex]\left| {\left\{ {A \subset \mathbb{N}:\left| A \right| \in \mathbb{N}} \right\}} \right| = \left| \mathbb{N} \right|[/tex]

?

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Thread starter bomba923
- Start date

- #1

- 759

- 0

[tex]\left| {\left\{ {A \subset \mathbb{N}:\left| A \right| \in \mathbb{N}} \right\}} \right| = \left| \mathbb{N} \right|[/tex]

?

- #2

matt grime

Science Advisor

Homework Helper

- 9,395

- 4

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

JasonRox

Homework Helper

Gold Member

- 2,314

- 3

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.

- #4

JasonRox

Homework Helper

Gold Member

- 2,314

- 3

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.

- #5

matt grime

Science Advisor

Homework Helper

- 9,395

- 4

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.

- #6

matt grime

Science Advisor

Homework Helper

- 9,395

- 4

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)

- #7

JasonRox

Homework Helper

Gold Member

- 2,314

- 3

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.

- #8

- 370

- 0

- #9

- 10

- 0

[tex]\left| {\left\{ {A \subset \mathbb{N}:\left| A \right| \in \mathbb{N}} \right\}} \right| = \left| \mathbb{N} \right|[/tex]

?

Indeed, if Axiom of Choice is assumed, the set of all finite subsets of an infinite set [tex]\alpha[/tex] has the same cardinality as [tex]\alpha[/tex].

This is seen in this way: Call the set of all finite subsets [tex]F(\alpha)[/tex].

[tex]|F(\alpha)|=\displaystyle \sum_{n\in\mathbb N}|\alpha^n|\\

= \displaystyle \sum_{n\in\mathbb N}|\alpha| = \aleph_0\cdot|\alpha|=|\alpha|[/tex]

Share: