# Library mathcomp.ssreflect.bigop

(* (c) Copyright 2006-2016 Microsoft Corporation and Inria.
Distributed under the terms of CeCILL-B.                                  *)

From mathcomp Require Import ssreflect ssrbool ssrfun eqtype ssrnat seq path.
From mathcomp Require Import div fintype tuple finfun.

This file provides a generic definition for iterating an operator over a set of indices (bigop); this big operator is parameterized by the return type (R), the type of indices (I), the operator (op), the default value on empty lists (idx), the range of indices (r), the filter applied on this range (P) and the expression we are iterating (F). The definition is not to be used directly, but via the wide range of notations provided and which support a natural use of big operators. To improve performance of the Coq typechecker on large expressions, the bigop constant is OPAQUE. It can however be unlocked to reveal the transparent constant reducebig, to let Coq expand summation on an explicit sequence with an explicit test. The lemmas can be classified according to the operator being iterated: 1. Results independent of the operator: extensionality with respect to the range of indices, to the filtering predicate or to the expression being iterated; reindexing, widening or narrowing of the range of indices; we provide lemmas for the special cases where indices are natural numbers or bounded natural numbers ("ordinals"). We supply several "functional" induction principles that can be used with the ssreflect 1.3 "elim" tactic to do induction over the index range for up to 3 bigops simultaneously. 2. Results depending on the properties of the operator: We distinguish: monoid laws (op is associative, idx is an identity element), abelian monoid laws (op is also commutative), and laws with a distributive operation (semirings). Examples of such results are splitting, permuting, and exchanging bigops. A special section is dedicated to big operators on natural numbers.
Notations: The general form for iterated operators is <bigop>_<range> <general_term>
• <bigop> is one of \big[op/idx], \sum, \prod, or \max (see below).
• <general_term> can be any expression.
• <range> binds an index variable in <general_term>; <range> is one of (i <- s) i ranges over the sequence s. (m <= i < n) i ranges over the nat interval m, m+1, ..., n-1. (i < n) i ranges over the (finite) type 'I_n (i.e., ordinal n). (i : T) i ranges over the finite type T. i or (i) i ranges over its (inferred) finite type. (i in A) i ranges over the elements that satisfy the collective predicate A (the domain of A must be a finite type). (i <- s | <condition>) limits the range to the i for which <condition> holds. <condition> can be any expression that coerces to bool, and may mention the bound index i. All six kinds of ranges above can have a <condition> part.
• One can use the "\big[op/idx]" notations for any operator.
• BIG_F and BIG_P are pattern abbreviations for the <general_term> and <condition> part of a \big ... expression; for (i in A) and (i in A | C) ranges the term matched by BIG_P will include the i \in A condition.
• The (locked) head constant of a \big notation is bigop.
• The "\sum", "\prod" and "\max" notations in the %N scope are used for natural numbers with addition, multiplication and maximum (and their corresponding neutral elements), respectively.
• The "\sum" and "\prod" reserved notations are overloaded in ssralg in the %R scope; in mxalgebra, vector & falgebra in the %MS and %VS scopes; "\prod" is also overloaded in fingroup, in the %g and %G scopes.
• We reserve "\bigcup" and "\bigcap" notations for iterated union and intersection (of sets, groups, vector spaces, etc).
Tips for using lemmas in this file: To apply a lemma for a specific operator: if no special property is required for the operator, simply apply the lemma; if the lemma needs certain properties for the operator, make sure the appropriate Canonical instances are declared.
Interfaces for operator properties are packaged in the Monoid submodule: Monoid.law idx == interface (keyed on the operator) for associative operators with identity element idx. Monoid.com_law idx == extension (telescope) of Monoid.law for operators that are also commutative. Monoid.mul_law abz == interface for operators with absorbing (zero) element abz. Monoid.add_law idx mop == extension of Monoid.com_law for operators over which operation mop distributes (mop will often also have a Monoid.mul_law idx structure). [law of op], [com_law of op], [mul_law of op], [add_law mop of op] == syntax for cloning Monoid structures. Monoid.Theory == submodule containing basic generic algebra lemmas for operators satisfying the Monoid interfaces. Monoid.simpm == generic monoid simplification rewrite multirule. oAC op == convert an AC operator op : T -> T -> T to a Monoid.com_law on option T Monoid structures are predeclared for many basic operators: (_ && _)%B, (_ || _)%B, (_ (+) _)%B (exclusive or) , (_ + _)%N, (_ * _)%N, maxn, gcdn, lcmn and (_ ++ _)%SEQ (list concatenation).
Additional documentation for this file: Y. Bertot, G. Gonthier, S. Ould Biha and I. Pasca. Canonical Big Operators. In TPHOLs 2008, LNCS vol. 5170, Springer. Article available at: http://hal.inria.fr/docs/00/33/11/93/PDF/main.pdf
Examples of use in: poly.v, matrix.v

Set Implicit Arguments.

Declare Scope big_scope.

Reserved Notation "\big [ op / idx ]_ i F"
(at level 36, F at level 36, op, idx at level 10, i at level 0,
right associativity,
format "'[' \big [ op / idx ]_ i '/ ' F ']'").
Reserved Notation "\big [ op / idx ]_ ( i <- r | P ) F"
(at level 36, F at level 36, op, idx at level 10, i, r at level 50,
format "'[' \big [ op / idx ]_ ( i <- r | P ) '/ ' F ']'").
Reserved Notation "\big [ op / idx ]_ ( i <- r ) F"
(at level 36, F at level 36, op, idx at level 10, i, r at level 50,
format "'[' \big [ op / idx ]_ ( i <- r ) '/ ' F ']'").
Reserved Notation "\big [ op / idx ]_ ( m <= i < n | P ) F"
(at level 36, F at level 36, op, idx at level 10, m, i, n at level 50,
format "'[' \big [ op / idx ]_ ( m <= i < n | P ) F ']'").
Reserved Notation "\big [ op / idx ]_ ( m <= i < n ) F"
(at level 36, F at level 36, op, idx at level 10, i, m, n at level 50,
format "'[' \big [ op / idx ]_ ( m <= i < n ) '/ ' F ']'").
Reserved Notation "\big [ op / idx ]_ ( i | P ) F"
(at level 36, F at level 36, op, idx at level 10, i at level 50,
format "'[' \big [ op / idx ]_ ( i | P ) '/ ' F ']'").
Reserved Notation "\big [ op / idx ]_ ( i : t | P ) F"
(at level 36, F at level 36, op, idx at level 10, i at level 50,
format "'[' \big [ op / idx ]_ ( i : t | P ) '/ ' F ']'").
Reserved Notation "\big [ op / idx ]_ ( i : t ) F"
(at level 36, F at level 36, op, idx at level 10, i at level 50,
format "'[' \big [ op / idx ]_ ( i : t ) '/ ' F ']'").
Reserved Notation "\big [ op / idx ]_ ( i < n | P ) F"
(at level 36, F at level 36, op, idx at level 10, i, n at level 50,
format "'[' \big [ op / idx ]_ ( i < n | P ) '/ ' F ']'").
Reserved Notation "\big [ op / idx ]_ ( i < n ) F"
(at level 36, F at level 36, op, idx at level 10, i, n at level 50,
format "'[' \big [ op / idx ]_ ( i < n ) F ']'").
Reserved Notation "\big [ op / idx ]_ ( i 'in' A | P ) F"
(at level 36, F at level 36, op, idx at level 10, i, A at level 50,
format "'[' \big [ op / idx ]_ ( i 'in' A | P ) '/ ' F ']'").
Reserved Notation "\big [ op / idx ]_ ( i 'in' A ) F"
(at level 36, F at level 36, op, idx at level 10, i, A at level 50,
format "'[' \big [ op / idx ]_ ( i 'in' A ) '/ ' F ']'").

