Re: [boost] Formal Review for Interval Library beginning

From: Peter Dimov (pdimov_at_[hidden])
Date: 2002-09-04 05:50:27

From: "David Bergman" <davidb_at_[hidden]>
> Peter,
>
> I am quite aware of that ;-)
>
> STL assumes semi-totality of orderings in that "elements are strictly
> and totally ordered up to (generated) equivalence". That generated
> equivalence is used for efficient sorting algorithms, to be able to
> shuffle equivalent (as in incomparable) values. This was also noted in
> my post to which you replied.
>
> I consider it to be unsound to use that STL template when dealing with
> explicitly partially ordered sets, since the mentioned equivalence (or,
> at least implication) is only valid for total orderings and semi-total
> orderings (mainly used in sorting algorithms) to enforce a (non-strict)
> total ordering.
>
> In other words, equivalence defined by incomparability is invalid when
> dealing with partially ordered sets.
>
> And, the '<=' in its ordinary logical interpretation (as a shorthand for
> just '<' or '==') also assumes '=='. I could argue that is not sound to
> define '<=' in a domain where there is no natural equivalence.
>
> But, this argument is not that productive when dealing with intervals,
> since they have a natural equivalence, so we can indead use both '<='
> and '=='. We just have to make sure they are consistent, i.e., that 'a
> <= b' iff 'a < b || a == b'...

Natural equivalence for intervals? I don't see it.

What I see as "natural" (regarding interval arithmetic, and not intervals as
objects) is:

I relop J :- foreach(x in I, y in J) x relop y.

IOW:

[1, 2] < [3, 4] :- true
[1, 3] < [2, 4] :- indeterminate
[3, 4] < [1, 2] :- false
[1, 2] == [3, 4] :- false
[1, 2] == [1, 2] :- indeterminate
[1, 1] == [1, 1] :- true

[1, 2] < [2, 3] :- indeterminate
[1, 2] == [2, 3] :- indeterminate
[1, 2] <= [2, 3] :- true

I.e. I <= J is not the same as I < J || I == J. It might be the same as !(J
< I) but I'm not in the mood to attempt a proof. :-)