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

Sergei Meshveliani mechvel at botik.ru
Fri Jan 10 13:30:52 CET 2014


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









More information about the Agda mailing list