[Agda] (s ◃ m ) * (s' ◃ n)

Sergei Meshveliani mechvel at botik.ru
Fri Jan 10 16:20:50 CET 2014


The below question of simplicity remains.

As to the question of omitting  "e : ...",  I suspect the following
effect, which may look natural.
The first clause proves the case of   0 m,
and the second clause reduces a proof for  m 0  to the case of  0 m
by applying commutativity of _*_ and by calling the same  lemma.
If the signature of  e  is omitted, the checker sees that  
(lemma ... m 0)  calls for  (lemma ... 0 m),  and does not see that the
argument pair has become smaller.
The signature for  e  is special, it contains `0'. 
And it is easier for the checker to see termination
(still, how does this occur?).  

------
Sergei


On Fri, 2014-01-10 at 16:30 +0400, Sergei Meshveliani wrote:
> People,
> I have a question about usage of Integer of Standard library.
> 
> Consider this trivial and naturally looking lemma: 
> 
>   lemma : (s s' : Sign) → (m n : ℕ) → 
>           (s ◃ m ) * (s' ◃ n) ≡ (s *s s') ◃ (m *n n), 
> 
> where  _*s_ = Sign._*_,  _*n_ = Nat._*_,  _*_ = Integer._*_. 
> 
> What can be a reasonably simple proof for it? 
> 
> This my proof is checked but looks rather complex:
> 
> ----------------------------------------------------------------
> lemma _ _  0 _ =  PE.refl
> lemma s s' m 0 =  e           -- reduce to  "0 m"
>   where
>   e : (s ◃ m) * (+ 0) ≡ (s *s s') ◃ (m *n 0)
>   e = ≡begin
>         (s ◃ m) * (+ 0)        ≡[ *0 (s ◃ m) ]
>         + 0                    ≡[ PE.sym $ 0* (s ◃ m) ]
>         (+ 0) * (s ◃ m)        ≡[ PE.cong (\z → z * (s ◃ m)) $ ◃-0 s' ]
>         (s' ◃ 0) * (s ◃ m)     ≡[ lemma s' s 0 m ]
>         (s' *s s) ◃ (0 *n m)   ≡[ PE.cong (_◃_ (s' *s s)) $ 
>                                                           *n-comm 0 m ]
>         (s' *s s) ◃ (m *n 0)   ≡[ PE.cong (\sg → sg ◃ (m *n 0)) $
>                                                          *s-comm s' s ]
>         (s *s s') ◃ (m *n 0)
>       ≡end
> 
> lemma s s' (sucN m) (sucN n) =
>   ≡begin
>     (s ◃ m') * (s' ◃ n')                                   ≡[ PE.refl ]
> 
>     (sign (s ◃ m') *s sign (s' ◃ n')) ◃ ((∣ s ◃ m' ∣) *n (∣ s' ◃ n' ∣))
> 
>                            ≡[ PE.cong (\sg → sg ◃ part2) $
>                                PE.cong₂ _*s_ (sign-◃ s m) (sign-◃ s' n)
>                             ]
>     (s *s s') ◃ ((∣ s ◃ m' ∣) *n (∣ s' ◃ n' ∣))
>                            ≡[ PE.cong (_◃_ (s *s s')) $
>                                PE.cong₂ _*n_ (abs-◃ s m') (abs-◃ s' n')
>                             ]
>     (s *s s') ◃ (m' *n n')
>   ≡end
>   where
>   m'    = sucN m
>   n'    = sucN n
>   part2 = (∣ s ◃ m' ∣) *n (∣ s' ◃ n' ∣)
> ------------------------------------------------------------------------
> 
> Also there are the two strange points. 
> 
> 1) The part
>  
>       e 
>    where
>    e : ....
>    e = 
> 
> needs to be skipped (as I usually do), so that the RHS to be just 
> (begin ... end). 
> But the checker   (MAlonzo of January 8, 2014)
> 
> does not allow this, showing      [ lemma s' s 0 m ]   with yellow
> (probably a termination problem).
> So that I have avoided a termination problem by a lucky occasion with 
> extra  "e : ...".
> 
> 
> 2) In     ≡[ PE.cong (\z → z * (s ◃ m)) $ ◃-0 s' ]
> 
>   "◃-0 s'"  is a lemma which maps to  s' ◃ 0 ≡ + 0.
> This is only by normalization, but the checker reports of unsolved metas
> when I set  PE.refl  directly to the place. I tried adding hidden args
> but failed.
> 
> Thank you in advance for your notes.
> 
> ------
> Sergei
> 
> 
> 
> 
> 
> 
> 
> _______________________________________________
> Agda mailing list
> Agda at lists.chalmers.se
> https://lists.chalmers.se/mailman/listinfo/agda
> 




More information about the Agda mailing list