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

$\displaystyle a \sim b \Rightarrow b \sim a$

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

but

$\displaystyle a \not\sim a$?

Printable View

- Oct 26th 2010, 01:02 AMSwlabrA relation
Does there exist a `naturally occurring' relation ~ such that,

$\displaystyle a \sim b \Rightarrow b \sim a$

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

but

$\displaystyle a \not\sim a$? - Oct 26th 2010, 03:58 AMtonio

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

then if the set has two or more elements we get from transitivity that $\displaystyle 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 - Oct 26th 2010, 04:36 AMSwlabr
- Oct 26th 2010, 06:20 AMemakarov
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. - Oct 26th 2010, 06:56 AMSwlabr
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, $\displaystyle \sim$, unioned with a singleton, $\displaystyle a$, and we stipulate that $\displaystyle 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 $\displaystyle (\mathbb{Q}, \sim)$, $\displaystyle a \sim b \Leftrightarrow a*b \neq 0$.) - Oct 26th 2010, 10:55 AMMoeBlee
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. - Oct 26th 2010, 11:08 AMMoeBlee
delete post

- Jun 8th 2011, 11:28 AMymar
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.

- Jun 8th 2011, 02:02 PMMatt Westwood
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.

- Jun 9th 2011, 05:50 AMDeveno
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.