Results 1 to 10 of 10

Math Help - Finite>Infinite

  1. #1
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9

    Finite>Infinite

    Proof that if S is any finite set and T is any infinite set then |S|<|T|. In mathematical words prove that there exists a surjection \phi:S\to T which is not one-to-one.

    What I am trying to get to is perhaps there exists a set that cannot be placed with ono-to-one correspondence with a proper subset and is greater then an infinite set! I doubt that but I am trying to connect this to my other post on "the set of all finite sets".
    Last edited by ThePerfectHacker; February 18th 2006 at 03:46 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,663
    Thanks
    298
    Awards
    1
    Quote Originally Posted by ThePerfectHacker
    Proof that if S is any finite set and T is any infinite set then |S|<|T|. In mathematical words prove that there exists a surjection \phi:S\to T which is not one-to-one.

    What I am trying to get to is perhaps there exists a set that cannot be placed with ono-to-one correspondence with a proper subset and is greater then an infinite set! I doubt that but I am trying to connect this to my other post on "the set of all finite sets".
    You can't. In order to have a surjection between the sets S and T, the cardinality of T must be less than or equal to the cardinality of S. Otherwise you wind up having at least one point of S being defined to have more than one value in T, which means your "function" violates one of the definitions of a function: No function can have multiple values on an element of the domain.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by topsquark
    You can't. In order to have a surjection between the sets S and T, the cardinality of T must be less than or equal to the cardinality of S. Otherwise you wind up having at least one point of S being defined to have more than one value in T, which means your "function" violates one of the definitions of a function: No function can have multiple values on an element of the domain.

    -Dan
    Can you proof it? I understand what you are saying but you are using the intuitive meaning of finity and infinity.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by ThePerfectHacker
    Can you proof it? I understand what you are saying but you are using the intuitive meaning of finity and infinity.
    I didn't see any reference to finite or infinite in topsquarks post, only to
    equality or inequality of cardinality. This uses an implied reference to the
    usual definition of infinite as applied to sets. This fully subsumes the normal
    dichotomy of finite/infinite.

    RonL
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    If a set S has property:
    |S|\not =|S'|,\forall S'\subset S.
    And another set T has property:
    |T|=|T'|,\exists T'\subset T.

    Prove that,
    |S|<|T|.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by ThePerfectHacker
    If a set S has property:
    |S|\not =|S'|,\forall S'\subset S.
    And another set T has property:
    |T|=|T'|,\exists T'\subset T.

    Prove that,
    |S|<|T|.
    I think you want to say:

    If a set S has property:
    <br />
\forall S'\subset S,\ |S|\not =|S'|<br />
.

    And another set T has property:
    <br />
\exists T'\subset T,\ |T|=|T'|<br />
.

    Prove that,
    |S|<|T|

    RonL
    Last edited by CaptainBlack; February 19th 2006 at 10:31 AM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by CaptainBlack
    I think you want to say:

    If a set S has property:
    <br />
\forall S'\subset S,\ |S|\not =|S'|<br />
.

    And another set T has property:
    <br />
\exists T'\subset T,\ |T|=|T'|<br />
.

    Prove that,
    |S|<|T|

    RonL
    To do this I think we will need more machinery than I suspect Mr Hacker
    has available, so it would be advantageous to show:

    If S is a set such that

    <br />
\forall S'\subset S,\ |S|\not =|S'|<br />
.

    then \forall P\subset S


    <br />
\forall P'\subset P,\ |P|\not =|P'|<br />
.

    RonL
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Perhaps, we can do this, (please check for errors).
    If \phi :S\to T is bijective.
    Then \exists T'\subset T\mbox { with }|T'|=|T|
    Thus,
    \phi^{-1}[T']\subset S with,
    |\phi^{-1}[T']|=|S|
    but that is impossible, thus,
    |S|\not =|T|.
    Now it remains to complete that,
    |S|<|T| by assuming |S|>|T|
    and then using trichtonomy.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by ThePerfectHacker
    Perhaps, we can do this, (please check for errors).
    If \phi :S\to T is bijective.
    We say |S| \ge |T| if there exists a one to one map from S into T

    We say |S|=|T| iff |S| \ge |T| and |T| \ge |S|.

    You will now need to prove the existance of the bijection.

    RonL
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by CaptainBlack
    We say |S| \ge |T| if there exists a one to one map from S into T

    We say |S|=|T| iff |S| \ge |T| and |T| \ge |S|.

    You will now need to prove the existance of the bijection.

    RonL
    No, I do not. I should have said this in the proof but I forgot, that I assumed that they had the same cardinality thus by definition there exists a bijective map, which leads to a contradiction.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Finite and infinite sets
    Posted in the Discrete Math Forum
    Replies: 11
    Last Post: August 6th 2011, 03:53 PM
  2. finite or infinite?
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: September 3rd 2010, 09:39 PM
  3. Finite and Infinite order
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: April 6th 2010, 07:51 AM
  4. finite and infinite sets...denumerable
    Posted in the Differential Geometry Forum
    Replies: 15
    Last Post: November 22nd 2009, 05:38 PM
  5. infinite/finite limits
    Posted in the Calculus Forum
    Replies: 9
    Last Post: March 10th 2009, 10:36 AM

Search Tags


/mathhelpforum @mathhelpforum