Results 1 to 11 of 11

Math Help - Countability Question

  1. #1
    Member
    Joined
    Sep 2008
    Posts
    95

    Countability Question

    Prove the following assumption:

    If C is a countable set and f: A->C is an injection, then A is countable.

    I'm stuck on how to prove this, as I originally learnt it as the very definition of a countable set. Actually, I think the definition of countable is that a set has the same cardinality as a subset of the natural numbers.

    How is this for a proof? I feel that it is just stating the obvious and not formal enough.

    Assume A is uncountable. From the definition of an injection, for all a∈A there exists c∈C such that f(a) = c. But C is countable so there exists a mapped to no c, a contradiction. Hence A is countable.

    Thanks in advance.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,617
    Thanks
    1582
    Awards
    1
    Quote Originally Posted by StaryNight View Post
    Prove the following assumption:
    If C is a countable set and f: A->C is an injection, then A is countable.
    Do you know this Schroeder-BernsteinTheorem?

    And another webpage.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Sep 2008
    Posts
    95
    Quote Originally Posted by Plato View Post
    Having just read the theorem, it states that if there is an injection A to B and an injection B to A, then there is a bijection between A and B and hence they have the same cardinality. I know there is an injection A to C in the question, so I must now show that there is an injection from C to A? Is this right?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,617
    Thanks
    1582
    Awards
    1
    Quote Originally Posted by StaryNight View Post
    Having just read the theorem, it states that if there is an injection A to B and an injection B to A, then there is a bijection between A and B and hence they have the same cardinality. I know there is an injection A to C in the question, so I must now show that there is an injection from C to A? Is this right?
    That is an easy task. You almost did that in the OP.
    Each c in C has at most one pre-image in A.
    There is also a well known theorem: If there is an injection from A to B then there is a surjection from B to A.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Sep 2008
    Posts
    95
    Quote Originally Posted by Plato View Post
    That is an easy task. You almost did that in the OP.
    Each c in C has at most one pre-image in A.
    There is also a well known theorem: If there is an injection from A to B then there is a surjection from B to A.
    Ok. So here is my corrected proof:

    Theorem: If C is a countable set and f: A->C is an injection, then A is countable.

    Proof: Assume A is infinite (if it is not infinite it is by definition countable). For all a∈A there exists a unique c such that f(a) = c. Now C is countable, so for all c there exists unique a such that f(a) = c. Hence there is a bijection from A to C and by Bernstein's theorem this implies they have the same cardinality. C is countable and therefore so is A.

    Does this sound right?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,617
    Thanks
    1582
    Awards
    1
    Quote Originally Posted by StaryNight View Post
    Ok. So here is my corrected proof:

    Theorem: If C is a countable set and f: A->C is an injection, then A is countable.
    Proof: Assume A is infinite (if it is not infinite it is by definition countable). For all a∈A there exists a unique c such that f(a) = c. Now C is countable, so for all c there exists unique a such that f(a) = c. Hence there is a bijection from A to C and by Bernstein's theorem this implies they have the same cardinality. C is countable and therefore so is A.
    Maybe we should discuss this question in detail.
    When I first read it, I dismissed it as some authorís effort to construct a question to get at a fundamental property of cardinality.
    These are really matters of definitions.
    If there is an injection from A to B, then the cardinality if A, |A|\le |B|.
    Then if there is a surjection from B to A, then |B|\ge |A|.
    In terms of this particular question, any subset of a countable set is countable.

    It just seems to me that this question almost answers itself.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Sep 2008
    Posts
    95
    Quote Originally Posted by Plato View Post
    Maybe we should discuss this question in detail.
    When I first read it, I dismissed it as some authorís effort to construct a question to get at a fundamental property of cardinality.
    These are really matters of definitions.
    If there is an injection from A to B, then the cardinality if A, |A|\le |B|.
    Then if there is a surjection from B to A, then |B|\ge |A|.
    In terms of this particular question, any subset of a countable set is countable.

    It just seems to me that this question almost answers itself.
    I was also confused about what the question wanted. This is the exact question: http://www.cl.cam.ac.uk/teaching/exa.../y2003p1q8.pdf. It's part c)i)
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,617
    Thanks
    1582
    Awards
    1
    Quote Originally Posted by StaryNight View Post
    I was also confused about what the question wanted. This is the exact question: http://www.cl.cam.ac.uk/teaching/exa.../y2003p1q8.pdf. It's part c)i)
    There is nothing confusing about the question in that link!
    Had you posted it to begin with, time would have been saved.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Sep 2008
    Posts
    95
    Quote Originally Posted by Plato View Post
    There is nothing confusing about the question in that link!
    Had you posted it to begin with, time would have been saved.
    Apologies, but how do you think one should answer the question?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774
    First, some remarks about suggested proofs.

    Quote Originally Posted by StaryNight View Post
    Assume A is uncountable. From the definition of an injection, for all a∈A there exists c∈C such that f(a) = c. This is true because f is a function from A to C, not necessarily an injection. But C is countable so there exists a mapped to no c, a contradiction. Hence A is countable.
    The fact that there exists an a that is mapped to no c is not sufficiently justified.

    Quote Originally Posted by StaryNight View Post
    Theorem: If C is a countable set and f: A->C is an injection, then A is countable.

    Proof: Assume A is infinite (if it is not infinite it is by definition countable). For all a∈A there exists a unique c such that f(a) = c. Now C is countable, so for all c there exists unique a such that f(a) = c. Hence there is a bijection from A to C and by Bernstein's theorem this implies they have the same cardinality. C is countable and therefore so is A.
    From the fact that C is countable it does not follow that for all c there exists unique a such that f(a) = c. If f is not a surjection, this is not the case. But if this is true, then f is a bijection and there is no need to invoke the Bernstein's theorem, which says that there is some bijection.

    In fact, I am not sure how to use Schroeder-Bernstein theorem for this problem.

    Quote Originally Posted by StaryNight View Post
    I think the definition of countable is that a set has the same cardinality as a subset of the natural numbers.
    If this is the definition, let B be the image of f. By definition, f : A -> B is a surjection and by assumption it is an injection. Therefore, f : A -> B is a bijection. Let g : C -> D where D ⊆ ℕ be a bijection, which exists since C is countable, and let g' be the restriction of g to B. Then g' is a bijection from B to some D' ⊆ D ⊆ ℕ. All in all, g' ∘ f is a bijection from A to D' ⊆ ℕ.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Quote Originally Posted by StaryNight View Post
    I think the definition of countable is that a set has the same cardinality as a subset of the natural numbers.
    More simply put: A set is countable iff it is 1-1 with some subset of the set of natural numbers.

    We have that C is 1-1 with some subset S of the natural numbers. So let g be a 1-1 function from C onto S. So fog (the composition of functions f and g) is a 1-1 function from A onto some subset T of S. And since T is a subset of S is a subset of the set of natural numbers, we have that T is a subset of the set of natural numbers. So A is 1-1 with a subset of the set of natural numbers.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. countability of a set
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: January 6th 2011, 03:18 AM
  2. Countability
    Posted in the Differential Geometry Forum
    Replies: 8
    Last Post: February 15th 2010, 08:36 PM
  3. Countability
    Posted in the Advanced Math Topics Forum
    Replies: 1
    Last Post: November 28th 2008, 10:49 AM
  4. Another countability question
    Posted in the Advanced Math Topics Forum
    Replies: 12
    Last Post: November 17th 2008, 11:08 PM
  5. Countability
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 12th 2008, 06:26 AM

Search Tags


/mathhelpforum @mathhelpforum