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
- Expected query cost from finite execution prefixes Definition
- Normalized output law for finite quantum query branches Definition
- Square-summable families on an arbitrary index set and the space ℓ²(I) Definition
- States, tracial states and faithful normal traces on a von Neumann algebra Definition
- The counting inner product on ℂ^ℤ/Nℤ Definition
- The unitary discrete Fourier transform on ℤ/Nℤ Definition
- The unnormalised cyclic convolution on ℤ/Nℤ Definition
- Finite abelian Fourier and convolution examples Example
- Frobenius reciprocity for group representations without tensor products Example
- Full-history cost and the bias from truncating memory Example
- Property (T) for finite groups via normalized counting measure 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
- Bluestein’s chirp identity embeds an arbitrary DFT in a padded cyclic convolution Lemma
- Conditional expectation on positive-probability events in finite spaces Lemma
- Counting measure on a discrete group is Haar, Haar measures there are its multiples, and integrals against them are sums Lemma
- Equality in the unit-complex finite-sum bound Lemma
- Expectation is the sum of each attained value times its probability Lemma
- F_N² is reflection and F_N⁴ is the identity Lemma
- Finite geometric sum for phase-estimation amplitudes Lemma
- Finite simple-random-sampling moment identities Lemma
- Incidence convolution is associative and distributes over pointwise addition Lemma
- Integer-valued finite formal sums of words form unital convolution rings Lemma
- Marginals and positive-mass conditionals of a finite joint law are probability vectors Lemma
- Mixed-radix Cooley–Tukey factorization with fixed index maps Lemma
- Multivariate polynomial and Laurent rings over commutative rings, domains and fraction fields Lemma
- Orthogonality of the characters x↦ e^2π ikx/N on ℤ/Nℤ Lemma
- Periodic heat-stencil eigenvalues and θ amplification factor Lemma
- Phase-estimation finite outcome law Lemma
- The Cauchy kernel expands as an absolutely and uniformly convergent multi-indexed geometric series Lemma
- The DFT turns cyclic convolution into a scaled pointwise product Lemma
- The free associative R-algebra on a set and descent of relations Lemma
- The multinomial theorem for finitely many complex variables Lemma
- The radix-two even/odd factorisation of the DFT 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
…and 35 more results.
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)