[Agda] _<=_ and _<_

Sergei Meshveliani mechvel at botik.ru
Tue Sep 24 15:18:52 CEST 2013


People, I have a couple of questions about general relation between 
                                                            _≤_ and _<_ 
in the  lib-0.7 standard library.

1. What is the most general situation in  lib-0.7  under which these
usual properties can be proved:
                                       
                       x ≤ y  iff  x < y ⊎ x ≈ y               (I),
                       x < y  ->  ¬ y ≤ x                      (II)
?

2. For  Nat,  
   it is natural to derive (I) and (II) from  DecTotalOrder,
   as a specialization of the above generic laws. 

But  DecTotalOrder  says nothing about  _<_.
Then, we are forced to derive (I) and (II) from the union of
DecTotalOrder and StrictTotalOrder.
Right?

Well,  Data.Nat  has  decTotalOrder.  But it is silent about 
Strict(Total)Order.

What is the way out?
The approach  "prove (I) and (II) individually for  Nat" 
will cause individual proofs for  Integer, Nat × Nat, List Nat,
and so on.


3. Consider the Order organization that follows literally the usual
formula "less or equal".

(A) Having _≈_ and _<_,   _≤_ needs to be defined 
                              (implemented) immediately
Or
(B) Having _≈_ and _≤_,   _<_ needs to be defined immediately.

Because this is natural.

Let us follow (A):

  record IsPartialOrder {a ℓ₁ ℓ₂} {A : Set a}
                        (_≈_ : Rel A ℓ₁) (_<_ : Rel A ℓ₂) :
                        Set (a ⊔ ℓ₁ ⊔ ℓ₂) where
    field
      isPreorder : IsPreorder _≈_ _<_   
                                   -- redefine IsPreorder respectively
      antisym    : Antisymmetric _≈_ _<_

    _≤_ : Rel A ℓ₂
    x ≤ y =  x < y ⊎ x ≈ y

Of course, the axioms need to be corrected slightly.
And  StrictPartialOrder  will not need to introduce  _<_  as something
independent on  _≤_.

I suspect that if the  Ordering library part  is reorganized this way,
then using orderings will become easier.

Am I missing something? What is your opinion?

Regards,

------
Sergei






More information about the Agda mailing list