Facebook Page
Twitter
RSS
+ Reply to Thread
Page 1 of 2 12 LastLast
Results 1 to 10 of 11
  1. MHB Master
    MHB Site Helper
    mathmari's Avatar
    Status
    Offline
    Join Date
    Apr 2013
    Posts
    3,815
    Thanks
    3,029 times
    Thanked
    995 times
    Awards
    MHB Model User Award (2017)  

MHB Chat Room Award (2015)  

MHB Model User Award (2015)  

MHB LaTeX Award (2015)
    #1
    Hey!!

    I am looking at the following:

    There are the terms reflexive, symmetric, antisymmetric and transitive.
    Give for each combination of the properties (if possible) a set $M$ and a relation $R$ on $M$, such that $R$ satisfies these properties.


    What is meant exactly? Every possible combination? So do we have to give a set and a relation that satisfies the below properties?
    • reflexive, symmetric
    • reflexive, antisymmetric
    • reflexive, transitive
    • symmetric, antisymmetric
    • symmetric, transitive
    • antisymmetric, transitive
    • reflexive, symmetric, antisymmetric
    • reflexive, symmetric, transitive
    • reflexive, antisymmetric, transitive
    • symmetric, antisymmetric, transitive
    • reflexive, symmetric, antisymmetric transitive



  2. # ADS
    Circuit advertisement
    Join Date
    Always
    Posts
    Many
     

  3. MHB Master
    MHB Math Helper

    Status
    Offline
    Join Date
    Jan 2012
    Posts
    1,102
    Thanks
    318 times
    Thanked
    1,098 time
    #2
    Well, you have four properties so 4!= 24 possible "combinations" (25 if you include the "empty combination"- that none of those properties are true).

    I think you should give special consideration to two of those properties. What must be true of a set so that it will be both "symmetric" and "anti-symmetric"?

  4. MHB Master
    MHB Site Helper
    mathmari's Avatar
    Status
    Offline
    Join Date
    Apr 2013
    Posts
    3,815
    Thanks
    3,029 times
    Thanked
    995 times
    Awards
    MHB Model User Award (2017)  

MHB Chat Room Award (2015)  

MHB Model User Award (2015)  

MHB LaTeX Award (2015)
    #3 Thread Author
    Quote Originally Posted by HallsofIvy View Post
    Well, you have four properties so 4!= 24 possible "combinations" (25 if you include the "empty combination"- that none of those properties are true).
    Since the order of the properties doesn't matter do we not have $\binom{4}{2}+\binom{4}{3}+\binom{4}{4}=11$ combinations?


    Quote Originally Posted by HallsofIvy View Post
    I think you should give special consideration to two of those properties. What must be true of a set so that it will be both "symmetric" and "anti-symmetric"?
    A relation R is symmetric if it holds $aRb \iff bRa$ for $a,b\in M$.
    A relation R is ant-symmetric if it holds $aRb$ then it doesn't hold that $bRa$ for $a\neq b\in M$.

    So this combination is not possible, right?

  5. MHB Master
    MHB Site Helper
    MHB Math Scholar

    Status
    Offline
    Join Date
    Jan 2012
    Posts
    2,483
    Thanks
    533 times
    Thanked
    4,408 times
    Thank/Post
    1.775
    Awards
    MHB University Math Award (2018)  

MHB Humor Award (2017)  

MHB Discrete Mathematics Award (2017)  

MHB Chat Room Award (2016)  

MHB Humor Award (2016)
    #4
    Quote Originally Posted by HallsofIvy View Post
    Well, you have four properties so 4!= 24 possible "combinations" (25 if you include the "empty combination"- that none of those properties are true).
    I believe there are $2^4=16$ possible combinations of 4 properties.

    Quote Originally Posted by mathmari View Post
    A relation R is symmetric if it holds $aRb \iff bRa$ for $a,b\in M$.
    A relation R is ant-symmetric if it holds $aRb$ then it doesn't hold that $bRa$ for $a\neq b\in M$.

    So this combination is not possible, right?
    It is possible.

  6. MHB Master
    MHB Site Helper
    mathmari's Avatar
    Status
    Offline
    Join Date
    Apr 2013
    Posts
    3,815
    Thanks
    3,029 times
    Thanked
    995 times
    Awards
    MHB Model User Award (2017)  

MHB Chat Room Award (2015)  

MHB Model User Award (2015)  

MHB LaTeX Award (2015)
    #5 Thread Author
    Quote Originally Posted by Evgeny.Makarov View Post
    It is possible.
    Ah yes! For the empty set, right?

    So do we have the following?

    We consider the set $M=\{0,1,2\}$.

    • reflexive, symmetric : $R=\{(0,0), (1,1), (2,2), (0,1), (1,0)\}$.
    • reflexive, anti-symmetric : $R=\{(0,0), (1,1), (2,2), (0,1)\}$.
    • reflexive, transitive : $R=\{(0,0), (1,1), (2,2), (0,1), (1,2), (0,2)\}$.
    • symmetric, anti-symmetric : $R=\emptyset$.
    • symmetric, transitive : $R=\{(0,0), (0,1), (1,0)\}$.
    • anti-symmetric, transitive : $R=\{(0,0), (1,1), (0,1)\}$.
    • reflexive, symmetric, anti-symmetric : $R=\emptyset$.
    • reflexive, symmetric, transitive : $R=\{(0,0), (1,1), (2,2), (0,1), (1,0), (1,2),(2,1),(0,2), (2,0)\}$.
    • reflexive, anti-symmetric, transitive : $R=\{(0,0), (1,1), (2,2), (0,1), (1,2),(0,2), (2,1)\}$.
    • symmetric, anti-symmetric, transitive : $R=\emptyset$.
    • reflexive, symmetric, anti-symmetric, transitive : $R=\emptyset$.



  7. MHB Master
    MHB Site Helper
    MHB Math Scholar

    Status
    Offline
    Join Date
    Jan 2012
    Posts
    2,483
    Thanks
    533 times
    Thanked
    4,408 times
    Thank/Post
    1.775
    Awards
    MHB University Math Award (2018)  

