Need some guidance for a proof of countable sets

Printable View

June 17th 2011, 08:59 AM
issacnewton

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 $A=\{a_1,a_2,\cdots,a_n\}$ and let

$B\subseteq A$

then $B=\{b_1,b_2,\cdots, b_m\}$

where $m\leqslant n$ and

$b_i \in A \;\; \forall \; i$

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 $B\subseteq A$

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

$f:N\rightarrow A$

Since $B\subseteq A$ ,

$\forall \;\;b\in B \;\;\exists \; n_1 \in N \backepsilon$

$f(n_1)=b$

Now we define a function

$g:N\rightarrow B$

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
June 17th 2011, 09:11 AM
Also sprach Zarathustra

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 $A=\{a_1,a_2,\cdots,a_n\}$ and let

$B\subseteq A$

then $B=\{b_1,b_2,\cdots, b_m\}$

where $m\leqslant n$ and

$b_i \in A \;\; \forall \; i$

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 $B\subseteq A$

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

$f:N\rightarrow A$

Since $B\subseteq A$ ,

$\forall \;\;b\in B \;\;\exists \; n_1 \in N \backepsilon$

$f(n_1)=b$

Now we define a function

$g:N\rightarrow B$

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...)
June 17th 2011, 09:31 AM
issacnewton

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 ?
June 17th 2011, 09:38 AM
Tinyboss

Re: Need some guidance for a proof of countable sets

Let $A$ be countable and $B\subset A$ . 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.)
June 17th 2011, 09:51 AM
issacnewton

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 ?
June 17th 2011, 09:52 AM
Plato

Re: Need some guidance for a proof of countable sets

Quote:

Originally Posted by issacnewton

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

There is no need for cases. Because $A\text{ is countable }$ by definition there is a injection $\mathif{f}:A\to \mathbb{N}$ .
Define $\mathif{g}:B\to \mathbb{N}$ as $\mathif{g} (b)= \mathif{f}(b).$
Now show that $\mathif{g}$ is an injection.
June 17th 2011, 10:09 AM
Deveno

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".
June 17th 2011, 10:14 AM
issacnewton

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.
June 20th 2011, 10:35 PM
issacnewton

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 $\exists$ an injection $f:A\to \mathbb{N}$

Now let $B\subseteq A$ , lets define a function

$g:B\to \mathbb{N}$

Consider arbitrary $b_1,b_2 \in B$ ,

since $B\subseteq A \;\;\Rightarrow b_1,b_2 \in A$

Since A is an injection, if $b_1\neq b_2 \Rightarrow f(b_1)\neq f(b_2)$

But since $B\subseteq A$ ,

$g(b)=f(b)$ (how do we justify this ?)

so, $\Rightarrow g(b_1)\neq g(b_2)$

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
June 21st 2011, 10:24 AM
issacnewton

Re: Need some guidance for a proof of countable sets

can anybody confirm my proof in the last post ?

thanks
June 21st 2011, 04:51 PM
emakarov

Re: Need some guidance for a proof of countable sets

Quote:

Originally Posted by issacnewton

Now let $B\subseteq A$ , lets define a function

$g:B\to \mathbb{N}$ ...

$g(b)=f(b)$ (how do we justify this ?)

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

$g(b) = f(b)$ for every $b\in B$

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 $\emptyset$ to $\mathbb{N}$ is the empty function.
June 22nd 2011, 01:30 AM
issacnewton

Re: Need some guidance for a proof of countable sets

Hi makarov

Thanks for the reply. Makes sense now.