Need some guidance for a proof of countable sets

Hi

I am proving that any subset of a countable set is also countable.

I will show my work here. Let set A be countable. We have as one of the cases, where A is an empty set , but by definition its finite and hence countable.

So I am not going to consider the empty subset of A as its trivial. So there are

two cases

Case 1) A is a finite set.

Let and let

then

where and

Then its clear that there exists a bijection from B to {1,2,..m} for some m in N

Hence B is finite and countable

Case 2) A is inifnite

Let

Since A is infinite , so there exists a bijection from A to N. Hence there exists a bijection from N to A.

Since ,

Now we define a function

from above arguments, its clear that g is onto. I have to prove that B is also countable, so it could mean that B is either finite or infinite or empty. So how

do I proceed now ? I have checked some proofs of this theorem online and I had

trouble understanding it , so I decided to post the question.

thanks

Re: Need some guidance for a proof of countable sets

Quote:

Originally Posted by

**issacnewton** Hi

I am proving that any subset of a countable set is also countable.

I will show my work here. Let set A be countable. We have as one of the cases, where A is an empty set , but by definition its finite and hence countable.

So I am not going to consider the empty subset of A as its trivial. So there are

two cases

Case 1) A is a finite set.

Let

and let

then

where

and

Then its clear that there exists a bijection from B to {1,2,..m} for some m in N

Hence B is finite and countable

Case 2) A is inifnite

Let

Since A is infinite ,

so there exists a bijection from A to N. Hence there exists a bijection from N to A.

Since

,

Now we define a function

from above arguments, its clear that g is onto. I have to prove that B is also countable, so it could mean that B is either finite or infinite or empty. So how

do I proceed now ? I have checked some proofs of this theorem online and I had

trouble understanding it , so I decided to post the question.

thanks

Define the following function:

f:B-->N where to every x in B, the set of elements from B that less than x is finite.

So, for every x in B, f(x) be the set of elements from B that less than x.

Example:

If B={1,4,9,16,25,...}

f(25)=4

f(16)=3

f(9)=2

.

.

.

Now, prove that f is 1-1 and onto.(Not an easy task...)

Re: Need some guidance for a proof of countable sets

Quote:

Originally Posted by

**Also sprach Zarathustra** f:B-->N where to every x in B,** the set of elements from B that less than x is finite**.

Why is that true, the highlighted part. Is there any other proof of that ?

Re: Need some guidance for a proof of countable sets

Let be countable and . If B is empty or finite the result is trivial, so the only interesting case is where A is countably infinite and B is infinite. Put A in bijection with N, this yields a bijection between B and an infinite subset (call it M) of N. So it's enough to show that an infinite subset of N is countable. By well-ordering, M has a least element m, so pair m with 1. Then M\{m} has a least element; pair that one with 2, and so on. Clearly we will exhaust every natural number in this way, and almost as clearly we will use up every element of M (this is where the thing AsZ said comes in), so we have the bijection.

(You can see that every element of M has only finitely many elements less than it, since elements of M are natural numbers and are finite.)

Re: Need some guidance for a proof of countable sets

Hi Tinyboss, so is my proof to case 1 right ? and within case 2, am I right when I say that we can use the same arguments for

the finite subset of infinite A ?

You said " Put A in bijection with N, this yields a bijection between B and an infinite subset (call it M) of N"

I did prove in my post that the function g : B --> N is onto. How do I prove your claim in the above statement ?

Re: Need some guidance for a proof of countable sets

Re: Need some guidance for a proof of countable sets

intuitively (and somewhat naively, or informally), we can list the elements of A.

since B is a subset of A, we just "cross off the elements in the list not in B" and "fill in the gaps" by "moving things up".

Re: Need some guidance for a proof of countable sets

Thanks everybody ......... I will try to put my proof together and show it here. Its late here , have to sleep now.

Re: Need some guidance for a proof of countable sets

Hi

Sorry for the late reply. I was out of town. So here's my proof. I have decided to use Plato's arguments.

Since A is countable an injection

Now let , lets define a function

Consider arbitrary ,

since

Since A is an injection, if

But since ,

(how do we justify this ?)

so,

which proves that g is an injection and so B is countable.

Like I said withing the proof, how do we justify that g(b)=f(b) for all b in B?

Second thing is when A itself is empty set. Is it still possible to say that there is

an injection from A to N, since its still countable ?

thanks

Re: Need some guidance for a proof of countable sets

can anybody confirm my proof in the last post ?

thanks

Re: Need some guidance for a proof of countable sets

Quote:

Originally Posted by

**issacnewton** Now let

, lets define a function

...

(how do we justify this ?)

You never said *how* you defined g. Plato's suggestion is that

for every

holds by definition. In other words, g is the restriction of f to B.

Quote:

Second thing is when A itself is empty set. Is it still possible to say that there is

an injection from A to N, since its still countable ?

The situation when A is empty does not require a special case; it is covered by the proof above. The injection from to is the empty function.

Re: Need some guidance for a proof of countable sets

Hi makarov

Thanks for the reply. Makes sense now.