changeset 338:2f21eb997559

sym of sum and mul in system T
author Shinji KONO <kono@ie.u-ryukyu.ac.jp>
date Sat, 29 Mar 2014 17:12:33 +0900
parents 203593ff1e60
children 716f85bc7259
files system-f.agda system-t.agda
diffstat 2 files changed, 92 insertions(+), 5 deletions(-) [+]
line wrap: on
line diff
--- a/system-f.agda	Mon Mar 24 16:45:25 2014 +0700
+++ b/system-f.agda	Sat Mar 29 17:12:33 2014 +0900
@@ -149,6 +149,13 @@
 mul : {l : Level } {X : Set l} → Int X → Int (Int X) → Int X
 mul {l} {X} x y = It Zero (add x) y
 
+--   λ x y → y y y y x
+--   λ x y → y y y x
+--   λ z t →   (λ x y → y y y y x) (λ x y → y y y y x) (λ x y → y y y y x) t
+--   λ z t →            t t t t             t t t t             t t t t    z
+-- mul : {l : Level } {X : Set l} → Int X → Int X → Int X
+-- mul {l} {X} x y = λ z t → x z ( λ w → y ? ? )
+
 fact : {l : Level} {X : Set l} → Int _ → Int X
 fact  {l} {X} n = R (S Zero) (λ z → λ w → mul z (S w) ) n
 
--- a/system-t.agda	Mon Mar 24 16:45:25 2014 +0700
+++ b/system-t.agda	Sat Mar 29 17:12:33 2014 +0900
@@ -141,10 +141,90 @@

 
 
--- lemma14 : (x y : Int) -> sum x y  ≡ sum y x
--- lemma14 zero zero = refl
--- lemma14 zero (S t) = cong (\x -> S x )( lemma14 zero t)
--- lemma14 (S t) t' = cong (\x -> {!!} ) (lemma14 t t')
+lemma13 : (x y : Int) -> sum x (S y)  ≡ S (sum x y )
+lemma13 zero y = refl
+lemma13 (S x) y = cong (\x -> S x ) (lemma13  x y )
+
+lemma14 : (x y : Int) -> sum x y  ≡ sum y x
+lemma14 zero zero = refl
+lemma14 zero (S t) = cong (\x -> S x )( lemma14 zero t)
+lemma14 (S t) zero = cong (\x -> S x ) ( lemma14 t zero )
+lemma14 (S t) (S t') =  let open ≡-Reasoning in 
+   begin 
+       sum (S t) (S t')
+   ≡⟨⟩
+       R (S t') ( λ z -> λ w -> S z ) (S t)
+   ≡⟨⟩
+       S ( R (S t') ( λ z -> λ w -> S z ) t) 
+   ≡⟨ cong ( \x -> S x ) ( lemma13 t t') ⟩
+       S ( S ( R t' ( λ z -> λ w -> S z ) t)) 
+   ≡⟨ cong ( \x -> S (S x ) ) ( lemma14 t t') ⟩
+       S ( S ( R t ( λ z -> λ w -> S z )  t'))
+   ≡⟨ sym ( cong ( \x -> S x ) ( lemma13 t' t)) ⟩
+       S ( R (S t) ( λ z -> λ w -> S z )  t')
+   ≡⟨⟩
+       R (S t) ( λ z -> λ w -> S z ) (S t')
+   ≡⟨⟩
+       sum (S t') (S t)
+   ∎
+
+lemma15assoc' : (x y : Int) -> S ( sum x y ) ≡ sum x (S y )
+lemma15assoc' zero _ = refl
+lemma15assoc' (S x) y = cong (\x -> S x ) ( lemma15assoc' x y  )
+
+lemma15assoc : (x y z : Int) -> sum x (sum y z ) ≡ sum y (sum x z )
+lemma15assoc zero y z  = refl
+lemma15assoc (S x) y z =  let open ≡-Reasoning in
+   begin
+     sum (S x) (sum y z)
+   ≡⟨⟩
+     S ( sum x (sum y z) )
+   ≡⟨ cong (\x -> S x ) ( lemma15assoc x y z ) ⟩
+     S ( sum y ( sum x z)  )
+   ≡⟨ lemma15assoc' y (sum x z )⟩
+     sum y (S ( sum x z) )
+   ≡⟨⟩
+     sum y (sum (S x) z)
+   ∎
 
 
-                   
+lemma15'' : (x y : Int) -> mul x (S y) ≡ sum x ( mul x y )
+lemma15'' zero y = refl
+lemma15'' (S x) y =   let open ≡-Reasoning in
+   begin
+     mul (S x) (S y)
+   ≡⟨⟩
+     sum (S y) (mul x (S y))
+   ≡⟨⟩
+     S (sum y (mul x (S y)  ))
+   ≡⟨ cong (\t -> S ( sum y t )) (lemma15'' x y ) ⟩
+     S (sum y (sum x (mul x y)))
+   ≡⟨ cong (\x -> S x ) (lemma15assoc y x (mul x y)) ⟩
+     S (sum x (sum y (mul x y) ))
+   ≡⟨⟩
+     S (sum x (mul (S x) y ) )
+   ≡⟨⟩
+     sum (S x) (mul (S x) y)
+   ∎
+
+lemma15' : (x : Int) -> mul zero x  ≡ mul x zero 
+lemma15' zero = refl
+lemma15' (S x) =  lemma15' x
+
+lemma15 : (x y : Int) -> mul x y  ≡ mul y x
+lemma15 zero x =  lemma15' x
+lemma15 (S x) y =  let open ≡-Reasoning in
+   begin
+      mul (S x) y
+   ≡⟨⟩
+     sum y (mul x y )
+   ≡⟨ cong ( \x -> sum y x ) (lemma15 x y ) ⟩
+     sum y (mul y x)
+   ≡⟨ sym ( lemma15'' y x ) ⟩
+     mul y (S x) 
+   ∎
+
+
+
+
+