Results 1 to 8 of 8

Math Help - Subset of A countable Set is countable

  1. #1
    Senior Member
    Joined
    Apr 2008
    From
    Vermont
    Posts
    318

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,389
    Thanks
    1324
    Quote Originally Posted by kathrynmath View Post
    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".)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Aug 2008
    Posts
    120
    Note: \mbox{If } T \subseteq S \mbox{ then } card(T) \leq card(S).

    This just makes your question seem trivial.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Apr 2008
    From
    Vermont
    Posts
    318
    Quote Originally Posted by HallsofIvy View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,389
    Thanks
    1324
    Quote Originally Posted by kathrynmath View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Apr 2008
    From
    Vermont
    Posts
    318
    Quote Originally Posted by HallsofIvy View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by whipflip15 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member
    Joined
    Apr 2008
    From
    Vermont
    Posts
    318
    I'm still confused on finding a one to one function T onto J.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 5
    Last Post: January 9th 2013, 06:14 AM
  2. ORD subset of L; |ORD| uncountable; |L| countable --?
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: November 15th 2010, 05:45 AM
  3. Replies: 1
    Last Post: February 9th 2010, 01:51 PM
  4. Countable Subset
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: November 10th 2009, 09:32 PM
  5. Replies: 11
    Last Post: October 11th 2008, 06:49 PM

Search Tags


/mathhelpforum @mathhelpforum