Reserved Notation "\sum_ i F"
(at level 41, F at level 41, i at level 0,
right associativity,
format "'[' \sum_ i '/ ' F ']'").
Reserved Notation "\sum_ ( i <- r | P ) F"
(at level 41, F at level 41, i, r at level 50,
format "'[' \sum_ ( i <- r | P ) '/ ' F ']'").
Reserved Notation "\sum_ ( i <- r ) F"
(at level 41, F at level 41, i, r at level 50,
format "'[' \sum_ ( i <- r ) '/ ' F ']'").
Reserved Notation "\sum_ ( m <= i < n | P ) F"
(at level 41, F at level 41, i, m, n at level 50,
format "'[' \sum_ ( m <= i < n | P ) '/ ' F ']'").
Reserved Notation "\sum_ ( m <= i < n ) F"
(at level 41, F at level 41, i, m, n at level 50,
format "'[' \sum_ ( m <= i < n ) '/ ' F ']'").
Reserved Notation "\sum_ ( i | P ) F"
(at level 41, F at level 41, i at level 50,
format "'[' \sum_ ( i | P ) '/ ' F ']'").
Reserved Notation "\sum_ ( i : t | P ) F"
(at level 41, F at level 41, i at level 50). (* only parsing *)
Reserved Notation "\sum_ ( i : t ) F"
(at level 41, F at level 41, i at level 50). (* only parsing *)
Reserved Notation "\sum_ ( i < n | P ) F"
(at level 41, F at level 41, i, n at level 50,
format "'[' \sum_ ( i < n | P ) '/ ' F ']'").
Reserved Notation "\sum_ ( i < n ) F"
(at level 41, F at level 41, i, n at level 50,
format "'[' \sum_ ( i < n ) '/ ' F ']'").
Reserved Notation "\sum_ ( i 'in' A | P ) F"
(at level 41, F at level 41, i, A at level 50,
format "'[' \sum_ ( i 'in' A | P ) '/ ' F ']'").
Reserved Notation "\sum_ ( i 'in' A ) F"
(at level 41, F at level 41, i, A at level 50,
format "'[' \sum_ ( i 'in' A ) '/ ' F ']'").

Reserved Notation "\max_ i F"
(at level 41, F at level 41, i at level 0,
format "'[' \max_ i '/ ' F ']'").
Reserved Notation "\max_ ( i <- r | P ) F"
(at level 41, F at level 41, i, r at level 50,
format "'[' \max_ ( i <- r | P ) '/ ' F ']'").
Reserved Notation "\max_ ( i <- r ) F"
(at level 41, F at level 41, i, r at level 50,
format "'[' \max_ ( i <- r ) '/ ' F ']'").
Reserved Notation "\max_ ( m <= i < n | P ) F"
(at level 41, F at level 41, i, m, n at level 50,
format "'[' \max_ ( m <= i < n | P ) '/ ' F ']'").
Reserved Notation "\max_ ( m <= i < n ) F"
(at level 41, F at level 41, i, m, n at level 50,
format "'[' \max_ ( m <= i < n ) '/ ' F ']'").
Reserved Notation "\max_ ( i | P ) F"
(at level 41, F at level 41, i at level 50,
format "'[' \max_ ( i | P ) '/ ' F ']'").
Reserved Notation "\max_ ( i : t | P ) F"
(at level 41, F at level 41, i at level 50). (* only parsing *)
Reserved Notation "\max_ ( i : t ) F"
(at level 41, F at level 41, i at level 50). (* only parsing *)
Reserved Notation "\max_ ( i < n | P ) F"
(at level 41, F at level 41, i, n at level 50,
format "'[' \max_ ( i < n | P ) '/ ' F ']'").
Reserved Notation "\max_ ( i < n ) F"
(at level 41, F at level 41, i, n at level 50,
format "'[' \max_ ( i < n ) F ']'").
Reserved Notation "\max_ ( i 'in' A | P ) F"
(at level 41, F at level 41, i, A at level 50,
format "'[' \max_ ( i 'in' A | P ) '/ ' F ']'").
Reserved Notation "\max_ ( i 'in' A ) F"
(at level 41, F at level 41, i, A at level 50,
format "'[' \max_ ( i 'in' A ) '/ ' F ']'").

Reserved Notation "\prod_ i F"
(at level 36, F at level 36, i at level 0,
format "'[' \prod_ i '/ ' F ']'").
Reserved Notation "\prod_ ( i <- r | P ) F"
(at level 36, F at level 36, i, r at level 50,
format "'[' \prod_ ( i <- r | P ) '/ ' F ']'").
Reserved Notation "\prod_ ( i <- r ) F"
(at level 36, F at level 36, i, r at level 50,
format "'[' \prod_ ( i <- r ) '/ ' F ']'").
Reserved Notation "\prod_ ( m <= i < n | P ) F"
(at level 36, F at level 36, i, m, n at level 50,
format "'[' \prod_ ( m <= i < n | P ) '/ ' F ']'").
Reserved Notation "\prod_ ( m <= i < n ) F"
(at level 36, F at level 36, i, m, n at level 50,
format "'[' \prod_ ( m <= i < n ) '/ ' F ']'").
Reserved Notation "\prod_ ( i | P ) F"
(at level 36, F at level 36, i at level 50,
format "'[' \prod_ ( i | P ) '/ ' F ']'").
Reserved Notation "\prod_ ( i : t | P ) F"
(at level 36, F at level 36, i at level 50). (* only parsing *)
Reserved Notation "\prod_ ( i : t ) F"
(at level 36, F at level 36, i at level 50). (* only parsing *)
Reserved Notation "\prod_ ( i < n | P ) F"
(at level 36, F at level 36, i, n at level 50,
format "'[' \prod_ ( i < n | P ) '/ ' F ']'").
Reserved Notation "\prod_ ( i < n ) F"
(at level 36, F at level 36, i, n at level 50,
format "'[' \prod_ ( i < n ) '/ ' F ']'").
Reserved Notation "\prod_ ( i 'in' A | P ) F"
(at level 36, F at level 36, i, A at level 50,
format "'[' \prod_ ( i 'in' A | P ) F ']'").
Reserved Notation "\prod_ ( i 'in' A ) F"
(at level 36, F at level 36, i, A at level 50,
format "'[' \prod_ ( i 'in' A ) '/ ' F ']'").

