Steven D'Aprano <steve+comp.lang.pyt...@pearwood.info> writes: > On Thu, 09 Dec 2010 12:21:45 +0000, Mark Wooding wrote: > > > John Nagle <na...@animats.com> writes: > > >> "sort" has failed because it assumes that a < b and b < c implies a < > >> c. But that's not a valid assumption here. > >> > >> It's not good to break trichotomy. > > > > You're confused. The property > > > > a < b and b < c => a < c > > > > is called `transitivity'. > > Yes, but I believe that John is referring to the trichotomy (like a > dichotomy,
Then why did he say `it assumes that a < b and b < c implies a < c'? This assumption is transitivity, not trichotomy. > > 2. Totality: a <= b or b <= a > > > > The above list sorting goes wrong because the `float' ordering isn't > > total. In particular, x </= NaN and NaN </= x for all x (including x = > > NaN!). > > I believe this is equivalent to trichotomy. No, it isn't. In particular, the definition of totality I gave above allows a <= b and b <= a and a /= b. You gave a perfectly good definition of trichotomy, which I have moved out of its original order: > exactly one of these relations are true: > > a < b > a == b > a > b A total preorder (as defined above) doesn't exhibit this property -- but can be described in terms of a total order (which /does/ exhibit proper trichotomy) applied to a set of equivalence classes. > > So, your last remark is in the right direction (though strict trichotomy > > is unnecessary, as I've mentioned), but apparently only by accident > > since the preceding discussion is completely wrong. > > "Completely" is surely a tad strong -- John might not be using the > exact same terminology as you, but he's clearly talking about the > equivalent concepts. He wants and expects all data types to either > meet a total order, or raise an exception to any of the < > <= and >= > operators. No. He was hopelessly confused, describing the problem in terms of a failure of transitivity (which doesn't, in fact, fail), but using the word `trichotomy', apparently more by luck than judgement. I don't want to insist on a total order. Efficient sorting requires a total preorder, and that's all I want. -- [mdw] -- http://mail.python.org/mailman/listinfo/python-list
