Transitive, Symmetric, Non-Reflexive Relation

• Feb 1st 2010, 09:32 PM
BlackBlaze
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?

• Feb 2nd 2010, 12:09 AM
Opalg
Quote:

Originally Posted by BlackBlaze
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.
• Apr 17th 2010, 11:39 PM
svhk109
Quote:

Originally Posted by BlackBlaze
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.

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.
• Apr 24th 2010, 07:12 AM
PiperAlpha167
Quote:

Originally Posted by BlackBlaze

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.

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.