RE: [boost] Formal Review for Interval Library beginning

From: David Bergman (davidb_at_[hidden])
Date: 2002-09-04 12:21:49

Peter,

No your suggestion is not a natural equivalence relation. It is not a
proper equivalence relation at all, since it is not reflexive.

Obviously, you cannot bypass reflexivity, meaning that truly identical
elements always have to be equivalent, so [1, 2] == [1, 2], no matter
what equivalence relation we pick. Sorry.

"But hey, what is it that says that [1, 2] is identical to [1, 2]? Uh?"

Well, first of all, in C++ intensional semantics, two objects are
identical if they occupy the same memory-based object, so if (sorry for
not using exact syntax): ' a = [1, 2] ' then ' a == a ' should hold.
But, you might not agree, since in your "equivalence" relation it does
not...

And then we have extensional identity, where a compound object is
identical to another one if their constituents are identical, such as
[1, 2] == [1, 2].

Then we also have algebraic identity, where two elements are identical
if they can replace eachother in any expression, such as [1, 2] and [1,
2]...

I hope you see my point by now, by *any* identity measurement, [1, 2]
and [1, 2] (occupying the same memory chunk or not) are identical and
therefore *must* belong to the same equivalence class.

The *only* natural equivalence relation on arithmetic interval, and the
one I referred to, was this one, of identical elements.

I do not want to use hard words, but what is it that makes people forget
that '<=' is pronounced "less than or equal" and should *always* be
"less than" or "equal", or in C++ syntax ' a < b || a == b '. There is
no choice here. "Well, that is your opinion".
It is not about syntax, cause one might want to, as you did, define '=='
as a relation not being an equivalence at all. But we are talking about
logical semantics, where that is not possible.

I will welcome the arithmetic interval library as soon as it has a
logically sound ordering and equivalence relation, being consistent with
that one, and they somehow deal with the dependence on transcendental
operations being defined (yes, I know it will compile anyhow...)

My suggestion for ordering and equivalence is

1.  '<'  as is
2.  '<=' as '< || =='
3.  '==' as (extensional or algebraic) identity, i.e., [a, b] == [c, d]
iff a == c && b == d

Obviously, (3) has to deal with inifinities, by extending the limit
class to one including such extended elements. I.e., in
interval<double>, the end points cannot be double, but rather
extended_num<double>, with conversion operators and all that...

/David

-----Original Message-----
From: boost-bounces_at_[hidden]
[mailto:boost-bounces_at_[hidden]] On Behalf Of Peter Dimov
Sent: Wednesday, September 04, 2002 6:50 AM
To: boost_at_[hidden]
Subject: Re: [boost] Formal Review for Interval Library beginning

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. :-)

_______________________________________________
Unsubscribe & other changes:
http://lists.boost.org/mailman/listinfo.cgi/boost