Set of finite subsets of Z+ is denumerable

[issacnewton]

Hi

I am trying to prove that

P=\{X\in\mathcal{P}(\mathbb{Z^+})\;|\;X\mbox{ is finite }\}

is denumerable. Now here is the strategy I am using. Let

A_n=\{X\in\mathcal{P}(\mathbb{Z^+})\;|\; |X|=n\;\}

So A_n are basically sets of subsets of \mathbb{Z^+} with cardinality
n. So we see that

P=A_0\cup A_1\cup A_2\cdots

I am trying to get help of the following theorem which is proved in the section of the book
(Velleman's How to prove it, section 7.2 )

Theorem: If \mathcal{F} is a family of sets, \mathcal{F} is countable
, and also every element of \mathcal{F} is countable , then \bigcup\mathcal{F} is countable .

So in this direction , let's define a family of sets \mathcal{F}

\mathcal{F}=\{A_n\;|\;n\in \mathbb{N}\}

\therefore \bigcup\mathcal{F}= P

So to use the theorem quoted, I need to prove first that for all n in N, A_n is
countable. How would I go about this ?

Thanks

 

[Dick]

Try and think of a relation between A_n and ( \mathbb{Z^+} )^n (the cartesian product of n copies of \mathbb{Z^+}).

 

[issacnewton]

Dick

I could show that ( \mathbb{Z^+} )^n is denumerable using induction. But
are you suggesting that I prove A_n \sim \;( \mathbb{Z^+} )^n ? Now
( \mathbb{Z^+} )^n has ordered pairs and A_n has sets as elements, which are unordered. So how would we map it for the bijection ?

 

[Dick]

Dick

I could show that ( \mathbb{Z^+} )^n is denumerable using induction. But
are you suggesting that I prove A_n \sim \;( \mathbb{Z^+} )^n ? Now
( \mathbb{Z^+} )^n has ordered pairs and A_n has sets as elements, which are unordered. So how would we map it for the bijection ?

Don't worry about a bijection. Figure out an injection of the sets into the tuples. Define ordering as part of the mapping.

 

[issacnewton]

Ok

So I can map an element of A_n into an element of ( \mathbb{Z^+} )^n such that an element of ( \mathbb{Z^+} )^n is sorted in an increasing order and all the members of n-tuple belong to the element of A_n which is being mapped. That way I can prove the injection from A_n to
( \mathbb{Z^+} )^n. So how would I put that formally ?

 

[Dick]

Ok

So I can map an element of A_n into an element of ( \mathbb{Z^+} )^n such that an element of ( \mathbb{Z^+} )^n is sorted in an
increasing order. That way I can prove the injection from A_n to
( \mathbb{Z^+} )^n. So how would I put that formally ?

I think you just did. Given a set, sort it in increasing order. That gives a unique tuple in ( \mathbb{Z^+} )^n. So given a set you can construct the corresponding ordered tuple. You don't have to spell out how you would sort it or anything. That's enough of a definition of a function for me. If you can explain to a computer programmer how to construct the correspondence then you've defined it.

 

[issacnewton]

Dick, I know that I gave the correct outline. I will try to formulate it using mathematical symbols now.

 

[Dick]

Dick, I know that I gave the correct outline. I will try to formulate it using mathematical symbols now.

You sure did. I don't think every proof has to be Principia Mathematica. But go ahead.

 

[issacnewton]

ok So I have proved an injection from A_n to ( \mathbb{Z^+} )^n.
Also I said in post # 3 , we can prove a bijection from ( \mathbb{Z^+} )^n to
\mathbb{Z^+}. That means we can prove an injection from A_n
to \mathbb{Z^+}. So for all n, A_n is denumerable and hence countable. So I have proved that every element of \mathcal{F} is countable.
I still have to prove that \mathcal{F} itself is countable to use that theorem I stated in post # 1. How would I do that ?

 

[Dick]

ok So I have proved an injection from A_n to ( \mathbb{Z^+} )^n.
Also I said in post # 3 , we can prove a bijection from ( \mathbb{Z^+} )^n to
\mathbb{Z^+}. That means we can prove an injection from A_n
to \mathbb{Z^+}. So for all n, A_n is denumerable and hence countable. So I have proved that every element of \mathcal{F} is countable.
I still have to prove that \mathcal{F} itself is countable to use that theorem I stated in post # 1. How would I do that ?

The n in A_n is nonnegative integer since it's a finite cardinality. Doesn't that make it obvious?

 

[issacnewton]

oh i missed that. so define a function

h=\{(b,k)\in \mathcal{F}\times \mathbb{Z^+}|k=1+\mbox{ cardinality of any set in }b\;\}

We can prove that h:\mathcal{F}\to \mathbb{Z^+} and that h is a bijection.
So this proves that \mathcal{F} is denumerable and hence countable. So using the theorem mentioned in post # 1, we see that P itself is countable. To prove that P is denumerable, I will still need to prove that P is infinite. To do that, I need to find a proper subset of P such that P is equipotent/equinumerous with that subset...

How would I do that ?

 

[Dick]

oh i missed that. so define a function

h=\{(b,k)\in \mathcal{F}\times \mathbb{Z^+}|k=1+\mbox{ cardinality of any set in }b\;\}

We can prove that h:\mathcal{F}\to \mathbb{Z^+} and that h is a bijection.
So this proves that \mathcal{F} is denumerable and hence countable. So using the theorem mentioned in post # 1, we see that P itself is countable. To prove that P is denumerable, I will still need to prove that P is infinite. To do that, I need to find a proper subset of P such that P is equipotent/equinumerous with that subset...

How would I do that ?

You can prove P is infinite by proving A_1 is infinite. And I think you are cluttering up a fairly simple proof with notationally complicated proofs of the obvious. If this were homework I was required to read, I wouldn't like that.

 

[issacnewton]

Dick , I am doing the problem from Daniel Velleman's "How to prove it" . The book is teaching to do proofs. As for the author, he is the student of Mary Ellen Rudin, who in turn was a student of Robert Lee Moore. And I have heard on other forums that these people were heckler for definitions. May be that's a school of thought.

 

[Dick]

Dick , I am doing the problem from Daniel Velleman's "How to prove it" . The book is teaching to do proofs. As for the author, he is the student of Mary Ellen Rudin, who in turn was a student of Robert Lee Moore. And I have heard on other forums that these people were heckler for definitions. May be that's a school of thought.

Oh, alright. I'll stop fussing about what I see as clutter. Maybe some people do like it.

 

[jbunniii]

oops, scratch that

 

[jbunniii]

You're overthinking the proof that P is infinite. P contains all the singletons {n}, where n is any positive integer, so obviously it is not finite.

 

[issacnewton]

Yes that makes sense...