Subset of A countable Set is countable

Printable View

October 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?
October 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".)
October 30th 2008, 03:27 AM
whipflip15

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

This just makes your question seem trivial.
October 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.
October 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.
October 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.
October 30th 2008, 08:58 AM
ThePerfectHacker

Quote:

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.
November 2nd 2008, 12:47 PM
kathrynmath

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