Reflexivity

72 views
Skip to first unread message

Peter Becker

unread,
Nov 23, 2008, 8:16:14 PM11/23/08
to java...@googlegroups.com
Hi Dick,

the math guy in me just has to comment on your comments on
transitivity/reflexivity in #218 ;-)

You got the transitivity part right, it means that if your relation
contains (A,B) and (B,C) then (A,C) is in there. This holds for
equivalence relations, which is what .equals() is supposed to be. If A
is equal to B and B is equal to C, then A and C are equal.

Reflexivity is the property that for all As (A,A) is in your relation
(think "reflection" in the mirroring sense). That holds for equality,
too: all As are equal to themselves. But it is not what you where
talking about, which is symmetry.

Symmetry means that if (A,B) is in your relation, then (B,A) is in
there, too. In terms of equality: if A is equal to B, then B has to be
equal to A. This is the property that is very commonly broken in
implementations of .equals, e.g. by using "instanceof" for checking
the type of the other class -- to ensure symmetry the class of the
other object has to be identical to the one implementing the method.


With reflexivity and symmetry you can also look at the opposite side:

Anti-reflexivity means there's no (A,A) in your relation for any value of A.

Anti-symmetry means if (A,B) is in there, (B,A) is guaranteed not to
be in there.

Note that the anti-Xs are stronger than just saying it's not X since
they guarantee that something not true at all. For example the
"greater than" is anti-reflexive since nothing can be greater than
itself.


The two important combinations are:

Reflexive, symmetric and transitive: an equivalence relation such as
.equals should be.

Reflexive, anti-symmetrix and transitive: an order relation (or
"partial order") with "greater or equal" being the archetypical
example. Comparable/Comparator should implement that.


It's called "partial order", since it is not necessarily guaranteed
that everything compares. If everything compares one way or the other
(i.e. for all possible pairs of As and Bs you have either (A,B) or
(B,A) in your relation), then the relation is a "total order" such as
"greater or equal". A good example for a partial order that's not
total is "contains" on shapes: if you know that A does not contain B
you still can't say anything about B containing A.

Sorry for letting the teacher out, but I hope it helps :-)

Peter

--
What happened to Schroedinger's cat? My invisible saddled white dragon ate it.

Jess Holle

unread,
Nov 23, 2008, 10:31:12 PM11/23/08
to java...@googlegroups.com
I believe that in context of the discussion Dick really meant to say
commutative, not associative, transitive, reflexive, or any other such term.

--
Jess Holle

Peter Becker

unread,
Nov 24, 2008, 6:33:57 AM11/24/08
to java...@googlegroups.com
You might be right - I tried to check, but I can't find the location.

He certainly talked about transitivity, reflexivity and .equals, but
maybe I missed that he wasn't talking relations at all. There's a
blurry line between symmetry and commutativity anyway if you model a
relation by something akin to a characteristic function as Java does.

Either way "reflexive" was wrong and don't we all love correcting our
celebrities as if we would never err like they did? :-)

Peter
Reply all
Reply to author
Forward
0 new messages