Results 1 to 15 of 15

Math Help - Countable set

  1. #1
    Junior Member
    Joined
    Aug 2006
    Posts
    29

    Countable set

    hello.

    I cant seem to prove the following:

     A,B are two different sets such that  A \subset B
    prove that if there exists an injective function  f:A\to B .
    then there exists a countable infinite set  C \subset A
    (C and A can overlap)

    can someone give me some hints?
    thanks.
    Last edited by parallel; November 10th 2006 at 01:35 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,962
    Thanks
    349
    Awards
    1
    Quote Originally Posted by parallel View Post
    hello.

    I cant seem to prove the following:

     A,B are two different sets such that  A \subset B
    prove that if there exists an injective function  f:A\to B .
    then there exists a countable infinite set  C \subset A
    (C and A can overlap)

    can someone give me some hints?
    thanks.
    There's something wrong here. First of all there is nothing in your statement to force A to be at least countably infinite, which is a requirement for C to be countably infinite.

    For a counter-example let A = {1, 2, 3} and B = {1, 2, 3, 4, 5, 6, 7}. Define an injection f: A \to B: a \mapsto a. Then A \subset B and f is an injection, but there exists no set C \subset A that is countably infinite.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Aug 2006
    Posts
    29
    I'm sorry,I typed it incorrectly

    should be:

    prove that if there exists an injective function  f:B\to A .
    then there exists a countable infinite set  C \subset A
    (C and A can overlap).

    thanks
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by parallel View Post
    I'm sorry,I typed it incorrectly

    should be:

    prove that if there exists an injective function  f:B\to A .
    then there exists a countable infinite set  C \subset A
    (C and A can overlap).

    thanks
    Which is again not true if both these sets are finite.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Aug 2006
    Posts
    29
    o.k so I think we can assume they are infinite(I think it's obvious),although I dont even have a clew,how to even start proving this.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,709
    Thanks
    1639
    Awards
    1
    If we were given that B is infinite then the statement is true.
    We can prove that any infinite set has a countablely infinite subset call it <br />
D \subseteq B.
    The subset of A you want is \overrightarrow f (D), that is the image of D under f.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    If B is infinite this implies that A is also infinite and at least as large as B because of the injective map. Now, the property of the integers say there are contained up to cardinality in any infinite set, thus, there exist an injection
    i:\mathbb{Z}\to C
    Then the image of the function,
    i[\mathbb{Z}]\subseteq C
    (I hope that is what you mean by overlap).
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Aug 2006
    Posts
    29
    I dont understand it.

    I know that inorder to prove a set is countable,I need to show that there exists an injective function from this set to N(positive integers)

    can you explain your proof again,please.

    thanks
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by parallel View Post
    I dont understand it.

    I know that inorder to prove a set is countable,I need to show that there exists an injective function from this set to N(positive integers)

    can you explain your proof again,please.

    thanks
    I assume that you are told B is an infinite set.


    1) A is an infinite set also because the injection from f:B\to A implies that |B|\leq |A| in cardinality. So it must be infinite becuase it is larger than another infinite set (it cannot be finite because any infinite set is larger than any finite set).

    2)Therefore, there exists an injection map i: \mathbb{Z}\to A. Because |\mathbb{Z}| is the smallest possible infinite set which implies its size is contained in any infinite set. Thus, we state that in terms of an injection (since injection shows that one set is less than another in cardinality).

    3)The image of the injection i [ \mathbb{Z}] (image of a function, you should know what that is) is an infinite set that is the size of the integers and is contained in A. Thus, i[\mathbb{Z}]\subset A which proves what you were asking.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,709
    Thanks
    1639
    Awards
    1
    Quote Originally Posted by ThePerfectHacker View Post
    1) A is an infinite set also because the injection from.
    While that is perfectually true, I think that is the point of this problem.
    In other words, I think that is what the student is asked to prove.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Junior Member
    Joined
    Aug 2006
    Posts
    29
    Thank you very much Plato.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by Plato View Post
    While that is perfectually true, I think that is the point of this problem.
    In other words, I think that is what the student is asked to prove.
    I can prove that! If that is what he wants.

    I shall show there cannot exist a surjection,
    s: F\to I
    where F is finite and I is infinite.

    Assume there is one.
    Then since I is infinite \exists I' \subset I, |I'|=|I| (definition of infinity).

    Then, the inverse image,
    s^{-1}[I'] is a proper subset of F (because that set was proper in the infinite set, the inverse image preserve this). But since |I|=|I'| we have |s^{-1}[I']|=|F|. Thus, there exists a proper subset of a finite set having the same cardinality which is impossible by the definition of what finiteness is.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,709
    Thanks
    1639
    Awards
    1
    This is another case where the uniformity of mathematical definitions fails.
    In the above, the definition of ‘infinite set’ was used.
    Well which definition. This makes hard to help with knowing the text being followed.

    There are at least three or maybe four popular definitions:
    A set is infinite if it is not finite. A finite set is equipotent to a natural number.
    A set is infinite if it is equipotent to a proper subset of itself (called Dedekind infinite).
    A set is infinite if it contains a copy of the natural numbers.

    I suspect that the purpose of the question was to show that “If an infinite set is mapped injectively of another set then the final set must also be infinite.” From the wording it is difficult to know what definition is being used. In any case my first response works.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by Plato View Post
    This is another case where the uniformity of mathematical definitions fails.
    In the above, the definition of ‘infinite set’ was used.
    Well which definition. This makes hard to help with knowing the text being followed.

    There are at least three or maybe four popular definitions:
    A set is infinite if it is not finite. A finite set is equipotent to a natural number.
    A set is infinite if it is equipotent to a proper subset of itself (called Dedekind infinite).
    A set is infinite if it contains a copy of the natural numbers.

    I suspect that the purpose of the question was to show that “If an infinite set is mapped injectively of another set then the final set must also be infinite.” From the wording it is difficult to know what definition is being used. In any case my first response works.
    But all of these definitions are equivalent!
    Makes no difference what to use.
    (I am only familar with Dedekind infinite).
    Follow Math Help Forum on Facebook and Google+

  15. #15
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,709
    Thanks
    1639
    Awards
    1
    Quote Originally Posted by ThePerfectHacker View Post
    But all of these definitions are equivalent!
    Makes no difference what to use.
    But the definition in use changes the approach to the proof.
    That was my point.
    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. Replies: 2
    Last Post: November 11th 2010, 04:56 AM
  3. [SOLVED] Countable union of closed sets/countable interesection of open sets
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: October 8th 2010, 01:59 PM
  4. Replies: 1
    Last Post: February 9th 2010, 01:51 PM
  5. Replies: 11
    Last Post: October 11th 2008, 06:49 PM

Search Tags


/mathhelpforum @mathhelpforum