72 views

Skip to first unread message

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.

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.

commutative, not associative, transitive, reflexive, or any other such term.

--

Jess Holle

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

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

Search

Clear search

Close search

Google apps

Main menu