Results 1 to 10 of 10

Math Help - A relation

  1. #1
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176

    A relation

    Does there exist a `naturally occurring' relation ~ such that,

    a \sim b \Rightarrow b \sim a

    (a \sim b \text{ and } b \sim c) \Rightarrow a \sim c

    but

    a \not\sim a?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by Swlabr View Post
    Does there exist a `naturally occurring' relation ~ such that,

    a \sim b \Rightarrow b \sim a

    (a \sim b \text{ and } b \sim c) \Rightarrow a \sim c

    but

    a \not\sim a?

    I don't think so, at least if the relation is fully symmetric (i.e., for any pair = different elements  a,b then a\sim b and also b\sim a) ,

    then if the set has two or more elements we get from transitivity that a\sim b\,\,and\,\,b\sim a\Longrightarrow a\sim a ...

    Of course, in the set of all people, the relation "to be sibling of" seems to comply with the conditions.

    Tonio
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by tonio View Post
    I don't think so, at least if the relation is fully symmetric (i.e., for any pair = different elements  a,b then a\sim b and also b\sim a) ,

    then if the set has two or more elements we get from transitivity that a\sim b\,\,and\,\,b\sim a\Longrightarrow a\sim a ...

    Of course, in the set of all people, the relation "to be sibling of" seems to comply with the conditions.

    Tonio
    Sorry, I meant that there exists some a such that a \not\sim a. It doesn't have to hold for all elements.

    `To be a sibling of' is quite neat though. Thanks.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,551
    Thanks
    783
    Symmetry and transitivity do not imply reflexivity. Otherwise, of course, we should change the definition of the equivalence relation from listing three properties to listing only two.

    If a relation R is symmetric and transitive and an element x is related to some y, then indeed R(x,x).

    If the relation "is a sibling of" is irreflexive, then it is not really transitive precisely because x ~ y and y ~ x do no imply x ~ x.

    No natural example comes to mind for the moment, but I am sure they are out there.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by emakarov View Post
    Symmetry and transitivity do not imply reflexivity. Otherwise, of course, we should change the definition of the equivalence relation from listing three properties to listing only two.

    If a relation R is symmetric and transitive and an element x is related to some y, then indeed R(x,x).

    If the relation "is a sibling of" is irreflexive, then it is not really transitive precisely because x ~ y and y ~ x do no imply x ~ x.

    No natural example comes to mind for the moment, but I am sure they are out there.
    Good point. In fact, I believe this means that all examples have the same basic structure. That is, they consist of some set, S, under an equivalence relation, \sim, unioned with a singleton, a, and we stipulate that a \not\sim s \: \forall s \in S \cup \{a\}. It's like adding a zero onto a semigroup. (EDIT: You can add lots of singletons on...)

    So, probably all examples are contrived! (A contrived one would be (\mathbb{Q}, \sim), a \sim b \Leftrightarrow a*b \neq 0.)
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Maybe contrived but the empty relation is an example.

    Consider {p}. The empty set is a subset of {p}X{p}. So the empty set is a relation on {p}. And the empty set is a symmetric and transitive relation, and there exists an a (viz. p) in {p} such that <a a> is not in the empty set.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    delete post
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Feb 2011
    Posts
    147
    Thanks
    3
    Hey, Swlabr. I know it's an old thread, but you might find this interesting. I'm not sure whether you're going to find this example contrived, but here it is: NaN is never equal NaN (see), so equality in the set of floating point numbers is an example of a relation that isn't reflexive, but is transitive and symmetric.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Super Member Matt Westwood's Avatar
    Joined
    Jul 2008
    From
    Reading, UK
    Posts
    824
    Thanks
    33
    Here's an example: let x \sim y mean "x = y = 0" on the set of integers. Then when x = 1, x \not \sim x but the other properties always hold.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762
    symmetry and transitivity "almost imply" reflexivity. the crucial "missing link" is this: there has to be a pair a~b FOR ALL a. otherwise, some elements of the diagonal are missing.

    an obvious symmetric and transitive relation on the set of some group of people is: "are both named Fred". this is reflexive only if all the people are named Fred.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: April 6th 2011, 11:46 PM
  2. Relation
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 13th 2010, 07:13 PM
  3. Replies: 1
    Last Post: March 1st 2010, 07:24 AM
  4. Relation ( Equivalence Relation)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: December 5th 2008, 08:55 AM
  5. relation ~
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: May 21st 2005, 12:58 AM

Search Tags


/mathhelpforum @mathhelpforum