298 greaterThanLessThan_def) |
298 greaterThanLessThan_def) |
299 |
299 |
300 lemma atLeastAtMostSuc_conv: "m \<le> Suc n \<Longrightarrow> {m..Suc n} = insert (Suc n) {m..n}" |
300 lemma atLeastAtMostSuc_conv: "m \<le> Suc n \<Longrightarrow> {m..Suc n} = insert (Suc n) {m..n}" |
301 by (auto simp add: atLeastAtMost_def) |
301 by (auto simp add: atLeastAtMost_def) |
302 |
302 |
|
303 subsubsection {* Image *} |
|
304 |
|
305 lemma image_add_atLeastAtMost: |
|
306 "(%n::nat. n+k) ` {i..j} = {i+k..j+k}" (is "?A = ?B") |
|
307 proof |
|
308 show "?A \<subseteq> ?B" by auto |
|
309 next |
|
310 show "?B \<subseteq> ?A" |
|
311 proof |
|
312 fix n assume a: "n : ?B" |
|
313 hence "n - k : {i..j}" by auto arith+ |
|
314 moreover have "n = (n - k) + k" using a by auto |
|
315 ultimately show "n : ?A" by blast |
|
316 qed |
|
317 qed |
|
318 |
|
319 lemma image_add_atLeastLessThan: |
|
320 "(%n::nat. n+k) ` {i..<j} = {i+k..<j+k}" (is "?A = ?B") |
|
321 proof |
|
322 show "?A \<subseteq> ?B" by auto |
|
323 next |
|
324 show "?B \<subseteq> ?A" |
|
325 proof |
|
326 fix n assume a: "n : ?B" |
|
327 hence "n - k : {i..<j}" by auto arith+ |
|
328 moreover have "n = (n - k) + k" using a by auto |
|
329 ultimately show "n : ?A" by blast |
|
330 qed |
|
331 qed |
|
332 |
|
333 corollary image_Suc_atLeastAtMost[simp]: |
|
334 "Suc ` {i..j} = {Suc i..Suc j}" |
|
335 using image_add_atLeastAtMost[where k=1] by simp |
|
336 |
|
337 corollary image_Suc_atLeastLessThan[simp]: |
|
338 "Suc ` {i..<j} = {Suc i..<Suc j}" |
|
339 using image_add_atLeastLessThan[where k=1] by simp |
|
340 |
|
341 lemma image_add_int_atLeastLessThan: |
|
342 "(%x. x + (l::int)) ` {0..<u-l} = {l..<u}" |
|
343 apply (auto simp add: image_def) |
|
344 apply (rule_tac x = "x - l" in bexI) |
|
345 apply auto |
|
346 done |
|
347 |
|
348 |
303 subsubsection {* Finiteness *} |
349 subsubsection {* Finiteness *} |
304 |
350 |
305 lemma finite_lessThan [iff]: fixes k :: nat shows "finite {..<k}" |
351 lemma finite_lessThan [iff]: fixes k :: nat shows "finite {..<k}" |
306 by (induct k) (simp_all add: lessThan_Suc) |
352 by (induct k) (simp_all add: lessThan_Suc) |
307 |
353 |
388 apply (subst image_atLeastZeroLessThan_int, assumption) |
434 apply (subst image_atLeastZeroLessThan_int, assumption) |
389 apply (rule finite_imageI) |
435 apply (rule finite_imageI) |
390 apply auto |
436 apply auto |
391 done |
437 done |
392 |
438 |
393 lemma image_atLeastLessThan_int_shift: |
|
394 "(%x. x + (l::int)) ` {0..<u-l} = {l..<u}" |
|
395 apply (auto simp add: image_def) |
|
396 apply (rule_tac x = "x - l" in bexI) |
|
397 apply auto |
|
398 done |
|
399 |
|
400 lemma finite_atLeastLessThan_int [iff]: "finite {l..<u::int}" |
439 lemma finite_atLeastLessThan_int [iff]: "finite {l..<u::int}" |
401 apply (subgoal_tac "(%x. x + l) ` {0..<u-l} = {l..<u}") |
440 apply (subgoal_tac "(%x. x + l) ` {0..<u-l} = {l..<u}") |
402 apply (erule subst) |
441 apply (erule subst) |
403 apply (rule finite_imageI) |
442 apply (rule finite_imageI) |
404 apply (rule finite_atLeastZeroLessThan_int) |
443 apply (rule finite_atLeastZeroLessThan_int) |
405 apply (rule image_atLeastLessThan_int_shift) |
444 apply (rule image_add_int_atLeastLessThan) |
406 done |
445 done |
407 |
446 |
408 lemma finite_atLeastAtMost_int [iff]: "finite {l..(u::int)}" |
447 lemma finite_atLeastAtMost_int [iff]: "finite {l..(u::int)}" |
409 by (subst atLeastLessThanPlusOne_atLeastAtMost_int [THEN sym], simp) |
448 by (subst atLeastLessThanPlusOne_atLeastAtMost_int [THEN sym], simp) |
410 |
449 |
428 apply (erule ssubst, rule card_atLeastZeroLessThan_int) |
467 apply (erule ssubst, rule card_atLeastZeroLessThan_int) |
429 apply (subgoal_tac "(%x. x + l) ` {0..<u-l} = {l..<u}") |
468 apply (subgoal_tac "(%x. x + l) ` {0..<u-l} = {l..<u}") |
430 apply (erule subst) |
469 apply (erule subst) |
431 apply (rule card_image) |
470 apply (rule card_image) |
432 apply (simp add: inj_on_def) |
471 apply (simp add: inj_on_def) |
433 apply (rule image_atLeastLessThan_int_shift) |
472 apply (rule image_add_int_atLeastLessThan) |
434 done |
473 done |
435 |
474 |
436 lemma card_atLeastAtMost_int [simp]: "card {l..u} = nat (u - l + 1)" |
475 lemma card_atLeastAtMost_int [simp]: "card {l..u} = nat (u - l + 1)" |
437 apply (subst atLeastLessThanPlusOne_atLeastAtMost_int [THEN sym]) |
476 apply (subst atLeastLessThanPlusOne_atLeastAtMost_int [THEN sym]) |
438 apply (auto simp add: compare_rls) |
477 apply (auto simp add: compare_rls) |
605 Note that for uniformity on @{typ nat} it is better to use |
644 Note that for uniformity on @{typ nat} it is better to use |
606 @{term"\<Sum>x::nat=0..<n. e"} rather than @{text"\<Sum>x<n. e"}: @{text setsum} may |
645 @{term"\<Sum>x::nat=0..<n. e"} rather than @{text"\<Sum>x<n. e"}: @{text setsum} may |
607 not provide all lemmas available for @{term"{m..<n}"} also in the |
646 not provide all lemmas available for @{term"{m..<n}"} also in the |
608 special form for @{term"{..<n}"}. *} |
647 special form for @{term"{..<n}"}. *} |
609 |
648 |
610 (* FIXME change the simplifier's treatment of congruence rules?? *) |
|
611 |
|
612 text{* This congruence rule should be used for sums over intervals as |
649 text{* This congruence rule should be used for sums over intervals as |
613 the standard theorem @{text[source]setsum_cong} does not work well |
650 the standard theorem @{text[source]setsum_cong} does not work well |
614 with the simplifier who adds the unsimplified premise @{term"x:B"} to |
651 with the simplifier who adds the unsimplified premise @{term"x:B"} to |
615 the context. *} |
652 the context. *} |
616 |
653 |
650 setsum f {m..<p} - setsum f {m..<n} = setsum f {n..<p}" |
687 setsum f {m..<p} - setsum f {m..<n} = setsum f {n..<p}" |
651 using setsum_add_nat_ivl [of m n p f,symmetric] |
688 using setsum_add_nat_ivl [of m n p f,symmetric] |
652 apply (simp add: add_ac) |
689 apply (simp add: add_ac) |
653 done |
690 done |
654 |
691 |
|
692 subsection{* Shifting bounds *} |
|
693 |
655 lemma setsum_shift_bounds_nat_ivl: |
694 lemma setsum_shift_bounds_nat_ivl: |
656 "setsum f {m+k..<n+k} = setsum (%i. f(i + k)){m..<n::nat}" |
695 "setsum f {m+k..<n+k} = setsum (%i. f(i + k)){m..<n::nat}" |
657 by (induct "n", auto simp:atLeastLessThanSuc) |
696 by (induct "n", auto simp:atLeastLessThanSuc) |
|
697 |
|
698 lemma setsum_shift_bounds_cl_nat_ivl: |
|
699 "setsum f {m+k..n+k} = setsum (%i. f(i + k)){m..n::nat}" |
|
700 apply (insert setsum_reindex[OF inj_on_add_nat, where h=f and B = "{m..n}"]) |
|
701 apply (simp add:image_add_atLeastAtMost o_def) |
|
702 done |
|
703 |
|
704 corollary setsum_shift_bounds_cl_Suc_ivl: |
|
705 "setsum f {Suc m..Suc n} = setsum (%i. f(Suc i)){m..n}" |
|
706 by (simp add:setsum_shift_bounds_cl_nat_ivl[where k=1,simplified]) |
|
707 |
|
708 corollary setsum_shift_bounds_Suc_ivl: |
|
709 "setsum f {Suc m..<Suc n} = setsum (%i. f(Suc i)){m..<n}" |
|
710 by (simp add:setsum_shift_bounds_nat_ivl[where k=1,simplified]) |
658 |
711 |
659 |
712 |
660 ML |
713 ML |
661 {* |
714 {* |
662 val Compl_atLeast = thm "Compl_atLeast"; |
715 val Compl_atLeast = thm "Compl_atLeast"; |