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.
The sum rule: a finite disjoint union is finite with and , and a sum over a finite index set splits along a partition
Statement
- Two blocks. If and are finite and disjoint, then is finite and (The cardinality of a finite set).
- A finite partition. If is a finite set and is a family of finite sets that are pairwise disjoint, then is finite and , the sum being that of The sum over a finite index set, and its product form.
- Splitting a sum along a partition of its index set. Let be finite, let be finite, and let be pairwise disjoint subsets of with . Then for or , In particular for disjoint finite and .
Disjointness is a hypothesis and not a formality. It is spent at exactly one step, the injectivity of the splice map, and dropping it makes clause 1 false; the companion page carries that false statement with its smallest witness.
Facts & Assumptions
Given: Finite sets as in the statement, and the truncated difference and the two finite sums of Finite sums and finite products of natural numbers, and in . Throughout, denotes either or on or on , the corresponding identity, and the associated iterated operation; the four cases are proved by one argument, as in A finite sum is unchanged by a permutation of its index range: for every bijection .
Induction (The principle of mathematical induction).
Cardinality (The cardinality of a finite set): is the unique natural with ; ; ; a bijection transports finiteness and cardinality.
Sums over a finite index set (The sum over a finite index set, and its product form): for any bijection , the value being independent of ; ; reindexing along a bijection leaves the value unchanged; and .
Recursion clauses: and (Finite sums and finite products of natural numbers, and in , Finite sums and finite products, by recursion).
Splitting at an index: for and , (clause 3 of Laws of finite sums and products in , and , clause 3 of Laws of finite sums and finite products).
Order and addition in : gives a unique with ; ; addition is commutative; (Order on the natural numbers, Addition is cancellative, Order is compatible with addition, Addition is commutative, Addition of natural numbers, On the order is membership: ).
Maps (Injection, surjection, bijection, Equinumerous sets, and ): composites and inverses of bijections are bijections, and an injective surjection is a bijection.
A subset of a finite set is finite (A subset of a finite set is finite, with , and equality holds if and only if , clause 1).
Proof
The splice map. Let , be finite and disjoint, put , , and fix bijections and . Define by when , and, when , by for the unique with ; that satisfies because . The map is well defined by [L6], it is surjective because every element of is some or some , and it is injective: two indices below are separated by the injectivity of , two indices at least by the injectivity of together with the uniqueness of , and an index below from one at least because , and . The last of these three cases is the only use of disjointness in the whole proof.
Base cases of the two inductions below, at . A family indexed by has empty union, so ; and a partition of indexed by forces , so both sides of clause 3 are .
Inductive hypothesis for both inductions, at : for pairwise disjoint finite the union is finite with cardinality ; and for a partition of a finite set into pairwise disjoint one has .
Clause 1. By step 1.1 the map is a bijection , so ; hence is finite and .
Clause 3 for two blocks. Let , be finite and disjoint and defined on . With , and the bijections of step 1.1 for the pair , , step 2.1 gives , so may be used as the enumeration in [L3]. Then , using [L5] at the second equality.
Inductive step for clause 2, in the case of an index set . Let be pairwise disjoint and finite. Then , and these two sets are disjoint because each with is disjoint from . By the hypothesis of step 1.3 the first is finite with cardinality , so clause 1 makes the union finite with cardinality by [L4].
Clause 2. By step 1.2, step 3.2 and induction, the statement holds for every family indexed by a natural number . For a general finite index set take a bijection with ; then and by the definition of the sum over a finite index set, so the two statements coincide.
Inductive step for clause 3, index set . Let be finite and partitioned into pairwise disjoint , and put , which is finite by [L8] and disjoint from . The hypothesis of step 1.3 applies to the partition of into , and step 3.1 applies to the disjoint pair , , giving by [L4].
Clause 3. By step 1.2, step 5.1 and induction it holds for every index set that is a natural number, and the general finite follows by reindexing along a bijection exactly as in step 4.1. The two-block form is step 3.1.
Clause 1 is step 2.1, clause 2 is step 4.1 and clause 3 is step 6.1; since was an arbitrary one of the four operations, both the sum and the product forms of clause 3 are proved.
Remarks
-
Why the splice map is built once. The same bijection proves clause 1 and, used as an enumeration, proves the two-block case of clause 3. Building it twice, once for cardinalities and once for sums, would be two chances to get the index arithmetic wrong.
-
The subtraction in the splice is legitimate. Writing for means: the unique with , which exists by the definition of and is unique by cancellation. No negative number is formed anywhere.
-
Clause 3 is what the multinomial theorem needs. Its outer sum is indexed by the set of weak compositions of into parts, and the induction on partitions that index set by the value of the last part. Without clause 3 that step could not be taken.
Depends on
- The cardinality $\lvert A\rvert$ of a finite set
- The sum $\sum_{i \in S} a_i$ over a finite index set, and its product form
- A finite sum is unchanged by a permutation of its index range: $\sum_{k<n} a_{\pi(k)} = \sum_{k<n} a_k$ for every bijection $\pi : n \to n$
- A subset of a finite set is finite, with $\lvert B\rvert \le \lvert A\rvert$, and equality holds if and only if $B = A$
- Finite sums and finite products of natural numbers, $\sum_{k<n} a_k$ and $\prod_{k<n} a_k$ in $\mathbb{N}$
- Laws of finite sums and products in $\mathbb{N}$, and $\iota\big(\sum_{k<n} a_k\big) = \sum_{k<n} \iota(a_k)$
- Finite sums and finite products, by recursion
- Laws of finite sums and finite products
- Injection, surjection, bijection
- Equinumerous sets, $A \approx B$ and $A \preceq B$
- Addition of natural numbers
- Order on the natural numbers
- Addition is cancellative
- Order is compatible with addition
- Addition is commutative
- On $\mathbb{N}$ the order is membership: $m < n \iff m \in n$
- The principle of mathematical induction
Used by
- ∑_k<n+1binomnk = 2ⁿ, and ∑_k<n+1(-1)ᵏιbinomnk = 0 for n ≥ 1 Corollary
- Aₙ is normal in Sₙ; for n≥2, 2 |Aₙ|=n!, while Aₙ=Sₙ for n=0,1 Corollary
- A count that overcounts because the blocks are not disjoint, and exactly where the sum rule's hypothesis is spent Counterexample
- The multinomial coefficient binomnk₀,…,kₘ₋₁ as the number of ordered partitions of an n-set into blocks of prescribed sizes Definition
- Distributing a finite set over a finite set of boxes, with the ceiling bound computed and attained Example
- Dₙ≅⟨ r,s∣ rⁿ, s², srs⁻¹r⟩ for the dihedral group Dₙ=⟨{ρ,σ}⟩leqSym(ℤ/n), n≥ 3 Example
- Finite partial sums of a real family form a net directed by inclusion Example
- Five-card hands from a 52-card deck: binom525 = 2598960, and the count of hands with all cards of one suit Example
- For a finite symmetric irreflexive relation the sum of the neighbour counts is twice the number of unordered related pairs Example
- In a finite set with a symmetric irreflexive relation and at least two elements, two elements have equally many neighbours Example
- The sieve run in full on three explicit finite sets and then on four, with every nonempty intersection listed Example
- The surjections from a five-element set onto a three-element set counted by the sieve formula and by direct subtraction Example
- Vandermonde's identity checked at m = 4, n = 3, k = 3, both sides equal to 35 Example
- FALSE: | A ∪ B| = | A| + | B| for all finite A and B False statement
- ∑_i ∈ S∑_j ∈ T aᵢⱼ = ∑_(i,j) ∈ S × T aᵢⱼ = ∑_j ∈ T∑_i ∈ S aᵢⱼ for finite index sets S and T Lemma
- A maximal pairwise disjoint subfamily either supplies a sunflower or gives a small transversal for the whole uniform family Lemma
- Every finite colouring of ℕ has an infinite colour class, in ZF Lemma
- Every point off a polygon admits a ray meeting it transversely in finitely many nonvertex points Lemma
- Extending a basis of the kernel to a basis of the domain gives a basis of the image Lemma
- Finite commutative-monoid sums are invariant under bijective reindexing, split over disjoint unions, and satisfy the finite Fubini rule Lemma
- If m→(s-1,t)² and n→(s,t-1)², then m+n→(s,t)² for s,t≥2 Lemma
- binomnk k! (n-k)! = n! for k ≤ n; hence binomnk k! = n^underlinek, the quotient n!/(k!(n-k)!) is a natural number, and binomnk = binomnn-k Theorem
- Cauchy-Frobenius orbit counting: |G| |X/G|=∑_g∈ G|Xᵍ| for a finite group action Theorem
- Double counting: ∑_x ∈ X| Rₓ| = | R| = ∑_y ∈ Y| Rʸ| for a relation between finite sets Theorem
- Erdős's finite counting bound R(k,k)>2^k/2 for every k≥3 Theorem
- Every natural number and ω are cardinals, every infinite cardinal is a limit ordinal, and on the natural numbers the cardinal operations are the published finite counting operations, with | A | in the finite sense equal to | A | in the cardinal sense Theorem
- For a prime p and k≥1, φ(pᵏ)=pᵏ-pᵏ⁻¹ Theorem
- For every forest, |V|=|E|+c, where c is the number of connected components Theorem
- For every positive integer n, ∑_d∣ n, d>0φ(d)=n Theorem
- For m ≥ 1 the number of weak compositions of n into m parts is binomn+m-1m-1, and the number of compositions is binomn-1m-1 for n ≥ 1 Theorem
- If | A| > k| B| then every f : A → B has a fibre with more than k elements, and for nonempty B some fibre has at least lceil | A| / | B|rceil elements Theorem
- If a finite p-group P acts on a finite set X, then |X|≡|X^P|pmod p Theorem
- Inclusion and exclusion: ι|⋃_i ∈ I Aᵢ| = ∑_∅ ≠ J ⊆ I(-1)^| J| + 1 ι| A_J|, together with the complementary form counting the elements in none of the Aᵢ Theorem
- Jordan's derangement theorem: every transitive action of a finite group on a finite set with more than one element has a nonidentity element with no fixed points Theorem
- Lagrange's theorem: |G|=[G:H]|H| for every subgroup H of a finite group G Theorem
- Local LYM inequality comparing a uniform family with its upper shadow Theorem
- Pascal's rule binomn+1k+1 = binomnk + binomnk+1, and the hockey-stick identity ∑_i ≤ nbinomik = binomn+1k+1 Theorem
- Rank-nullity: dim_F V=nullityT+rankT Theorem
- The bounds ω(G)≤χ(G) and |V(G)|≤χ(G)α(G) Theorem
- The class equation |G|=|Z(G)|+∑ᵢ [G:C_G(xᵢ)] for a finite group Theorem
…and 9 more results.
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
- Rule of sum (Wikipedia) (standard reference, not scraped)
- Summation (Wikipedia) (standard reference, not scraped)
- R. Stanley, Enumerative Combinatorics, Vol. 1, Ch. 1 (standard reference, not scraped)