matroid_finset_indep_extend_to_card
An independent finite set can be extended to an independent set of any cardinality realized by a larger independent set.
Statement
theorem matroid_finset_indep_extend_to_card {V : Type*} [Fintype V] [DecidableEq V] (M : Matroid V) (I J : Finset V) (hI : M.Indep (I : Set V)) (hJ : M.Indep (J : Set V)) (hcard : I.card ≤ J.card) : ∃ K : Finset V, I ⊆ K ∧ K.card = J.card ∧ M.Indep (K : Set V)
- Source
- Filed by the prover as a step towards another result
- Verified
- 13 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
To extend an independent set I to an independent set of cardinality |J| where |I| ≤ |J|, the argument proceeds by induction on the difference d = |J| - |I|. At each step, if the current set is smaller than J, the matroid augmentation property supplies an element from J that can be added while preserving independence, reducing the difference by one until the target cardinality is reached. The provided code proves this induction as extend_to_card, applies it in all_pairs_not_two_codim_one to prove by contradiction that a matroid on at least 4 elements cannot have all pairs independent and exactly two independent hyperplanes, and re-exports the extension lemma as matroid_finset_indep_extend_to_card.
In the base case where |J| - |P| = 0, P itself is the required independent extension of cardinality |J|.
We establish the result by induction on the non-negative difference d = |J| - |P|. When d = 0, since |P| ≤ |J| and |J| - |P| = 0, linear arithmetic gives |P| = |J|. Since P ⊆ P and P is independent by assumption, K = P satisfies all required conditions.
have go : ∀ d (P : Finset V), M.Indep (P : Set V) → P.card ≤ J.card → J.card - P.card = d → ∃ K : Finset V, P ⊆ K ∧ K.card = J.card ∧ M.Indep (K : Set V) := by intro d induction d with | zero => intro P hP hle hd refine ⟨P, by intro x hx; exact hx, ?_, hP⟩ omega
In the induction step where |J| - |P| = d + 1, augmenting P by an element from J \\ P and applying the induction hypothesis produces the desired extension.
Since d + 1 > 0, we have |P| < |J|. By the matroid augmentation property for independent sets, there exists an element x ∈ J \\ P such that P ∪ {x} is independent. Inserting x increases the cardinality of P by 1 (via Finset.card_insert_of_notMem), so |J| - |P ∪ {x}| = d. Applying the induction hypothesis to P ∪ {x} produces an independent set K of cardinality |J| containing P ∪ {x}. By transitivity of subset inclusion with Finset.subset_insert, P ⊆ K.
uses
Finset.card_insert_of_notMem,Finset.coe_insert,Finset.subset_insert| succ d ih => intro P hP hle hd have hlt : P.card < J.card := by omega obtain ⟨x, hxJ, hxP, hxInd⟩ := hP.augment_finset hJ hlt have hnewCard : (insert x P).card = P.card + 1 := Finset.card_insert_of_notMem hxP have hnewLe : (insert x P).card ≤ J.card := by omega have hnewDiff : J.card - (insert x P).card = d := by omega have hnewInd : M.Indep ((insert x P : Finset V) : Set V) := by simpa only [Finset.coe_insert] using hxInd obtain ⟨K, hPK, hKcard, hKind⟩ := ih (insert x P) hnewInd hnewLe hnewDiff refine ⟨K, ?_, hKcard, hKind⟩ exact (Finset.subset_insert x P).trans hPKThe lemma extend_to_card holds for arbitrary independent sets I and J with |I| ≤ |J|.
Applying the generalized induction statement go with d = |J| - |I| and P = I immediately yields an independent extension K of cardinality |J| containing I.
exact go (J.card - I.card) I hI hcard rfl
Every two-element subset of V is independent in M.
Let pairs be the set of all 2-element subsets of V, of size Nat.choose |V| 2, and goodPairs the subset of independent pairs. Hypothesis h2 says that the number of independent 2-element subsets is Nat.choose |V| 2. Converting the set cardinality using Set.ncard_eq_toFinset_card', goodPairs has the same cardinality as pairs. By Finset.eq_of_subset_of_card_le and Finset.filter_subset, goodPairs = pairs. Thus, every pair of elements is independent (Finset.mem_filter.mp).
uses
Set.ncard_eq_toFinset_card',Finset.eq_of_subset_of_card_le,Finset.filter_subset,Finset.mem_filter.mpclassical let pairs : Finset (Finset V) := (Finset.univ : Finset V).powersetCard 2 let goodPairs : Finset (Finset V) := pairs.filter (fun W => M.Indep (W : Set V)) have hpairs : pairs.card = Nat.choose (Fintype.card V) 2 := by simp [pairs] have hgoodPairs : goodPairs.card = Nat.choose (Fintype.card V) 2 := by rw [Set.ncard_eq_toFinset_card'] at h2 have heq : ({W : Finset V | W.card = 2 ∧ M.Indep (W : Set V)} : Set (Finset V)).toFinset = goodPairs := by ext W simp [goodPairs, pairs] rw [heq] at h2 exact h2 have heqPairs : goodPairs = pairs := Finset.eq_of_subset_of_card_le (Finset.filter_subset _ _) (by omega) have allPairs (P : Finset V) (hP : P.card = 2) : M.Indep (P : Set V) := by have hmem : P ∈ pairs := by simp [pairs, hP] rw [← heqPairs] at hmem exact (Finset.mem_filter.mp hmem).2
Assuming there are exactly two independent sets of size |V| - 1, they are distinct sets A and B.
Suppose for contradiction that the number of independent sets of size |V| - 1 is 2. Converting the cardinality of the finset codim of such sets via Set.ncard_eq_toFinset_card', we get |codim| = 2. By Finset.card_eq_two.mp, codim consists of exactly two distinct subsets A and B, each of cardinality |V| - 1 and independent in M (Finset.mem_filter.mp).
uses
Set.ncard_eq_toFinset_card',Finset.card_eq_two.mp,Finset.mem_filter.mpintro h3 let codim : Finset (Finset V) := Finset.univ.filter (fun W => W.card = Fintype.card V - 1 ∧ M.Indep (W : Set V)) have hcnt : codim.card = 2 := by rw [Set.ncard_eq_toFinset_card'] at h3 convert h3 using 1 <;> simp [codim] obtain ⟨A, B, hAB, hcodim⟩ := Finset.card_eq_two.mp hcnt have hA : A ∈ codim := by rw [hcodim]; simp have hB : B ∈ codim := by rw [hcodim]; simp have hAprops := (Finset.mem_filter.mp hA).2 have hBprops := (Finset.mem_filter.mp hB).2
The complements of A and B are singletons {a} and {b} with a ≠ b, where a ∉ A and b ∉ B.
Using Finset.card_sdiff, the complements V \\ A and V \\ B both have cardinality |V| - (|V| - 1) = 1. By Finset.card_eq_one.mp, there exist elements a and b such that V \\ A = {a} and V \\ B = {b}, which implies a ∉ A and b ∉ B by Finset.mem_sdiff.mp. If a = b, then V \\ A = V \\ B, which forces A = B (using congrArg, Finset.mem_sdiff, Finset.mem_univ, true_and, not_iff_not.mp, and Iff.of_eq), contradicting A ≠ B. Thus a ≠ b.
uses
Finset.card_sdiff,Finset.card_eq_one.mp,Finset.mem_sdiff.mp,congrArg,Finset.mem_sdiff,Finset.mem_univ,true_and,not_iff_not.mp,Iff.of_eqhave hAc : ((Finset.univ : Finset V) \ A).card = 1 := by simp [Finset.card_sdiff, hAprops.1] omega have hBc : ((Finset.univ : Finset V) \ B).card = 1 := by simp [Finset.card_sdiff, hBprops.1] omega obtain ⟨a, ha⟩ := Finset.card_eq_one.mp hAc obtain ⟨b, hb⟩ := Finset.card_eq_one.mp hBc have haA : a ∉ A := by have : a ∈ (Finset.univ : Finset V) \ A := by rw [ha]; simp exact (Finset.mem_sdiff.mp this).2 have hbB : b ∉ B := by have : b ∈ (Finset.univ : Finset V) \ B := by rw [hb]; simp exact (Finset.mem_sdiff.mp this).2 have hab : a ≠ b := by intro h subst b have hc : (Finset.univ : Finset V) \ A = Finset.univ \ B := ha.trans hb.symm apply hAB ext x have hx := congrArg (fun S : Finset V => x ∈ S) hc simp only [Finset.mem_sdiff, Finset.mem_univ, true_and] at hx exact not_iff_not.mp (Iff.of_eq hx)
Extending the pair P = {a, b} to an independent set of size |V| - 1 produces a contradiction.
Since a ≠ b, the set P = {a, b} has cardinality 2 and is therefore independent. Because |V| ≥ 4, |P| = 2 ≤ |V| - 1 = |A|. By extend_to_card, P extends to an independent set K of cardinality |A| = |V| - 1. Then K ∈ codim by Finset.mem_filter.mpr and Finset.mem_univ. Since codim = {A, B} (using Finset.mem_insert and Finset.mem_singleton), either K = A or K = B. If K = A, then a ∈ P ⊆ K = A contradicts a ∉ A; if K = B, then b ∈ P ⊆ K = B contradicts b ∉ B. Both cases are impossible.
uses
extend_to_card,Finset.mem_filter.mpr,Finset.mem_univ,Finset.mem_insert,Finset.mem_singletonlet P : Finset V := {a,b} have hPc : P.card = 2 := by simp [P, hab] have hPi := allPairs P hPc obtain ⟨K, hPK, hKc, hKi⟩ := extend_to_card M P A hPi hAprops.2 (by omega) have hK : K ∈ codim := by apply Finset.mem_filter.mpr exact ⟨Finset.mem_univ _, by omega, hKi⟩ rw [hcodim] at hK simp only [Finset.mem_insert, Finset.mem_singleton] at hK rcases hK with hK | hK · have : a ∈ A := by rw [← hK]; exact hPK (by simp [P]) exact haA this · have : b ∈ B := by rw [← hK]; exact hPK (by simp [P]) exact hbB this
An independent set can be extended to an independent set of any cardinality realized by a larger independent set.
The theorem matroid_finset_indep_extend_to_card follows immediately by applying IN800GeneralMatroid.extend_to_card to the matroid M, the sets I and J, and the hypotheses.
uses
IN800GeneralMatroid.extend_to_cardexact IN800GeneralMatroid.extend_to_card M I J hI hJ hcard
Finset.card_insert_of_notMem- Inserting an element a ∉ s into a finite set s increases its cardinality by 1.
Finset.coe_insert- The set coercion of insert a s equals the set-theoretic insertion of a into the coercion of s.
Finset.subset_insert- A finite set s is a subset of insert a s.
Set.ncard_eq_toFinset_card'- The set cardinality ncard of a finite set equals the cardinality of its finset representation.
Finset.eq_of_subset_of_card_le- If s ⊆ t and |t| ≤ |s| for finite sets, then s = t.
Finset.filter_subset- Filtering a finite set by a predicate produces a subset of the original set.
Finset.mem_filter.mp- If an element belongs to a filtered finite set, then it belongs to the set and satisfies the predicate.
Finset.card_eq_two.mp- A finite set has cardinality 2 if and only if it consists of two distinct elements.
Finset.card_sdiff- The cardinality of the difference of two finite sets t \\ s is |t| - |s ∩ t|.
Finset.card_eq_one.mp- A finite set of cardinality 1 consists of a single element.
Finset.mem_sdiff.mp- If an element belongs to s \\ t, then it belongs to s and does not belong to t.
congrArg- Applying a function to equal arguments yields equal results.
Finset.mem_sdiff- An element belongs to s \\ t if and only if it belongs to s and not to t.
Finset.mem_univ- Every element of a finite type belongs to the universal finset.
true_and- Conjunction with True is equivalent to the proposition itself.
not_iff_not.mp- An equivalence between negations implies an equivalence between the propositions.
Iff.of_eq- Equality of propositions implies their logical equivalence.
extend_to_card- An independent finite set can be extended to an independent set of any cardinality realized by a larger independent set.
Finset.mem_filter.mpr- If an element belongs to a finite set and satisfies a predicate, it belongs to the filtered finset.
Finset.mem_insert- An element belongs to insert b s if and only if it equals b or belongs to s.
Finset.mem_singleton- An element belongs to {a} if and only if it equals a.
IN800GeneralMatroid.extend_to_card- An independent finite set can be extended to an independent set of any cardinality realized by a larger independent set.
- The provided source contains an auxiliary lemma extend_to_card, an application theorem all_pairs_not_two_codim_one, and the target theorem matroid_finset_indep_extend_to_card which calls extend_to_card.
- Matroid independence is formalized on coerced subsets (M.Indep (P : Set V)), requiring Finset.coe_insert when reasoning about element insertion.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
set_option maxRecDepth 8192set_option maxHeartbeats 8000000namespace IN800GeneralMatroidlemma extend_to_card {V : Type*} [Fintype V] [DecidableEq V] (M : Matroid V) (I J : Finset V) (hI : M.Indep (I : Set V)) (hJ : M.Indep (J : Set V)) (hcard : I.card ≤ J.card) : ∃ K : Finset V, I ⊆ K ∧ K.card = J.card ∧ M.Indep (K : Set V) := by have go : ∀ d (P : Finset V), M.Indep (P : Set V) → P.card ≤ J.card → J.card - P.card = d → ∃ K : Finset V, P ⊆ K ∧ K.card = J.card ∧ M.Indep (K : Set V) := by intro d induction d with | zero => intro P hP hle hd refine ⟨P, by intro x hx; exact hx, ?_, hP⟩ omega | succ d ih => intro P hP hle hd have hlt : P.card < J.card := by omega obtain ⟨x, hxJ, hxP, hxInd⟩ := hP.augment_finset hJ hlt have hnewCard : (insert x P).card = P.card + 1 := Finset.card_insert_of_notMem hxP have hnewLe : (insert x P).card ≤ J.card := by omega have hnewDiff : J.card - (insert x P).card = d := by omega have hnewInd : M.Indep ((insert x P : Finset V) : Set V) := by simpa only [Finset.coe_insert] using hxInd obtain ⟨K, hPK, hKcard, hKind⟩ := ih (insert x P) hnewInd hnewLe hnewDiff refine ⟨K, ?_, hKcard, hKind⟩ exact (Finset.subset_insert x P).trans hPK exact go (J.card - I.card) I hI hcard rfltheorem all_pairs_not_two_codim_one {V : Type*} [Fintype V] [DecidableEq V] (M : Matroid V) (hn : 4 ≤ Fintype.card V) (h2 : {W : Finset V | W.card = 2 ∧ M.Indep (W : Set V)}.ncard = Nat.choose (Fintype.card V) 2) : {W : Finset V | W.card = Fintype.card V - 1 ∧ M.Indep (W : Set V)}.ncard ≠ 2 := by classical let pairs : Finset (Finset V) := (Finset.univ : Finset V).powersetCard 2 let goodPairs : Finset (Finset V) := pairs.filter (fun W => M.Indep (W : Set V)) have hpairs : pairs.card = Nat.choose (Fintype.card V) 2 := by simp [pairs] have hgoodPairs : goodPairs.card = Nat.choose (Fintype.card V) 2 := by rw [Set.ncard_eq_toFinset_card'] at h2 have heq : ({W : Finset V | W.card = 2 ∧ M.Indep (W : Set V)} : Set (Finset V)).toFinset = goodPairs := by ext W simp [goodPairs, pairs] rw [heq] at h2 exact h2 have heqPairs : goodPairs = pairs := Finset.eq_of_subset_of_card_le (Finset.filter_subset _ _) (by omega) have allPairs (P : Finset V) (hP : P.card = 2) : M.Indep (P : Set V) := by have hmem : P ∈ pairs := by simp [pairs, hP] rw [← heqPairs] at hmem exact (Finset.mem_filter.mp hmem).2 intro h3 let codim : Finset (Finset V) := Finset.univ.filter (fun W => W.card = Fintype.card V - 1 ∧ M.Indep (W : Set V)) have hcnt : codim.card = 2 := by rw [Set.ncard_eq_toFinset_card'] at h3 convert h3 using 1 <;> simp [codim] obtain ⟨A, B, hAB, hcodim⟩ := Finset.card_eq_two.mp hcnt have hA : A ∈ codim := by rw [hcodim]; simp have hB : B ∈ codim := by rw [hcodim]; simp have hAprops := (Finset.mem_filter.mp hA).2 have hBprops := (Finset.mem_filter.mp hB).2 have hAc : ((Finset.univ : Finset V) \ A).card = 1 := by simp [Finset.card_sdiff, hAprops.1] omega have hBc : ((Finset.univ : Finset V) \ B).card = 1 := by simp [Finset.card_sdiff, hBprops.1] omega obtain ⟨a, ha⟩ := Finset.card_eq_one.mp hAc obtain ⟨b, hb⟩ := Finset.card_eq_one.mp hBc have haA : a ∉ A := by have : a ∈ (Finset.univ : Finset V) \ A := by rw [ha]; simp exact (Finset.mem_sdiff.mp this).2 have hbB : b ∉ B := by have : b ∈ (Finset.univ : Finset V) \ B := by rw [hb]; simp exact (Finset.mem_sdiff.mp this).2 have hab : a ≠ b := by intro h subst b have hc : (Finset.univ : Finset V) \ A = Finset.univ \ B := ha.trans hb.symm apply hAB ext x have hx := congrArg (fun S : Finset V => x ∈ S) hc simp only [Finset.mem_sdiff, Finset.mem_univ, true_and] at hx exact not_iff_not.mp (Iff.of_eq hx) let P : Finset V := {a,b} have hPc : P.card = 2 := by simp [P, hab] have hPi := allPairs P hPc obtain ⟨K, hPK, hKc, hKi⟩ := extend_to_card M P A hPi hAprops.2 (by omega) have hK : K ∈ codim := by apply Finset.mem_filter.mpr exact ⟨Finset.mem_univ _, by omega, hKi⟩ rw [hcodim] at hK simp only [Finset.mem_insert, Finset.mem_singleton] at hK rcases hK with hK | hK · have : a ∈ A := by rw [← hK]; exact hPK (by simp [P]) exact haA this · have : b ∈ B := by rw [← hK]; exact hPK (by simp [P]) exact hbB thisend IN800GeneralMatroidtheorem matroid_finset_indep_extend_to_card {V : Type*} [Fintype V] [DecidableEq V] (M : Matroid V) (I J : Finset V) (hI : M.Indep (I : Set V)) (hJ : M.Indep (J : Set V)) (hcard : I.card ≤ J.card) : ∃ K : Finset V, I ⊆ K ∧ K.card = J.card ∧ M.Indep (K : Set V) := by exact IN800GeneralMatroid.extend_to_card M I J hI hJ hcard