Results 1 to 5 of 5

Math Help - Sets

  1. #1
    Member
    Joined
    Sep 2006
    Posts
    221

    Sets

    Given A is a set with 6 elements,

    a.) Determine the number of relations on A there are

    b.) Determine the number of symmetric relations on A there are

    c.) Determine the number of reflexive relations on A there are
    Follow Math Help Forum on Facebook and Google+

  2. #2
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by Ideasman View Post
    Given A is a set with 6 elements,

    a.) Determine the number of relations on A there are
    well, we have 6 elements in A. How many choices are there to map the first element to? After that, how many choices are there to map the second element to...continue this procedure. The product of all the choices is what you seek.

    b.) Determine the number of symmetric relations on A there are
    are you aware of what symmetric means?

    here is a symmetric mapping. try to untangle it's secrets:

    let the elements of A be a,b,c,d,e,f, the mapping defined by:

    a --> b

    b --> a

    c --> d

    d --> c

    e --> f

    f --> e

    is symmetric

    c.) Determine the number of reflexive relations on A there are
    this is only the identity, right?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Sep 2006
    Posts
    221
    Quote Originally Posted by Jhevon View Post
    well, we have 6 elements in A. How many choices are there to map the first element to? After that, how many choices are there to map the second element to...continue this procedure. The product of all the choices is what you seek.

    are you aware of what symmetric means?

    here is a symmetric mapping. try to untangle it's secrets:

    let the elements of A be a,b,c,d,e,f, the mapping defined by:

    a --> b

    b --> a

    c --> d

    d --> c

    e --> f

    f --> e

    is symmetric

    this is only the identity, right?
    For the first one,

    If I have 6 elements, say a b c d e f, then wouldn't it be something like:

    a -> b, c, d, e, f
    b -> a, c, d, e, f
    c -> a, b, d, e, f
    d -> a, b, c, e, f
    e -> a, b, c, d, f
    f -> a, b, c, d, e

    So you're saying that there'd be 5^5 relations on A?

    For b, I don't quite understand how there's only 6 symmetrical mappings.

    Why can't a -> f and then f -> a, etc.

    And for c, what do you mean by just the identity? Itself? So a -> a, b -> b, etc. (so an onto mapping?)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by Ideasman View Post
    For the first one,

    If I have 6 elements, say a b c d e f, then wouldn't it be something like:

    a -> b, c, d, e, f
    b -> a, c, d, e, f
    c -> a, b, d, e, f
    d -> a, b, c, e, f
    e -> a, b, c, d, f
    f -> a, b, c, d, e

    So you're saying that there'd be 5^5 relations on A?
    no.

    there are 6 elements in A, each of which have 6 choices of what to map to. Let A and B be sets, the number of mappings from the set A to the set B is |B|^{|A|}

    (it is possible for an element to map to itself)



    For b, I don't quite understand how there's only 6 symmetrical mappings.

    Why can't a -> f and then f -> a, etc.
    i posted a SINGLE mapping. please look up what a mapping is, for you to think that was 6 mappings is really bad. I merely gave you ONE of the possible mappings so that you could see some sort of pattern. For example, note that when we made the choice a --> b, we automatically made the choice b --> a, there was no choice for what b could map to, it had to be a for the mapping to be symmetric. so that means, when we get to the element c, it only has 4 choices of what to map to, since a and b are taken. continue with this logic and generalize to complete the problem.

    And for c, what do you mean by just the identity? Itself? So a -> a, b -> b, etc. (so an onto mapping?)
    reflexive means, every element maps to itself. can you think of any other map besides the identity that does this?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,657
    Thanks
    1607
    Awards
    1
    Quote Originally Posted by Ideasman View Post
    Given A is a set with 6 elements,
    a.) Determine the number of relations on A there are
    b.) Determine the number of symmetric relations on A there are
    c.) Determine the number of reflexive relations on A there are
    Recall that a relation no a set A is simply a subset of A \times A. Because \left| {A \times A} \right| = 36 there are 2^{36} possible relations on A (CAREFUL, some mathematicians will not allow an empty relation so you may have to subtract one from that.)

    To answer part (b), think of a table that represents A \times A.
    There are 21 pairs ‘on or below the diagonal’, call that set L for the ‘lower triangle’. Now if S \subseteq L then S \cup S^{ - 1} is a symmetric relation on A (again be careful of an empty set). So that gives 2^{21} possible symmetric relations.

    Any reflexive relation on A must contain the diagonal \Delta _A .
    Then if R \subseteq (A \times A)\backslash \Delta _A then R \cup \Delta _A is a reflexive relation on A or 2^{30}.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Open sets and sets of interior points
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: August 9th 2011, 03:10 AM
  2. Metric spaces, open sets, and closed sets
    Posted in the Differential Geometry Forum
    Replies: 4
    Last Post: March 16th 2011, 05:17 PM
  3. Replies: 9
    Last Post: November 6th 2010, 12:47 PM
  4. Approximation of borel sets from the top with closed sets.
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: February 18th 2010, 08:51 AM
  5. how to show these sets are 95% confidence sets
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: February 11th 2009, 09:08 PM

Search Tags


/mathhelpforum @mathhelpforum