TheoremBase

Expanding a Product of Sums over a Fixed Finite Index Set

For finite sets A and B and a map u from A x B to a commutative ring, the product over A of the sums over B of u equals the sum, over all maps from A to B, of the products of u along the map; the term maps of both sides exist.

Statement

In the setting of Routine Facts Used Without Citation: Arithmetic, Maps, Predicativity and Indices, let RR, with ++, ⋅\cdot, 00 and 11, be a commutative ring, let AA and BB be finite sets, and let u:A×B→Ru:A\times B\to R. The set BAB^{A} of maps from AA to BB is finite by Finite Sets: the Pigeonhole Principle, Uniqueness of the Length, Subsets, Unions, Products, Images, Bounded Sets of Natural Numbers, Extreme Elements, Sets of Maps, Finite Unions and Finite Choice §maps.

There are a map A→RA\to R, x↦∑y∈Bu(x,y)x\mapsto\sum_{y\in B}u(x,y), and a map BA→RB^{A}\to R, φ↦∏x∈Au(x,φ(x))\varphi\mapsto\prod_{x\in A}u(x,\varphi(x)).

∏x∈A∑y∈Bu(x,y)=∑φ∈BA∏x∈Au(x,φ(x))\prod_{x\in A}\sum_{y\in B}u(x,y)=\sum_{\varphi\in B^{A}}\prod_{x\in A}u(x,\varphi(x)).

Proofs

Log in to submit a proof.

Loading...

Citations

Loading…

Dependencies

Loading…

Related

0 relations

Curated associations between results. These are editable and subjective — they do not replace the dependency graph, which is derived from the references in the text.

No relations recorded yet.

Comments

Log in to comment.

Loading…