CODEWITHSUNDEEP
agda
ajayv
ajayv

Reputation: 713

Combining proofs of commutativity and associativity of addition

I am trying to proof the below lemma

 infixr 5 _~_
 _~_ = trans

lemma-+swap : ∀ a b c → a + (b + c) ≡ b + (a + c)
lemma-+swap zero b c = refl
lemma-+swap (suc a) b c = (+-assoc a b c) ~ (comm-+ a (b + c)) ~ (+-assoc b c a)

Note : I imported this file 

open import Relation.Binary.PropositionalEquality as PropEq
  using (_≡_; refl; sym; trans; cong; cong₂)

While on paper I tried in this way :

(a + b) + c equivalent a + (b + c) -- associativity
 a + (b + c) equivalent to (b + c) + a -- commutativity
(b + c) + a equi to b + (c + a) -- associativity

I wrote this in goal but getting error. I have proof of associative and commutative property. Please help.

Upvotes: 0

Views: 736

Answers (2)

Cactus
Cactus

Reputation: 27626

Transcribing the proof you already have on paper

A very nice way of writing proofs like this is to use the Relation.Binary.PropositionalEquality.≡-Reasoning module, because it enables you to write out your proof exactly how you would do it on paper:

open import Relation.Binary.PropositionalEquality as PropEq using (_≡_)
open import Data.Nat
open import Data.Nat.Properties.Simple using (+-assoc; +-comm)

lemma-+swap : ∀ a b c → a + (b + c) ≡ b + (a + c)
lemma-+swap a b c = begin
  a + (b + c) ≡⟨ {!!} ⟩
  (a + b) + c ≡⟨ {!!} ⟩
  (b + a) + c ≡⟨ {!!} ⟩
  b + (a + c) ∎
  where
    open PropEq.≡-Reasoning

Now all you need to fill in are the three holes corresponding to the three steps of the proof.

Using the semiring solver

The hassle-free way is to just let the semiring solver take care of your equality, since addition and multiplication of natural numbers form a semiring. However, I don't recommend you do this for now, since it seems you need way more experience with the fundamentals to ensure you won't fall into the trap of thinking the semiring solver is black-box magic that shouldn't be understood. So the below is meant more for other readers of this answer and not so much to OP:

open import Relation.Binary.PropositionalEquality as PropEq using (_≡_; refl)
open import Data.Nat

lemma-+swap : ∀ a b c → a + (b + c) ≡ b + (a + c)
lemma-+swap = solve 3 (λ a b c → a :+ (b :+ c) := b :+ (a :+ c)) refl
  where
    open import Data.Nat.Properties as Nat
    open Nat.SemiringSolver

Upvotes: 3

Vitus
Vitus

Reputation: 11922

You are basically doing needless case splitting. Let's check the goal in both function clauses. In the first one, we get:

lemma-+swap zero b c = ?

-- goal: b + c ≡ b + c

which is satisfied by simple refl. The second one is however:

lemma-+swap (suc a) b c = ?

-- goal: suc (a + (b + c)) ≡ b + suc (a + c)

And notice that +-assoc a b c (from Data.Nat.Properties.Simple) has a type a + b + c ≡ a + (b + c) - with no suc in sight.

So you have two options: the prefered one is to avoid case splitting and use the properties directly. The other one is to use the properties with suc a instead of a.

Your implementation also most likely won't work even if you fix the above problem.

Here, I assume your properties have the same type as the ones from the module mentioned above (which is a fair assumption, given that for the other variations the subexpression +-assoc a b c ~ comm-+ a (b + c) ~ +-assoc b c a does not typecheck).

+-assoc a b c    : a + b + c   ≡ a + (b + c)
+-comm a (b + c) : a + (b + c) ≡ b + c + a
+-assoc b c a    : b + c + a   ≡ b + (c + a)

+-assoc a b c ~ comm-+ a (b + c) ~ +-assoc b c a : a + b + c ≡ b + (c + a)       (*)

So, the subexpression has the type (*), but your goal is a + (b + c) ≡ b + (a + c).

Upvotes: 2

Related Questions