[Agda] Matching problem at end of equational reasoning proof

Christoph Herrmann ch at cs.st-andrews.ac.uk
Wed May 27 19:54:14 CEST 2009


Hi,

the missing part is
 
2 * (n + 1) + n * (n + 1)
 ≈⟨ sym (proj₂ distrib (n + 1) 2 n) ⟩
  (2 + n) * (n + 1)

I was confused by the error message; since the error location
given was the last line including the \qed box, I assumed
that all equations before had been checked correct.

If it is the case as it appears now that the equations are
checked from bottom to top, then I would of course write them
in the same order to check them on the fly.

Cheers
 
Liang-Ting Chen wrote:
> Hi,
>
> On Wed, May 27, 2009 at 11:26 PM, Christoph Herrmann 
> <ch at cs.st-andrews.ac.uk <mailto:ch at cs.st-andrews.ac.uk>> wrote:
>
>     Hi,
>
>     I have attached an inductive proof (attempt) of Gauss' summation
>     formula.
>
>     The problem is that at the end of the equational reasoning the
>     matching
>     with the right-hand side of the type does not seem to work, namely:
>
>     (suc n) * ((suc n) + 1) against (a * (a + 1)) in the case that
>     a=(suc n)
>
>     I am wondering whether Agda still knows that it is in the case
>     a=(suc n)
>     or whether this information is available only for matching the
>     left-hand side.
>
> You pass "refl" as the proof term that tells agda that
>
> ((suc n) + 1) * (suc n)
>
> is computaionally equal to
>
> (suc n) * ((suc n) + 1), but it is not so trivial to know this fact. 
> It doesn't complain that a != (suc n) but some terms are different.
>
> Here is my proof, and I leave an unsolved hole as a practice. It might 
> be more compact, but I don't want to modify your proof too much.
>
> module Gauss where
>
> open import Algebra
> open import Data.Nat
> open import Data.Nat.Properties
> import Relation.Binary.EqReasoning
> open Relation.Binary.EqReasoning (Data.Nat.setoid)
> open import Relation.Binary.PropositionalEquality using (cong; cong₂)
> open Algebra.CommutativeSemiring commutativeSemiring
>         hiding (_+_; _*_)
>         renaming (zero to *-zero)
> open import Data.Product
> sum : ℕ -> ℕ
> sum 0 = 0
> sum (suc n) = suc n + sum n
>
> gauss-formula : (a : ℕ) -> 2 * sum a ≈ a * (a + 1)
> gauss-formula 0 = refl
> gauss-formula (suc n) =
>  begin
>  2 * sum (suc n)
>  ≈⟨ refl ⟩
>  2 * (suc n + sum n)
>  ≈⟨ proj₁ distrib 2 (suc n) (sum n) ⟩
>  (2 * suc n) + 2 * sum n
>  ≈⟨ cong (λ p -> 2 * suc n + p) (gauss-formula n) ⟩
>  (2 * suc n) + (n * (n + 1))
>  ≈⟨ cong (λ p → 2 * p + n * (n + 1)) (+-comm 1 n) ⟩
>  2 * (n + 1) + n * (n + 1)
>  ≈⟨ {!!} ⟩
>  (2 + n) * (n + 1)
>  ≈⟨ cong₂ _*_ (cong (λ p → 1 + p) (+-comm 1 n)) (+-comm n 1)⟩
>  ((suc n) + 1) * (suc n)
>  ≈⟨ *-comm ((suc n) + 1) (suc n)⟩
>  (suc n) * ((suc n) + 1)
>>
>
> -- 
> sincerely,
> Liang-Ting


-- 
  Dr. Christoph Herrmann
  University of St Andrews, Scotland/UK
  phone: office: +44 1334 461629, home: +44 1334 478648
  email: ch at cs.st-andrews.ac.uk,  c.herrmann at virgin.net
  URL:   http://www.cs.st-andrews.ac.uk/~ch
 
  The University of St Andrews is a charity registered in Scotland: No SC013532
 



More information about the Agda mailing list