Sorting without transitivity

[Steven Taschuk]

Quoth Frank Niessink:
> [It's been while since I've dealt with transitivity and stuff, so
> I hope I got the terminology right]
> 
> I have objects that are not transitivily ordered, e.g.:
> 
> A > B
> A == C
> B == C
  [...]

Martelli's already given the magic words "topological sort"; this
post is just about the terminology.  (All from memory; corrections
welcomed.)

Usually == is supposed to be an "equivalence relation", which
means that
    1. x == x (reflexivity)
    2. x == y if and only if y == x (symmetry)
    3. if x == y and y == z then x == z (transitivity)
Above we see a violation of these assumptions.  Since b == c, by
symmetry we expect c == b.  Then, since a == c, by transitivity we
expect a == b; but actually a > b.

So your == above seems not to be an equivalence relation; it seems
to mean "not ordered with respect to" instead of "equal to" or
"equivalent to".  Some authors use <> for "not ordered with
respect to".  (This is not its meaning in Python, where it is a
synonym of !=, "not equal to".)  In this notation, your statements
above would be
    a > b
    a <> c
    b <> c
Formally, x <> y means just that neither x > y nor y > x.

Usually the symbol > denotes a "total order" or a "partial order".
A total order is a relation > such that
    1. not x > x (irreflexivity?)
    2. if x > y then not y > x (antisymmetry)
    3. if x > y and y > z then x > z (transitivity)
    4. for any x and y, either x == y, x > y, or y > x (trichotomy?)
The difference between a total order and a partial order is that
(4) need not hold for the latter; thus we can have unequal
elements which have no determinate order relationship.

So your > looks at first glance like what they call a partial
order.

-- 
Steven Taschuk                          staschuk at telusplanet.net
"Its force is immeasurable.  Even Computer cannot determine it."
                           -- _Space: 1999_ episode "Black Sun"