(* Title: HOL/Big_Operators.thy
Author: Tobias Nipkow, Lawrence C Paulson and Markus Wenzel
with contributions by Jeremy Avigad
*)
header {* Big operators and finite (non-empty) sets *}
theory Big_Operators
imports Plain
begin
subsection {* Generic monoid operation over a set *}
no_notation times (infixl "*" 70)
no_notation Groups.one ("1")
locale comm_monoid_big = comm_monoid +
fixes F :: "('b \ 'a) \ 'b set \ 'a"
assumes F_eq: "F g A = (if finite A then fold_image (op *) g 1 A else 1)"
sublocale comm_monoid_big < folding_image proof
qed (simp add: F_eq)
context comm_monoid_big
begin
lemma infinite [simp]:
"\ finite A \ F g A = 1"
by (simp add: F_eq)
lemma F_cong:
assumes "A = B" "\x. x \ B \ h x = g x"
shows "F h A = F g B"
proof cases
assume "finite A"
with assms show ?thesis unfolding `A = B` by (simp cong: cong)
next
assume "\ finite A"
then show ?thesis unfolding `A = B` by simp
qed
lemma If_cases:
fixes P :: "'b \ bool" and g h :: "'b \ 'a"
assumes fA: "finite A"
shows "F (\x. if P x then h x else g x) A =
F h (A \ {x. P x}) * F g (A \ - {x. P x})"
proof-
have a: "A = A \ {x. P x} \ A \ -{x. P x}"
"(A \ {x. P x}) \ (A \ -{x. P x}) = {}"
by blast+
from fA
have f: "finite (A \ {x. P x})" "finite (A \ -{x. P x})" by auto
let ?g = "\x. if P x then h x else g x"
from union_disjoint[OF f a(2), of ?g] a(1)
show ?thesis
by (subst (1 2) F_cong) simp_all
qed
end
text {* for ad-hoc proofs for @{const fold_image} *}
lemma (in comm_monoid_add) comm_monoid_mult:
"class.comm_monoid_mult (op +) 0"
proof qed (auto intro: add_assoc add_commute)
notation times (infixl "*" 70)
notation Groups.one ("1")
subsection {* Generalized summation over a set *}
definition (in comm_monoid_add) setsum :: "('b \ 'a) => 'b set => 'a" where
"setsum f A = (if finite A then fold_image (op +) f 0 A else 0)"
sublocale comm_monoid_add < setsum!: comm_monoid_big "op +" 0 setsum proof
qed (fact setsum_def)
abbreviation
Setsum ("\_" [1000] 999) where
"\A == setsum (%x. x) A"
text{* Now: lot's of fancy syntax. First, @{term "setsum (%x. e) A"} is
written @{text"\x\A. e"}. *}
syntax
"_setsum" :: "pttrn => 'a set => 'b => 'b::comm_monoid_add" ("(3SUM _:_. _)" [0, 51, 10] 10)
syntax (xsymbols)
"_setsum" :: "pttrn => 'a set => 'b => 'b::comm_monoid_add" ("(3\_\_. _)" [0, 51, 10] 10)
syntax (HTML output)
"_setsum" :: "pttrn => 'a set => 'b => 'b::comm_monoid_add" ("(3\_\_. _)" [0, 51, 10] 10)
translations -- {* Beware of argument permutation! *}
"SUM i:A. b" == "CONST setsum (%i. b) A"
"\i\A. b" == "CONST setsum (%i. b) A"
text{* Instead of @{term"\x\{x. P}. e"} we introduce the shorter
@{text"\x|P. e"}. *}
syntax
"_qsetsum" :: "pttrn \ bool \ 'a \ 'a" ("(3SUM _ |/ _./ _)" [0,0,10] 10)
syntax (xsymbols)
"_qsetsum" :: "pttrn \ bool \ 'a \ 'a" ("(3\_ | (_)./ _)" [0,0,10] 10)
syntax (HTML output)
"_qsetsum" :: "pttrn \ bool \ 'a \ 'a" ("(3\_ | (_)./ _)" [0,0,10] 10)
translations
"SUM x|P. t" => "CONST setsum (%x. t) {x. P}"
"\x|P. t" => "CONST setsum (%x. t) {x. P}"
print_translation {*
let
fun setsum_tr' [Abs (x, Tx, t), Const (@{const_syntax Collect}, _) $ Abs (y, Ty, P)] =
if x <> y then raise Match
else
let
val x' = Syntax_Trans.mark_bound x;
val t' = subst_bound (x', t);
val P' = subst_bound (x', P);
in Syntax.const @{syntax_const "_qsetsum"} $ Syntax_Trans.mark_bound x $ P' $ t' end
| setsum_tr' _ = raise Match;
in [(@{const_syntax setsum}, setsum_tr')] end
*}
lemma setsum_empty:
"setsum f {} = 0"
by (fact setsum.empty)
lemma setsum_insert:
"finite F ==> a \ F ==> setsum f (insert a F) = f a + setsum f F"
by (fact setsum.insert)
lemma setsum_infinite:
"~ finite A ==> setsum f A = 0"
by (fact setsum.infinite)
lemma (in comm_monoid_add) setsum_reindex:
assumes "inj_on f B" shows "setsum h (f ` B) = setsum (h \ f) B"
proof -
interpret comm_monoid_mult "op +" 0 by (fact comm_monoid_mult)
from assms show ?thesis by (auto simp add: setsum_def fold_image_reindex dest!:finite_imageD)
qed
lemma (in comm_monoid_add) setsum_reindex_id:
"inj_on f B ==> setsum f B = setsum id (f ` B)"
by (simp add: setsum_reindex)
lemma (in comm_monoid_add) setsum_reindex_nonzero:
assumes fS: "finite S"
and nz: "\ x y. x \ S \ y \ S \ x \ y \ f x = f y \ h (f x) = 0"
shows "setsum h (f ` S) = setsum (h o f) S"
using nz
proof(induct rule: finite_induct[OF fS])
case 1 thus ?case by simp
next
case (2 x F)
{assume fxF: "f x \ f ` F" hence "\y \ F . f y = f x" by auto
then obtain y where y: "y \ F" "f x = f y" by auto
from "2.hyps" y have xy: "x \ y" by auto
from "2.prems"[of x y] "2.hyps" xy y have h0: "h (f x) = 0" by simp
have "setsum h (f ` insert x F) = setsum h (f ` F)" using fxF by auto
also have "\ = setsum (h o f) (insert x F)"
unfolding setsum.insert[OF `finite F` `x\F`]
using h0
apply simp
apply (rule "2.hyps"(3))
apply (rule_tac y="y" in "2.prems")
apply simp_all
done
finally have ?case .}
moreover
{assume fxF: "f x \ f ` F"
have "setsum h (f ` insert x F) = h (f x) + setsum h (f ` F)"
using fxF "2.hyps" by simp
also have "\ = setsum (h o f) (insert x F)"
unfolding setsum.insert[OF `finite F` `x\F`]
apply simp
apply (rule cong [OF refl [of "op + (h (f x))"]])
apply (rule "2.hyps"(3))
apply (rule_tac y="y" in "2.prems")
apply simp_all
done
finally have ?case .}
ultimately show ?case by blast
qed
lemma (in comm_monoid_add) setsum_cong:
"A = B ==> (!!x. x:B ==> f x = g x) ==> setsum f A = setsum g B"
by (cases "finite A") (auto intro: setsum.cong)
lemma (in comm_monoid_add) strong_setsum_cong [cong]:
"A = B ==> (!!x. x:B =simp=> f x = g x)
==> setsum (%x. f x) A = setsum (%x. g x) B"
by (rule setsum_cong) (simp_all add: simp_implies_def)
lemma (in comm_monoid_add) setsum_cong2: "\\x. x \ A \ f x = g x\ \ setsum f A = setsum g A"
by (auto intro: setsum_cong)
lemma (in comm_monoid_add) setsum_reindex_cong:
"[|inj_on f A; B = f ` A; !!a. a:A \ g a = h (f a)|]
==> setsum h B = setsum g A"
by (simp add: setsum_reindex)
lemma (in comm_monoid_add) setsum_0[simp]: "setsum (%i. 0) A = 0"
by (cases "finite A") (erule finite_induct, auto)
lemma (in comm_monoid_add) setsum_0': "ALL a:A. f a = 0 ==> setsum f A = 0"
by (simp add:setsum_cong)
lemma (in comm_monoid_add) setsum_Un_Int: "finite A ==> finite B ==>
setsum g (A Un B) + setsum g (A Int B) = setsum g A + setsum g B"
-- {* The reversed orientation looks more natural, but LOOPS as a simprule! *}
by (fact setsum.union_inter)
lemma (in comm_monoid_add) setsum_Un_disjoint: "finite A ==> finite B
==> A Int B = {} ==> setsum g (A Un B) = setsum g A + setsum g B"
by (fact setsum.union_disjoint)
lemma setsum_mono_zero_left:
assumes fT: "finite T" and ST: "S \ T"
and z: "\i \ T - S. f i = 0"
shows "setsum f S = setsum f T"
proof-
have eq: "T = S \ (T - S)" using ST by blast
have d: "S \ (T - S) = {}" using ST by blast
from fT ST have f: "finite S" "finite (T - S)" by (auto intro: finite_subset)
show ?thesis
by (simp add: setsum_Un_disjoint[OF f d, unfolded eq[symmetric]] setsum_0'[OF z])
qed
lemma setsum_mono_zero_right:
"finite T \ S \ T \ \i \ T - S. f i = 0 \ setsum f T = setsum f S"
by(blast intro!: setsum_mono_zero_left[symmetric])
lemma setsum_mono_zero_cong_left:
assumes fT: "finite T" and ST: "S \ T"
and z: "\i \ T - S. g i = 0"
and fg: "\x. x \ S \ f x = g x"
shows "setsum f S = setsum g T"
proof-
have eq: "T = S \ (T - S)" using ST by blast
have d: "S \ (T - S) = {}" using ST by blast
from fT ST have f: "finite S" "finite (T - S)" by (auto intro: finite_subset)
show ?thesis
using fg by (simp add: setsum_Un_disjoint[OF f d, unfolded eq[symmetric]] setsum_0'[OF z])
qed
lemma setsum_mono_zero_cong_right:
assumes fT: "finite T" and ST: "S \ T"
and z: "\i \ T - S. f i = 0"
and fg: "\x. x \ S \ f x = g x"
shows "setsum f T = setsum g S"
using setsum_mono_zero_cong_left[OF fT ST z] fg[symmetric] by auto
lemma setsum_delta:
assumes fS: "finite S"
shows "setsum (\k. if k=a then b k else 0) S = (if a \ S then b a else 0)"
proof-
let ?f = "(\k. if k=a then b k else 0)"
{assume a: "a \ S"
hence "\ k\ S. ?f k = 0" by simp
hence ?thesis using a by simp}
moreover
{assume a: "a \ S"
let ?A = "S - {a}"
let ?B = "{a}"
have eq: "S = ?A \ ?B" using a by blast
have dj: "?A \ ?B = {}" by simp
from fS have fAB: "finite ?A" "finite ?B" by auto
have "setsum ?f S = setsum ?f ?A + setsum ?f ?B"
using setsum_Un_disjoint[OF fAB dj, of ?f, unfolded eq[symmetric]]
by simp
then have ?thesis using a by simp}
ultimately show ?thesis by blast
qed
lemma setsum_delta':
assumes fS: "finite S" shows
"setsum (\k. if a = k then b k else 0) S =
(if a\ S then b a else 0)"
using setsum_delta[OF fS, of a b, symmetric]
by (auto intro: setsum_cong)
lemma setsum_restrict_set:
assumes fA: "finite A"
shows "setsum f (A \ B) = setsum (\x. if x \ B then f x else 0) A"
proof-
from fA have fab: "finite (A \ B)" by auto
have aba: "A \ B \ A" by blast
let ?g = "\x. if x \ A\B then f x else 0"
from setsum_mono_zero_left[OF fA aba, of ?g]
show ?thesis by simp
qed
lemma setsum_cases:
assumes fA: "finite A"
shows "setsum (\x. if P x then f x else g x) A =
setsum f (A \ {x. P x}) + setsum g (A \ - {x. P x})"
using setsum.If_cases[OF fA] .
(*But we can't get rid of finite I. If infinite, although the rhs is 0,
the lhs need not be, since UNION I A could still be finite.*)
lemma (in comm_monoid_add) setsum_UN_disjoint:
assumes "finite I" and "ALL i:I. finite (A i)"
and "ALL i:I. ALL j:I. i \ j --> A i Int A j = {}"
shows "setsum f (UNION I A) = (\i\I. setsum f (A i))"
proof -
interpret comm_monoid_mult "op +" 0 by (fact comm_monoid_mult)
from assms show ?thesis by (simp add: setsum_def fold_image_UN_disjoint)
qed
text{*No need to assume that @{term C} is finite. If infinite, the rhs is
directly 0, and @{term "Union C"} is also infinite, hence the lhs is also 0.*}
lemma setsum_Union_disjoint:
assumes "\A\C. finite A" "\A\C. \B\C. A \ B \ A Int B = {}"
shows "setsum f (Union C) = setsum (setsum f) C"
proof cases
assume "finite C"
from setsum_UN_disjoint[OF this assms]
show ?thesis
by (simp add: SUP_def)
qed (force dest: finite_UnionD simp add: setsum_def)
(*But we can't get rid of finite A. If infinite, although the lhs is 0,
the rhs need not be, since SIGMA A B could still be finite.*)
lemma (in comm_monoid_add) setsum_Sigma:
assumes "finite A" and "ALL x:A. finite (B x)"
shows "(\x\A. (\y\B x. f x y)) = (\(x,y)\(SIGMA x:A. B x). f x y)"
proof -
interpret comm_monoid_mult "op +" 0 by (fact comm_monoid_mult)
from assms show ?thesis by (simp add: setsum_def fold_image_Sigma split_def)
qed
text{*Here we can eliminate the finiteness assumptions, by cases.*}
lemma setsum_cartesian_product:
"(\x\A. (\y\B. f x y)) = (\(x,y) \ A <*> B. f x y)"
apply (cases "finite A")
apply (cases "finite B")
apply (simp add: setsum_Sigma)
apply (cases "A={}", simp)
apply (simp)
apply (auto simp add: setsum_def
dest: finite_cartesian_productD1 finite_cartesian_productD2)
done
lemma (in comm_monoid_add) setsum_addf: "setsum (%x. f x + g x) A = (setsum f A + setsum g A)"
by (cases "finite A") (simp_all add: setsum.distrib)
subsubsection {* Properties in more restricted classes of structures *}
lemma setsum_SucD: "setsum f A = Suc n ==> EX a:A. 0 < f a"
apply (case_tac "finite A")
prefer 2 apply (simp add: setsum_def)
apply (erule rev_mp)
apply (erule finite_induct, auto)
done
lemma setsum_eq_0_iff [simp]:
"finite F ==> (setsum f F = 0) = (ALL a:F. f a = (0::nat))"
by (induct set: finite) auto
lemma setsum_eq_Suc0_iff: "finite A \
(setsum f A = Suc 0) = (EX a:A. f a = Suc 0 & (ALL b:A. a\b \ f b = 0))"
apply(erule finite_induct)
apply (auto simp add:add_is_1)
done
lemmas setsum_eq_1_iff = setsum_eq_Suc0_iff[simplified One_nat_def[symmetric]]
lemma setsum_Un_nat: "finite A ==> finite B ==>
(setsum f (A Un B) :: nat) = setsum f A + setsum f B - setsum f (A Int B)"
-- {* For the natural numbers, we have subtraction. *}
by (subst setsum_Un_Int [symmetric], auto simp add: algebra_simps)
lemma setsum_Un: "finite A ==> finite B ==>
(setsum f (A Un B) :: 'a :: ab_group_add) =
setsum f A + setsum f B - setsum f (A Int B)"
by (subst setsum_Un_Int [symmetric], auto simp add: algebra_simps)
lemma (in comm_monoid_add) setsum_eq_general_reverses:
assumes fS: "finite S" and fT: "finite T"
and kh: "\y. y \ T \ k y \ S \ h (k y) = y"
and hk: "\x. x \ S \ h x \ T \ k (h x) = x \ g (h x) = f x"
shows "setsum f S = setsum g T"
proof -
interpret comm_monoid_mult "op +" 0 by (fact comm_monoid_mult)
show ?thesis
apply (simp add: setsum_def fS fT)
apply (rule fold_image_eq_general_inverses)
apply (rule fS)
apply (erule kh)
apply (erule hk)
done
qed
lemma (in comm_monoid_add) setsum_Un_zero:
assumes fS: "finite S" and fT: "finite T"
and I0: "\x \ S\T. f x = 0"
shows "setsum f (S \ T) = setsum f S + setsum f T"
proof -
interpret comm_monoid_mult "op +" 0 by (fact comm_monoid_mult)
show ?thesis
using fS fT
apply (simp add: setsum_def)
apply (rule fold_image_Un_one)
using I0 by auto
qed
lemma setsum_UNION_zero:
assumes fS: "finite S" and fSS: "\T \ S. finite T"
and f0: "\T1 T2 x. T1\S \ T2\S \ T1 \ T2 \ x \ T1 \ x \ T2 \ f x = 0"
shows "setsum f (\S) = setsum (\T. setsum f T) S"
using fSS f0
proof(induct rule: finite_induct[OF fS])
case 1 thus ?case by simp
next
case (2 T F)
then have fTF: "finite T" "\T\F. finite T" "finite F" and TF: "T \ F"
and H: "setsum f (\ F) = setsum (setsum f) F" by auto
from fTF have fUF: "finite (\F)" by auto
from "2.prems" TF fTF
show ?case
by (auto simp add: H[symmetric] intro: setsum_Un_zero[OF fTF(1) fUF, of f])
qed
lemma setsum_diff1_nat: "(setsum f (A - {a}) :: nat) =
(if a:A then setsum f A - f a else setsum f A)"
apply (case_tac "finite A")
prefer 2 apply (simp add: setsum_def)
apply (erule finite_induct)
apply (auto simp add: insert_Diff_if)
apply (drule_tac a = a in mk_disjoint_insert, auto)
done
lemma setsum_diff1: "finite A \
(setsum f (A - {a}) :: ('a::ab_group_add)) =
(if a:A then setsum f A - f a else setsum f A)"
by (erule finite_induct) (auto simp add: insert_Diff_if)
lemma setsum_diff1'[rule_format]:
"finite A \ a \ A \ (\ x \ A. f x) = f a + (\ x \ (A - {a}). f x)"
apply (erule finite_induct[where F=A and P="% A. (a \ A \ (\ x \ A. f x) = f a + (\ x \ (A - {a}). f x))"])
apply (auto simp add: insert_Diff_if add_ac)
done
lemma setsum_diff1_ring: assumes "finite A" "a \ A"
shows "setsum f (A - {a}) = setsum f A - (f a::'a::ring)"
unfolding setsum_diff1'[OF assms] by auto
(* By Jeremy Siek: *)
lemma setsum_diff_nat:
assumes "finite B" and "B \ A"
shows "(setsum f (A - B) :: nat) = (setsum f A) - (setsum f B)"
using assms
proof induct
show "setsum f (A - {}) = (setsum f A) - (setsum f {})" by simp
next
fix F x assume finF: "finite F" and xnotinF: "x \ F"
and xFinA: "insert x F \ A"
and IH: "F \ A \ setsum f (A - F) = setsum f A - setsum f F"
from xnotinF xFinA have xinAF: "x \ (A - F)" by simp
from xinAF have A: "setsum f ((A - F) - {x}) = setsum f (A - F) - f x"
by (simp add: setsum_diff1_nat)
from xFinA have "F \ A" by simp
with IH have "setsum f (A - F) = setsum f A - setsum f F" by simp
with A have B: "setsum f ((A - F) - {x}) = setsum f A - setsum f F - f x"
by simp
from xnotinF have "A - insert x F = (A - F) - {x}" by auto
with B have C: "setsum f (A - insert x F) = setsum f A - setsum f F - f x"
by simp
from finF xnotinF have "setsum f (insert x F) = setsum f F + f x" by simp
with C have "setsum f (A - insert x F) = setsum f A - setsum f (insert x F)"
by simp
thus "setsum f (A - insert x F) = setsum f A - setsum f (insert x F)" by simp
qed
lemma setsum_diff:
assumes le: "finite A" "B \ A"
shows "setsum f (A - B) = setsum f A - ((setsum f B)::('a::ab_group_add))"
proof -
from le have finiteB: "finite B" using finite_subset by auto
show ?thesis using finiteB le
proof induct
case empty
thus ?case by auto
next
case (insert x F)
thus ?case using le finiteB
by (simp add: Diff_insert[where a=x and B=F] setsum_diff1 insert_absorb)
qed
qed
lemma setsum_mono:
assumes le: "\i. i\K \ f (i::'a) \ ((g i)::('b::{comm_monoid_add, ordered_ab_semigroup_add}))"
shows "(\i\K. f i) \ (\i\K. g i)"
proof (cases "finite K")
case True
thus ?thesis using le
proof induct
case empty
thus ?case by simp
next
case insert
thus ?case using add_mono by fastforce
qed
next
case False
thus ?thesis
by (simp add: setsum_def)
qed
lemma setsum_strict_mono:
fixes f :: "'a \ 'b::{ordered_cancel_ab_semigroup_add,comm_monoid_add}"
assumes "finite A" "A \ {}"
and "!!x. x:A \ f x < g x"
shows "setsum f A < setsum g A"
using assms
proof (induct rule: finite_ne_induct)
case singleton thus ?case by simp
next
case insert thus ?case by (auto simp: add_strict_mono)
qed
lemma setsum_strict_mono_ex1:
fixes f :: "'a \ 'b::{comm_monoid_add, ordered_cancel_ab_semigroup_add}"
assumes "finite A" and "ALL x:A. f x \ g x" and "EX a:A. f a < g a"
shows "setsum f A < setsum g A"
proof-
from assms(3) obtain a where a: "a:A" "f a < g a" by blast
have "setsum f A = setsum f ((A-{a}) \ {a})"
by(simp add:insert_absorb[OF `a:A`])
also have "\ = setsum f (A-{a}) + setsum f {a}"
using `finite A` by(subst setsum_Un_disjoint) auto
also have "setsum f (A-{a}) \ setsum g (A-{a})"
by(rule setsum_mono)(simp add: assms(2))
also have "setsum f {a} < setsum g {a}" using a by simp
also have "setsum g (A - {a}) + setsum g {a} = setsum g((A-{a}) \ {a})"
using `finite A` by(subst setsum_Un_disjoint[symmetric]) auto
also have "\ = setsum g A" by(simp add:insert_absorb[OF `a:A`])
finally show ?thesis by (metis add_right_mono add_strict_left_mono)
qed
lemma setsum_negf:
"setsum (%x. - (f x)::'a::ab_group_add) A = - setsum f A"
proof (cases "finite A")
case True thus ?thesis by (induct set: finite) auto
next
case False thus ?thesis by (simp add: setsum_def)
qed
lemma setsum_subtractf:
"setsum (%x. ((f x)::'a::ab_group_add) - g x) A =
setsum f A - setsum g A"
proof (cases "finite A")
case True thus ?thesis by (simp add: diff_minus setsum_addf setsum_negf)
next
case False thus ?thesis by (simp add: setsum_def)
qed
lemma setsum_nonneg:
assumes nn: "\x\A. (0::'a::{ordered_ab_semigroup_add,comm_monoid_add}) \ f x"
shows "0 \ setsum f A"
proof (cases "finite A")
case True thus ?thesis using nn
proof induct
case empty then show ?case by simp
next
case (insert x F)
then have "0 + 0 \ f x + setsum f F" by (blast intro: add_mono)
with insert show ?case by simp
qed
next
case False thus ?thesis by (simp add: setsum_def)
qed
lemma setsum_nonpos:
assumes np: "\x\A. f x \ (0::'a::{ordered_ab_semigroup_add,comm_monoid_add})"
shows "setsum f A \ 0"
proof (cases "finite A")
case True thus ?thesis using np
proof induct
case empty then show ?case by simp
next
case (insert x F)
then have "f x + setsum f F \ 0 + 0" by (blast intro: add_mono)
with insert show ?case by simp
qed
next
case False thus ?thesis by (simp add: setsum_def)
qed
lemma setsum_nonneg_leq_bound:
fixes f :: "'a \ 'b::{ordered_ab_group_add}"
assumes "finite s" "\i. i \ s \ f i \ 0" "(\i \ s. f i) = B" "i \ s"
shows "f i \ B"
proof -
have "0 \ (\ i \ s - {i}. f i)" and "0 \ f i"
using assms by (auto intro!: setsum_nonneg)
moreover
have "(\ i \ s - {i}. f i) + f i = B"
using assms by (simp add: setsum_diff1)
ultimately show ?thesis by auto
qed
lemma setsum_nonneg_0:
fixes f :: "'a \ 'b::{ordered_ab_group_add}"
assumes "finite s" and pos: "\ i. i \ s \