MHB Humor Award (2017)  

MHB Discrete Mathematics Award (2017)  

MHB Chat Room Award (2016)  

MHB Humor Award (2016)
    #6
    Quote Originally Posted by mathmari View Post
    For the empty set, right?
    No, for any subset of the diagonal relation $\Delta=\{(x,x)\mid x\in M\}$.

    I don't have time now to check all your answers, but as I said, there are 16 combinations, and they should be enumerated in a systematic way that makes it easy to see that nothing is missing. In your enumeration the first item "reflexive, symmetric" does not mean "reflexive, symmetric, not antisymmetric and not transitive" because this relation is transitive.

  8. MHB Master
    MHB Site Helper
    mathmari's Avatar
    Status
    Offline
    Join Date
    Apr 2013
    Posts
    3,815
    Thanks
    3,029 times
    Thanked
    995 times
    Awards
    MHB Model User Award (2017)  

MHB Chat Room Award (2015)  

MHB Model User Award (2015)  

MHB LaTeX Award (2015)
    #7 Thread Author
    Quote Originally Posted by Evgeny.Makarov View Post
    No, for any subset of the diagonal relation $\Delta=\{(x,x)\mid x\in M\}$.

    I don't have time now to check all your answers, but as I said, there are 16 combinations, and they should be enumerated in a systematic way that makes it easy to see that nothing is missing. In your enumeration the first item "reflexive, symmetric" does not mean "reflexive, symmetric, not antisymmetric and not transitive" because this relation is transitive.
    So a relation that is symmetric, anti-symmetric and transitiveis is every relation in the form $\{(x,x)\mid x\in M\}$, right? But the empty set satisfies also these properties, or not?

  9. MHB Master
    MHB Site Helper
    MHB Math Scholar

    Status
    Offline
    Join Date
    Jan 2012
    Posts
    2,483
    Thanks
    533 times
    Thanked
    4,408 times
    Thank/Post
    1.775
    Awards
    MHB University Math Award (2018)  

MHB Humor Award (2017)  

MHB Discrete Mathematics Award (2017)  

MHB Chat Room Award (2016)  

MHB Humor Award (2016)
    #8
    Quote Originally Posted by mathmari View Post
    So a relation that is symmetric, anti-symmetric and transitiveis is every relation in the form $\{(x,x)\mid x\in M\}$, right?
    $\{(x,x)\mid x\in M\}$ is a fixed set. You would not say, "Any number of the form 5", right? But yes, a relation is both symmetric and antisymmetric iff it is a subset of the diagonal relation $\Delta=\{(x,x)\mid x\in M\}$. The empty relation is also a subset of $\Delta$ and is symmetric and antisymmetric.

  10. MHB Master
    MHB Site Helper
    mathmari's Avatar
    Status
    Offline
    Join Date
    Apr 2013
    Posts
    3,815
    Thanks
    3,029 times
    Thanked
    995 times
    Awards
    MHB Model User Award (2017)  

MHB Chat Room Award (2015)  

MHB Model User Award (2015)  

MHB LaTeX Award (2015)
    #9 Thread Author
    Quote Originally Posted by Evgeny.Makarov View Post
    $\{(x,x)\mid x\in M\}$ is a fixed set. You would not say, "Any number of the form 5", right? But yes, a relation is both symmetric and antisymmetric iff it is a subset of the diagonal relation $\Delta=\{(x,x)\mid x\in M\}$. The empty relation is also a subset of $\Delta$ and is symmetric and antisymmetric.
    Ah ok!

    So $\Delta$ is symmetric and antisymmetric and so also transitive, right?

  11. MHB Master
    MHB Site Helper
    MHB Math Scholar

    Status
    Offline
    Join Date
    Jan 2012
    Posts
    2,483
    Thanks
    533 times
    Thanked
    4,408 times
    Thank/Post
    1.775
    Awards
    MHB University Math Award (2018)  

MHB Humor Award (2017)  

MHB Discrete Mathematics Award (2017)  

MHB Chat Room Award (2016)  

MHB Humor Award (2016)
    #10
    Yes, every subset of $\Delta$, including $\Delta$ itself, is transitive.

Similar Threads

  1. Relations - State whether the relation is an equivalence or partial order relation
    By CH1203 in forum Discrete Mathematics, Set Theory, and Logic
    Replies: 3
    Last Post: January 23rd, 2018, 12:27
  2. Partial Order Relation and Equivalence Relation
    By Yankel in forum Discrete Mathematics, Set Theory, and Logic
    Replies: 5
    Last Post: June 8th, 2017, 17:03
  3. Replies: 1
    Last Post: February 21st, 2017, 19:18
  4. Find the only value of N which satisfies all of the following
    By lmae in forum Pre-Algebra and Algebra
    Replies: 5
    Last Post: August 30th, 2016, 17:55
  5. Properties of the equivalence relation
    By paulmdrdo in forum Pre-Algebra and Algebra
    Replies: 6
    Last Post: July 23rd, 2013, 15:22

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
Math Help Boards