Reserved Notation "\bigcup_ i F"
(at level 41, F at level 41, i at level 0,
format "'[' \bigcup_ i '/ ' F ']'").
Reserved Notation "\bigcup_ ( i <- r | P ) F"
(at level 41, F at level 41, i, r at level 50,
format "'[' \bigcup_ ( i <- r | P ) '/ ' F ']'").
Reserved Notation "\bigcup_ ( i <- r ) F"
(at level 41, F at level 41, i, r at level 50,
format "'[' \bigcup_ ( i <- r ) '/ ' F ']'").
Reserved Notation "\bigcup_ ( m <= i < n | P ) F"
(at level 41, F at level 41, m, i, n at level 50,
format "'[' \bigcup_ ( m <= i < n | P ) '/ ' F ']'").
Reserved Notation "\bigcup_ ( m <= i < n ) F"
(at level 41, F at level 41, i, m, n at level 50,
format "'[' \bigcup_ ( m <= i < n ) '/ ' F ']'").
Reserved Notation "\bigcup_ ( i | P ) F"
(at level 41, F at level 41, i at level 50,
format "'[' \bigcup_ ( i | P ) '/ ' F ']'").
Reserved Notation "\bigcup_ ( i : t | P ) F"
(at level 41, F at level 41, i at level 50,
format "'[' \bigcup_ ( i : t | P ) '/ ' F ']'").
Reserved Notation "\bigcup_ ( i : t ) F"
(at level 41, F at level 41, i at level 50,
format "'[' \bigcup_ ( i : t ) '/ ' F ']'").
Reserved Notation "\bigcup_ ( i < n | P ) F"
(at level 41, F at level 41, i, n at level 50,
format "'[' \bigcup_ ( i < n | P ) '/ ' F ']'").
Reserved Notation "\bigcup_ ( i < n ) F"
(at level 41, F at level 41, i, n at level 50,
format "'[' \bigcup_ ( i < n ) '/ ' F ']'").
Reserved Notation "\bigcup_ ( i 'in' A | P ) F"
(at level 41, F at level 41, i, A at level 50,
format "'[' \bigcup_ ( i 'in' A | P ) '/ ' F ']'").
Reserved Notation "\bigcup_ ( i 'in' A ) F"
(at level 41, F at level 41, i, A at level 50,
format "'[' \bigcup_ ( i 'in' A ) '/ ' F ']'").

Reserved Notation "\bigcap_ i F"
(at level 41, F at level 41, i at level 0,
format "'[' \bigcap_ i '/ ' F ']'").
Reserved Notation "\bigcap_ ( i <- r | P ) F"
(at level 41, F at level 41, i, r at level 50,
format "'[' \bigcap_ ( i <- r | P ) F ']'").
Reserved Notation "\bigcap_ ( i <- r ) F"
(at level 41, F at level 41, i, r at level 50,
format "'[' \bigcap_ ( i <- r ) '/ ' F ']'").
Reserved Notation "\bigcap_ ( m <= i < n | P ) F"
(at level 41, F at level 41, m, i, n at level 50,
format "'[' \bigcap_ ( m <= i < n | P ) '/ ' F ']'").
Reserved Notation "\bigcap_ ( m <= i < n ) F"
(at level 41, F at level 41, i, m, n at level 50,
format "'[' \bigcap_ ( m <= i < n ) '/ ' F ']'").
Reserved Notation "\bigcap_ ( i | P ) F"
(at level 41, F at level 41, i at level 50,
format "'[' \bigcap_ ( i | P ) '/ ' F ']'").
Reserved Notation "\bigcap_ ( i : t | P ) F"
(at level 41, F at level 41, i at level 50,
format "'[' \bigcap_ ( i : t | P ) '/ ' F ']'").
Reserved Notation "\bigcap_ ( i : t ) F"
(at level 41, F at level 41, i at level 50,
format "'[' \bigcap_ ( i : t ) '/ ' F ']'").
Reserved Notation "\bigcap_ ( i < n | P ) F"
(at level 41, F at level 41, i, n at level 50,
format "'[' \bigcap_ ( i < n | P ) '/ ' F ']'").
Reserved Notation "\bigcap_ ( i < n ) F"
(at level 41, F at level 41, i, n at level 50,
format "'[' \bigcap_ ( i < n ) '/ ' F ']'").
Reserved Notation "\bigcap_ ( i 'in' A | P ) F"
(at level 41, F at level 41, i, A at level 50,
format "'[' \bigcap_ ( i 'in' A | P ) '/ ' F ']'").
Reserved Notation "\bigcap_ ( i 'in' A ) F"
(at level 41, F at level 41, i, A at level 50,
format "'[' \bigcap_ ( i 'in' A ) '/ ' F ']'").

Module Monoid.

Section Definitions.
Variables (T : Type) (idm : T).

Structure law := Law {
operator : T T T;
_ : associative operator;
_ : left_id idm operator;
_ : right_id idm operator
}.

Structure com_law := ComLaw {
com_operator : law;
_ : commutative com_operator
}.

Structure mul_law := MulLaw {
mul_operator : T T T;
_ : left_zero idm mul_operator;
_ : right_zero idm mul_operator
}.

}.

Let op_id (op1 op2 : T T T) := phant_id op1 op2.

