1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Combinatorics: Starting Posets/Relations

  1. Jun 1, 2009 #1
    1. The problem statement, all variables and given/known data


    We say that a relation [tex]R [/tex] on a set X is symmetric if [tex](x, y) \in R [/tex] implies [tex] (y, x) \in R [/tex] for all [tex] x, y \in X.[/tex] If [tex]X = \{a, b, c, d, e, f \}[/tex], how many symmetric relations are there on [tex]X[/tex]? How many of these are reflexive?


    2. Relevant equations



    3. The attempt at a solution

    At this point, I understand that there are [tex] 2^6 [/tex] subsets of X. I don't understand how to count the number of relations that are symmetric though. Also, I would have thought that since there are [tex] 2^6 [/tex] subsets, that there would be [tex] 2^6 [/tex] reflexive relations, but I know the answer to that question to be [tex] 2^{15} [/tex]. All help is appreciated!
     
  2. jcsd
  3. Jun 1, 2009 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Try with a smaller example, like 3 elements {a,b,c} to begin with - or just try writing out a few symmetric relations and trying to see what needs to be true about them.

    You notion of 2^6 implies that a relation (of some type) is purely defined by being a subset - if that were true then it wouldn't be a very interesting property.
     
  4. Jun 1, 2009 #3
    You mean to say that there are 2^15 relations on X that are both reflexive and symmetric (there are 2^30 reflexive relations). If you want to think about relations as sets, you should be looking at sets of ordered pairs whose entries come from X.
     
  5. Jun 2, 2009 #4

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    A relation on X is NOT a subset of X. It is a subset of the Cartesian product of X with iteself.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook