Results 1 to 4 of 4

Math Help - Transitive, Symmetric, Non-Reflexive Relation

  1. #1
    Junior Member
    Joined
    Sep 2009
    Posts
    32

    Transitive, Symmetric, Non-Reflexive Relation

    Can anyone give me an example of a symmetric, transitive but non-reflexive relation with the set S as any integer? I can only think of the sibling example, which doesn't work since I need integers, and the empty relation, which is rather cheap...Recipricol too, but it needs real numbers and not integers. Blllarrrrgh!

    In addition, why is this proof not valid?
    Suppose R is a symmetric and transitive relation. aRb means bRa by the symmetric property. By the transitive property, aRb and bRa means aRa, so the relation must also be reflexive.

    Since the sibling example exists, I know for sure it's wrong. But I can't see what it doesn't take into account. Perhaps the chance that the property of the relation forces the transitive property to use three different numbers?

    Thanks in advance.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by BlackBlaze View Post
    In addition, why is this proof not valid?
    Suppose R is a symmetric and transitive relation. aRb means bRa by the symmetric property. By the transitive property, aRb and bRa means aRa, so the relation must also be reflexive.

    Since the sibling example exists, I know for sure it's wrong.
    That proof is valid (unless R is the empty relation, in which case it fails), and it illustrates why the sibling relation is not transitive. So your example of the empty relation, while it may be cheap, is the only one available.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Apr 2010
    Posts
    1
    Quote Originally Posted by BlackBlaze View Post
    In addition, why is this proof not valid?
    Suppose R is a symmetric and transitive relation. aRb means bRa by the symmetric property. By the transitive property, aRb and bRa means aRa, so the relation must also be reflexive.

    Thanks in advance.
    The proof is indeed invalid. The problem is that, unlike reflexive relations, neither the symmetric nor the transitive relations require every element of the set to be related to other elements. What the given proof has proved is IF aRb then aRa. It does not guarantee that for all a, there exists b so that aRb is true. Which means, while it may show aRa for some a (if R is non-empty relation), it fails to show for all a in the (unmentioned) set, aRa. Here is a rather cheap counter example.
    R = {(1,1)}, where R is a relation on all integers.
    It can be easily seen that R is symmetric and transitive, but R is not reflexive simply because (3,3) is not there (or (4,4) or (-1,-1) or ...).


    Oh, as for the sibling example, it may not work in this crazy world.
    Suppose A is a child of F1 and M1, and B is a child of F2 and M1, and C a child of F2 and M2.
    A is a sibling of B, and B a sibling of C. But indeed, A and C are complete strangers.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Oct 2006
    Posts
    71
    Quote Originally Posted by BlackBlaze View Post

    In addition, why is this proof not valid?
    Suppose R is a symmetric and transitive relation. aRb means bRa by the symmetric property. By the transitive property, aRb and bRa means aRa, so the relation must also be reflexive.

    Thanks in advance.
    If you use the definition for reflexivity that Elliot Mendelson, Patrick Suppes and John Pollack work with, then it's a theorem. (And these are just three individuals.)

    Mendelson: Definition. A binary relation R is said to be reflexive if xRx for all x in the field of R.

    Pollack: Theorem. If R is transitive and symmetric, then R is reflexive.

    Even Bertrand Russell weights in on this:
    "It is obvious that a relation which is symmetrical and transitive must be reflexive throughout its domain."

    Clearly under this definition, the counterexample given becomes an example.

    I guess the point here is that the phrase I often hear/read, "just go to the defintion", is not really of too much substance
    until one examines what's actually out there. Then after some deliberation, either leave the definition tacit (because it is in fact the
    definition and "everyone" presumably knows it), or state it explicitly (when it's discovered that there are other versions in use).

    And most certainly this particular version has not been used by a bunch of cranks.
    Last edited by PiperAlpha167; April 24th 2010 at 10:20 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. reflexive, symmetric, antisymmetric, transitive?
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: April 8th 2011, 06:47 AM
  2. Symmetric, transitive, not reflexive?
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 2nd 2010, 01:32 AM
  3. Replies: 2
    Last Post: January 24th 2010, 08:06 PM
  4. Reflexive, symmetric, and transitive
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 5th 2009, 12:08 PM
  5. Reflexive, Transitive, Symmetric
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 20th 2009, 03:24 PM

Search Tags


/mathhelpforum @mathhelpforum