Thm* k,b: , f:( k  ). ( x: k. b f(x))  b k sum(f(x) | x < k) | [sum_lower_bound] |
Thm* k,b: , f:( k  ). ( x: k. f(x) b)  sum(f(x) | x < k) b k | [sum_bound] |
Thm* k: , f,g:( k  ). ( x: k. f(x) g(x))  sum(f(x) | x < k) sum(g(x) | x < k) | [sum_le] |
Thm* A,B:T List. no_repeats(T;A)  ( x:T. (x A)  (x B))  ||A|| ||B|| | [length_le] |
Thm* R:(A A' Prop), P:(B A  ), P':(B A'  ), F,G,H:(B A A), F',G',H':(B A' A'), N:(B A (B List)), N':(B A' (B List)), M:(A  ), M':(A'  ). ( i:B, s:A. P(i,s)  M(F(i,s)) M(s))  ( i:B, s:A. M(G(i,s)) M(s))  ( i:B, s:A. P(i,s)  M(H(i,s)) < M(s))  ( i:B, s:A'. P'(i,s)  M'(F'(i,s)) M'(s))  ( i:B, s:A'. M'(G'(i,s)) M'(s))  ( i:B, s:A'. P'(i,s)  M'(H'(i,s)) < M'(s))  ( j:B, u:A, v:A'. R(u,v)  (P(j,u)  P'(j,v)))  ( j:B, u:A, v:A'. R(u,v)  P(j,u)  P'(j,v)  R(F(j,u),F'(j,v)))  ( j:B, u:A, v:A'. R(u,v)  P(j,u)  P'(j,v)  R(H(j,u),H'(j,v)))  ( j:B, u:A, v:A'. R(u,v)  R(G(j,u),G'(j,v)))  ( j:B, u:A, v:A'. R(u,v)  N(j,u) = N'(j,v))  ( j:B, u:A, v:A'. R(u,v)  R(process u j where process s i == if P(i,s) then F(i,s) else G(i,s) where xs := N(i,s); s:= H(i,s); while not null xs { s := process s (hd xs); xs := tl xs; } ,process v j where process s i == if P'(i,s) then F'(i,s) else G'(i,s) where xs := N'(i,s); s:= H'(i,s); while not null xs { s := process s (hd xs); xs := tl xs; } )) | [accumulate-rel] |
Thm* M:(A  ), Q:(B A A Prop), P:(B A  ), F,G,H:(B A A), N:(B A (B List)). ( i:B, s:A. P(i,s)  M(F(i,s)) M(s))  ( i:B, s:A. M(G(i,s)) M(s))  ( i:B, s:A. P(i,s)  M(H(i,s)) < M(s))  ( j:B, u:A. P(j,u)  Q(j,u,F(j,u)))  ( j:B, u,z:A. P(j,u)  Q(j,H(j,u),z)  Q(j,u,G(j,z)))  ( j:B, u:A. Q(j,u,u))  ( i,j:B, u,v,z:A. Q(i,u,v)  Q(j,v,z)  Q(j,u,z))  ( j:B, u:A. Q(j,u,process u j where process s i == if P(i,s) then F(i,s) else G(i,s) where xs := N(i,s); s:= H(i,s); while not null xs { s := process s (hd xs); xs := tl xs; } )) | [accumulate-induction1] |
Thm* A,B:Type, P:(B A  ), F,G,H:(B A A), N:(B A (B List)), M:(A  ). ( i:B, s:A. P(i,s)  M(F(i,s)) M(s))  ( i:B, s:A. M(G(i,s)) M(s))  ( i:B, s:A. P(i,s)  M(H(i,s)) < M(s))  ( j:B, u:A. process u j where process s i == if P(i,s) then F(i,s) else G(i,s) where xs := N(i,s); s:= H(i,s); while not null xs { s := process s (hd xs); xs := tl xs; } {s:A| M(s) M(u) }) | [accumulate_wf] |
Thm* i,j,k: . i j  j k  (upto(i;k) ~ (upto(i;j) @ upto(j;k))) | [append_upto] |
Thm* i,j,k: . (k upto(i;j))  i k & k < j | [member_upto] |
Thm* x1,z,x2,x3:T List. ||z|| ||x1||  (x1 @ x2) = (z @ x3)  ( z':T List. x1 = (z @ z') & x3 = (z' @ x2)) | [equal_appends_case2] |
Thm* x1,z,x2,x3:T List. ||x1|| ||z||  (x1 @ x2) = (z @ x3)  ( z':T List. z = (x1 @ z') & x2 = (z' @ x3)) | [equal_appends_case1] |