Results 1 to 6 of 6

Math Help - Cardinality

  1. #1
    Newbie
    Joined
    Mar 2010
    Posts
    11

    Cardinality

    Let S,T, and W be sets.

    a. Prove: If  S \preceq T and  T \prec W , then  S \prec W .

    b. Prove: If  S \prec T and  T \preceq W , then  S \prec W .

    is this like the transitive property??? I'm so confused.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by txsoutherngirl84 View Post
    Let S,T, and W be sets.

    a. Prove: If  S \preceq T and  T \prec W , then  S \prec W .

    b. Prove: If  S \prec T and  T \preceq W , then  S \prec W .

    is this like the transitive property??? I'm so confused.
    According to Wikipedia's table of mathematical symbols, \prec refers to Karp reduction, which is part of computational complexity theory. Is this what we're talking about?

    Edit: Oh, I guess since S, T, and W are sets we must be talking about something else.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Banned
    Joined
    Sep 2009
    Posts
    502
    Quote Originally Posted by undefined View Post
    According to Wikipedia's table of mathematical symbols, \prec refers to Karp reduction, which is part of computational complexity theory. Is this what we're talking about?

    Edit: Oh, I guess since S, T, and W are sets we must be talking about something else.
    I saw in an old book, the notation being used for cardinality related topics.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,962
    Thanks
    1784
    Awards
    1
    The is almost standard notation is many areas of mathematics.
    This is lesson that a posting should contain explanations of terminology.
    It is also a warning not to rely heavily upon Wikipedia. There are mistakes there.
    Here is a guess as to the uses of those symbols.
    On a collection of subsets  S \preceq T means that there is a injection S\to T.
    Whereas,  S \prec T means that there is a non-bijective injection S\to T.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Quote Originally Posted by Plato View Post
     S \prec T means that there is a non-bijective injection S\to T.
    Ordinarily, it means "there is an injection from S into T but no bijection between S and T" or "S is strictly dominated by T". That is different from "there exists an injection from S into T that is not a bijection" or, as you've put it, "There is a non-bijective injection from S to T". For example, there is an injection from the set of natural numbers into itself that is not a bijection (there is a non-bijective injection from the set of natural numbers into itself) but the set of natural numbers does not strictly dominate the set of natural numbers.

    In other words, to prove that T strictly dominates S, it is not enough to show that there exists an injection from S into T that is not a bijection (since it might be the case that there is an injection from S into T that is not a bijection while still there does exist a bijection from S to T), but rather it does suffice to show that there is an injection from S into T while also there does not exist a bijection from S to T.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    To address the original question, hints:

    a. For existence of injection from S into W, consider composition of functions. For non-existence of a bijection from S into W, argue by contradiction, and apply a famous theorem you probably just covered in your course.

    b. Same as for a., mutatis mutandis.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Cardinality of R, [0,1], R^2, [0,1] x [0,1]
    Posted in the Differential Geometry Forum
    Replies: 11
    Last Post: March 18th 2010, 03:20 PM
  2. Cardinality
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 31st 2009, 04:56 PM
  3. Cardinality
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: February 11th 2009, 06:36 PM
  4. Cardinality
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: February 8th 2009, 03:23 PM
  5. Cardinality of a Set
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: January 27th 2009, 04:33 PM

Search Tags


/mathhelpforum @mathhelpforum