LemmaStatement: AI-adaptedProof: AI-generatedprecheck passjudge pass (z-ai/glm-5.2)audited 2026-07-29

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.

A finite sum is unchanged by a permutation of its index range: $\sum_{k < n} a_{π (k)} = \sum_{k < n} a_{k}$ for every bijection $π : n \to n$

Statement

Let $n \in N$ and let $π : n \to n$ be a bijection (Injection, surjection, bijection). Then:

for every list $a : n \to R$ , $\sum_{k < n} a_{π (k)} = \sum_{k < n} a_{k}$ and $\prod_{k < n} a_{π (k)} = \prod_{k < n} a_{k}$ (Finite sums and finite products, by recursion);
for every list $a : n \to N$ , $\sum_{k < n} a_{π (k)} = \sum_{k < n} a_{k}$ and $\prod_{k < n} a_{π (k)} = \prod_{k < n} a_{k}$ (Finite sums and finite products of natural numbers, $\sum_{k < n} a_{k}$ and $\prod_{k < n} a_{k}$ in $N$ ).

This is not in Laws of finite sums and finite products. That item proves additivity, scaling, splitting, monotonicity, telescoping and the product laws, and states no invariance clause; the same is true of the $N$ -valued list on this page. Permutation invariance is exactly what makes a sum over a finite set of indices well posed, which is the next item, so it is proved here first.

Facts & Assumptions

Given: A natural number $n$ , a bijection $π : n \to n$ , and a list $a$ of length $n$ . Throughout, $σ (n) = n \cup {n}$ , $n = {k : k < n}$ , and $*$ denotes any one of the four operations $(R, +)$ , $(R, \cdot)$ , $(N, +)$ , $(N, \cdot)$ , with $e$ the corresponding identity element $0$ , $1$ , $0$ , $1$ . Write $★_{k < n} c_{k}$ for the associated iterated operation, that is, for $\sum_{k < n} c_{k}$ in the two additive cases and $\prod_{k < n} c_{k}$ in the two multiplicative ones.

[L1]

Induction (The principle of mathematical induction).

[L2]

The four iterated operations obey the same two recursion clauses: $★_{k < 0} c_{k} = e$ and $★_{k < σ (n)} c_{k} = (★_{k < n} c_{k}) * c_{n}$ (Finite sums and finite products, by recursion, Finite sums and finite products of natural numbers, $\sum_{k < n} a_{k}$ and $\prod_{k < n} a_{k}$ in $N$ ).

[L3]

Each of the four operations is associative and commutative on its set and has $e$ as a two-sided identity (Field, Ordered field for $R$ ; Addition is associative, Addition is commutative, Multiplication is associative, Multiplication is commutative, Left identity for addition, Zero and one under multiplication for $N$ ). These three properties are the only facts about $*$ used below, which is why one argument proves all four clauses.

[L4]

Order and membership: $k < n ⟺ k \in n$ , $n = {k : k < n}$ , $k < σ (n) ⟺ k \leq n$ , $n \notin n$ , and $σ (n) ∖ {n} = n$ (On $N$ the order is membership: $m < n ⟺ m \in n$ , The natural numbers $N$ (von Neumann), Order on the natural numbers).

[L5]

Discreteness and successors: $m < n ⟺ σ (m) \leq n$ ; every nonzero natural is $σ (s)$ for a unique $s$ (Discreteness: $σ (n)$ is the immediate successor, Every nonzero natural number is a successor, The von Neumann naturals form a Peano system).

[L6]

Maps: a composite of bijections is a bijection; a bijection restricted to a subset of its domain is a bijection onto the image of that subset (Injection, surjection, bijection).

Proof

technique · induction

1.1L4L5L6construct

