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 $v : n \to V$ is independent when $\sum_{i<n} \lambda_i v_i = 0_V$ forces every $\lambda_i = 0_F$, and a subset $S \subseteq V$ is independent when every injective finite list into $S$ is independent
- Linear combination of a finite list, and the span $\operatorname{span}(S)$ as the smallest linear subspace containing $S$
- The product $g_0 g_1 \cdots g_{n-1}$ of a finite list in a monoid, by recursion, with the empty product ($n = 0$) equal to the identity
- The sum $U + W$ of two linear subspaces and the sum $\sum_{i<n} U_i$ 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 $0_F v = 0_V$, $\lambda 0_V = 0_V$, $(-\lambda)v = -(\lambda v)$, $(-1_F)v = -v$, and $\lambda v = 0_V$ forces $\lambda = 0_F$ or $v = 0_V$
- The principle of mathematical induction
- The natural numbers $\mathbb{N}$ (von Neumann)
- On $\mathbb{N}$ the order is membership: $m < n \iff m \in n$
- Order on the natural numbers
- Trichotomy of the order on $\mathbb{N}$
- Every nonzero natural number is a successor
- Discreteness: $\sigma(n)$ is the immediate successor
- Addition is cancellative
- Addition is commutative
- Order is compatible with addition
- $\le$ is a linear order on $\mathbb{N}$
- Injection, surjection, bijection
- Equinumerous sets, $A \approx B$ and $A \preceq B$
Used by
- Every linear subspace U of a vector space V has a complement: a linear subspace W with V = U ⊕ W Corollary
- Inside the space of eventually zero families, the linear subspace spanned by { eᵢ : i ≥ 1 } is proper and has a basis equinumerous with a basis of the whole space, so "equal dimension forces equality" fails without finite dimension Counterexample
- Basis of a vector space: a linearly independent spanning subset; and ordered basis: an injective finite list whose image is a basis Definition
- The standard unit families eₖ ∈ F^ℕ form a basis of the linear subspace of eventually zero families: an explicit infinite basis, built with no choice principle Example
- FALSE: the union of two linearly independent subsets of a vector space is linearly independent False statement
- A subset S ⊆ V is linearly dependent if and only if some s ∈ S lies in span(S ∖ {s}); and span(S) is already the set of linear combinations of INJECTIVE finite lists into S Lemma
- For B ⊆ V the following are equivalent: B is a basis; B is a maximal linearly independent subset of V; B is a minimal spanning subset of V — maximality and minimality being in the inclusion order Lemma
- If S ⊆ V is linearly independent and w ∉ span(S) then S ∪ {w} is linearly independent and span(S) ⊊ span(S ∪ {w}); and if w ∈ span(S) then span(S ∪ {w}) = span(S) Lemma
- S ⊆ V is linearly independent if and only if every finite subset of S is; consequently the union of a nonempty chain of linearly independent subsets of V, ordered by inclusion, is linearly independent Lemma
- A finite list v : n → V is an ordered basis if and only if every x ∈ V equals ∑_i<n λᵢ vᵢ for exactly one λ : n → F; those scalars are the coordinates of x in that ordered basis Theorem
- The dimension formula: for finite-dimensional linear subspaces U and W of V, the subspaces U + W and U ∩ W are finite-dimensional and dim_F(U+W) + dim_F(U ∩ W) = dim_F U + dim_F W Theorem
- The Steinitz exchange lemma: if L ⊆ V is linearly independent and S ⊆ V spans V with S finite of size n, then L is finite with |L| = m ≤ n, and there is T ⊆ S of size n - m such that L ∪ T spans V Theorem
Dependency tree · next 3 levels
Direct dependencies and their dependencies through the next three levels: 63 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
- Linear independence (Wikipedia) (standard reference, not scraped)
- S. Axler, Linear Algebra Done Right, 4th ed., Ch. 2 (standard reference, not scraped)
- Sheldon Axler, Linear Algebra Done Right, 4th ed. (standard reference, not scraped)
- Cambridge University Press excerpt: Vector spaces and bases (standard reference, not scraped)