Re: Testing for the equivalence relation

From: Mikito Harakiri <mikharakiri_nospaum_at_yahoo.com>
Date: 30 Jun 2005 16:01:34 -0700
Message-ID: <1120172494.706325.291620_at_g43g2000cwa.googlegroups.com>


I just posted the similar question on sci.math couple days ago. Counter example:

domain x={1,2}
relation {(1,1)}
symmetric, antisymmetric, transitive, not reflecive, not irreflective.

See the diagram in the Gotz Pfeifer paper "Counting Transitive Relations"

Dan wrote:
> Hi,
>
> I'm seeking some help on a rather basic and trivial question.
>
> Is there a case where a relation's extension proves to be symmetric and
> transitive, but the relation is not an equivalence relation? In other
> words, can a relation be symmetric and transitive, but not be
> reflexive?
>
> If I recall correctly, by definition, a relation is an equivalence
> relation if, and only if, the relation is reflexive, symmetric, and
> transitive. It seems intuitive that if a relation has the properties
> of being symmetric and transitive, the relation must also be reflexive.
>
> My current rationale (that I want disproved) is the following:
>
> Hypothesis: If a binary relation R is symmetric and transitive, it is
> an equivalence relation (ie. it implies reflexivity - in contrast to
> the classic definition).
>
> By definition of symmetric property of a relation,
>
> for all x,y that are elements of A, x R y --> y R x.
>
> By definition of transitive property of a relation,
>
> for all x, y, z that are elements of A, x R y and y R z --> x R z.
>
> Reflexivity of the relation is implied because
>
> If x R y and y R x, then x R x (by the definition of transitivity),
> and therefore R is reflexive.
>
> Thus, if relation R is symmetric and transitive, it is an equivalence
> relation.
>
> I'm looking for a counterexample to this.
>
> Thanks,
>
> - Dan
Received on Fri Jul 01 2005 - 01:01:34 CEST

Original text of this message