Results 1 to 4 of 4

Math Help - How to count binary relations?

  1. #1
    Newbie
    Joined
    May 2008
    Posts
    11

    How to count binary relations?

    Hello.

    If I for example have a set A=\{1,2,3\}, I know that a binary relation on the set A is any subset of A \times A=\{(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3)\}. (I hope I'm correct so far!) The problem however is how many different binary relations there is?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,395
    Thanks
    1480
    Awards
    1
    Quote Originally Posted by kjey View Post
    The problem however is how many different binary relations there is?
    If A is a set and |A|=n is the number of elements in A then there are 2^{n^2} binary relations on A.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2008
    Posts
    11
    But what if I have to find out how many of the relations that are for example reflexive? Is there an easy way to solve such problems?

    Thanks for the answer by the way
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,395
    Thanks
    1480
    Awards
    1
    Quote Originally Posted by kjey View Post
    But what if I have to find out how many of the relations that are for example reflexive? Is there an easy way to solve such problems?
    Yes there is. Any reflexive relation on A contains the diagonal: \Delta_A=\{(x,x):x\in A\}~\&~|\Delta_A|=|A|.

    Any reflexive relation corresponds to a relation that contains no 'diagonal' elements. So we get: 2^{|A|^2-|A|}
    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. binary relations help please :)
    Posted in the Algebra Forum
    Replies: 2
    Last Post: February 13th 2010, 08:08 AM
  3. Binary Relations
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 8th 2009, 04:20 PM
  4. Binary Relations
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: April 13th 2008, 10:41 AM
  5. binary relations
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 15th 2007, 12:56 PM

Search Tags


/mathhelpforum @mathhelpforum