Results 1 to 3 of 3

Thread: binary relations , no of symmetric, reflexive relations

  1. #1
    Newbie
    Joined
    Aug 2017
    From
    usa
    Posts
    1

    binary relations , no of symmetric, reflexive relations

    Let X = {a; b; c; d; e}. Let us call a binary relation R on X special if it satisfies all of
    the following conditions: (i) R is reflexive, (ii) R is symmetric and (iii) R contains the pair (a; b). Find the number of special binary relations on X. You need not simplify your answer.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    2,971
    Thanks
    1141

    Re: binary relations , no of symmetric, reflexive relations

    To satisfy (iii), R must contain (a,b). To satisfy (ii), R must contain (b,a). To satisfy (i), R must contain (a,a) and (b,b). That is the base. Now, let's consider some other pairs:

    We can add (c,c) without needing to add any additional pairs. We can add (d,d) without adding any additional pairs. We can add (e,e) without adding any additional pairs. So, for each of those pairs, R either has it or it does not. For any pair of the form (x,y) where $x \neq y$, we also need to add the pair (y,x), (x,x), and (y,y). So, let's count pairs that we can add. We will only consider elements of the pair in alphabetical order. So, we will consider (a,c), but not (c,a), because if we add (a,c), we also add (c,a). With (c,c), we can add (a,c) or (b,c) without needing to add (d,d) or (e,e). With (d,d), we can add (a,d) or (b,d) without needing to add (c,c) or (e,e). If we add (c,c) and (d,d), we can add (c,d) without needing to add (e,e). So, for any two pairs among (c,c), (d,d), or (e,e), we can add none of them, which gives 1 possibility. We can add one of them and the associated (a,*), (b,*), which gives $3\cdot 2^2$ possibilities. We can add two of them, which gives $3\cdot 2^5$ possibilities. We can add all three of them, which gives us the possibility of adding (a,c), (a,d), (a,e), (b,c), (b,d), (b,e), (c,d), (c,e), or (d,e), which is $2^9$ possibilities.

    So, all told, there are $1+3\cdot 2^2 + 3\cdot 2^5+2^9$ different possible special binary relations on X.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,459
    Thanks
    2728
    Awards
    1

    Re: binary relations , no of symmetric, reflexive relations

    Quote Originally Posted by ritz View Post
    Let X = {a; b; c; d; e}. Let us call a binary relation R on X special if it satisfies all of
    the following conditions: (i) R is reflexive, (ii) R is symmetric and (iii) R contains the pair (a; b). Find the number of special binary relations on X. You need not simplify your answer.
    Suppose that $\mathscr{T}=\{(a,a),(b,b),(c,c),(d,d),(e,e),(a,b) ,(b,a)\}$ is the minimal relation satisfying the basic requirements for such a relation on $\mathscr{X}$.

    The set $\mathscr{S}=\{(a,c),(a,d),(a,e),(b,c),(b,d),(b,e) ,(c,d),(c,e),(d,e)\}$ is such that $\mathscr{V}=\mathscr{S}\cup\mathscr{S}^{-1}$ is the set of all pairs not in $\mathscr{T}$

    If $\mathscr{Y}\subseteq \mathscr{S}$ then $\mathscr{S'}=\mathscr{T}\cup\mathscr{Y}\cup \mathscr{Y}^{-1}$ is a unique required relation on $\mathscr{X}$.

    So there are $2^9$ such relations.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 13
    Last Post: Mar 21st 2016, 08:51 AM
  2. Replies: 2
    Last Post: Sep 13th 2015, 10:17 PM
  3. Replies: 6
    Last Post: Dec 17th 2012, 01:49 PM
  4. Relations theory, reflexive, transitive, symmetric
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Dec 1st 2012, 05:49 AM
  5. Replies: 1
    Last Post: Sep 19th 2011, 02:09 PM

/mathhelpforum @mathhelpforum