-- Mathlib/LinearAlgebra/LinearIndependent/Lemmas.lean
theorem exists_of_linearIndepOn_of_finite_span {t : Finset V}
    (hs : LinearIndepOn K id s) (hst : s ⊆ (span K ↑t : Submodule K V)) :
    ∃ t' : Finset V, ↑t' ⊆ s ∪ ↑t ∧ s ⊆ ↑t' ∧ t'.card = t.card

Proof state:
K : Type u_3
V : Type u
inst✝² : DivisionRing K
inst✝¹ : AddCommGroup V
inst✝ : Module K V
s : Set V
t✝¹ : Finset V
hs : LinearIndepOn K id s
hst✝¹ : s ⊆ ↑(span K ↑t✝¹)
t✝ : Finset V
b₁ : V
t : Finset V
hb₁t : b₁ ∉ t
ih :
  ∀ (s' : Finset V),
    ↑s' ⊆ s → s ∩ ↑t = ∅ → s ⊆ ↑(span K ↑(s' ∪ t)) → ∃ t', ↑t' ⊆ s ∪ ↑t ∧ s ⊆ ↑t' ∧ t'.card = (s' ∪ t).card
s' : Finset V
hs' : ↑s' ⊆ s
hst✝ : s ∩ ↑(insert b₁ t) = ∅
hss' : s ⊆ ↑(span K ↑(s' ∪ insert b₁ t))
hb₁s : b₁ ∉ s
hb₁s' : b₁ ∉ s'
hst : s ∩ ↑t = ∅
this✝¹ : ¬s ⊆ ↑(span K ↑(s' ∪ t))
b₂ : V
hb₂s : b₂ ∈ s
hb₂t : b₂ ∉ ↑(span K ↑(s' ∪ t))
hb₂t' : b₂ ∉ s' ∪ t
b₃ : V
hb₃✝ : b₃ ∈ s
this✝ : ↑(s' ∪ insert b₁ t) ⊆ insert b₁ (insert b₂ ↑(s' ∪ t))
hb₃ : b₃ ∈ span K (insert b₂ ↑(s' ∪ t))
this : s ⊆ ↑(span K (insert b₁ ↑(s' ∪ t)))
hb₁ : b₁ ∈ span K (insert b₂ ↑(s' ∪ t))
⊢ b₃ ∈ ↑(span K ↑(insert b₂ s' ∪ t))

Tactic:
simpa using hb₃

Result:
no goals

Proof state:
K : Type u_3
V : Type u
inst✝² : DivisionRing K
inst✝¹ : AddCommGroup V
inst✝ : Module K V
s : Set V
t : Finset V
hs : LinearIndepOn K id s
hst : s ⊆ ↑(span K ↑t)
this :
  ∀ (t s' : Finset V),
    ↑s' ⊆ s → s ∩ ↑t = ∅ → s ⊆ ↑(span K ↑(s' ∪ t)) → ∃ t', ↑t' ⊆ s ∪ ↑t ∧ s ⊆ ↑t' ∧ t'.card = (s' ∪ t).card
eq : Finset.filter (fun x => x ∈ s) t ∪ Finset.filter (fun x => x ∉ s) t = t
u : Finset V
h :
  ↑u ⊆ s ∪ ↑(Finset.filter (fun x => x ∉ s) t) ∧
    s ⊆ ↑u ∧ u.card = (Finset.filter (fun x => x ∈ s) t ∪ Finset.filter (fun x => x ∉ s) t).card
⊢ s ∪ ↑(Finset.filter (fun x => x ∉ s) t) ⊆ s ∪ ↑t

Tactic:
simp +contextual [subset_def, and_imp, or_imp]

Result:
no goals

Proof state:
K : Type u_3
V : Type u
inst✝² : DivisionRing K
inst✝¹ : AddCommGroup V
inst✝ : Module K V
s : Set V
t✝ : Finset V
hs : LinearIndepOn K id s
hst : s ⊆ ↑(span K ↑t✝)
t s' : Finset V
hs' : ↑s' ⊆ s
x✝ : s ∩ ↑∅ = ∅
hss' : s ⊆ ↑(span K ↑(s' ∪ ∅))
⊢ s ⊆ ↑(span K ↑s')

Tactic:
simpa using hss'

Result:
no goals

Proof state:
K : Type u_3
V : Type u
inst✝² : DivisionRing K
inst✝¹ : AddCommGroup V
inst✝ : Module K V
s : Set V
t✝¹ : Finset V
hs : LinearIndepOn K id s
hst✝¹ : s ⊆ ↑(span K ↑t✝¹)
t✝ : Finset V
b₁ : V
t : Finset V
hb₁t : b₁ ∉ t
ih :
  ∀ (s' : Finset V),
    ↑s' ⊆ s → s ∩ ↑t = ∅ → s ⊆ ↑(span K ↑(s' ∪ t)) → ∃ t', ↑t' ⊆ s ∪ ↑t ∧ s ⊆ ↑t' ∧ t'.card = (s' ∪ t).card
s' : Finset V
hs' : ↑s' ⊆ s
hst✝ : s ∩ ↑(insert b₁ t) = ∅
hss' : s ⊆ ↑(span K ↑(s' ∪ insert b₁ t))
hb₁s : b₁ ∉ s
hb₁s' : b₁ ∉ s'
hst : s ∩ ↑t = ∅
this : s ⊆ ↑(span K ↑(s' ∪ t))
u : Finset V
hust : ↑u ⊆ s ∪ ↑t
hsu : s ⊆ ↑u
Eq : u.card = (s' ∪ t).card
hb₁u : b₁ ∉ u
⊢ ↑(insert b₁ u) ⊆ s ∪ ↑(insert b₁ t)

Tactic:
simp [insert_subset_insert hust]

Result:
no goals

Proof state:
K : Type u_3
V : Type u
inst✝² : DivisionRing K
inst✝¹ : AddCommGroup V
inst✝ : Module K V
s : Set V
t : Finset V
hs : LinearIndepOn K id s
hst : s ⊆ ↑(span K ↑t)
⊢ ∃ t', ↑t' ⊆ s ∪ ↑t ∧ s ⊆ ↑t' ∧ t'.card = t.card

Tactic:
classical
have :
  ∀ t : Finset V,
    ∀ s' : Finset V,
      ↑s' ⊆ s →
        s ∩ ↑t = ∅ →
          s ⊆ (span K ↑(s' ∪ t) : Submodule K V) →
            ∃ t' : Finset V, ↑t' ⊆ s ∪ ↑t ∧ s ⊆ ↑t' ∧ t'.card = (s' ∪ t).card :=
  fun t =>
  Finset.induction_on t
    (fun s' hs' _ hss' =>
      have : s = ↑s' := eq_of_linearIndepOn_id_of_span_subtype hs hs' <| by simpa using hss'
      ⟨s', by simp [this]⟩)
    fun b₁ t hb₁t ih s' hs' hst hss' =>
    have hb₁s : b₁ ∉ s := fun h => by
      have : b₁ ∈ s ∩ ↑(insert b₁ t) := ⟨h, Finset.mem_insert_self _ _⟩
      rwa [hst] at this
    have hb₁s' : b₁ ∉ s' := fun h => hb₁s <| hs' h
    have hst : s ∩ ↑t = ∅ :=
      eq_empty_of_subset_empty <|
        Subset.trans
          (by simp [inter_subset_inter, Subset.refl, -inter_subset_left, -subset_inter_iff])
          (le_of_eq hst)
    Classical.by_cases (p := s ⊆ (span K ↑(s' ∪ t) : Submodule K V))
      (fun this =>
        let ⟨u, hust, hsu, Eq⟩ := ih _ hs' hst this
        have hb₁u : b₁ ∉ u := fun h => (hust h).elim hb₁s hb₁t
        ⟨insert b₁ u, by simp [insert_subset_insert hust], Subset.trans hsu (by simp), by
          simp [Eq, hb₁t, hb₁s', hb₁u]⟩)
      fun this =>
      let ⟨b₂, hb₂s, hb₂t⟩ := not_subset.mp this
      have hb₂t' : b₂ ∉ s' ∪ t := fun h => hb₂t <| subset_span h
      have : s ⊆ (span K ↑(insert b₂ s' ∪ t) : Submodule K V) := fun b₃ hb₃ => by
        have : ↑(s' ∪ insert b₁ t) ⊆ insert b₁ (insert b₂ ↑(s' ∪ t) : Set V) := by
          simp only [insert_eq, union_subset_union, Subset.refl,
            subset_union_right, Finset.union_insert, Finset.coe_insert]
        have hb₃ : b₃ ∈ span K (insert b₁ (insert b₂ ↑(s' ∪ t) : Set V)) :=
          span_mono this (hss' hb₃)
        have : s ⊆ (span K (insert b₁ ↑(s' ∪ t)) : Submodule K V) := by
          simpa [insert_eq, -singleton_union, -union_singleton] using hss'
        have hb₁ : b₁ ∈ span K (insert b₂ ↑(s' ∪ t)) :=
          mem_span_insert_exchange (this hb₂s) hb₂t
        rw [span_insert_eq_span hb₁] at hb₃; simpa using hb₃
      let ⟨u, hust, hsu, eq⟩ := ih _ (by simp [insert_subset_iff, hb₂s, hs']) hst this
      ⟨u, Subset.trans hust <| union_subset_union (Subset.refl _) (by simp [subset_insert]), hsu,
        by simp [eq, hb₂t', hb₁t, hb₁s']⟩
have eq : ((t.filter fun x => x ∈ s) ∪ t.filter fun x => x ∉ s) = t := by
  ext1 x
  by_cases x ∈ s <;> simp [*]
apply
  Exists.elim
    (this (t.filter fun x => x ∉ s) (t.filter fun x => x ∈ s) (by simp [Set.subset_def])
      (by simp +contextual [Set.ext_iff]) (by rwa [eq]))
intro u h
exact
  ⟨u, Subset.trans h.1 (by simp +contextual [subset_def, and_imp, or_imp]),
    h.2.1, by simp only [h.2.2, eq]⟩

Result:
no goals

Proof state:
K : Type u_3
V : Type u
inst✝² : DivisionRing K
inst✝¹ : AddCommGroup V
inst✝ : Module K V
s : Set V
t✝¹ : Finset V
hs : LinearIndepOn K id s
hst✝¹ : s ⊆ ↑(span K ↑t✝¹)
t✝ : Finset V
b₁ : V
t : Finset V
hb₁t : b₁ ∉ t
ih :
  ∀ (s' : Finset V),
    ↑s' ⊆ s → s ∩ ↑t = ∅ → s ⊆ ↑(span K ↑(s' ∪ t)) → ∃ t', ↑t' ⊆ s ∪ ↑t ∧ s ⊆ ↑t' ∧ t'.card = (s' ∪ t).card
s' : Finset V
hs' : ↑s' ⊆ s
hst✝ : s ∩ ↑(insert b₁ t) = ∅
hss' : s ⊆ ↑(span K ↑(s' ∪ insert b₁ t))
hb₁s : b₁ ∉ s
hb₁s' : b₁ ∉ s'
hst : s ∩ ↑t = ∅
this✝ : ¬s ⊆ ↑(span K ↑(s' ∪ t))
b₂ : V
hb₂s : b₂ ∈ s
hb₂t : b₂ ∉ ↑(span K ↑(s' ∪ t))
hb₂t' : b₂ ∉ s' ∪ t
this : s ⊆ ↑(span K ↑(insert b₂ s' ∪ t))
u : Finset V
hust : ↑u ⊆ s ∪ ↑t
hsu : s ⊆ ↑u
eq : u.card = (insert b₂ s' ∪ t).card
⊢ ↑t ⊆ ↑(insert b₁ t)

Tactic:
simp [subset_insert]

Result:
no goals

Proof state:
K : Type u_3
V : Type u
inst✝² : DivisionRing K
inst✝¹ : AddCommGroup V
inst✝ : Module K V
s : Set V
t✝ : Finset V
hs : LinearIndepOn K id s
hst : s ⊆ ↑(span K ↑t✝)
t s' : Finset V
hs' : ↑s' ⊆ s
x✝ : s ∩ ↑∅ = ∅
hss' : s ⊆ ↑(span K ↑(s' ∪ ∅))
this : s = ↑s'
⊢ ↑s' ⊆ s ∪ ↑∅ ∧ s ⊆ ↑s' ∧ s'.card = (s' ∪ ∅).card

Tactic:
simp [this]

Result:
no goals

Proof state:
K : Type u_3
V : Type u
inst✝² : DivisionRing K
inst✝¹ : AddCommGroup V
inst✝ : Module K V
s : Set V
t : Finset V
hs : LinearIndepOn K id s
hst : s ⊆ ↑(span K ↑t)
this :
  ∀ (t s' : Finset V),
    ↑s' ⊆ s → s ∩ ↑t = ∅ → s ⊆ ↑(span K ↑(s' ∪ t)) → ∃ t', ↑t' ⊆ s ∪ ↑t ∧ s ⊆ ↑t' ∧ t'.card = (s' ∪ t).card
eq : Finset.filter (fun x => x ∈ s) t ∪ Finset.filter (fun x => x ∉ s) t = t
⊢ s ∩ ↑(Finset.filter (fun x => x ∉ s) t) = ∅

Tactic:
simp +contextual [Set.ext_iff]

Result:
no goals