# Subset of A countable Set is countable

• Oct 29th 2008, 05:39 PM
kathrynmath
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?
• Oct 29th 2008, 11:09 PM
HallsofIvy
Quote:

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!

Quote:

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".)
• Oct 30th 2008, 03:27 AM
whipflip15
Note: $\displaystyle \mbox{If } T \subseteq S \mbox{ then } card(T) \leq card(S).$

This just makes your question seem trivial.
• Oct 30th 2008, 06:10 AM
kathrynmath
Quote:

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.
• Oct 30th 2008, 06:37 AM
HallsofIvy
Quote:

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.
• Oct 30th 2008, 06:54 AM
kathrynmath
Quote:

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.
• Oct 30th 2008, 08:58 AM
ThePerfectHacker
Quote:

Originally Posted by whipflip15
Note: $\displaystyle \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 $\displaystyle |A| \leq |\mathbb{N}|$ then $\displaystyle |A| = |\mathbb{N}|$ or $\displaystyle A$ is finite. Which is not trivial.

---
If $\displaystyle S$ is countable it means there is a sequence $\displaystyle s: \mathbb{N} \to S$ which is a bijection. Therefore, $\displaystyle \{ s_n | n\in \mathbb{N} \} = S$. Now let $\displaystyle T\subseteq S$ be an infinite subset. Define $\displaystyle t: \mathbb{N} \to T$ as $\displaystyle t_0 = s_{m_0}$ where $\displaystyle m_0 \in \mathbb{N}$ is least so that $\displaystyle s_{m_0} \in T$. Now define $\displaystyle t_{n+1} = s_M$ to be least $\displaystyle M\in \mathbb{N}$ so that $\displaystyle s_M \in T - \{ t_k | k\leq n \}$. This is always defined since $\displaystyle T$ is infinite and such a function exists by recursion theorem. It remains to prove $\displaystyle t: \mathbb{N}\to T$ is a bijection.
• Nov 2nd 2008, 12:47 PM
kathrynmath
I'm still confused on finding a one to one function T onto J.