Re: Partial orders. Re: Comments on SRFI 128 Draft 5 (2015-11-08). Sudarshan S Chawathe 10 Nov 2015 16:03 UTC

```Taylan Ulrich Bayirli/Kammer wrote:

> "Sudarshan S Chawathe" <xxxxxx@eip10.org> writes:
>
> > John Cowan wrote:
> >
> >> Sudarshan S Chawathe scripsit:
> >>
> >> >   (make-comparator exact-integer?
> >> >   		   =
> >> > 		   (lambda (i j)
> >> >                      (and (even? i)
> >> >                           (even? j)
> >> >                           (< i j)))
> >> > 		   number-hash)
> >>
> >> This clearly violates the programmer's responsibilities section, as
> >> I said before.  The ordering predicate is required to be asymmetric.
> >> An asymmetric predicate is one in which, for all values of a and b,
> >> if (pred a b) is true than (pred b a) is false.  This is obviously not
> >> true here, so what you have is a comparator whose behavior when passed
> >> to standard routines is undefined.
> >
> > I agree that the SRFI requires the ordering predicate to be
> > asymmetric.  I also agree with your definition of asymmetric
> > predicates.
> >
> > However, I do not understand why you claim that the ordering predicate
> > in the above example (let's call it 'e<') is not asymmetric.  Using
> > your definition, could you please exhibit values of 'a' and 'b' for
> > which (e< a b) is true and (e< a b) is not false?  (If your claim is
> > true then at least one such pair a,b must exist.)
> >
> > I have similar comments about the other example in my earlier message,
> > but perhaps it's best to focus on this one here.
>
> For a 3 and b 5, (e< a b) is #f and (e< b a) is also #f.

The requirement for asymmetry (from John's message) is a statement of
the form:

If P then not Q

The above values of a and b (3 and 5) make both P and Q false.  In that
case, the statement "If P then not Q" is true.

Unless I am horribly confused (which does seem increasingly likely!),
the way to prove that e< is not asymmetric, using John's definition
(which is fairly standard) and a counterexample, is to exhibit a and b
for which (e< a b) and (e< b a) are both *true* (not both false as
above).

I am using the common interpretation of logical implication:

"if P then not Q" is equivalent to
"(not P) or (not Q)" which is equivalent to
"not (P and Q)".

Negating the implication requires demonstrating "P and Q", not "(not P)
and (not Q)"; the a=3 b=5 values do the latter.

Regards,

-chaw

```