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

$\displaystyle B\subseteq A$

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

where $\displaystyle m\leqslant n$ and

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

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

$\displaystyle f:N\rightarrow A$

Since $\displaystyle B\subseteq A$ ,

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

$\displaystyle f(n_1)=b$

Now we define a function

$\displaystyle 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

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

$\displaystyle B\subseteq A$

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

where $\displaystyle m\leqslant n$ and

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

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

$\displaystyle f:N\rightarrow A$

Since $\displaystyle B\subseteq A$ ,

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

$\displaystyle f(n_1)=b$

Now we define a function

$\displaystyle 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...)

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 ?

Let $\displaystyle A$ be countable and $\displaystyle 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.)

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 ?

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 $\displaystyle A\text{ is countable }$ by definition there is a injection $\displaystyle \mathif{f}:A\to \mathbb{N}$.
Define $\displaystyle \mathif{g}:B\to \mathbb{N}$ as $\displaystyle \mathif{g} (b)= \mathif{f}(b). $
Now show that $\displaystyle \mathif{g}$ is an injection.

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

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

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

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

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

Consider arbitrary $\displaystyle b_1,b_2 \in B$ ,

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

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

But since $\displaystyle B\subseteq A$,

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

so, $\displaystyle \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

can anybody confirm my proof in the last post ?

thanks

Quote:

---

Originally Posted by issacnewton

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

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

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

---

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

$\displaystyle g(b) = f(b)$ for every $\displaystyle 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 $\displaystyle \emptyset$ to $\displaystyle \mathbb{N}$ is the empty function.

Hi makarov

Thanks for the reply. Makes sense now.