Results 1 to 8 of 8

Math Help - Proof Help please!

  1. #1
    Newbie
    Joined
    Mar 2011
    Posts
    3

    Proof Help please!

    Hey guys,

    I really need some help please!
    I would really appreciate it if anyone can help out:

    Question:
    (i)Decide and state whether any subset of a countable set is itself countable.Explain your answer in your own words.

    Hope someone can help!Thank in advance!

    Panakas
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,824
    Thanks
    1717
    Awards
    1
    Quote Originally Posted by Panakas View Post
    Question:
    (i)Decide and state whether any subset of a countable set is itself countable.Explain your answer in your own words.
    Hello Panakas and welcome to MathHelpForum.
    You should understand that this is not a homework service nor is it a tutorial service. Please either post some of your own work on this problem or explain what you do not understand about the question.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Sep 2009
    Posts
    177
    Thanks
    1
    Some certainly are. Think about the natural numbers. Think about the primes, ect....
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Mar 2011
    Posts
    3
    This is what I wrote:

    [C] (vii)
    A set is countable if it is finite, or it can be placed in 1-1 correspondence with the positive integers. A set is countably infinite if it is countable and infinite, just like the positive integers.
    The non negative integers are countable, as shown by the bijection f(n) = n+1.
    The even numbers are countable, map n to n/2.
    The integers are countable. Map n to 2n for n ≥ 0, and map n to 1-2n for n < 0.
    Any set that can be listed in order, or enumerated, is countable. Thus the prime numbers are countable, and so on.
    Ordered pairs of positive integers are countable. List them this way:
    1/1 2/1 1/2 3/1 2/2 1/3 4/1 3/2 2/3 1/4 5/1 4/2 3/3 2/4 1/5 …
    Since fractions are ordered pairs of integers, the rational numbers are countable.
    The cross product (i.e. ordered pairs) of countable sets is countable. Use this fact again and again to show that the n-tuples of integers are countable. The integer points, or even the rational points in n space are countable.
    All finite ordered tuples of the integers, or any other countable set for that matter, are countable.
    As a corollary, the finite sets of integers are countable, as these are all represented, perhaps many times, by various ordered tuples. The set (1,2,3) appears six times when order is significant. Since the ordered tuples over count the unordered subsets, and the tuples are countable, the finite subsets are also countable.
    Since the tuples are countable, the polynomials are countable. Of course the coefficients can be drawn from any countable set, so the polynomials over the rationals are countable.
    The polynomials over x and y are the polynomials in y, whose coefficients are polynomials in x. The polynomials in x are countable, and since these act as coefficients, the polynomials in x and y are countable. This extends to polynomials in x y z, and so on.

    So is this the answer to my question???
    Thank you guys for your help!
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Sep 2009
    Posts
    177
    Thanks
    1
    The map should be n to 2n
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Sep 2009
    Posts
    177
    Thanks
    1
    What would happen if a subset of a countable set was uncountable??
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Mar 2011
    Posts
    3
    I don't really know...I'm not sure...What I wrote above is correct or is a total mess??
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Apr 2005
    Posts
    16,057
    Thanks
    1690
    What you wrote was a correct exposition of what "countable" means and some countable sets. But it does not at all answer the question!

    Suppose a countable set, A, had an uncountable subset. What would that say about the "one-to-one mapping" of A onto the natural numbers?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 15
    Last Post: June 8th 2011, 11:13 AM
  2. Replies: 5
    Last Post: October 19th 2010, 10:50 AM
  3. Replies: 0
    Last Post: June 29th 2010, 08:48 AM
  4. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 01:20 PM
  5. proof that the proof that .999_ = 1 is not a proof (version)
    Posted in the Advanced Applied Math Forum
    Replies: 4
    Last Post: April 14th 2008, 04:07 PM

Search Tags


/mathhelpforum @mathhelpforum