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