AFTD Auto-Formalizing Theoretical Domains

matroid_finset_indep_extend_to_card

theoremverified

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.

  1. 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.

    lines 10–17

      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
  2. 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.

    lines 18–29

    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 hPK
  3. The 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.

    line 30

      exact go (J.card - I.card) I hI hcard rfl
  4. 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).

    lines 37–54

    uses Set.ncard_eq_toFinset_card', Finset.eq_of_subset_of_card_le, Finset.filter_subset, Finset.mem_filter.mp

      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
  5. 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).

    lines 55–65

    uses Set.ncard_eq_toFinset_card', Finset.card_eq_two.mp, Finset.mem_filter.mp

      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
  6. 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.

    lines 66–88

    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_eq

      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)
  7. 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.

    lines 89–102

    uses extend_to_card, Finset.mem_filter.mpr, Finset.mem_univ, Finset.mem_insert, Finset.mem_singleton

      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 this
  8. 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.

    line 107

    uses IN800GeneralMatroid.extend_to_card

      exact 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.

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

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
See it in the graphDiscuss this resultChallenge it