Definition clone_law op :=
fun (opL : law) & op_id opL op
fun opmA op1m opm1 (opL' := @Law op opmA op1m opm1)
& phant_id opL' opLopL'.

Definition clone_com_law op :=
fun (opL : law) (opC : com_law) & op_id opL op & op_id opC op
fun opmC (opC' := @ComLaw opL opmC) & phant_id opC' opCopC'.

Definition clone_mul_law op :=
fun (opM : mul_law) & op_id opM op
fun op0m opm0 (opM' := @MulLaw op op0m opm0) & phant_id opM' opMopM'.

fun (opC : com_law) (opA : add_law mop) & op_id opC aop & op_id opA aop
fun mopDm mopmD (opA' := @AddLaw mop opC mopDm mopmD)
& phant_id opA' opAopA'.

End Definitions.

Module Import Exports.
Coercion operator : law >-> Funclass.
Coercion com_operator : com_law >-> law.
Coercion mul_operator : mul_law >-> Funclass.
Notation "[ 'law' 'of' f ]" := (@clone_law _ _ f _ id _ _ _ id)
(at level 0, format"[ 'law' 'of' f ]") : form_scope.
Notation "[ 'com_law' 'of' f ]" := (@clone_com_law _ _ f _ _ id id _ id)
(at level 0, format "[ 'com_law' 'of' f ]") : form_scope.
Notation "[ 'mul_law' 'of' f ]" := (@clone_mul_law _ _ f _ id _ _ id)
(at level 0, format"[ 'mul_law' 'of' f ]") : form_scope.
Notation "[ 'add_law' m 'of' a ]" := (@clone_add_law _ _ m a _ _ id id _ _ id)
(at level 0, format "[ 'add_law' m 'of' a ]") : form_scope.
End Exports.

Section CommutativeAxioms.

Variable (T : Type) (zero one : T) (mul add : T T T) (inv : T T).
Hypothesis mulC : commutative mul.

Lemma mulC_id : left_id one mul right_id one mul.

Lemma mulC_zero : left_zero zero mul right_zero zero mul.

End CommutativeAxioms.

Module Theory.

Section Theory.
Variables (T : Type) (idm : T).

Section Plain.
Variable mul : law idm.
Lemma mul1m : left_id idm mul.
Lemma mulm1 : right_id idm mul.
Lemma mulmA : associative mul.
Lemma iteropE n x : iterop n mul x idm = iter n (mul x) idm.
End Plain.

Section Commutative.
Variable mul : com_law idm.
Lemma mulmC : commutative mul.
Lemma mulmCA : left_commutative mul.
Lemma mulmAC : right_commutative mul.
Lemma mulmACA : interchange mul mul.
End Commutative.

Section Mul.
Variable mul : mul_law idm.
Lemma mul0m : left_zero idm mul.
Lemma mulm0 : right_zero idm mul.
End Mul.

Lemma mulmDl : left_distributive mul add.
Lemma mulmDr : right_distributive mul add.

Definition simpm := (mulm1, mulm0, mul1m, mul0m, mulmA).

End Theory.

End Theory.
Include Theory.

End Monoid.
Export Monoid.Exports.

Section PervasiveMonoids.

Import Monoid.

Canonical andb_monoid := Law andbA andTb andbT.
Canonical andb_comoid := ComLaw andbC.

Canonical andb_muloid := MulLaw andFb andbF.
Canonical orb_monoid := Law orbA orFb orbF.
Canonical orb_comoid := ComLaw orbC.
Canonical orb_muloid := MulLaw orTb orbT.

Canonical muln_monoid := Law mulnA mul1n muln1.
Canonical muln_comoid := ComLaw mulnC.
Canonical muln_muloid := MulLaw mul0n muln0.

Canonical maxn_monoid := Law maxnA max0n maxn0.
Canonical maxn_comoid := ComLaw maxnC.

Canonical gcdn_monoid := Law gcdnA gcd0n gcdn0.
Canonical gcdn_comoid := ComLaw gcdnC.
Canonical gcdnDoid := AddLaw muln_gcdl muln_gcdr.

Canonical lcmn_monoid := Law lcmnA lcm1n lcmn1.
Canonical lcmn_comoid := ComLaw lcmnC.

Canonical cat_monoid T := Law (@catA T) (@cat0s T) (@cats0 T).

End PervasiveMonoids.

Unit test for the [...law of ... ] Notations Definition myp := addn. Definition mym := muln. Canonical myp_mon := [law of myp]. Canonical myp_cmon := [com_law of myp]. Canonical mym_mul := [mul_law of mym]. Canonical myp_add := [add_law _ of myp]. Print myp_add. Print Canonical Projections.

Delimit Scope big_scope with BIG.
Open Scope big_scope.

The bigbody wrapper is a workaround for a quirk of the Coq pretty-printer, which would fail to redisplay the \big notation when the <general_term> or <condition> do not depend on the bound index. The BigBody constructor packages both in in a term in which i occurs; it also depends on the iterated <op>, as this can give more information on the expected type of the <general_term>, thus allowing for the insertion of coercions.
Variant bigbody R I := BigBody of I & (R R R) & bool & R.

Definition applybig {R I} (body : bigbody R I) x :=
let: BigBody _ op b v := body in if b then op v x else x.

Definition reducebig R I idx r (body : I bigbody R I) :=
foldr (applybig \o body) idx r.

Module Type BigOpSig.
Parameter bigop : R I, R seq I (I bigbody R I) R.
Axiom bigopE : bigop = reducebig.
End BigOpSig.

Module BigOp : BigOpSig.
Definition bigop := reducebig.
Lemma bigopE : bigop = reducebig.
End BigOp.

Notation bigop := BigOp.bigop (only parsing).
Canonical bigop_unlock := Unlockable BigOp.bigopE.

Definition index_iota m n := iota m (n - m).

Lemma mem_index_iota m n i : i \in index_iota m n = (m i < n).

Legacy mathcomp scripts have been relying on the fact that enum A and filter A (index_enum T) are convertible. This is likely to change in the next mathcomp release when enum, pick, subset and card are generalised to predicates with finite support in a choiceType - in fact the two will only be equal up to permutation in this new theory. It is therefore advisable to stop relying on this, and use the new facilities provided in this library: lemmas big_enumP, big_enum, big_image and such. Users wishing to test compliance should change the Defined in index_enum_key to Qed, and comment out the filter_index_enum compatibility definition below (or Import Deprecation.Reject).
Fact index_enum_key : unit. (* Qed. *)
Definition index_enum (T : finType) :=
locked_with index_enum_key (Finite.enum T).

Lemma deprecated_filter_index_enum T P : filter P (index_enum T) = enum P.

Lemma mem_index_enum T i : i \in index_enum T.
#[global] Hint Resolve mem_index_enum : core.

Lemma index_enum_uniq T : uniq (index_enum T).

Notation "\big [ op / idx ]_ ( i <- r | P ) F" :=
(bigop idx r (fun iBigBody i op P%B F)) : big_scope.
Notation "\big [ op / idx ]_ ( i <- r ) F" :=
(bigop idx r (fun iBigBody i op true F)) : big_scope.
Notation "\big [ op / idx ]_ ( m <= i < n | P ) F" :=
(bigop idx (index_iota m n) (fun i : natBigBody i op P%B F))
: big_scope.
Notation "\big [ op / idx ]_ ( m <= i < n ) F" :=
(bigop idx (index_iota m n) (fun i : natBigBody i op true F))
: big_scope.
Notation "\big [ op / idx ]_ ( i | P ) F" :=
(bigop idx (index_enum _) (fun iBigBody i op P%B F)) : big_scope.
Notation "\big [ op / idx ]_ i F" :=
(bigop idx (index_enum _) (fun iBigBody i op true F)) : big_scope.
Notation "\big [ op / idx ]_ ( i : t | P ) F" :=
(bigop idx (index_enum _) (fun i : tBigBody i op P%B F))
(only parsing) : big_scope.
Notation "\big [ op / idx ]_ ( i : t ) F" :=
(bigop idx (index_enum _) (fun i : tBigBody i op true F))
(only parsing) : big_scope.
Notation "\big [ op / idx ]_ ( i < n | P ) F" :=
(\big[op/idx]_(i : ordinal n | P%B) F) : big_scope.
Notation "\big [ op / idx ]_ ( i < n ) F" :=
(\big[op/idx]_(i : ordinal n) F) : big_scope.
Notation "\big [ op / idx ]_ ( i 'in' A | P ) F" :=
(\big[op/idx]_(i | (i \in A) && P) F) : big_scope.
Notation "\big [ op / idx ]_ ( i 'in' A ) F" :=
(\big[op/idx]_(i | i \in A) F) : big_scope.

Notation BIG_F := (F in \big[_/_]_(i <- _ | _) F i)%pattern.
Notation BIG_P := (P in \big[_/_]_(i <- _ | P i) _)%pattern.

Notation "\sum_ ( i <- r | P ) F" :=
(\big[+%N/0%N]_(i <- r | P%B) F%N) : nat_scope.
Notation "\sum_ ( i <- r ) F" :=
(\big[+%N/0%N]_(i <- r) F%N) : nat_scope.
Notation "\sum_ ( m <= i < n | P ) F" :=
(\big[+%N/0%N]_(m i < n | P%B) F%N) : nat_scope.
Notation "\sum_ ( m <= i < n ) F" :=
(\big[+%N/0%N]_(m i < n) F%N) : nat_scope.
Notation "\sum_ ( i | P ) F" :=
(\big[+%N/0%N]_(i | P%B) F%N) : nat_scope.
Notation "\sum_ i F" :=
(\big[+%N/0%N]_i F%N) : nat_scope.
Notation "\sum_ ( i : t | P ) F" :=
(\big[+%N/0%N]_(i : t | P%B) F%N) (only parsing) : nat_scope.
Notation "\sum_ ( i : t ) F" :=
(\big[+%N/0%N]_(i : t) F%N) (only parsing) : nat_scope.
Notation "\sum_ ( i < n | P ) F" :=
(\big[+%N/0%N]_(i < n | P%B) F%N) : nat_scope.
Notation "\sum_ ( i < n ) F" :=
(\big[+%N/0%N]_(i < n) F%N) : nat_scope.
Notation "\sum_ ( i 'in' A | P ) F" :=
(\big[+%N/0%N]_(i in A | P%B) F%N) : nat_scope.
Notation "\sum_ ( i 'in' A ) F" :=
(\big[+%N/0%N]_(i in A) F%N) : nat_scope.

Notation "\prod_ ( i <- r | P ) F" :=
(\big[*%N/1%N]_(i <- r | P%B) F%N) : nat_scope.
Notation "\prod_ ( i <- r ) F" :=
(\big[*%N/1%N]_(i <- r) F%N) : nat_scope.
Notation "\prod_ ( m <= i < n | P ) F" :=
(\big[*%N/1%N]_(m i < n | P%B) F%N) : nat_scope.
Notation "\prod_ ( m <= i < n ) F" :=
(\big[*%N/1%N]_(m i < n) F%N) : nat_scope.
Notation "\prod_ ( i | P ) F" :=
(\big[*%N/1%N]_(i | P%B) F%N) : nat_scope.
Notation "\prod_ i F" :=
(\big[*%N/1%N]_i F%N) : nat_scope.
Notation "\prod_ ( i : t | P ) F" :=
(\big[*%N/1%N]_(i : t | P%B) F%N) (only parsing) : nat_scope.
Notation "\prod_ ( i : t ) F" :=
(\big[*%N/1%N]_(i : t) F%N) (only parsing) : nat_scope.
Notation "\prod_ ( i < n | P ) F" :=
(\big[*%N/1%N]_(i < n | P%B) F%N) : nat_scope.
Notation "\prod_ ( i < n ) F" :=
(\big[*%N/1%N]_(i < n) F%N) : nat_scope.
Notation "\prod_ ( i 'in' A | P ) F" :=
(\big[*%N/1%N]_(i in A | P%B) F%N) : nat_scope.
Notation "\prod_ ( i 'in' A ) F" :=
(\big[*%N/1%N]_(i in A) F%N) : nat_scope.

Notation "\max_ ( i <- r | P ) F" :=
(\big[maxn/0%N]_(i <- r | P%B) F%N) : nat_scope.
Notation "\max_ ( i <- r ) F" :=
(\big[maxn/0%N]_(i <- r) F%N) : nat_scope.
Notation "\max_ ( i | P ) F" :=
(\big[maxn/0%N]_(i | P%B) F%N) : nat_scope.
Notation "\max_ i F" :=
(\big[maxn/0%N]_i F%N) : nat_scope.
Notation "\max_ ( i : I | P ) F" :=
(\big[maxn/0%N]_(i : I | P%B) F%N) (only parsing) : nat_scope.
Notation "\max_ ( i : I ) F" :=
(\big[maxn/0%N]_(i : I) F%N) (only parsing) : nat_scope.
Notation "\max_ ( m <= i < n | P ) F" :=
(\big[maxn/0%N]_(m i < n | P%B) F%N) : nat_scope.
Notation "\max_ ( m <= i < n ) F" :=
(\big[maxn/0%N]_(m i < n) F%N) : nat_scope.
Notation "\max_ ( i < n | P ) F" :=
(\big[maxn/0%N]_(i < n | P%B) F%N) : nat_scope.
Notation "\max_ ( i < n ) F" :=
(\big[maxn/0%N]_(i < n) F%N) : nat_scope.
Notation "\max_ ( i 'in' A | P ) F" :=
(\big[maxn/0%N]_(i in A | P%B) F%N) : nat_scope.
Notation "\max_ ( i 'in' A ) F" :=
(\big[maxn/0%N]_(i in A) F%N) : nat_scope.

Lemma big_load R (K K' : R Type) idx op I r (P : pred I) F :
K (\big[op/idx]_(i <- r | P i) F i) × K' (\big[op/idx]_(i <- r | P i) F i)
K' (\big[op/idx]_(i <- r | P i) F i).

Arguments big_load [R] K [K'] idx op [I].

Section Elim3.

Variables (R1 R2 R3 : Type) (K : R1 R2 R3 Type).
Variables (id1 : R1) (op1 : R1 R1 R1).
Variables (id2 : R2) (op2 : R2 R2 R2).
Variables (id3 : R3) (op3 : R3 R3 R3).

Hypothesis Kid : K id1 id2 id3.

Lemma big_rec3 I r (P : pred I) F1 F2 F3
(K_F : i y1 y2 y3, P i K y1 y2 y3
K (op1 (F1 i) y1) (op2 (F2 i) y2) (op3 (F3 i) y3)) :
K (\big[op1/id1]_(i <- r | P i) F1 i)
(\big[op2/id2]_(i <- r | P i) F2 i)
(\big[op3/id3]_(i <- r | P i) F3 i).

Hypothesis Kop : x1 x2 x3 y1 y2 y3,
K x1 x2 x3 K y1 y2 y3 K (op1 x1 y1) (op2 x2 y2) (op3 x3 y3).
Lemma big_ind3 I r (P : pred I) F1 F2 F3
(K_F : i, P i K (F1 i) (F2 i) (F3 i)) :
K (\big[op1/id1]_(i <- r | P i) F1 i)
(\big[op2/id2]_(i <- r | P i) F2 i)
(\big[op3/id3]_(i <- r | P i) F3 i).

End Elim3.

Arguments big_rec3 [R1 R2 R3] K [id1 op1 id2 op2 id3 op3] _ [I r P F1 F2 F3].
Arguments big_ind3 [R1 R2 R3] K [id1 op1 id2 op2 id3 op3] _ _ [I r P F1 F2 F3].

Section Elim2.

Variables (R1 R2 : Type) (K : R1 R2 Type) (f : R2 R1).
Variables (id1 : R1) (op1 : R1 R1 R1).
Variables (id2 : R2) (op2 : R2 R2 R2).

Hypothesis Kid : K id1 id2.

Lemma big_rec2 I r (P : pred I) F1 F2
(K_F : i y1 y2, P i K y1 y2
K (op1 (F1 i) y1) (op2 (F2 i) y2)) :
K (\big[op1/id1]_(i <- r | P i) F1 i) (\big[op2/id2]_(i <- r | P i) F2 i).

Hypothesis Kop : x1 x2 y1 y2,
K x1 x2 K y1 y2 K (op1 x1 y1) (op2 x2 y2).
Lemma big_ind2 I r (P : pred I) F1 F2 (K_F : i, P i K (F1 i) (F2 i)) :
K (\big[op1/id1]_(i <- r | P i) F1 i) (\big[op2/id2]_(i <- r | P i) F2 i).

Hypotheses (f_op : {morph f : x y / op2 x y >-> op1 x y}) (f_id : f id2 = id1).
Lemma big_morph I r (P : pred I) F :
f (\big[op2/id2]_(i <- r | P i) F i) = \big[op1/id1]_(i <- r | P i) f (F i).

End Elim2.

Arguments big_rec2 [R1 R2] K [id1 op1 id2 op2] _ [I r P F1 F2].
Arguments big_ind2 [R1 R2] K [id1 op1 id2 op2] _ _ [I r P F1 F2].
Arguments big_morph [R1 R2] f [id1 op1 id2 op2] _ _ [I].

Section Elim1.

Variables (R : Type) (K : R Type) (f : R R).
Variables (idx : R) (op op' : R R R).

Hypothesis Kid : K idx.

Lemma big_rec I r (P : pred I) F
(Kop : i x, P i K x K (op (F i) x)) :
K (\big[op/idx]_(i <- r | P i) F i).

Hypothesis Kop : x y, K x K y K (op x y).
Lemma big_ind I r (P : pred I) F (K_F : i, P i K (F i)) :
K (\big[op/idx]_(i <- r | P i) F i).

Hypothesis Kop' : x y, K x K y op x y = op' x y.
Lemma eq_big_op I r (P : pred I) F (K_F : i, P i K (F i)) :
\big[op/idx]_(i <- r | P i) F i = \big[op'/idx]_(i <- r | P i) F i.

Hypotheses (fM : {morph f : x y / op x y}) (f_id : f idx = idx).
Lemma big_endo I r (P : pred I) F :
f (\big[op/idx]_(i <- r | P i) F i) = \big[op/idx]_(i <- r | P i) f (F i).

End Elim1.

Arguments big_rec [R] K [idx op] _ [I r P F].
Arguments big_ind [R] K [idx op] _ _ [I r P F].
Arguments eq_big_op [R] K [idx op] op' _ _ _ [I].
Arguments big_endo [R] f [idx op] _ _ [I].

Section oAC.

Variables (T : Type) (op : T T T).

Definition AC_subdef of associative op & commutative op :=
fun xoapp (fun ySome (oapp (op^~ y) y x)) x.
Definition oAC := nosimpl AC_subdef.

Hypothesis (opA : associative op) (opC : commutative op).

Lemma oACE x y : oop (Some x) (Some y) = some (op x y).

Lemma oopA_subdef : associative oop.

Lemma oopx1_subdef : left_id None oop.
Lemma oop1x_subdef : right_id None oop.

Lemma oopC_subdef : commutative oop.

Canonical oAC_law := Monoid.Law oopA_subdef oopx1_subdef oop1x_subdef.
Canonical oAC_com_law := Monoid.ComLaw oopC_subdef.

Context [x : T].

Lemma some_big_AC_mk_monoid [I : Type] r P (F : I T) :
Some (\big[op/x]_(i <- r | P i) F i) =
oop (\big[oop/None]_(i <- r | P i) Some (F i)) (Some x).

Lemma big_AC_mk_monoid [I : Type] r P (F : I T) :
\big[op/x]_(i <- r | P i) F i =
odflt x (oop (\big[oop/None]_(i <- r | P i) Some (F i)) (Some x)).

End oAC.

Section Extensionality.

Variables (R : Type) (idx : R) (op : R R R).

Section SeqExtension.

Variable I : Type.

Lemma foldrE r : foldr op idx r = \big[op/idx]_(x <- r) x.

Lemma big_filter r (P : pred I) F :
\big[op/idx]_(i <- filter P r) F i = \big[op/idx]_(i <- r | P i) F i.

Lemma big_filter_cond r (P1 P2 : pred I) F :
\big[op/idx]_(i <- filter P1 r | P2 i) F i
= \big[op/idx]_(i <- r | P1 i && P2 i) F i.

Lemma eq_bigl r (P1 P2 : pred I) F :
P1 =1 P2
\big[op/idx]_(i <- r | P1 i) F i = \big[op/idx]_(i <- r | P2 i) F i.

A lemma to permute aggregate conditions.
The following lemmas can be used to localise extensionality to a specific index sequence. This is done by ssreflect rewriting, before applying congruence or induction lemmas.
Similar lemmas for exposing integer indexing in the predicate.
This lemma can be used to introduce an enumeration into a non-abelian bigop, in one of three ways: have [e big_e [Ue mem_e] [e_enum size_e] ] := big_enumP P. gives a permutation e of enum P alongside a equation big_e for converting between bigops iterating on (i <- e) and ones on (i | P i). Usually not all properties of e are needed, but see below the big_distr_big_dep proof where most are. rewrite -big_filter; have [e ... ] := big_enumP. uses big_filter to do this conversion first, and then abstracts the resulting filter P (index_enum T) enumeration as an e with the same properties (see big_enum_cond below for an example of this usage). Finally rewrite -big_filter; case def_e: _ / big_enumP => [e ... ] does the same while remembering the definition of e.

Lemma big_enumP I P : big_enum_spec P (filter P (index_enum I)).

Section BigConst.

Variables (R : Type) (idx : R) (op : R R R).

Lemma big_const_seq I r (P : pred I) x :
\big[op/idx]_(i <- r | P i) x = iter (count P r) (op x) idx.

Lemma big_const (I : finType) (A : {pred I}) x :
\big[op/idx]_(i in A) x = iter #|A| (op x) idx.

Lemma big_const_nat m n x :
\big[op/idx]_(m i < n) x = iter (n - m) (op x) idx.

Lemma big_const_ord n x :
\big[op/idx]_(i < n) x = iter n (op x) idx.

End BigConst.

Section Plain.

Variable R : Type.
Variable op : R R R.
Variable x : R.

Lemma big_seq1_id I (i : I) (F : I R) :
\big[op/x]_(j <- [:: i]) F j = op (F i) x.

Lemma big_nat1_id n F : \big[op/x]_(n i < n.+1) F i = op (F n) x.

Lemma big_pred1_eq_id (I : finType) (i : I) F :
\big[op/x]_(j | j == i) F j = op (F i) x.

Lemma big_pred1_id (I : finType) i (P : pred I) F :
P =1 pred1 i \big[op/x]_(j | P j) F j = op (F i) x.

End Plain.

TODO: once ported to HB, enrich the Monoid hierarchy with semigroups (associative laws, no need for neutral element)
Section SemiGroupProperties.

Variable R : Type.

Variable op : R R R.

Hypothesis opA : associative op.

Section Id.

Variable x : R.
Hypothesis opxx : op x x = x.

Lemma big_const_idem I (r : seq I) P : \big[op/x]_(i <- r | P i) x = x.

Lemma big1_idem I r (P : pred I) F :
( i, P i F i = x) \big[op/x]_(i <- r | P i) F i = x.

Lemma big_id_idem I (r : seq I) P F :
op (\big[op/x]_(i <- r | P i) F i) x = \big[op/x]_(i <- r | P i) F i.

End Id.

Section Abelian.

Hypothesis opC : commutative op.

Let opCA : left_commutative op.

Variable x : R.

Lemma big_rem_AC (I : eqType) (r : seq I) z (P : pred I) F : z \in r
\big[op/x]_(y <- r | P y) F y
= if P z then op (F z) (\big[op/x]_(y <- rem z r | P y) F y)
else \big[op/x]_(y <- rem z r | P y) F y.

Lemma big_undup_AC (I : eqType) (r : seq I) (P : pred I) F :
idempotent op
\big[op/x]_(i <- undup r | P i) F i = \big[op/x]_(i <- r | P i) F i.

Lemma perm_big_AC (I : eqType) r1 r2 (P : pred I) F :
perm_eq r1 r2
\big[op/x]_(i <- r1 | P i) F i = \big[op/x]_(i <- r2 | P i) F i.

Lemma big_enum_cond_AC (I : finType) (A : {pred I}) (P : pred I) F :
\big[op/x]_(i <- enum A | P i) F i = \big[op/x]_(i in A | P i) F i.

Lemma big_enum_AC (I : finType) (A : {pred I}) F :
\big[op/x]_(i <- enum A) F i = \big[op/x]_(i in A) F i.

Lemma big_uniq_AC (I : finType) (r : seq I) F :
uniq r \big[op/x]_(i <- r) F i = \big[op/x]_(i in r) F i.

Lemma bigD1_AC (I : finType) j (P : pred I) F :
P j \big[op/x]_(i | P i) F i
= op (F j) (\big[op/x]_(i | P i && (i != j)) F i).
Arguments bigD1_AC [I] j [P F].

Lemma bigD1_seq_AC (I : eqType) (r : seq I) j F :
j \in r uniq r
\big[op/x]_(i <- r) F i = op (F j) (\big[op/x]_(i <- r | i != j) F i).

Lemma big_image_cond_AC I (J : finType) (h : J I) (A : pred J) (P : pred I) F :
\big[op/x]_(i <- [seq h j | j in A] | P i) F i
= \big[op/x]_(j in A | P (h j)) F (h j).

Lemma big_image_AC I (J : finType) (h : J I) (A : pred J) F :
\big[op/x]_(i <- [seq h j | j in A]) F i = \big[op/x]_(j in A) F (h j).

Lemma big_image_cond_id_AC
(J : finType) (h : J R) (A : pred J) (P : pred R) :
\big[op/x]_(i <- [seq h j | j in A] | P i) i
= \big[op/x]_(j in A | P (h j)) h j.

Lemma big_image_id_AC (J : finType) (h : J R) (A : pred J) :
\big[op/x]_(i <- [seq h j | j in A]) i = \big[op/x]_(j in A) h j.

Lemma cardD1x (I : finType) (A : pred I) j :
A j #|SimplPred A| = 1 + #|[pred i | A i & i != j]|.
Arguments cardD1x [I A].

Lemma reindex_omap_AC (I J : finType) (h : J I) h' (P : pred I) F :
( i, P i omap h (h' i) = some i)
\big[op/x]_(i | P i) F i =
\big[op/x]_(j | P (h j) && (h' (h j) == some j)) F (h j).
Arguments reindex_omap_AC [I J] h h' [P F].

Lemma reindex_onto_AC (I J : finType) (h : J I) h' (P : pred I) F :
( i, P i h (h' i) = i)
\big[op/x]_(i | P i) F i =
\big[op/x]_(j | P (h j) && (h' (h j) == j)) F (h j).
Arguments reindex_onto_AC [I J] h h' [P F].

Lemma reindex_AC (I J : finType) (h : J I) (P : pred I) F :
{on [pred i | P i], bijective h}
\big[op/x]_(i | P i) F i = \big[op/x]_(j | P (h j)) F (h j).
Arguments reindex_AC [I J] h [P F].

Lemma reindex_inj_AC (I : finType) (h : I I) (P : pred I) F :
injective h \big[op/x]_(i | P i) F i = \big[op/x]_(j | P (h j)) F (h j).
Arguments reindex_inj_AC [I h P F].

Lemma bigD1_ord_AC n j (P : pred 'I_n) F :
P j \big[op/x]_(i < n | P i) F i
= op (F j) (\big[op/x]_(i < n.-1 | P (lift j i)) F (lift j i)).

Lemma big_enum_val_cond_AC (I : finType) (A : pred I) (P : pred I) F :
\big[op/x]_(x in A | P x) F x =
\big[op/x]_(i < #|A| | P (enum_val i)) F (enum_val i).
Arguments big_enum_val_cond_AC [I A] P F.

Lemma big_enum_rank_cond_AC (I : finType) (A : pred I) z (zA : z \in A) P F
(h := enum_rank_in zA) :
\big[op/x]_(i < #|A| | P i) F i = \big[op/x]_(s in A | P (h s)) F (h s).
Arguments big_enum_rank_cond_AC [I A z] zA P F.

Lemma big_nat_rev_AC m n P F :
\big[op/x]_(m i < n | P i) F i
= \big[op/x]_(m i < n | P (m + n - i.+1)) F (m + n - i.+1).

Lemma big_rev_mkord_AC m n P F :
\big[op/x]_(m k < n | P k) F k
= \big[op/x]_(k < n - m | P (n - k.+1)) F (n - k.+1).

Section Id.

Hypothesis opxx : op x x = x.

Lemma big_mkcond_idem I r (P : pred I) F :
\big[op/x]_(i <- r | P i) F i = \big[op/x]_(i <- r) (if P i then F i else x).

Lemma big_mkcondr_idem I r (P Q : pred I) F :
\big[op/x]_(i <- r | P i && Q i) F i =
\big[op/x]_(i <- r | P i) (if Q i then F i else x).

Lemma big_mkcondl_idem I r (P Q : pred I) F :
\big[op/x]_(i <- r | P i && Q i) F i =
\big[op/x]_(i <- r | Q i) (if P i then F i else x).

Lemma big_rmcond_idem I (r : seq I) (P : pred I) F :
( i, ~~ P i F i = x)
\big[op/x]_(i <- r | P i) F i = \big[op/x]_(i <- r) F i.

Lemma big_rmcond_in_idem (I : eqType) (r : seq I) (P : pred I) F :
( i, i \in r ~~ P i F i = x)
\big[op/x]_(i <- r | P i) F i = \big[op/x]_(i <- r) F i.

Lemma big_cat_idem I r1 r2 (P : pred I) F :
\big[op/x]_(i <- r1 ++ r2 | P i) F i =
op (\big[op/x]_(i <- r1 | P i) F i) (\big[op/x]_(i <- r2 | P i) F i).

Lemma big_allpairs_dep_idem I1 (I2 : I1 Type) J (h : i1, I2 i1 J)
(r1 : seq I1) (r2 : i1, seq (I2 i1)) (F : J R) :
\big[op/x]_(i <- [seq h i1 i2 | i1 <- r1, i2 <- r2 i1]) F i =
\big[op/x]_(i1 <- r1) \big[op/x]_(i2 <- r2 i1) F (h i1 i2).

Lemma big_allpairs_idem I1 I2 (r1 : seq I1) (r2 : seq I2) F :
\big[op/x]_(i <- [seq (i1, i2) | i1 <- r1, i2 <- r2]) F i =
\big[op/x]_(i1 <- r1) \big[op/x]_(i2 <- r2) F (i1, i2).

Lemma big_cat_nat_idem n m p (P : pred nat) F : m n n p
\big[op/x]_(m i < p | P i) F i =
op (\big[op/x]_(m i < n | P i) F i) (\big[op/x]_(n i < p | P i) F i).

Lemma big_split_idem I r (P : pred I) F1 F2 :
\big[op/x]_(i <- r | P i) op (F1 i) (F2 i) =
op (\big[op/x]_(i <- r | P i) F1 i) (\big[op/x]_(i <- r | P i) F2 i).

Lemma big_id_idem_AC I (r : seq I) P F :
\big[op/x]_(i <- r | P i) op (F i) x = \big[op/x]_(i <- r | P i) F i.

Lemma bigID_idem I r (a P : pred I) F :
\big[op/x]_(i <- r | P i) F i =
op (\big[op/x]_(i <- r | P i && a i) F i)
(\big[op/x]_(i <- r | P i && ~~ a i) F i).
Arguments bigID_idem [I r].

Lemma bigU_idem (I : finType) (A B : pred I) F :
[disjoint A & B]
\big[op/x]_(i in [predU A & B]) F i =
op (\big[op/x]_(i in A) F i) (\big[op/x]_(i in B) F i).

Lemma partition_big_idem I (s : seq I)
(J : finType) (P : pred I) (p : I J) (Q : pred J) F :
( i, P i Q (p i))
\big[op/x]_(i <- s | P i) F i =
\big[op/x]_(j : J | Q j) \big[op/x]_(i <- s | (P i) && (p i == j)) F i.

Arguments partition_big_idem [I s J P] p Q [F].

Lemma sig_big_dep_idem (I : finType) (J : I finType)
(P : pred I) (Q : {i}, pred (J i)) (F : {i}, J i R) :
\big[op/x]_(i | P i) \big[op/x]_(j : J i | Q j) F j =
\big[op/x]_(p : {i : I & J i} | P (tag p) && Q (tagged p)) F (tagged p).

Lemma pair_big_dep_idem (I J : finType) (P : pred I) (Q : I pred J) F :
\big[op/x]_(i | P i) \big[op/x]_(j | Q i j) F i j =
\big[op/x]_(p | P p.1 && Q p.1 p.2) F p.1 p.2.

Lemma pair_big_idem (I J : finType) (P : pred I) (Q : pred J) F :
\big[op/x]_(i | P i) \big[op/x]_(j | Q j) F i j =
\big[op/x]_(p | P p.1 && Q p.2) F p.1 p.2.

Lemma pair_bigA_idem (I J : finType) (F : I J R) :
\big[op/x]_i \big[op/x]_j F i j = \big[op/x]_p F p.1 p.2.

Lemma exchange_big_dep_idem I J rI rJ (P :