Results 1 to 8 of 8

Math Help - Very simple Binary Relation definition needed

  1. #1
    Junior Member
    Joined
    Mar 2009
    Posts
    32

    Very simple Binary Relation definition needed

    Everywhere I look, binary relation is defined as the set of ordered pairs containing elements from 2 sets.

    But then I get a a problem that says

    How many binary relations are there on the set (1, 2, 3}?


    This doesn't make sense to me. How can you have a relation with only 1 set?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Aug 2009
    Posts
    125
    Phrase "R is a binary relation on a set A" is commonly used to mean that R is a subset of the cartesian product A x A. That is, R is a collection of ordered pairs of elements of A.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1
    Do you understand the following calculations?
    \begin{gathered}<br />
  X = \left\{ {1,2,3} \right\}\; \Rightarrow \;\left| X \right| = 3 \hfill \\<br />
  X \times X = \left\{ {\left( {1,1} \right),\left( {1,2} \right),\left( {1,3} \right),\left( {2,2} \right),\left( {2,1} \right),\left( {2,3} \right),\left( {3,3} \right),\left( {3,1} \right),\left( {3,2} \right)} \right\} \hfill \\<br />
  \left| {X \times X} \right| = 9\; \Rightarrow \;\left| {P(X \times X)} \right| = 2^9  \hfill \\ <br />
\end{gathered}

    Because a binary relation on X is any subset of pairs in X\times X there are 2^9 possible binary relations on X.
    (Some authors say 2^9-1 because of not liking an empty relation.)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Mar 2009
    Posts
    32
    Yes, that makes sense to me. I had actually tried 9 as an answer, and I was wrong.




    .... any idea why this was wrong?
    Last edited by JTG2003; August 28th 2009 at 04:09 PM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,313
    Thanks
    1291
    I believe Plato has already answered that! Could you tell us why you thought it was 9?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Mar 2009
    Posts
    32
    I just took the cartesian product and found that there were 9 results. It was more of a guess than anything else.

    It took a few times reading to figure this out a little more.

    May I present you with another example, and maybe you could help me figure out what I'm doing wrong?

    I am presented with the set {1,2}
    So, the product is {(1,1), (1,2), (2,1), (2,2)}
    and there would be 16 relations?

    I am then asked a series of questions such as "How many relations are reflexive? Symmetrical?"

    I know I need to set up a matrix showing all the possible relations, but... aren't they all possible? Wouldn't the matrix be all "1"s?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member Matt Westwood's Avatar
    Joined
    Jul 2008
    From
    Reading, UK
    Posts
    737
    Thanks
    1
    Think about what the definition is.

    A relation on a set is a subset of the Cartesian product.

    So you have to think about all the possible subsets of:
    \{(1, 1), (1, 2), (2, 1), (2, 2)\}

    A reflexive relation is one which includes (1,1) and (2,2). (By looking hard at the definition of "reflexive", ask yourself: why?)

    A symmetric relation is one where, if (a, b) is in the relation, then (b, a) is also in that relation.

    So as there's only 16 possible relations, it's feasible to list them all out and examine them one by one for whether they have all these properties.

    For example, \{(1, 1), (1, 2), (2, 2)\} is reflexive, because it has (1, 1) and (2, 2), but not symmetric - because it has (1, 2) but not (2, 1).

    And so on. As I say, list them all out and look at them - it's an instructional exercise in its own right.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1
    Quote Originally Posted by JTG2003 View Post
    I am then asked a series of questions such as "How many relations are reflexive? Symmetrical?"
    Suppose that |X|=n then there are 2^n binary relations on X.

    The are 2^{n^2-n} reflexive relations on X

    The are 2^{\frac{n(n+1)}{2}} symmetric relations on X
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Basic definition of binary operations
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: December 10th 2011, 02:54 PM
  2. show a binary relation is well-defined
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 23rd 2010, 02:08 PM
  3. A question about definition of "Binary Relation"
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 16th 2009, 02:56 AM
  4. Binary relation
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: May 3rd 2008, 11:58 AM
  5. binary relation
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: March 24th 2008, 10:34 AM

Search Tags


/mathhelpforum @mathhelpforum