How statement and proof provenance work
The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.
- Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
- AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
- AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.
These labels describe origin, not correctness: citations and verification chips remain separate evidence.
Finite commutative-monoid sums are invariant under bijective reindexing, split over disjoint unions, and satisfy the finite Fubini rule
Statement
Let be a commutative monoid and let all index sets below be finite.
- If is a bijection and , then .
- If and are disjoint and , then .
- If , then
Facts & Assumptions
Given: A commutative monoid , finite sets , and functions and a bijection as in the Statement.
A finite commutative-monoid sum is obtained from any enumeration of its finite index set, and its value is independent of that enumeration (A finite sum in a commutative monoid indexed by an arbitrary finite set).
A finite monoid product splits at a cut, may be regrouped into consecutive blocks, and in a commutative monoid is invariant under permutations (Generalised associativity: in a monoid the product of a finite list does not depend on the bracketing, and in a commutative monoid it does not depend on the order of the factors either).
A finite family of pairwise disjoint finite sets has finite union, and its cardinality is the sum of the cardinalities; in particular, when and are disjoint (The sum rule: a finite disjoint union is finite with and , and a sum over a finite index set splits along a partition).
A Cartesian product of finite sets is finite with (The product rule: , and ).
Composites and inverses of bijections are bijections (Injection, surjection, bijection).
Proof
For clause 1, choose an enumeration . Then enumerates , and [F1] gives .
For clause 2, choose enumerations of and and concatenate them. By [L2] this gives an enumeration of of length , and the splitting law in [L1] turns the resulting finite sum into the sum over followed by the sum over .
For clause 3, choose enumerations and . The disjoint slices cover ; concatenate their -enumerations in the order of . By [L2] and [L3] this is an enumeration of , and regrouping it into the consecutive slices gives .
The column-major list also enumerates , and permutation invariance followed by regrouping into columns gives .
Steps 1.1, 1.2, 1.3 and 2.1 prove reindexing, disjoint splitting and both finite Fubini equalities.
Depends on
- A finite sum in a commutative monoid indexed by an arbitrary finite set
- The product rule: $\lvert A \times B\rvert = \lvert A\rvert\,\lvert B\rvert$, and $\big\lvert\prod_{i<m} A_i\big\rvert = \prod_{i<m}\lvert A_i\rvert$
- The sum rule: a finite disjoint union is finite with $\lvert A \cup B\rvert = \lvert A\rvert + \lvert B\rvert$ and $\lvert\bigcup_{i \in I} A_i\rvert = \sum_{i \in I}\lvert A_i\rvert$, and a sum over a finite index set splits along a partition
- Injection, surjection, bijection
- Generalised associativity: in a monoid the product of a finite list does not depend on the bracketing, and in a commutative monoid it does not depend on the order of the factors either
Used by
- Classical Möbius inversion over positive divisors Corollary
- The free-group functor F:Set toGrp and free-module functor R⁽⁻⁾:Set→ R-Mod Example
- Incidence convolution is associative and distributes over pointwise addition Lemma
- Linearity, power rule, Leibniz rule and the degree bound for the formal derivative Proposition
- For A∈ M_m× n(F) and B∈ M_n× m(F), tr(AB)=tr(BA) Theorem
- For A⊆ B in a finite Boolean lattice, μ(A,B)=(-1)^| B∖ A| Theorem
- For every square matrix over a commutative ring, det(A^mathsf T)=det(A) Theorem
- Matrix arithmetic over a commutative ring is associative, unital and distributive, and transpose reverses products Theorem
- Matrix multiplication is associative, unital, distributive, and compatible with scalar multiplication Theorem
- Möbius inversion on a lower-finite poset, with the dual upper-finite form Theorem
- Polynomial convolution makes R[x] a commutative ring containing R as its constant subring Theorem
- The Leibniz determinant is column-multilinear, alternating and normalized over every commutative ring Theorem
- The Möbius function of a product poset is the product of the Möbius functions Theorem
- Universal property of R[x]: a coefficient homomorphism and the image of x determine a unique ring homomorphism Theorem
Dependency tree · next 3 levels
Direct dependencies and their dependencies through the next three levels: 73 results over 22 levels. An arrow runs from a result to what uses it, and this result sits at the bottom with a heavier outline. Click the chart to enlarge it.
Sources
- Andrade–da Cruz, Finite products in commutative monoids (standard reference, not scraped)