Results 1 to 10 of 10

Math Help - Determining number of relations on a set

  1. #1
    Member
    Joined
    Dec 2010
    Posts
    107

    Determining number of relations on a set

    Let A = {1,2,...,n}.
    (a) How many relations are there on the set A?
    (b) How many reflexive relations are there on the set A?
    (c) How many symmetric relations are there on the set A?
    (d) How many relations are there on the set A which are both reflexive and symmetric?

    I think that the answer to (a) is n^2 because it will be ther number of ordered pairs, but this is just a guess.
    If someone could point me in the right direction.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,705
    Thanks
    1637
    Awards
    1
    Quote Originally Posted by worc3247 View Post
    Let A = {1,2,...,n}.
    (a) How many relations are there on the set A?
    (b) How many reflexive relations are there on the set A?
    (c) How many symmetric relations are there on the set A?
    (d) How many relations are there on the set A which are both reflexive and symmetric?
    A relation is any set of ordered pairs, (some say any non-empty set) so the answer to part (a) is 2^{n^2}(\text{ or }2^{n^2}-1) .

    \Delta_A=\{(1,1),(2,2),\cdots,(n,n)\} A relation is reflexive if and only if \Delta_A is a subset of the relation. SO?

    How many pairs are on the diagonal or above it?
    2 to that power answers (c). WHY?
    Now you answer with some reasonable effort on your part.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Dec 2010
    Posts
    107
    O
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Dec 2010
    Posts
    107
    Ok so now I am getting answers of 2^{n^2-n} and 2^{(n^2-n)/2} for (b) and (c) respectively. But what I don't understand is why a relation is reflexive only if \Delta_A is a subset of the relation.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,705
    Thanks
    1637
    Awards
    1
    What it mean to be reflexive?
    Is \Delta_A itself a reflexive relation on A?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Dec 2010
    Posts
    107
    Reflexive is when sRs (R is the relation) \forall s \epsilon S. So yes, \Delta_Awill be an equivalence relation. But then surely the answer to (b) would be 2^n because there are n elements in \Delta_A.
    Sorry about this, I just can't quite understand the concept of the question.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,705
    Thanks
    1637
    Awards
    1
    Quote Originally Posted by worc3247 View Post
    But then surely the answer to (b) would be 2^n because there are n elements in \Delta_A.
    Sorry about this, I just can't quite understand the concept of the question.
    How many subsets of (A\times A)\setminus \Delta_A are there?
    Unite each of those with \Delta_A to get a reflexive relation.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Dec 2010
    Posts
    107
    Quote Originally Posted by Plato View Post
    How many subsets of (A\times A)\setminus \Delta_A are there?
    n^2 - n. So the answer is 2^{n^2-n}?

    So a symmetric relation is when: if sRt, tRs for s,t \epsilon S.
    But how are you suppose to determine what is a symmetric relation without knowing what the relation is?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,705
    Thanks
    1637
    Awards
    1
    Quote Originally Posted by worc3247 View Post
    n^2 - n. So the answer is 2^{n^2-n}? So a symmetric relation is when: if sRt, tRs for s,t \epsilon S.
    But how are you suppose to determine what is a symmetric relation without knowing what the relation is?
    Are you sure that you are ready to do these?
    A relation \mathcal{S} is symmetric if and only if \mathcal{S}=\mathcal{S}^{-1}.
    Any subset of pairs from the diagonal or above is a relation. Unite that subset with its inverse. Then we have a symmetric relation.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Member
    Joined
    Dec 2010
    Posts
    107
    I have to be ready, these are mock questions for mods exams :S
    But thanks a lot, I get it now
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: September 19th 2011, 01:09 PM
  2. Determining if n is a square from number of divisors?
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: August 21st 2009, 07:38 AM
  3. Number of relations?
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: April 28th 2009, 02:04 PM
  4. Number relations
    Posted in the Advanced Math Topics Forum
    Replies: 1
    Last Post: October 31st 2008, 05:46 AM
  5. Number of relations
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: September 16th 2008, 05:52 AM

Search Tags


/mathhelpforum @mathhelpforum