A relation

Printable View

October 26th 2010, 01:02 AM
Swlabr

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$ ?
October 26th 2010, 03:58 AM
tonio

Quote:

Originally Posted by Swlabr

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
October 26th 2010, 04:36 AM
Swlabr

Quote:

Originally Posted by tonio

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.
October 26th 2010, 06:20 AM
emakarov

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.
October 26th 2010, 06:56 AM
Swlabr

Quote:

Originally Posted by emakarov

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$ .)
October 26th 2010, 10:55 AM
MoeBlee

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.
October 26th 2010, 11:08 AM
MoeBlee

delete post
June 8th 2011, 11:28 AM
ymar

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.
June 8th 2011, 02:02 PM
Matt 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.
June 9th 2011, 05:50 AM
Deveno

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.