[Agda] Proving a + suc b == b + suc a

Jan Stolarek jan.stolarek at p.lodz.pl
Thu Nov 14 10:21:47 CET 2013


Thanks Sergei! This looks more verbose, but it makes it clear what derives from what. I like that. 
As a beginner I'm only a bit scared of all these imports - I didn't find any documentation or 
tutorial of the standard library and learning it from the source comments seems like a daunting 
task.

Janek

Dnia czwartek, 14 listopada 2013, napisałeś:
> open import Algebra  using (module CommutativeSemiring)
> open import Data.Nat using (ℕ; suc; _+_)
> open import Data.Nat.Properties as NatProp using ()
>                  renaming (commutativeSemiring to natCommSemiring)
> open import Relation.Binary.PropositionalEquality as PE using (_≡_)
> open CommutativeSemiring natCommSemiring using (+-comm)
> open PE.≡-Reasoning renaming (_≡⟨_⟩_ to _≡[_]_; begin_ to ≡begin_;
>                                                 _∎ to _≡end)
>
> +suc : (a b : ℕ) → a + suc b ≡ b + suc a
> +suc a b =
>      ≡begin
>        a + (suc b)    ≡[ +-comm a _ ]
>        (suc b) + a    ≡[ PE.refl ]  -- can be skipped
>
>        suc (b + a)    ≡[ PE.cong suc (+-comm b a) ]
>        suc (a + b)    ≡[ PE.sym PE.refl ]
>        (suc a) + b    ≡[ +-comm _ b ]
>        b + (suc a)
>      ≡end
>
> On Thu, 2013-11-14 at 09:45 +0100, Jan Stolarek wrote:
> > Thank you all for responses. I came up with this proof:
> >
> > +x : (a b : Nat) → a + suc b ≡ b + suc a
> > +x a b = trans (sym (+suc a b)) (trans (cong suc (+comm a b)) (+suc b a))
> >
> > which indeed looks a bit ugly. I'll take a look at ≡-Reasoning some time
> > in the future. For the moment I'm learning basics of Agda, so I'm
> > reinventing the wheel wherever I can :-)
> >
> > Janek
> >
> > Dnia środa, 13 listopada 2013, Andrea Vezzosi napisał:
> > > On Wed, Nov 13, 2013 at 12:27 PM, Jan Stolarek <jan.stolarek at p.lodz.pl>wrote:
> > > > [...]
> > > > Now if I could apply +suc to both sides of (cong suc (+comm a b)) I
> > > > would turn:
> > > >     suc (a + b) == suc (b + a)
> > > > into:
> > > >     a + suc b == b + suc a
> > > > which would end my proof. How can I do that?
> > >
> > > To chain proofs like that you can use transitivity:
> > >
> > >   trans : forall {A}{x y z : A} -> x == y -> y == z -> x == z
> > >   trans refl eq = eq
> > >
> > > in fact you'll need to nest them to apply something on both sides:
> > >
> > >   trans (....) (trans (cong suc (+comm a b)) (....))
> > >
> > > (Usually at this point the thing gets less than readable and we use the
> > > prettier syntax provided by ≡-Reasoning in
> > > Relation.Binary.PropositionalEquality from the stdlib.)
> > >
> > > -- Andrea
> > >
> > > > Janek
> > > > _______________________________________________
> > > > Agda mailing list
> > > > Agda at lists.chalmers.se
> > > > https://lists.chalmers.se/mailman/listinfo/agda
> >
> > _______________________________________________
> > Agda mailing list
> > Agda at lists.chalmers.se
> > https://lists.chalmers.se/mailman/listinfo/agda




More information about the Agda mailing list