From: David Bergman (davidb_at_[hidden])
Date: 2002-09-04 12:21:49
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
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,
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...
[mailto:boost-bounces_at_[hidden]] On Behalf Of Peter Dimov
Sent: Wednesday, September 04, 2002 6:50 AM
Subject: Re: [boost] Formal Review for Interval Library beginning
From: "David Bergman" <davidb_at_[hidden]>
> 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
> 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
I relop J :- foreach(x in I, y in J) x relop y.
[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:
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk