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 integral of a continuous derivative over a cycle is zero Corollary
- Square-summable families on an arbitrary index set and the space ℓ²(I) Definition
- Frobenius reciprocity for group representations without tensor products Example
- The free-group functor F:Set toGrp and free-module functor R⁽⁻⁾:Set→ R-Mod Example
- ℤ[x] represents the underlying-set functor on unital rings Example
- Equality in the unit-complex finite-sum bound Lemma
- Expectation is the sum of each attained value times its probability Lemma
- Incidence convolution is associative and distributes over pointwise addition Lemma
- Integer-valued finite formal sums of words form unital convolution rings Lemma
- The Cauchy kernel expands as an absolutely and uniformly convergent multi-indexed geometric series Lemma
- The moment generating function of a finite sum of independent variables is the product of their moment generating functions Lemma
- Linearity, power rule, Leibniz rule and the degree bound for the formal derivative Proposition
- The convolution 1*λ detects perfect squares Proposition
- A k-uniform hypergraph is 2-colourable when every edge meets at most d other edges and e(d+1)≤2ᵏ⁻¹ Theorem
- Arithmetic functions form a commutative ring under pointwise addition and Dirichlet convolution Theorem
- Cauchy multiplication makes R⟦ x⟧ a commutative ring containing R[x] as the finitely supported subring Theorem
- Chain integration and the index are additive in the chain, and reverse with it Theorem
- Dirichlet convolution preserves multiplicativity, and multiplicative inverses stay multiplicative Theorem
- Dirichlet's hyperbola method for summatory convolutions Theorem
- Expectation factors over a finite product of mutually independent random variables Theorem
- Expectation is linear for every finite family of random variables, without any independence hypothesis Theorem
- Finite convolution makes R[xᵢ:i∈ I] a commutative ring containing R Theorem
- 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^T)=det(A) Theorem
- Galois orbits classify simple modules after splitting base change 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
- PBW symmetrization in characteristic zero Theorem
- Polynomial convolution makes R[x] a commutative ring containing R as its constant subring Theorem
- Probability is additive on every finite pairwise-disjoint family of events Theorem
- Product weights normalize, and coordinate events are mutually independent Theorem
- Summable formal families may be regrouped and rearranged, distribute over multiplication, and have well-defined locally finite products Theorem
- The divisor formula for the two-square representation count Theorem
- The index of a cycle about a point off its trace is an integer 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 a polynomial ring on an arbitrary family of indeterminates Theorem
…and 1 more result.
Dependency tree · two levels
33 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.
Sources
- Andrade–da Cruz, Finite products in commutative monoids (standard reference, not scraped)