# Thread: Subset of A countable Set is countable

1. ## Subset of A countable Set is countable

I am trying to prove that any subset of a countable set is countable.
I'm working with the with S being countably infinite right now.

Proof:
Let S be countably infinite. A set S is countably infinite iff S is equivalent to the set J of positive integers. Then there exists f such that S is 1-1 and onto J. A subset of S will also be in the set of positive integers. Thus, also countably infinite. Therefore, T is countable.

I think i went wrong somewhere. Do I need to find a 1-1 and onto function T to J?

2. Originally Posted by kathrynmath
I am trying to prove that any subset of a countable set is countable.
I'm working with the with S being countably infinite right now.

Proof:
Let S be countably infinite. A set S is countably infinite iff S is equivalent to the set J of positive integers. Then there exists f such that S is 1-1 and onto J. A subset of S will also be in the set of positive integers. Thus, also countably infinite. Therefore, T is countable.
That's not even true! A subset of a countable set may be finite! Your statement "A subset of S will also be in the set of positive integers" is also not true- it is not assumed that S itself is "in" the set of positive integers. You may have meant that there is a 1-1 and onto function from the subset to positive integers but that is exactly what you want to prove.- you can't just say it!

I think i went wrong somewhere. Do I need to find a 1-1 and onto function T to J?
You mean, I presume, "any infinite subset of a countable set is countably infinite". What you need to do is show that there exist 1-1 onto function from the subset to N (the standard notation of the set of positive integers. There is no need for a "J".)

3. Note: $\mbox{If } T \subseteq S \mbox{ then } card(T) \leq card(S).$

This just makes your question seem trivial.

4. Originally Posted by HallsofIvy
That's not even true! A subset of a countable set may be finite! Your statement "A subset of S will also be in the set of positive integers" is also not true- it is not assumed that S itself is "in" the set of positive integers. You may have meant that there is a 1-1 and onto function from the subset to positive integers but that is exactly what you want to prove.- you can't just say it!

You mean, I presume, "any infinite subset of a countable set is countably infinite". What you need to do is show that there exist 1-1 onto function from the subset to N (the standard notation of the set of positive integers. There is no need for a "J".)
Sorry, I already proved for the finite set and my book uses J for natural numbers.
So, up to here, am i correct?
Proof:
Let S be countably infinite. A set S is countably infinite iff S is equivalent to the set J of positive integers. Then there exists f such that S is 1-1 and onto J.

5. Originally Posted by kathrynmath
Sorry, I already proved for the finite set and my book uses J for natural numbers.
So, up to here, am i correct?
Proof:
Let S be countably infinite. A set S is countably infinite iff S is equivalent to the set J of positive integers. Then there exists f such that S is 1-1 and onto J.
You don't have to say "Let S be countably infinite", that is given in the hypothesis. And it is f that is 1-1 and onto not S.

6. Originally Posted by HallsofIvy
You don't have to say "Let S be countably infinite", that is given in the hypothesis. And it is f that is 1-1 and onto not S.
Then, can I now say that the subset will be 1-1 and onto. The subset will either be finite or countably infinite.

7. Originally Posted by whipflip15
Note: $\mbox{If } T \subseteq S \mbox{ then } card(T) \leq card(S).$

This just makes your question seem trivial.
No it does not. You are assuming it is a trivial fact that if $|A| \leq |\mathbb{N}|$ then $|A| = |\mathbb{N}|$ or $A$ is finite. Which is not trivial.

---
If $S$ is countable it means there is a sequence $s: \mathbb{N} \to S$ which is a bijection. Therefore, $\{ s_n | n\in \mathbb{N} \} = S$. Now let $T\subseteq S$ be an infinite subset. Define $t: \mathbb{N} \to T$ as $t_0 = s_{m_0}$ where $m_0 \in \mathbb{N}$ is least so that $s_{m_0} \in T$. Now define $t_{n+1} = s_M$ to be least $M\in \mathbb{N}$ so that $s_M \in T - \{ t_k | k\leq n \}$. This is always defined since $T$ is infinite and such a function exists by recursion theorem. It remains to prove $t: \mathbb{N}\to T$ is a bijection.

8. I'm still confused on finding a one to one function T onto J.