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 subset is linearly dependent if and only if some lies in ; and is already the set of linear combinations of INJECTIVE finite lists into
Statement
Let be a vector space over a field (Vector space over a field) and let .
- is linearly dependent (Linear independence: a finite list is independent when forces every , and a subset is independent when every injective finite list into is independent) if and only if there is with (Linear combination of a finite list, and the span as the smallest linear subspace containing ).
- That is, restricting the lists in is exactly the set of linear combinations of finite lists of elements of , and to injective lists changes nothing.
The two boundary cases are instances, not exceptions. For both sides of claim 1 fail: is independent and there is no . For both hold: is dependent, and ( is exactly the set of linear combinations of finite lists of elements of , and ).
Facts & Assumptions
Given: A field , a vector space over , and a subset .
is exactly the set of vectors with , and ; it is a linear subspace of containing ; and ( is exactly the set of linear combinations of finite lists of elements of , and , Linear combination of a finite list, and the span as the smallest linear subspace containing ).
Finite sums: and , the value depending 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) an all- list sums to ; (F2) ; (F3) for , where agrees with off and is at (The sum of two linear subspaces and the sum of a finite family).
Deleting one index: for the map is injective with image , and a list with satisfies (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, claim 2).
The vector space axioms (Vector space over a field) and their elementary consequences (In any vector space , , , , and forces or ): is an abelian group; ; ; ; ; and (V4) , (V3) .
is a field: , every has an inverse with , and every has an additive inverse (Field).
A list is independent when forces every , and is dependent exactly when some injective finite list into is dependent (Linear independence: a finite list is independent when forces every , and a subset is independent when every injective finite list into is independent).
Naturals and maps: every is a successor (Every nonzero natural number is a successor); with (The natural numbers (von Neumann), On the order is membership: ); induction (The principle of mathematical induction); and injectivity as in Injection, surjection, bijection.
Proof
Collecting repeated entries. For every , every and every there are , an injective with , and , with . By induction on : at take , both sums being . Assume it at , and let and ; applying the hypothesis to the restrictions gives with injective and , and the recursion gives . If , extend to by and to by ; then is injective with and the recursion gives . If instead for the unique such , put and for ; applying (F3) at to the lists and , whose -deleted forms coincide, and using (V3) in the form , gives , which is the required value.
A scalar passes through a finite sum: for , and , applying (F2) with the all- second list and using (F1) and the identity law gives ; combined with (V4) this yields for scalars and vectors .
Claim 2. Every with is a linear combination of elements of , hence lies in , so the right-hand set is contained in . Conversely an element of is for some , and step 1.1 rewrites it as with injective and , so is an injective finite list.
Claim 1, from left to right. Let be dependent, witnessed by an injective and with and for some . Put , so (F3) at gives with , whence and . Now where and for , since ; also , say , and the entry of this list at is , so deleting the index gives . Applying step 1.2 to the scalar gives with and . Since has image and is injective, takes its values in , so is a linear combination of elements of and therefore lies in . Taking finishes this direction.
Claim 1, from right to left. Let with . By step 2.1 applied to there are , an injective and with . Extend to by , which is injective because , and extend to by . The recursion then gives , while , since would give . So is an injective finite list into that is dependent, and is dependent.
Claim 1 is steps 2.2 and 3.1 together, and claim 2 is step 2.1.
Remarks
-
Claim 2 is the working form of the span. Once it is available, "a vector of " may always be taken to come with an injective list of vectors of carrying it, which is what makes the coefficient of a chosen entry meaningful. Every later argument on this page that solves for one entry of a list drawn from a span uses it in that form — The Steinitz exchange lemma: if is linearly independent and spans with finite of size , then is finite with , and there is of size such that spans and Every linear subspace of a vector space has a complement: a linear subspace with — and is exactly the set of linear combinations of finite lists of elements of , and on its own does not supply it, since its lists may repeat. If is linearly independent and then is linearly independent and ; and if then solves for an entry too but needs nothing from here, its list being injective by hypothesis, drawn from the definition of independence of a subset.
-
Claim 1 removes the lists from the statement. Dependence as defined is an existential over lists and witnesses; claim 1 restates it as a property of the set alone: some member is redundant, in that the span does not shrink when it is removed. That is also the form in which dependence is used to characterise bases (For the following are equivalent: is a basis; is a maximal linearly independent subset of ; is a minimal spanning subset of — maximality and minimality being in the inclusion order).
-
The vector produced is not unique and the lemma does not say it is. In a dependent set several members may be redundant, and which ones they are depends on the set. What the proof produces is one , read off from a chosen witness; a different witness may produce a different .
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
- 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 $0_V$, 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
- 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$
- Linear combination of a finite list, and the span $\operatorname{span}(S)$ as the smallest linear subspace containing $S$
- $\operatorname{span}(S)$ is exactly the set of linear combinations of finite lists of elements of $S$, and $\operatorname{span}(\varnothing) = \{0_V\}$
- The sum $U + W$ of two linear subspaces and the sum $\sum_{i<n} U_i$ of a finite family
- 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 principle of mathematical induction
- The natural numbers $\mathbb{N}$ (von Neumann)
- On $\mathbb{N}$ the order is membership: $m < n \iff m \in n$
- Every nonzero natural number is a successor
- Injection, surjection, bijection
Used by
- Every linear subspace U of a vector space V has a complement: a linear subspace W with V = U ⊕ W Corollary
- {(1,0), (0,1), (1,1)} spans F² and is linearly dependent, so a spanning set need not be a basis; each of its three two-element subsets is a basis Counterexample
- FALSE: the union of two linearly independent subsets of a vector space is linearly independent False statement
- Assuming the Axiom of Choice, ℝ has a Hamel basis over ℚ: there is B ⊆ ℝ such that every real is a finite ℚ-linear combination of elements of B in exactly one way, and each basis vector carries a well-defined ℚ-linear coefficient map 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
- 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: 65 results over 23 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)
- Interactive Linear Algebra: Linear Independence (standard reference, not scraped)