Re: Empty interval representations & Motion 13...
> Subject: Re: Empty interval representations & Motion 13...
> From: John Pryce <j.d.pryce@xxxxxxxxxxxx>
> Date: Mon, 3 May 2010 17:20:24 +0100
> To: P1788 <stds-1788@xxxxxxxxxxxxxxxxx>
>
> Dan & P1788
>
> I have gone through Dan's work on comparisons with the empty
> set (below), checking against the set theory definitions given
> in my mail earlier today.
>
> I think they all agree, except the two I have marked (*).
> Namely I think
> empty interior empty
> empty strictLess empty
> should both give True.
>
> Pretty good overall.
>
> John
Well, nobody's perfect. :-)
Still, I was using the endpoint comparison definition
in that note & you recently raised the issue that we
should, perhaps, consider a set theoretic definition.
In that spirit, should we define:
aa interior bb = there exists b1 & b2 in bb such
that for all a in aa we have b1 < a < b2
and
aa strictLess bb = (there exists a in aa such that
for all b in bb we have a < b) and (there
exists b in bb such that for all a in aa
we have a < b)?
With these definitions we have
empty interior anyNonEmpty = True
empty interior empty = False
empty strictLess empty = False
empty strictLess anyNonEmpty = False
Given that the comparisons are strict in each case,
these results appear valid to me. But I can see how
the mixture of existential & universal qualification
might be a sticking point for some.
What do you think?
Are there better set theoretic definitions?
Dan
P.S. - Dominique appealed to the trichotomy property
of Real numbers in her recent note. Namely, that for
any two reals exactly one of {<, =, >} is true.
First, we must be cautious in that, while this is true
among the Reals, in is NOT true among the IEEE floating-
point numbers. The proper set of comparisons in that
case is {<, =, >, ||} where '||' is 'unordered' which
is what you get when you compare with a NaN. (This
could be called 'tetrachotomy, I suppose. But we have
never found the need to name it. :-)
On the other hand, trichotomy IS true among the IEEE
floating-point numbers so long as NaNs are excluded.
Another reason for excluding them, perhaps.
And, while there may be natural a set of (perhaps 7)
comparisons that have the "exactly one is true for any
pair of intervals" property, I am unaware of such a set.
If one of you knows such a set, let's see it.
It may serve us for our next Motion 13. The use of
a bit for each primitive comparison in {<, =, >, ||}
has been a useful way of forming all other comparisons
in IEEE 754 hardware implementations. A 7-bit set
could work well for us.
Cumbersome? Maybe. But the hardware guys will like it.
Septachotomy? Hmm... :-)
>
> On 22 Apr 2010, at 03:46, Dan Zuras Intervals wrote:
> > But if we use empty = [+oo,-oo], how does that come out
> > for Ulrich's comparisons?
> >
> > a equals b <==> a1 = b1 && a2 = b2
> > a subset b <==> b1 <= a1 && a2 <= b2
> > a lessEqual b <==> a1 <= b1 && a2 <= b2
> > a precedeTouch b <==> a2 <= b1
> > a interior b <==> b1 < a1 && a2 < b2
> > a strictLess b <==> a1 < b1 && a2 < b2
> > a preceed b <==> a2 < b1
> >
> > Let's let any = [b1,b2] be some otherwise non-empty
> > interval. I believe we have that
> >
> > empty equals any = False
> > empty subset any = True
> > empty lessEqual any = False (1)
> > empty precedeTouch any = True (2)
> > empty interior any = True
> > empty strictLess any = False
> > empty preceed any = True (3)
> >
> > as well as
> >
> > any equals empty = False
> > any subset empty = False
> > any lessEqual empty = False (1)
> > any precedeTouch empty = True (2)
> > any interior empty = False
> > any strictLess empty = False
> > any preceed empty = True (3)
> >
> > and, for completeness sake
> >
> > empty equals empty = True
> > empty subset empty = True
> > empty lessEqual empty = True (4)
> > empty precedeTouch empty = True (2)
> > empty interior empty = False (*)
> > empty strictLess empty = False (*)
> > empty preceed empty = True (4)
> >
> >
> > Which are all correct with the following qualifications
> >
> > (1) (a lessEqual b) tests for mere overlap in one direction
> > or the other. Therefore, it is acceptable to the programmer
> > that this be true if SOME a is less than or equal to SOME b.
> > This has the flavor of an existential quantification & if
> > this test is written in this way, empty tests correct.
> >
> > (2) Similarly, (a precedeTouch b) test to make sure that NO
> > element of a exceeds ANY element of b. If it is written
> > with universal quantification (essentially not (any a >
> > any b)) then empty tests correct.
> >
> > (3) This one is True except for (empty preceed [-oo,x]) or
> > ([x,+oo] preceed empty) in which case it tests False. This
> > may have to be special cased.
> >
> > (4) My interpretation is that these two are False with the
> > quantification I suggest. So they may have to be special
> > cased as well.