[Agda] Total: x !<= y ==> y <= x

Serge D. Mechveliani mechvel at botik.ru
Thu Oct 11 17:18:49 CEST 2012


On Wed, Oct 10, 2012 at 10:20:08AM -0700, wren ng thornton wrote:
> On 10/10/12 11:59 AM, Serge D. Mechveliani wrote:> People,
> > I have a beginner question on usage of DecTotalOrder of Standard
> > library.
> >
> > I have  ord : DecTotalOrder,
> >          _<=_  extracted from this  ord,
> >          ``with  x <=? y''   produced    no x-!<=-y
> >          (I think,   x-!<=-y :  \neg x <= y )
> >
> > (here I replace \<= with <= ).
> >
> > And from this   x-!<=-y,  I need to construct  y<=x : y <= x.
> > Because I think that this a constructive reifation for a classical
[..]

> I'm not sure of the particular names of things in Agda, but \u+ is the
> disjoint union operator (aka Either in Haskell).
> 
> So, the way you'd use it is:
> (1) this is a decidable total order, so let's analyze: total x y
> (2) Case x <= y: absurd, because we have a proof of \neg x <= y
> (3) Case y <= x: hey, I can just return this proof


I am sorry for my stupidity,
but I fail to force Agda to reject  Case x <= y
(when having   neg : \neg (x <= y))
!

Thanks to people,
now as I see the definition of  \u+  in  Data.Sum,  I try to derive  
y <= x  from  \neg (x <= y)  under  ord : DecTotalOrder ...

The corresponding lemma coded in Agda is 

  !<=thenFlip : {c l1 l2 : Level} -> (ord : DecTotalOrder c l1 l2) ->
                let leq = _<=_ ord
                in  (x y : Carrier ord) -> \neg (leq x y) -> leq y x

  !<=thenFlip ord x y neg =   ??

(I replace the math symbols in an evident way).

Please,  what is the simplest code for it?

First, I tried 
                    with  total ord x y
              ... | inj_2 y<=x = y<=x 

And I fail to force it to skip the pattern of  (inj_1 _)
(tried also setting () in various places).
Somehow the  neg  map to  \bottom  needs to be used for this ...
Or do I need to add 
                    inj_1 _ = p  where p = postulate p : leq y x
?
The second attempt is via mapping it to  Empty \u+ (leq y x) :

   f v 
   where
   leq = _<=_ ord

   v : Empty \u+ (leq y x)
   v = Sum.map neg id $ total ord x y

   f : Empty \u+ (leq y x) -> leq y x
   f (inj_2 u) = u
   f ()             ??

Here  Empty  is the empty type -- denoted by a math symbol  \bottom.

Sum.map  applies  neg   and obtains a member of a disjoint sum  
                                             v : Empty \u+ (leq y x)
(is \u+ a disjoint sum?).

Further, it is clear to us that for any set T we can define a map 
                                                 f : Empty \u+ T -> T
If any such  f  is defined for  T = (y <= x),  then  f v  is the goal.
But I fail to define such  f  in Agda !
Agda asks for the value for a pattern   f (inj_1 _) -- despite that
(inj-1 u)  has  u  being a member of Empty.
And I fail to force it to skip this pattern, and fail with setting ()
in various places.
Do I need to add   f (inj_1 _) = p  where p = postulate p : leq y x
?
What a constructive philosophy has Agda for a map
                                              f : \bottom \u+ T -> T
?
Thank you in advance for explanation,

------
Sergei


More information about the Agda mailing list