annotate system-t.agda @ 790:1e7319868d77

Sets is CCC
author Shinji KONO <kono@ie.u-ryukyu.ac.jp>
date Fri, 19 Apr 2019 23:42:19 +0900
parents af321e38ecee
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
315
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
1 module system-t where
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
2 open import Relation.Binary.PropositionalEquality
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
3
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
4 record _×_ ( U : Set ) ( V : Set ) : Set where
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
5 field
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
6 π1 : U
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
7 π2 : V
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
8
346
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
9 <_,_> : {U V : Set} → U → V → U × V
315
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
10 < u , v > = record {π1 = u ; π2 = v }
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
11
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
12 open _×_
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
13
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
14 postulate U : Set
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
15 postulate V : Set
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
16
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
17 postulate v : V
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
18 postulate u : U
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
19
346
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
20 f : U → V
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
21 f = λ u → v
315
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
22
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
23
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
24 UV : Set
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
25 UV = U × V
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
26
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
27 uv : U × V
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
28 uv = < u , v >
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
29
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
30 lemma01 : π1 < u , v > ≡ u
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
31 lemma01 = refl
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
32
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
33 lemma02 : π2 < u , v > ≡ v
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
34 lemma02 = refl
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
35
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
36 lemma03 : (uv : U × V ) → < π1 uv , π2 uv > ≡ uv
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
37 lemma03 uv = refl
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
38
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
39 lemma04 : (λ x → f x ) u ≡ f u
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
40 lemma04 = refl
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
41
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
42 lemma05 : (λ x → f x ) ≡ f
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
43 lemma05 = refl
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
44
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
45 nn = λ (x : U ) → u
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
46 n1 = λ ( x : U ) → f x
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
47
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
48 data Bool : Set where
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
49 T : Bool
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
50 F : Bool
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
51
346
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
52 D : { U : Set } → U → U → Bool → U
315
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
53 D u v T = u
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
54 D u v F = v
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
55
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
56 data Int : Set where
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
57 zero : Int
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
58 S : Int → Int
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
59
346
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
60 pred : Int → Int
315
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
61 pred zero = zero
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
62 pred (S t) = t
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
63
346
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
64 R : { U : Set } → U → ( U → Int → U ) → Int → U
315
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
65 R u v zero = u
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
66 R u v ( S t ) = v (R u v t) t
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
67
346
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
68 null : Int → Bool
315
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
69 null zero = T
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
70 null (S _) = F
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
71
346
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
72 It : { T : Set } → T → (T → T) → Int → T
315
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
73 It u v zero = u
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
74 It u v ( S t ) = v (It u v t )
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
75
346
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
76 R' : { T : Set } → T → ( T → Int → T ) → Int → T
315
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
77 R' u v t = π1 ( It ( < u , zero > ) (λ x → < v (π1 x) (π2 x) , S (π2 x) > ) t )
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
78
346
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
79 sum : Int → Int → Int
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
80 sum x y = R y ( λ z → λ w → S z ) x
315
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
81
605
af321e38ecee another snat-cong approach
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 346
diff changeset
82 sum2 : Int → Int → Int
af321e38ecee another snat-cong approach
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 346
diff changeset
83 sum2 zero x = x
af321e38ecee another snat-cong approach
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 346
diff changeset
84 sum2 (S x) y = S ( sum2 x y )
af321e38ecee another snat-cong approach
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 346
diff changeset
85
af321e38ecee another snat-cong approach
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 346
diff changeset
86 cong1 : { x y : Int } -> ( f : Int -> Int ) -> x ≡ y -> f x ≡ f y
af321e38ecee another snat-cong approach
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 346
diff changeset
87 cong1 {x} {.x} f refl = refl
af321e38ecee another snat-cong approach
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 346
diff changeset
88
af321e38ecee another snat-cong approach
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 346
diff changeset
89 lemma1 : ( x y : Int ) → sum x y ≡ sum2 x y
af321e38ecee another snat-cong approach
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 346
diff changeset
90 lemma1 zero y = refl
af321e38ecee another snat-cong approach
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 346
diff changeset
91 lemma1 (S x) y = cong1 ( λ z -> S z ) ( lemma1 x y )
af321e38ecee another snat-cong approach
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 346
diff changeset
92
346
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
93 mul : Int → Int → Int
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
94 mul x y = R zero ( λ z → λ w → sum y z ) x
315
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
95
346
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
96 sum' : Int → Int → Int
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
97 sum' x y = R' y ( λ z → λ w → S z ) x
315
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
98
346
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
99 mul' : Int → Int → Int
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
100 mul' x y = R' zero ( λ z → λ w → sum y z ) x
315
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
101
346
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
102 fact : Int → Int
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
103 fact n = R (S zero) (λ z → λ w → mul (S w) z ) n
315
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
104
346
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
105 fact' : Int → Int
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
106 fact' n = R' (S zero) (λ z → λ w → mul (S w) z ) n
315
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
107
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
108 f3 = fact (S (S (S zero)))
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
109 f3' = fact' (S (S (S zero)))
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
110
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
111 lemma21 : f3 ≡ f3'
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
112 lemma21 = refl
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
113
346
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
114 lemma07 : { U : Set } → ( u : U ) → ( v : U → Int → U ) →( t : Int ) →
315
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
115 (π2 (It < u , zero > (λ x → < v (π1 x) (π2 x) , S (π2 x) >) t )) ≡ t
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
116 lemma07 u v zero = refl
346
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
117 lemma07 u v (S t) = cong ( λ x → S x ) ( lemma07 u v t )
315
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
118
346
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
119 lemma06 : { U : Set } → ( u : U ) → ( v : U → Int → U ) →( t : Int ) → ( (R u v t) ≡ (R' u v t ))
315
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
120 lemma06 u v zero = refl
346
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
121 lemma06 u v (S t) = trans ( cong ( λ x → v x t ) ( lemma06 u v t ) )
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
122 ( cong ( λ y → v (R' u v t) y ) (sym ( lemma07 u v t ) ) )
315
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
123
346
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
124 lemma08 : ( n m : Int ) → ( sum' n m ≡ sum n m )
315
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
125 lemma08 zero _ = refl
346
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
126 lemma08 (S t) y = cong ( λ x → S x ) ( lemma08 t y )
315
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
127
346
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
128 lemma09 : ( n m : Int ) → ( mul' n m ≡ mul n m )
315
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
129 lemma09 zero _ = refl
346
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
130 lemma09 (S t) y = cong ( λ x → sum y x) ( lemma09 t y )
315
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
131
346
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
132 lemma10 : ( n : Int ) → ( fact n ≡ fact n )
315
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
133 lemma10 zero = refl
346
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
134 lemma10 (S t) = cong ( λ x → mul (S t) x ) ( lemma10 t )
315
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
135
346
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
136 lemma11 : ( n : Int ) → ( fact n ≡ fact' n )
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
137 lemma11 n = lemma06 (S zero) (λ z → λ w → mul (S w) z ) n
315
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
138
346
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
139 lemma06' : { U : Set } → ( u : U ) → ( v : U → Int → U ) →( t : Int ) → ( (R u v t) ≡ (R' u v t ))
315
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
140 lemma06' u v zero = refl
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
141 lemma06' u v (S t) = let open ≡-Reasoning in
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
142 begin
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
143 R u v (S t)
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
144 ≡⟨⟩
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
145 v (R u v t) t
346
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
146 ≡⟨ cong (λ x → v x t ) ( lemma06' u v t ) ⟩
315
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
147 v (R' u v t) t
346
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
148 ≡⟨ cong (λ x → v (R' u v t) x ) ( sym ( lemma07 u v t )) ⟩
315
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
149 v (R' u v t) (π2 (It < u , zero > (λ x → < v (π1 x) (π2 x) , S (π2 x) >) t))
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
150 ≡⟨⟩
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
151 R' u v (S t)
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
152
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
153
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
154
346
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
155 sum1 : (x y : Int) → sum x (S y) ≡ S (sum x y )
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
156 sum1 zero y = refl
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
157 sum1 (S x) y = cong (λ x → S x ) (sum1 x y )
338
2f21eb997559 sym of sum and mul in system T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 324
diff changeset
158
346
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
159 sum-sym : (x y : Int) → sum x y ≡ sum y x
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
160 sum-sym zero zero = refl
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
161 sum-sym zero (S t) = cong (λ x → S x )( sum-sym zero t)
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
162 sum-sym (S t) zero = cong (λ x → S x ) ( sum-sym t zero )
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
163 sum-sym (S t) (S t') = let open ≡-Reasoning in
338
2f21eb997559 sym of sum and mul in system T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 324
diff changeset
164 begin
2f21eb997559 sym of sum and mul in system T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 324
diff changeset
165 sum (S t) (S t')
2f21eb997559 sym of sum and mul in system T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 324
diff changeset
166 ≡⟨⟩
339
716f85bc7259 assoc in sysem-T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 338
diff changeset
167 S (sum t (S t'))
346
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
168 ≡⟨ cong ( λ x → S x ) ( sum1 t t') ⟩
339
716f85bc7259 assoc in sysem-T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 338
diff changeset
169 S ( S (sum t t'))
346
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
170 ≡⟨ cong ( λ x → S (S x ) ) ( sum-sym t t') ⟩
339
716f85bc7259 assoc in sysem-T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 338
diff changeset
171 S ( S (sum t' t))
346
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
172 ≡⟨ sym ( cong ( λ x → S x ) ( sum1 t' t)) ⟩
339
716f85bc7259 assoc in sysem-T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 338
diff changeset
173 S (sum t' (S t))
338
2f21eb997559 sym of sum and mul in system T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 324
diff changeset
174 ≡⟨⟩
346
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
175 R (S t) ( λ z → λ w → S z ) (S t')
338
2f21eb997559 sym of sum and mul in system T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 324
diff changeset
176 ≡⟨⟩
2f21eb997559 sym of sum and mul in system T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 324
diff changeset
177 sum (S t') (S t)
2f21eb997559 sym of sum and mul in system T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 324
diff changeset
178
2f21eb997559 sym of sum and mul in system T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 324
diff changeset
179
346
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
180 sum-assoc : (x y z : Int) → sum x (sum y z ) ≡ sum (sum x y) z
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
181 sum-assoc zero y z = refl
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
182 sum-assoc (S x) y z = let open ≡-Reasoning in
338
2f21eb997559 sym of sum and mul in system T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 324
diff changeset
183 begin
339
716f85bc7259 assoc in sysem-T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 338
diff changeset
184 sum (S x) ( sum y z )
338
2f21eb997559 sym of sum and mul in system T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 324
diff changeset
185 ≡⟨⟩
339
716f85bc7259 assoc in sysem-T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 338
diff changeset
186 S ( sum x ( sum y z ) )
346
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
187 ≡⟨ cong (λ x → S x ) ( sum-assoc x y z) ⟩
339
716f85bc7259 assoc in sysem-T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 338
diff changeset
188 S ( sum (sum x y) z )
338
2f21eb997559 sym of sum and mul in system T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 324
diff changeset
189 ≡⟨⟩
339
716f85bc7259 assoc in sysem-T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 338
diff changeset
190 sum (S ( sum x y)) z
716f85bc7259 assoc in sysem-T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 338
diff changeset
191 ≡⟨⟩
716f85bc7259 assoc in sysem-T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 338
diff changeset
192 sum (sum (S x) y) z
338
2f21eb997559 sym of sum and mul in system T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 324
diff changeset
193
315
0d7fa6fc5979 System T and System F
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
diff changeset
194
346
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
195 mul-distr1 : (x y : Int) → mul x (S y) ≡ sum x ( mul x y )
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
196 mul-distr1 zero y = refl
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
197 mul-distr1 (S x) y = let open ≡-Reasoning in
338
2f21eb997559 sym of sum and mul in system T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 324
diff changeset
198 begin
2f21eb997559 sym of sum and mul in system T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 324
diff changeset
199 mul (S x) (S y)
2f21eb997559 sym of sum and mul in system T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 324
diff changeset
200 ≡⟨⟩
2f21eb997559 sym of sum and mul in system T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 324
diff changeset
201 sum (S y) (mul x (S y))
2f21eb997559 sym of sum and mul in system T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 324
diff changeset
202 ≡⟨⟩
2f21eb997559 sym of sum and mul in system T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 324
diff changeset
203 S (sum y (mul x (S y) ))
346
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
204 ≡⟨ cong (λ t → S ( sum y t )) (mul-distr1 x y ) ⟩
338
2f21eb997559 sym of sum and mul in system T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 324
diff changeset
205 S (sum y (sum x (mul x y)))
346
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
206 ≡⟨ cong (λ x → S x ) (
339
716f85bc7259 assoc in sysem-T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 338
diff changeset
207 begin
716f85bc7259 assoc in sysem-T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 338
diff changeset
208 sum y (sum x (mul x y))
346
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
209 ≡⟨ sum-assoc y x (mul x y) ⟩
339
716f85bc7259 assoc in sysem-T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 338
diff changeset
210 sum (sum y x) (mul x y)
346
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
211 ≡⟨ cong (λ t → sum t (mul x y)) (sum-sym y x ) ⟩
339
716f85bc7259 assoc in sysem-T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 338
diff changeset
212 sum (sum x y) (mul x y)
346
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
213 ≡⟨ sym ( sum-assoc x y (mul x y)) ⟩
339
716f85bc7259 assoc in sysem-T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 338
diff changeset
214 sum x (sum y (mul x y))
716f85bc7259 assoc in sysem-T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 338
diff changeset
215
716f85bc7259 assoc in sysem-T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 338
diff changeset
216 ) ⟩
338
2f21eb997559 sym of sum and mul in system T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 324
diff changeset
217 S (sum x (sum y (mul x y) ))
2f21eb997559 sym of sum and mul in system T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 324
diff changeset
218 ≡⟨⟩
2f21eb997559 sym of sum and mul in system T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 324
diff changeset
219 S (sum x (mul (S x) y ) )
2f21eb997559 sym of sum and mul in system T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 324
diff changeset
220 ≡⟨⟩
2f21eb997559 sym of sum and mul in system T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 324
diff changeset
221 sum (S x) (mul (S x) y)
2f21eb997559 sym of sum and mul in system T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 324
diff changeset
222
2f21eb997559 sym of sum and mul in system T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 324
diff changeset
223
346
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
224 mul-sym0 : (x : Int) → mul zero x ≡ mul x zero
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
225 mul-sym0 zero = refl
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
226 mul-sym0 (S x) = mul-sym0 x
338
2f21eb997559 sym of sum and mul in system T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 324
diff changeset
227
346
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
228 mul-sym : (x y : Int) → mul x y ≡ mul y x
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
229 mul-sym zero x = mul-sym0 x
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
230 mul-sym (S x) y = let open ≡-Reasoning in
338
2f21eb997559 sym of sum and mul in system T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 324
diff changeset
231 begin
2f21eb997559 sym of sum and mul in system T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 324
diff changeset
232 mul (S x) y
2f21eb997559 sym of sum and mul in system T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 324
diff changeset
233 ≡⟨⟩
2f21eb997559 sym of sum and mul in system T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 324
diff changeset
234 sum y (mul x y )
346
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
235 ≡⟨ cong ( λ x → sum y x ) (mul-sym x y ) ⟩
338
2f21eb997559 sym of sum and mul in system T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 324
diff changeset
236 sum y (mul y x)
346
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
237 ≡⟨ sym ( mul-distr1 y x ) ⟩
338
2f21eb997559 sym of sum and mul in system T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 324
diff changeset
238 mul y (S x)
2f21eb997559 sym of sum and mul in system T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 324
diff changeset
239
2f21eb997559 sym of sum and mul in system T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 324
diff changeset
240
2f21eb997559 sym of sum and mul in system T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 324
diff changeset
241
346
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
242 mul-ditr : (y z w : Int) → sum (mul y z) ( mul w z ) ≡ mul (sum y w) z
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
243 mul-ditr y zero w = let open ≡-Reasoning in
339
716f85bc7259 assoc in sysem-T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 338
diff changeset
244 begin
716f85bc7259 assoc in sysem-T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 338
diff changeset
245 sum (mul y zero) ( mul w zero )
346
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
246 ≡⟨ cong ( λ t → sum (mul y zero ) t ) (mul-sym w zero ) ⟩
339
716f85bc7259 assoc in sysem-T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 338
diff changeset
247 sum (mul y zero ) ( mul zero w )
346
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
248 ≡⟨ cong ( λ t → sum t zero ) (mul-sym y zero ) ⟩
339
716f85bc7259 assoc in sysem-T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 338
diff changeset
249 sum zero zero
716f85bc7259 assoc in sysem-T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 338
diff changeset
250 ≡⟨⟩
716f85bc7259 assoc in sysem-T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 338
diff changeset
251 mul zero (sum y w)
346
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
252 ≡⟨ mul-sym0 (sum y w) ⟩
339
716f85bc7259 assoc in sysem-T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 338
diff changeset
253 mul (sum y w) zero
716f85bc7259 assoc in sysem-T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 338
diff changeset
254
346
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
255 mul-ditr y (S z) w = let open ≡-Reasoning in
339
716f85bc7259 assoc in sysem-T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 338
diff changeset
256 begin
716f85bc7259 assoc in sysem-T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 338
diff changeset
257 sum (mul y (S z)) ( mul w (S z) )
346
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
258 ≡⟨ cong ( λ t → sum t ( mul w (S z ))) (mul-distr1 y z) ⟩
339
716f85bc7259 assoc in sysem-T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 338
diff changeset
259 sum ( sum y ( mul y z)) ( mul w (S z) )
346
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
260 ≡⟨ cong ( λ t → sum ( sum y ( mul y z)) t ) (mul-distr1 w z) ⟩
339
716f85bc7259 assoc in sysem-T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 338
diff changeset
261 sum ( sum y ( mul y z)) ( sum w ( mul w z) )
346
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
262 ≡⟨ sym ( sum-assoc y (mul y z ) ( sum w ( mul w z) ) ) ⟩
339
716f85bc7259 assoc in sysem-T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 338
diff changeset
263 sum y ( sum ( mul y z) ( sum w ( mul w z) ))
346
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
264 ≡⟨ cong ( λ t → sum y t) (sum-sym ( mul y z) ( sum w ( mul w z) )) ⟩
339
716f85bc7259 assoc in sysem-T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 338
diff changeset
265 sum y ( sum ( sum w ( mul w z) )( mul y z))
346
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
266 ≡⟨ sym ( cong ( λ t → sum y t) (sum-assoc w (mul w z) (mul y z )) ) ⟩
339
716f85bc7259 assoc in sysem-T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 338
diff changeset
267 sum y ( sum w (sum ( mul w z) ( mul y z)) )
346
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
268 ≡⟨ cong ( λ t → sum y (sum w t) ) ( sum-sym (mul w z) (mul y z )) ⟩
339
716f85bc7259 assoc in sysem-T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 338
diff changeset
269 sum y ( sum w (sum ( mul y z) ( mul w z)) )
346
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
270 ≡⟨ cong ( λ t → sum y (sum w t) ) ( mul-ditr y z w ) ⟩
339
716f85bc7259 assoc in sysem-T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 338
diff changeset
271 sum y ( sum w (mul (sum y w) z) )
346
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
272 ≡⟨ sum-assoc y w (mul (sum y w) z) ⟩
339
716f85bc7259 assoc in sysem-T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 338
diff changeset
273 sum (sum y w) ( mul (sum y w) z )
346
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
274 ≡⟨ sym ( mul-distr1 (sum y w) z ) ⟩
339
716f85bc7259 assoc in sysem-T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 338
diff changeset
275 mul (sum y w) (S z)
716f85bc7259 assoc in sysem-T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 338
diff changeset
276
716f85bc7259 assoc in sysem-T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 338
diff changeset
277
716f85bc7259 assoc in sysem-T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 338
diff changeset
278
346
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
279 mul-assoc : (x y z : Int) → mul x (mul y z ) ≡ mul (mul x y) z
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
280 mul-assoc zero y z = refl
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
281 mul-assoc (S x) y z = let open ≡-Reasoning in
339
716f85bc7259 assoc in sysem-T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 338
diff changeset
282 begin
716f85bc7259 assoc in sysem-T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 338
diff changeset
283 mul (S x) (mul y z )
716f85bc7259 assoc in sysem-T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 338
diff changeset
284 ≡⟨⟩
716f85bc7259 assoc in sysem-T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 338
diff changeset
285 sum (mul y z) ( mul x ( mul y z ) )
346
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
286 ≡⟨ cong (λ t → sum (mul y z) t ) (mul-assoc x y z ) ⟩
339
716f85bc7259 assoc in sysem-T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 338
diff changeset
287 sum (mul y z) ( mul ( mul x y) z )
346
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 340
diff changeset
288 ≡⟨ mul-ditr y z (mul x y) ⟩
339
716f85bc7259 assoc in sysem-T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 338
diff changeset
289 mul (sum y (mul x y)) z
716f85bc7259 assoc in sysem-T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 338
diff changeset
290 ≡⟨⟩
716f85bc7259 assoc in sysem-T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 338
diff changeset
291 mul (mul (S x) y) z
716f85bc7259 assoc in sysem-T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 338
diff changeset
292
338
2f21eb997559 sym of sum and mul in system T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 324
diff changeset
293
2f21eb997559 sym of sum and mul in system T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 324
diff changeset
294
2f21eb997559 sym of sum and mul in system T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 324
diff changeset
295
339
716f85bc7259 assoc in sysem-T
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 338
diff changeset
296