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 sums re-indexed along an injection, with a zero term deleted, and concatenated; and the closure properties of linear independence: an independent list is injective and never , its sublists are independent, a list is independent exactly when it is injective with linearly independent image, and every subset of a linearly independent set is linearly independent
Statement
Let be a vector space over a field (Vector space over a field), with finite sums of vectors as in Linear combination of a finite list, and the span as the smallest linear subspace containing and linear independence as in Linear independence: a finite list is independent when forces every , and a subset is independent when every injective finite list into is independent. For a function and a set we write for the image of (Injection, surjection, bijection).
Three facts about finite sums.
- Re-indexing along an injection. Let , let be injective, and let satisfy for every with . Then
- Deleting one index. Let and . The map given by for and for is injective with image . Consequently, if has , then .
- Concatenation. Let , and . There is exactly one list with for and for , and it satisfies If moreover and are injective with , then is injective with image .
Four facts about independence.
- Every linearly independent list is injective, and for every .
- If is linearly independent and is injective, then the sublist is linearly independent.
- A list is linearly independent if and only if it is injective and its image is a linearly independent subset of ; in that case is a bijection , so (Equinumerous sets, and ).
- Every subset of a linearly independent subset of is linearly independent.
Facts & Assumptions
Given: A field , a vector space over , and the finite sums of Linear combination of a finite list, and the span as the smallest linear subspace containing read additively in the abelian group .
Finite sums: ; ; and the value depends only on (The product of a finite list in a monoid, by recursion, with the empty product () equal to the identity, Linear combination of a finite list, and the span as the smallest linear subspace containing ).
(F1) a list all of whose entries are sums to ; (F3) for and , , where agrees with at every and (The sum of two linear subspaces and the sum of a finite family).
Induction on (The principle of mathematical induction).
is an abelian group; , and for all , ; ; and in a field (Vector space over a field, In any vector space , , , , and forces or , Field).
A list is linearly independent when forces for every , and a subset is linearly independent when every injective finite list into is (Linear independence: a finite list is independent when forces every , and a subset is independent when every injective finite list into is independent).
Maps (Injection, surjection, bijection): a composite of injections is injective; a restriction of an injection is injective; an injection is a bijection onto its image and has a two-sided inverse there; and means a bijection exists (Equinumerous sets, and ).
Naturals (The natural numbers (von Neumann), On the order is membership: , Order on the natural numbers): and ; and ; ; (Discreteness: is the immediate successor); exactly one of , , holds (Trichotomy of the order on ); and every is a successor (Every nonzero natural number is a successor).
Splitting law for finite products in a monoid, read additively here: (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).
Addition on : means for some ; is a total order; ; and forces (Order on the natural numbers, is a linear order on , Order is compatible with addition, Addition is cancellative, Addition is commutative).
Proof
Claim 1, by induction on . At the image is empty, so for every and (F1) gives , which is also the empty sum . Assume the claim for , and let be injective with vanishing off . Put , let be the list agreeing with off and equal to at , and let be the restriction of to , which is injective. Then vanishes off : it vanishes at by construction, and a outside is outside , so . The inductive hypothesis therefore gives , the second equality because for by injectivity. Finally (F3) at gives , by commutativity and the recursion.
Claim 2, the deletion map. Fix and , so . The two clauses define a function : for we have , hence , and for we have . It is injective, being injective on each of the two blocks while its values on the first are below and its values on the second satisfy . Its image is : a with is ; a with is nonzero, hence for some , and then gives while gives , so ; and itself is not a value, the first block giving values below and the second values above .
Claim 3, the concatenated list. Let , and . Every satisfies exactly one of and ; in the second case there is with , and forces , while is unique by cancellation of addition. So the clauses for and for determine exactly one function . If and are injective with , then is injective: it is injective on each block, and a value from the first block lies in while a value from the second lies in , two disjoint sets. Its image is by the two clauses.
Claim 3, the sum identity. The splitting law for finite sums gives , and by the defining clauses for and for , so .
Claim 4, injectivity. Let be independent and suppose with and . Define by , and otherwise, and put . Extracting the term at by (F3) and then the term at from the resulting list gives , where agrees with off and is at both. Every entry of is , since for , so (F1) makes the last sum . Hence , while , contradicting independence. So is injective.
Claim 4, no entry equal to . Let be independent and suppose for some . Define by and for , and put , so for every . Then (F3) at together with (F1) gives , while , contradicting independence. So for every .
Zero extension of a list of scalars. Let be injective, let and let . Because is injective there is exactly one with for every and for every outside . The list then satisfies for every outside , and for every .
Claim 7. Let be independent and let . Every injective finite list is in particular an injective finite list into , hence independent; so every injective finite list into is independent, which is exactly independence of .
Claim 6, from right to left. Suppose is injective and is an independent subset of . Read as a function , the list is an injective finite list into , hence independent; the vanishing condition is a condition on sums computed in and is unaffected by which codomain is read into, so the list is independent. Moreover is a bijection , so .
Claim 2, the consequence. Let with for some . By step 1.2 the map is injective with image , so vanishes off that image, and claim 1, proved in step 1.1, gives .
Claim 5. Let be independent, injective, and with . Take the zero extension of step 1.7, so the list vanishes off and . Then step 1.1 gives , so independence of forces for every , and in particular for every . Hence is independent.
Claim 6, from left to right. Let be independent; it is injective by step 1.5, so it is a bijection and has a two-sided inverse there. Let be an injective finite list; then is injective and , so is independent by step 2.2. Hence every injective finite list into is independent, that is, is an independent subset of , and .
Claim 1 is step 1.1; claim 2 is step 1.2 with step 2.1; claim 3 is step 1.3 with step 1.4; claim 4 is step 1.5 with step 1.6; claim 5 is step 2.2; claim 6 is step 1.9 with step 3.1; and claim 7 is step 1.8.
Remarks
-
Claims 1 to 3 are the only finite-sum machinery this page adds. Everything else it needs about sums of vectors is (F1), (F2) and (F3) of The sum of two linear subspaces and the sum of a finite family, which were collected there for exactly this purpose, together with the splitting law of 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. Claim 1 is what lets a sum be recomputed over the indices that actually carry a nonzero term, claim 2 is its everyday special case, and claim 3 is what lets two independent lists be laid end to end.
-
Claim 6 is the bridge between the two notions of Linear independence: a finite list is independent when forces every , and a subset is independent when every injective finite list into is independent. It says that nothing is lost either way: an independent list is exactly an injective enumeration of an independent set. That is why the injectivity clause in the subset definition costs nothing, and why an ordered basis can be defined as an injective list whose image is a basis (Basis of a vector space: a linearly independent spanning subset; and ordered basis: an injective finite list whose image is a basis) without creating a second notion.
-
Claim 4 fails without independence, and both halves are used. A list may be injective and dependent, and a list containing is dependent whatever else it contains, since the single index carrying already supports the witness built in step 1.6. The second half is the list form of the observation in Linear independence: a finite list is independent when forces every , and a subset is independent when every injective finite list into is independent that is dependent.
Depends on
Linear independence: a finite list is independent when forces every , and a subset is independent when every injective finite list into is independent
Linear combination of a finite list, and the span as the smallest linear subspace containing
The product of a finite list in a monoid, by recursion, with the empty product () equal to the identity
The sum of two linear subspaces and the sum of a finite family
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
Vector space over a field
Field
In any vector space , , , , and forces or
The principle of mathematical induction
The natural numbers (von Neumann)
On the order is membership:
Order on the natural numbers
Trichotomy of the order on
Every nonzero natural number is a successor
Discreteness: is the immediate successor
Addition is cancellative
Addition is commutative
Order is compatible with addition
is a linear order on
Injection, surjection, bijection
Equinumerous sets, and