For $n \in N$ and $j \leq n$ define $d_{j}^{n} : n \to σ (n)$ by $d_{j}^{n} (k) = k$ for $k < j$ and $d_{j}^{n} (k) = σ (k)$ for $j \leq k < n$ ; this is the increasing enumeration of $σ (n) ∖ {j}$ . It is a bijection of $n$ onto $σ (n) ∖ {j}$ : its values lie in $σ (n)$ and avoid $j$ , since $k < j$ in the first clause and $σ (k) > k \geq j$ in the second; it is injective, being strictly increasing on each clause and satisfying $k < j \leq σ (k^{'})$ across them; and it is surjective, since $t \in σ (n)$ with $t < j$ has $t < n$ and $d_{j}^{n} (t) = t$ , while $t > j$ is nonzero, so $t = σ (s)$ with $j \leq s$ by [L5] and $s < n$ because $σ (s) \leq n$ , giving $d_{j}^{n} (s) = t$ .

1.2baseL2L3

Claim $(A)$ at $n = 0$ : for a list $c$ of length $σ (0) = 1$ and the only admissible index $j = 0$ , both sides of $(A)$ read $c_{0}$ , since $★_{k < 1} c_{k} = e * c_{0} = c_{0}$ and $(★_{k < 0} c_{d_{0}^{0} (k)}) * c_{0} = e * c_{0} = c_{0}$ .

1.3ih

Inductive hypothesis for $(A)$ : fix $n$ and assume that for every list $c$ of length $σ (n)$ and every $j \leq n$ one has $★_{k < σ (n)} c_{k} = (★_{k < n} c_{d_{j}^{n} (k)}) * c_{j}$ .

1.4L2

The main claim at $n = 0$ : the only bijection $0 \to 0$ is the empty map and both sides are the empty iterate $e$ .

2.1step 1.3L2L3

Inductive step for $(A)$ . Let $c$ be a list of length $σ (σ (n))$ and let $j \leq σ (n)$ . If $j = σ (n)$ then $d_{j}^{σ (n)}$ is the identity of $σ (n)$ , so the right-hand side is $(★_{k < σ (n)} c_{k}) * c_{σ (n)}$ , which is the left-hand side by [L2]. If instead $j \leq n$ , apply the hypothesis of step 1.3 to the restriction of $c$ to $σ (n)$ to get $★_{k < σ (n)} c_{k} = (★_{k < n} c_{d_{j}^{n} (k)}) * c_{j}$ ; hence $★_{k < σ (σ (n))} c_{k} = ((★_{k < n} c_{d_{j}^{n} (k)}) * c_{j}) * c_{σ (n)} = ((★_{k < n} c_{d_{j}^{n} (k)}) * c_{σ (n)}) * c_{j}$ by [L3]. Finally $d_{j}^{σ (n)}$ agrees with $d_{j}^{n}$ on $n$ and sends $n$ to $σ (n)$ , because $j \leq n$ , so the inner bracket is $★_{k < σ (n)} c_{d_{j}^{σ (n)} (k)}$ by [L2], which is the right-hand side at $σ (n)$ .

3.1step 1.2step 2.1L1

Claim $(A)$ therefore holds for every $n$ : for every list $c$ of length $σ (n)$ and every $j \leq n$ , $★_{k < σ (n)} c_{k} = (★_{k < n} c_{d_{j}^{n} (k)}) * c_{j}$ . Informally, any single entry may be moved to the end without changing the value.

4.1step 1.1step 3.1assume-hypL2L4L6

Inductive step for the main claim. Assume it at $n$ , for every list of length $n$ and every bijection of $n$ . Let $π : σ (n) \to σ (n)$ be a bijection, let $a$ be a list of length $σ (n)$ , and put $j : = π^{- 1} (n) \leq n$ . Applying $(A)$ to the list $c_{k} : = a_{π (k)}$ at the index $j$ gives $★_{k < σ (n)} a_{π (k)} = (★_{k < n} a_{ρ (k)}) * a_{π (j)}$ with $ρ : = π \circ d_{j}^{n}$ and $a_{π (j)} = a_{n}$ . Now $ρ$ is a bijection of $n$ onto $n$ : $d_{j}^{n}$ is a bijection of $n$ onto $σ (n) ∖ {j}$ by step 1.1, and $π$ restricts to a bijection of $σ (n) ∖ {j}$ onto $σ (n) ∖ {n} = n$ . So the inductive hypothesis applies to $ρ$ and gives $★_{k < n} a_{ρ (k)} = ★_{k < n} a_{k}$ , whence $★_{k < σ (n)} a_{π (k)} = (★_{k < n} a_{k}) * a_{n} = ★_{k < σ (n)} a_{k}$ .

5.1step 1.4step 4.1L1

By induction the main claim holds for every $n \in N$ , every list of length $n$ and every bijection $π : n \to n$ .

6.1step 5.1L3discharge-induction∎

Since $*$ was any one of the four operations of the Given, and [L3] holds for each of them, step 5.1 is exactly clauses 1 and 2.

Remarks

Where the deletion map earns its keep. The usual textbook proof says "move the term $a_{n}$ to the end and delete it", and leaves the resulting map on the shorter index range unexamined. That map is $d_{j}^{n}$ composed with $π$ , and checking that it really is a bijection of $n$ onto $n$ is the only place where anything can go wrong; step 1.1 writes it down and verifies it in both directions.
One proof, four statements. Only associativity, commutativity, the identity and the two recursion clauses are used, so the argument is indifferent to which of the four operations is meant. The same observation is what later licenses the identical statement in an arbitrary monoid, where it belongs; nothing here needs that generality.
No choice is used. The index $j = π^{- 1} (n)$ is determined, not selected, because $π$ is a bijection.

A finite sum is unchanged by a permutation of its index range: $\sum_{k < n} a_{π (k)} = \sum_{k < n} a_{k}$ for every bijection $π : n \to n$

Statement

Facts & Assumptions

Proof

Remarks

Depends on

Dependency tree · 2 levels

Sources

A finite sum is unchanged by a permutation of its index range: ∑k<naπ(k)=∑k<nak∑k<n​aπ(k)​=∑k<n​ak​ for every bijection π:n→nπ:n→n

Statement

Facts & Assumptions

Proof

Remarks

Depends on

Dependency tree · 2 levels

Sources

A finite sum is unchanged by a permutation of its index range: $\sum_{k < n} a_{π (k)} = \sum_{k < n} a_{k}$ for every bijection $π : n \to n$