[Agda] `<' reasoning

Sergei Meshveliani mechvel at botik.ru
Thu Dec 7 21:14:42 CET 2017


People,

I meet the following difficulty in Agda reasoning about _<_. 

For  Nat,  it is all right, because  m < n  is defined as  suc m ≤ n, 
and it works the construct 

 e[1]<e[n] =
     begin suc e[1]    ≤⟨ .. ⟩
           ...
           ...         ≡⟨ .. ⟩
           ...
           e[n]
     ∎

formed with standard functions   
                     begin_ , _∎ , _≡⟨_⟩_ , _≤⟨_⟩_ 

But there are domains without  suc  operator (agreed with _≤_, _<_).
For example, consider the proof

----------------------------------------------
postulate  bs1<bs'1 :  bs1 < bs'1

goal :  0bs1 < 0# + 0bs'1
goal = 	subst₂ _<_ (sym eq0) eq1 le
     where
     eq0 :  0bs1 ≡ bs1 * 2bin
     eq0 =  *2≗*2bin bs1

     eq1 = begin bs'1 * 2bin    ≡⟨ sym (*2≗*2bin bs'1) ⟩
                 bs'1 *2        ≡⟨ sym (0+ 0bs'1) ⟩
                 0# + 0bs'1
           ∎

     le :  bs1 * 2bin < bs'1 * 2bin
     le =  *bs1-mono-< [ 0b ] bs1<bs'1
----------------------------------------------

_≤_  is defined as   x ≤ y =  x < y ⊎ x ≡ y.
And imagine that we do not use  suc  for redefining  _≤_.

This is more difficult to compose and to read than the `linear'
construct of
goal =
  begin< 0bs1          (1) ≡[ *2≗*2bin bs1 ]
         bs1 * 2bin    (2) <[ *bs1-mono-< [ 0b ] bs1<bs'1 ]
         bs'1 * 2bin   (3) ≡[ sym (*2≗*2bin bs'1) ]
         bs'1 *2       (4) ≡[ sym (0+ 0bs'1) ]
         0# + 0bs'1    (5)
  end<

Each next term in the column is less or is equal to the current one,
and there is at least one line of the strict construct (that is of
_<[_]_). Hence this proves the goal.

Are there provers in Standard library that enable writing something like
the above `linear' proofs with _<_ ?   

Thanks,

------
Sergei



More information about the Agda mailing list