AFTD Auto-Formalizing Theoretical Domains

matroid_sbo_reduction_pairs_of_two_indep

theoremverifiedformalization

Let M be a finite strongly base-orderable matroid whose ground set is the union of two disjoint independent sets I and J. Then M has a reduction to a unit-capacity partition matroid with classes of size at most two: there is an involution p such that every subset T of the ground set containing no two distinct elements e, p e is independent in M.

Statement

theorem matroid_sbo_reduction_pairs_of_two_indep {α : Type*} (M : Matroid α) [M.Finite]
    (hM : matroid_strongly_base_orderable M) (I J : Set α) (hI : M.Indep I) (hJ : M.Indep J)
    (hIJ : Disjoint I J) (hE : I ∪ J = M.E) :
    ∃ p : α → α, Function.Involutive p ∧
      ∀ T ⊆ M.E, (∀ e ∈ T, p e ∈ T → p e = e) → M.Indep T
Formalizes
arXiv:2610.07318 (A note on the list chromatic number of two matroids), Proposition 2.2. The classes are given as the orbits {e, p e} of an involution. The proof differs from the paper's: instead of applying strong base-orderability in the contraction by the common part of the two bases, the exchange bijection is made to fix that common part by successive transpositions, which keep the exchange property; disjointness of I and J is not used.
Verified
08 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • matroid_strongly_base_orderableA matroid M is strongly base-orderable if for every two bases B₁, B₂ there is a bijection φ : B₁ → B₂ such that (B₁ \ X) ∪ φ(X) is a base…
Used by 1

The proof, explained

The independent sets I and J are extended to bases B₁ and B₂ of the strongly base-orderable matroid M, which guarantees the existence of an exchange bijection between them. By an induction on the number of unfixed shared elements using transpositions, this exchange bijection can be chosen to fix every element in B₁ ∩ B₂. The candidate involution p is defined by swapping each element of B₁ \ B₂ with its image under the bijection, while fixing all other elements. Finally, any subset T containing no non-trivial orbit under p is shown to embed into an exchange base (B₁ \ X) ∪ φ(X), which proves that T is independent in M.

  1. The exchange property for φ composed with the transposition of z = φ⁻¹(k) and k reduces to showing (B₁ \ X) ∪ φ((z k) '' X) = (B₁ \ Y) ∪ φ(Y) for a suitably modified set Y.

    Fix a subset X ⊆ B₁, let k ∈ B₁ ∩ B₂ with φ(k) ≠ k, and let z = φ⁻¹(k) ∈ B₁. Since φ(k) ≠ k, we have z ≠ k. We record the standard action of the swap τ = (z k): it interchanges z and k and fixes every other element. Setting Y = X ∪ {k} if z ∈ X and Y = X \ {k} if z ∉ X, applying the exchange property of φ to Y reduces the exchange property of τ ∘ φ on X to establishing the equality of the two resulting base sets.

    lines 8–20

    uses Equiv.swap_apply_left, Equiv.swap_apply_right, Equiv.swap_apply_of_ne_of_ne, Subtype.ext

      classical
      intro X
      set z := φ.symm ⟨k, hk⟩ with hz
      have hφz : (φ z : α) = k := by simp [hz]
      have hzk : z ≠ k := fun h => hne (by rw [← h, hφz, h])
      have hsz : Equiv.swap z k z = k := Equiv.swap_apply_left z k
      have hsk : Equiv.swap z k k = z := Equiv.swap_apply_right z k
      have hso : ∀ x, x ≠ z → x ≠ k → Equiv.swap z k x = x :=
        fun x h1 h2 => Equiv.swap_apply_of_ne_of_ne h1 h2
      have hkB : (k : α) ∈ B₁ := k.2
      have hcoe : ∀ x : B₁, (x : α) = k → x = k := fun x h => Subtype.ext h
      set Y : Set B₁ := if z ∈ X then insert k X else X \ {k} with hY
      convert hφ Y using 1
  2. The set equality (B₁ \ X) ∪ φ((z k) '' X) = (B₁ \ Y) ∪ φ(Y) holds when both z ∈ X and k ∈ X.

    We unfold set membership into logical equivalences and perform a four-way case split on whether z and k belong to X. When both z ∈ X and k ∈ X, the definition of Y simplifies to Y = X. Furthermore, the swap τ = (z k) stabilizes X because it exchanges z and k and fixes the remaining elements. Since τ is an involution preserving X, the image under τ is X itself, and both sides coincide.

    lines 21–39

    uses Set.mem_union, Set.mem_sdiff, Set.mem_image, Equiv.trans_apply, if_pos, Set.insert_eq_of_mem, Equiv.swap_apply_self

      ext a
      simp only [Set.mem_union, Set.mem_sdiff, Set.mem_image, Equiv.trans_apply]
      by_cases hzX : z ∈ X <;> by_cases hkX : k ∈ X
      · have hYX : Y = X := by rw [hY, if_pos hzX, Set.insert_eq_of_mem hkX]
        rw [hYX]
        have hmem : ∀ x ∈ X, Equiv.swap z k x ∈ X := by
          intro x hx
          by_cases h1 : x = z
          · rw [h1, hsz]; exact hkX
          by_cases h2 : x = k
          · rw [h2, hsk]; exact hzX
          rw [hso x h1 h2]; exact hx
        constructor
        · rintro (h | ⟨x, hx, rfl⟩)
          · exact Or.inl h
          · exact Or.inr ⟨Equiv.swap z k x, hmem x hx, rfl⟩
        · rintro (h | ⟨x, hx, rfl⟩)
          · exact Or.inl h
          · exact Or.inr ⟨Equiv.swap z k x, hmem x hx, by rw [Equiv.swap_apply_self]⟩
  3. The set equality holds when z ∈ X and k ∉ X.

    When z ∈ X and k ∉ X, the definition yields Y = X ∪ {k}. We verify inclusion in both directions: any element a ∈ B₁ \ X is either k (which equals φ(z) ∈ φ(Y)) or differs from k (placing it in B₁ \ Y); conversely, taking k out of B₁ \ X is compensated by φ(z) = k being in the image, while τ maps z ∈ X to k ∈ Y.

    lines 40–67

    uses if_pos, Set.mem_insert_of_mem, Set.mem_insert

      · have hYX : Y = insert k X := by rw [hY, if_pos hzX]
        rw [hYX]
        constructor
        · rintro (⟨haB, ha⟩ | ⟨x, hx, rfl⟩)
          · by_cases hak : a = k
            · exact Or.inr ⟨z, Set.mem_insert_of_mem _ hzX, by rw [hφz, hak]⟩
            · refine Or.inl ⟨haB, ?_⟩
              rintro ⟨x, hx, rfl⟩
              rcases hx with rfl | hx
              · exact hak rfl
              · exact ha ⟨x, hx, rfl⟩
          · refine Or.inr ⟨Equiv.swap z k x, ?_, rfl⟩
            by_cases h1 : x = z
            · rw [h1, hsz]; exact Set.mem_insert _ _
            have h2 : x ≠ k := fun h => hkX (h ▸ hx)
            rw [hso x h1 h2]; exact Set.mem_insert_of_mem _ hx
        · rintro (⟨haB, ha⟩ | ⟨x, hx, rfl⟩)
          · exact Or.inl ⟨haB, fun ⟨x, hx, hxa⟩ => ha ⟨x, Set.mem_insert_of_mem _ hx, hxa⟩⟩
          · rcases hx with rfl | hx
            · exact Or.inr ⟨z, hzX, by rw [hsz]⟩
            · by_cases h1 : x = z
              · subst h1
                refine Or.inl ⟨by rw [hφz]; exact hkB, ?_⟩
                rintro ⟨y, hy, hya⟩
                rw [hφz] at hya
                exact hkX (hcoe y hya ▸ hy)
              · have h2 : x ≠ k := fun h => hkX (h ▸ hx)
                exact Or.inr ⟨x, hx, by rw [hso x h1 h2]⟩
  4. The set equality holds when z ∉ X and k ∈ X.

    When z ∉ X and k ∈ X, we have Y = X \ {k}. Symmetrically to the previous case, k ∈ X is mapped by τ to z, and φ(z) = k. Any element in B₁ \ X is already in B₁ \ Y, while in the image, τ(k) = z ensures that φ(τ(k)) = k ∈ B₁ \ Y, matching the two sides.

    lines 68–88

    uses if_neg

      · have hYX : Y = X \ {k} := by rw [hY, if_neg hzX]
        rw [hYX]
        constructor
        · rintro (⟨haB, ha⟩ | ⟨x, hx, rfl⟩)
          · exact Or.inl ⟨haB, fun ⟨x, hx, hxa⟩ => ha ⟨x, hx.1, hxa⟩⟩
          · by_cases h2 : x = k
            · subst h2
              refine Or.inl ⟨by rw [hsk, hφz]; exact hkB, ?_⟩
              rintro ⟨y, hy, hya⟩
              rw [hsk, hφz] at hya
              exact hy.2 (hcoe y hya)
            · have h1 : x ≠ z := fun h => hzX (h ▸ hx)
              exact Or.inr ⟨x, ⟨hx, h2⟩, by rw [hso x h1 h2]⟩
        · rintro (⟨haB, ha⟩ | ⟨x, hx, rfl⟩)
          · by_cases hak : a = k
            · exact Or.inr ⟨k, hkX, by rw [hsk, hφz, hak]⟩
            · refine Or.inl ⟨haB, ?_⟩
              rintro ⟨x, hx, rfl⟩
              exact ha ⟨x, ⟨hx, fun h => hak (by rw [h])⟩, rfl⟩
          · have h1 : x ≠ z := fun h => hzX (h ▸ hx.1)
            exact Or.inr ⟨x, hx.1, by rw [hso x h1 hx.2]⟩
  5. The set equality holds when neither z nor k belongs to X.

    When z ∉ X and k ∉ X, we have Y = X. Because neither transposed element lies in X, the swap τ fixes every element of X pointwise. Therefore τ '' X = X, so φ(τ '' X) = φ(X) and both sides are identical.

    lines 89–99

    uses if_neg, Set.sdiff_singleton_eq_self

      · have hYX : Y = X := by rw [hY, if_neg hzX, Set.sdiff_singleton_eq_self hkX]
        rw [hYX]
        have hfix : ∀ x ∈ X, Equiv.swap z k x = x := fun x hx =>
          hso x (fun h => hzX (h ▸ hx)) (fun h => hkX (h ▸ hx))
        constructor
        · rintro (h | ⟨x, hx, rfl⟩)
          · exact Or.inl h
          · exact Or.inr ⟨x, hx, by rw [hfix x hx]⟩
        · rintro (h | ⟨x, hx, rfl⟩)
          · exact Or.inl h
          · exact Or.inr ⟨x, hx, by rw [hfix x hx]⟩
  6. To construct an exchange bijection fixing all common elements, it suffices to show by induction on n that any exchange bijection with at most n unfixed common elements can be modified to fix all of B₁ ∩ B₂.

    Because B₁ is finite, the set of common elements not fixed by φ, {x ∈ B₁ ∩ B₂ | φ(x) ≠ x}, is finite. We formulate an induction principle on the cardinality n of this unfixed set; once proved for all n, the desired result follows by taking n to be the cardinality of the unfixed set for φ.

    lines 108–114

    uses le_rfl

      have : Finite B₁ := hfin.to_subtype
      suffices h : ∀ n : ℕ, ∀ φ : B₁ ≃ B₂,
          (∀ X : Set B₁, M.IsBase ((B₁ \ ((↑) '' X)) ∪ ((fun x => (φ x : α)) '' X))) →
          {x : B₁ | (x : α) ∈ B₂ ∧ (φ x : α) ≠ x}.ncard ≤ n →
          ∃ ψ : B₁ ≃ B₂, (∀ X : Set B₁, M.IsBase ((B₁ \ ((↑) '' X)) ∪ ((fun x => (ψ x : α)) '' X)))
            ∧ ∀ x : B₁, (x : α) ∈ B₂ → (ψ x : α) = x from h _ φ hφ le_rfl
      intro n
  7. In the base case n = 0, any exchange bijection with at most 0 unfixed common elements already fixes every element of B₁ ∩ B₂.

    If the unfixed set has cardinality at most 0, it must be empty. If there were any common element x with φ(x) ≠ x, the set would be nonempty and hence have strictly positive cardinality, contradicting the bound. Thus φ already fixes all common elements, so ψ = φ satisfies the requirements.

    lines 115–122

    uses Set.ncard_pos, Set.toFinite

      induction n with
      | zero =>
        intro φ hφ hn
        refine ⟨φ, hφ, fun x hx => ?_⟩
        by_contra h
        have : {x : B₁ | (x : α) ∈ B₂ ∧ (φ x : α) ≠ x}.Nonempty := ⟨x, hx, h⟩
        rw [← Set.ncard_pos (Set.toFinite _)] at this
        omega
  8. In the inductive step, swapping an unfixed common element with its preimage produces an exchange bijection with strictly fewer unfixed common elements, completing the induction.

    If φ already fixes all common elements, we are done. Otherwise, let k ∈ B₁ ∩ B₂ be an unfixed element, and let z = φ⁻¹(k). By lemma sbo_exchange_swap, the modified bijection φ' = τ ∘ φ (with τ = (z k)) preserves the exchange property. Furthermore, φ'(k) = φ(z) = k, so k is now fixed. Any common element not fixed by φ' was already not fixed by φ and cannot be k, so the unfixed set for φ' is contained in that of φ minus {k}. Its cardinality is at most (n + 1) - 1 = n, so the induction hypothesis applies to φ'.

    lines 123–149

    uses sbo_exchange_swap, Equiv.trans_apply, Equiv.swap_apply_right, Set.ncard_le_ncard, Set.toFinite, Set.ncard_sdiff_singleton_of_mem

      | succ n ih =>
        intro φ hφ hn
        by_cases hall : ∀ x : B₁, (x : α) ∈ B₂ → (φ x : α) = x
        · exact ⟨φ, hφ, hall⟩
        push Not at hall
        obtain ⟨k, hk, hne⟩ := hall
        set z := φ.symm ⟨k, hk⟩ with hz
        have hφz : (φ z : α) = k := by simp [hz]
        have hzk : z ≠ k := fun h => hne (by rw [← h, hφz, h])
        set φ' := (Equiv.swap z k).trans φ with hφ'
        apply ih φ' (sbo_exchange_swap M φ hφ k hk hne)
        have hsub : {x : B₁ | (x : α) ∈ B₂ ∧ (φ' x : α) ≠ x} ⊆
            {x : B₁ | (x : α) ∈ B₂ ∧ (φ x : α) ≠ x} \ {k} := by
          rintro x ⟨hx2, hxne⟩
          refine ⟨⟨hx2, ?_⟩, ?_⟩
          · by_cases h1 : x = z
            · rw [h1, hφz]; exact fun h => hzk (Subtype.ext h.symm)
            · by_cases h2 : x = k
              · subst h2; exact hne
              · rwa [hφ', Equiv.trans_apply, Equiv.swap_apply_of_ne_of_ne h1 h2] at hxne
          · rintro rfl
            apply hxne
            rw [hφ', Equiv.trans_apply, Equiv.swap_apply_right, hφz]
        have hk' : k ∈ {x : B₁ | (x : α) ∈ B₂ ∧ (φ x : α) ≠ x} := ⟨hk, hne⟩
        have := Set.ncard_le_ncard hsub (Set.toFinite _)
        rw [Set.ncard_sdiff_singleton_of_mem hk'] at this
        omega
  9. Extend I and J to bases B₁ and B₂, obtain an exchange bijection φ fixing B₁ ∩ B₂, and define the candidate involution p.

    We extend the independent sets I and J to bases B₁ and B₂ of M. By strong base orderability, there exists an exchange bijection between them, and by lemma sbo_exchange_fix_common, we may choose an exchange bijection φ : B₁ ≃ B₂ that fixes every element in B₁ ∩ B₂. We then define p : α → α by sending a ∈ B₁ to φ(a), sending a ∈ B₂ \ B₁ to φ⁻¹(a), and fixing all other elements.

    lines 156–164

    uses sbo_exchange_fix_common

      classical
      obtain ⟨B₁, hB₁, hIB⟩ := hI.exists_isBase_superset
      obtain ⟨B₂, hB₂, hJB⟩ := hJ.exists_isBase_superset
      obtain ⟨φ₀, hφ₀⟩ := hM B₁ B₂ hB₁ hB₂
      obtain ⟨φ, hφ, hfix⟩ := sbo_exchange_fix_common M (M.ground_finite.subset hB₁.subset_ground)
        φ₀ hφ₀
      set p : α → α := fun a =>
        if h : a ∈ B₁ then (φ ⟨a, h⟩ : α) else if h2 : a ∈ B₂ then (φ.symm ⟨a, h2⟩ : α) else a
        with hp
  10. The bijection φ maps every element of B₁ \ B₂ outside of B₁.

    Let a ∈ B₁ \ B₂. If φ(a) were in B₁, then φ(a) would belong to B₁ ∩ B₂. Since φ fixes every element of B₁ ∩ B₂, we would have φ(φ(a)) = φ(a). By injectivity of φ, this implies φ(a) = a, which would place a in B₂, contradicting a ∉ B₂.

    lines 165–173

    uses Subtype.ext, congrArg

      -- an element of `B₁ \ B₂` is sent outside `B₁`
      have hout : ∀ (a : α) (h : a ∈ B₁), a ∉ B₂ → (φ ⟨a, h⟩ : α) ∉ B₁ := by
        intro a h ha hb
        have h2 : (φ ⟨a, h⟩ : α) ∈ B₂ := (φ ⟨a, h⟩).2
        have := hfix ⟨_, hb⟩ h2
        have hinj : φ ⟨(φ ⟨a, h⟩ : α), hb⟩ = φ ⟨a, h⟩ := Subtype.ext this
        have := φ.injective hinj
        have h3 : (φ ⟨a, h⟩ : α) = a := congrArg Subtype.val this
        exact ha (h3 ▸ h2)
  11. The map p is an involution on α.

    We analyze the position of an arbitrary element a with respect to B₁ and B₂. If a ∈ B₁ ∩ B₂, then φ(a) = a, so p(a) = a and p(p(a)) = a. If a ∈ B₁ \ B₂, then p(a) = φ(a) ∈ B₂ \ B₁ by the previous step, so p(p(a)) = φ⁻¹(φ(a)) = a. If a ∈ B₂ \ B₁, then p(a) = φ⁻¹(a) ∈ B₁, so p(p(a)) = φ(φ⁻¹(a)) = a. Finally, if a ∉ B₁ ∪ B₂, p fixes a, so p(p(a)) = a.

    lines 174–189

    uses dif_pos, dif_neg

      refine ⟨p, ?_, ?_⟩
      · intro a
        by_cases h : a ∈ B₁
        · by_cases h2 : a ∈ B₂
          · have hf := hfix ⟨a, h⟩ h2
            simp only [hp, dif_pos h]
            simp only [hf, dif_pos h]
          · have hb := hout a h h2
            have hb2 : (φ ⟨a, h⟩ : α) ∈ B₂ := (φ ⟨a, h⟩).2
            simp only [hp, dif_pos h, dif_neg hb, dif_pos hb2]
            simp
        · by_cases h2 : a ∈ B₂
          · have hc : (φ.symm ⟨a, h2⟩ : α) ∈ B₁ := (φ.symm ⟨a, h2⟩).2
            simp only [hp, dif_neg h, dif_pos h2, dif_pos hc]
            simp
          · simp only [hp, dif_neg h, dif_neg h2]
  12. For any T ⊆ M.E containing no distinct pair {e, p(e)}, showing independence of T reduces to showing T ⊆ B' = (B₁ \ X) ∪ φ(X) for X = {x ∈ B₁ | φ(x) ∈ T ∧ x ∉ B₂}, and every t ∈ T ∩ B₁ belongs to B₁ \ X.

    By the exchange property of φ, the set B' = (B₁ \ X) ∪ φ(X) is a base of M, hence independent. Since any subset of an independent set is independent, it suffices to show T ⊆ B'. For t ∈ T ∩ B₁: if t were in X, then φ(t) ∈ T and t ∉ B₂. Since t ∈ B₁ \ B₂, p(t) = φ(t) ∈ T. The condition on T then forces p(t) = t, meaning φ(t) = t ∈ B₂, which contradicts t ∉ B₂. Thus t ∉ X, so t ∈ B₁ \ X ⊆ B'.

    lines 190–201

      · intro T hT hTp
        set X : Set B₁ := {x | (φ x : α) ∈ T ∧ (x : α) ∉ B₂} with hX
        refine (hφ X).indep.subset ?_
        intro t ht
        by_cases htB : t ∈ B₁
        · refine Or.inl ⟨htB, ?_⟩
          rintro ⟨x, ⟨hxT, hxB⟩, rfl⟩
          have hpx : p x = (φ x : α) := by simp [hp, x.2]
          have := hTp x ht (hpx ▸ hxT)
          rw [hpx] at this
          exact hxB (this ▸ (φ x).2)
        · have htE : t ∈ I ∪ J := hE ▸ hT ht
  13. Every element t ∈ T \ B₁ belongs to φ(X) ⊆ B', establishing T ⊆ B' and completing the proof of independence.

    Since t ∈ T ⊆ M.E = I ∪ J and t ∉ B₁ (which contains I), t must belong to J ⊆ B₂. Let x = φ⁻¹(t) ∈ B₁. If x were in B₂, then x ∈ B₁ ∩ B₂, so φ(x) = x, which would imply t = x ∈ B₁, a contradiction. Thus x ∉ B₂, and since φ(x) = t ∈ T, we have x ∈ X. Consequently, t = φ(x) ∈ φ(X) ⊆ B', which shows T ⊆ B' and proves that T is independent.

    lines 202–213

          have htB2 : t ∈ B₂ := by
            rcases htE with h | h
            · exact absurd (hIB h) htB
            · exact hJB h
          set x := φ.symm ⟨t, htB2⟩ with hx
          have hφx : (φ x : α) = t := by simp [hx]
          have hxB : (x : α) ∉ B₂ := by
            intro h
            have := hfix x h
            rw [hφx] at this
            exact htB (this ▸ x.2)
          exact Or.inr ⟨x, ⟨hφx ▸ ht, hxB⟩, hφx⟩
congrArg
The equality f(a₁) = f(a₂) follows from a₁ = a₂.
dif_neg
A dependent if-then-else evaluates to the else-branch when the condition is false.
dif_pos
A dependent if-then-else evaluates to the then-branch when the condition is true.
Equiv.swap_apply_left
Swapping a and b maps a to b.
Equiv.swap_apply_of_ne_of_ne
Swapping a and b fixes any element distinct from both a and b.
Equiv.swap_apply_right
Swapping a and b maps b to a.
Equiv.swap_apply_self
Applying the swap of two elements twice to any element returns the original element.
Equiv.trans_apply
The composition (f.trans g)(a) is equal to g(f(a)).
if_neg
An if-then-else evaluates to the else-branch when the condition is false.
if_pos
An if-then-else evaluates to the then-branch when the condition is true.
le_rfl
The inequality relation on a preorder is reflexive: a ≤ a.
sbo_exchange_fix_common
In a matroid, an exchange bijection between two finite bases can be chosen to fix every element common to both bases.
sbo_exchange_swap
Composing an exchange bijection with the transposition of an unfixed common element and its preimage preserves the exchange property.
Set.insert_eq_of_mem
Inserting an element into a set that already contains it leaves the set unchanged.
Set.mem_image
An element y is in the image f '' s if and only if y = f(x) for some x ∈ s.
Set.mem_insert
The element x belongs to the set insert x s.
Set.mem_insert_of_mem
If x ∈ s, then x belongs to insert y s.
Set.mem_sdiff
An element belongs to s \ t if and only if it belongs to s and does not belong to t.
Set.mem_union
An element belongs to s ∪ t if and only if it belongs to s or to t.
Set.ncard_le_ncard
A subset of a finite set has cardinality at most that of the ambient set.
Set.ncard_pos
A finite set has strictly positive cardinality if and only if it is nonempty.
Set.ncard_sdiff_singleton_of_mem
Removing an element from a set reduces its cardinality by 1.
Set.sdiff_singleton_eq_self
Removing an element from a set that does not contain it leaves the set unchanged.
Set.toFinite
A set whose subtype is finite is finite as a set.
Subtype.ext
Two elements of a subtype are equal if their underlying values are equal.

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

/-- One swap: composing an exchange bijection `φ : B₁ ≃ B₂` with the transposition of`z = φ⁻¹(k)` and `k` (for `k ∈ B₁ ∩ B₂`) keeps the exchange property. -/theorem sbo_exchange_swap {α : Type*} [DecidableEq α] (M : Matroid α) {B₁ B₂ : Set α} (φ : B₁ ≃ B₂)    (hφ : ∀ X : Set B₁, M.IsBase ((B₁ \ ((↑) '' X)) ∪ ((fun x => (φ x : α)) '' X)))    (k : B₁) (hk : (k : α) ∈ B₂) (hne : (φ k : α) ≠ k) :    ∀ X : Set B₁, M.IsBase ((B₁ \ ((↑) '' X)) ∪      ((fun x => (((Equiv.swap (φ.symm ⟨k, hk⟩) k).trans φ) x : α)) '' X)) := by  classical  intro X  set z := φ.symm ⟨k, hk⟩ with hz  have hφz : (φ z : α) = k := by simp [hz]  have hzk : z ≠ k := fun h => hne (by rw [← h, hφz, h])  have hsz : Equiv.swap z k z = k := Equiv.swap_apply_left z k  have hsk : Equiv.swap z k k = z := Equiv.swap_apply_right z k  have hso : ∀ x, x ≠ z → x ≠ k → Equiv.swap z k x = x :=    fun x h1 h2 => Equiv.swap_apply_of_ne_of_ne h1 h2  have hkB : (k : α) ∈ B₁ := k.2  have hcoe : ∀ x : B₁, (x : α) = k → x = k := fun x h => Subtype.ext h  set Y : Set B₁ := if z ∈ X then insert k X else X \ {k} with hY  convert hφ Y using 1  ext a  simp only [Set.mem_union, Set.mem_sdiff, Set.mem_image, Equiv.trans_apply]  by_cases hzX : z ∈ X <;> by_cases hkX : k ∈ X  · have hYX : Y = X := by rw [hY, if_pos hzX, Set.insert_eq_of_mem hkX]    rw [hYX]    have hmem : ∀ x ∈ X, Equiv.swap z k x ∈ X := by      intro x hx      by_cases h1 : x = z      · rw [h1, hsz]; exact hkX      by_cases h2 : x = k      · rw [h2, hsk]; exact hzX      rw [hso x h1 h2]; exact hx    constructor    · rintro (h | ⟨x, hx, rfl⟩)      · exact Or.inl h      · exact Or.inr ⟨Equiv.swap z k x, hmem x hx, rfl⟩    · rintro (h | ⟨x, hx, rfl⟩)      · exact Or.inl h      · exact Or.inr ⟨Equiv.swap z k x, hmem x hx, by rw [Equiv.swap_apply_self]⟩  · have hYX : Y = insert k X := by rw [hY, if_pos hzX]    rw [hYX]    constructor    · rintro (⟨haB, ha⟩ | ⟨x, hx, rfl⟩)      · by_cases hak : a = k        · exact Or.inr ⟨z, Set.mem_insert_of_mem _ hzX, by rw [hφz, hak]⟩        · refine Or.inl ⟨haB, ?_⟩          rintro ⟨x, hx, rfl⟩          rcases hx with rfl | hx          · exact hak rfl          · exact ha ⟨x, hx, rfl⟩      · refine Or.inr ⟨Equiv.swap z k x, ?_, rfl⟩        by_cases h1 : x = z        · rw [h1, hsz]; exact Set.mem_insert _ _        have h2 : x ≠ k := fun h => hkX (h ▸ hx)        rw [hso x h1 h2]; exact Set.mem_insert_of_mem _ hx    · rintro (⟨haB, ha⟩ | ⟨x, hx, rfl⟩)      · exact Or.inl ⟨haB, fun ⟨x, hx, hxa⟩ => ha ⟨x, Set.mem_insert_of_mem _ hx, hxa⟩⟩      · rcases hx with rfl | hx        · exact Or.inr ⟨z, hzX, by rw [hsz]⟩        · by_cases h1 : x = z          · subst h1            refine Or.inl ⟨by rw [hφz]; exact hkB, ?_⟩            rintro ⟨y, hy, hya⟩            rw [hφz] at hya            exact hkX (hcoe y hya ▸ hy)          · have h2 : x ≠ k := fun h => hkX (h ▸ hx)            exact Or.inr ⟨x, hx, by rw [hso x h1 h2]⟩  · have hYX : Y = X \ {k} := by rw [hY, if_neg hzX]    rw [hYX]    constructor    · rintro (⟨haB, ha⟩ | ⟨x, hx, rfl⟩)      · exact Or.inl ⟨haB, fun ⟨x, hx, hxa⟩ => ha ⟨x, hx.1, hxa⟩⟩      · by_cases h2 : x = k        · subst h2          refine Or.inl ⟨by rw [hsk, hφz]; exact hkB, ?_⟩          rintro ⟨y, hy, hya⟩          rw [hsk, hφz] at hya          exact hy.2 (hcoe y hya)        · have h1 : x ≠ z := fun h => hzX (h ▸ hx)          exact Or.inr ⟨x, ⟨hx, h2⟩, by rw [hso x h1 h2]⟩    · rintro (⟨haB, ha⟩ | ⟨x, hx, rfl⟩)      · by_cases hak : a = k        · exact Or.inr ⟨k, hkX, by rw [hsk, hφz, hak]⟩        · refine Or.inl ⟨haB, ?_⟩          rintro ⟨x, hx, rfl⟩          exact ha ⟨x, ⟨hx, fun h => hak (by rw [h])⟩, rfl⟩      · have h1 : x ≠ z := fun h => hzX (h ▸ hx.1)        exact Or.inr ⟨x, hx.1, by rw [hso x h1 hx.2]⟩  · have hYX : Y = X := by rw [hY, if_neg hzX, Set.sdiff_singleton_eq_self hkX]    rw [hYX]    have hfix : ∀ x ∈ X, Equiv.swap z k x = x := fun x hx =>      hso x (fun h => hzX (h ▸ hx)) (fun h => hkX (h ▸ hx))    constructor    · rintro (h | ⟨x, hx, rfl⟩)      · exact Or.inl h      · exact Or.inr ⟨x, hx, by rw [hfix x hx]⟩    · rintro (h | ⟨x, hx, rfl⟩)      · exact Or.inl h      · exact Or.inr ⟨x, hx, by rw [hfix x hx]⟩/-- In a matroid, an exchange bijection between two finite bases can be chosen to fix everyelement the two bases share. -/theorem sbo_exchange_fix_common {α : Type*} [DecidableEq α] (M : Matroid α) {B₁ B₂ : Set α} (hfin : B₁.Finite)    (φ : B₁ ≃ B₂)    (hφ : ∀ X : Set B₁, M.IsBase ((B₁ \ ((↑) '' X)) ∪ ((fun x => (φ x : α)) '' X))) :    ∃ ψ : B₁ ≃ B₂, (∀ X : Set B₁, M.IsBase ((B₁ \ ((↑) '' X)) ∪ ((fun x => (ψ x : α)) '' X)))      ∧ ∀ x : B₁, (x : α) ∈ B₂ → (ψ x : α) = x := by  have : Finite B₁ := hfin.to_subtype  suffices h : ∀ n : ℕ, ∀ φ : B₁ ≃ B₂,      (∀ X : Set B₁, M.IsBase ((B₁ \ ((↑) '' X)) ∪ ((fun x => (φ x : α)) '' X))) →      {x : B₁ | (x : α) ∈ B₂ ∧ (φ x : α) ≠ x}.ncard ≤ n →      ∃ ψ : B₁ ≃ B₂, (∀ X : Set B₁, M.IsBase ((B₁ \ ((↑) '' X)) ∪ ((fun x => (ψ x : α)) '' X)))        ∧ ∀ x : B₁, (x : α) ∈ B₂ → (ψ x : α) = x from h _ φ hφ le_rfl  intro n  induction n with  | zero =>    intro φ hφ hn    refine ⟨φ, hφ, fun x hx => ?_⟩    by_contra h    have : {x : B₁ | (x : α) ∈ B₂ ∧ (φ x : α) ≠ x}.Nonempty := ⟨x, hx, h⟩    rw [← Set.ncard_pos (Set.toFinite _)] at this    omega  | succ n ih =>    intro φ hφ hn    by_cases hall : ∀ x : B₁, (x : α) ∈ B₂ → (φ x : α) = x    · exact ⟨φ, hφ, hall⟩    push Not at hall    obtain ⟨k, hk, hne⟩ := hall    set z := φ.symm ⟨k, hk⟩ with hz    have hφz : (φ z : α) = k := by simp [hz]    have hzk : z ≠ k := fun h => hne (by rw [← h, hφz, h])    set φ' := (Equiv.swap z k).trans φ with hφ'    apply ih φ' (sbo_exchange_swap M φ hφ k hk hne)    have hsub : {x : B₁ | (x : α) ∈ B₂ ∧ (φ' x : α) ≠ x} ⊆        {x : B₁ | (x : α) ∈ B₂ ∧ (φ x : α) ≠ x} \ {k} := by      rintro x ⟨hx2, hxne⟩      refine ⟨⟨hx2, ?_⟩, ?_⟩      · by_cases h1 : x = z        · rw [h1, hφz]; exact fun h => hzk (Subtype.ext h.symm)        · by_cases h2 : x = k          · subst h2; exact hne          · rwa [hφ', Equiv.trans_apply, Equiv.swap_apply_of_ne_of_ne h1 h2] at hxne      · rintro rfl        apply hxne        rw [hφ', Equiv.trans_apply, Equiv.swap_apply_right, hφz]    have hk' : k ∈ {x : B₁ | (x : α) ∈ B₂ ∧ (φ x : α) ≠ x} := ⟨hk, hne⟩    have := Set.ncard_le_ncard hsub (Set.toFinite _)    rw [Set.ncard_sdiff_singleton_of_mem hk'] at this    omegatheorem matroid_sbo_reduction_pairs_of_two_indep {α : Type*} (M : Matroid α) [M.Finite]    (hM : matroid_strongly_base_orderable M) (I J : Set α) (hI : M.Indep I) (hJ : M.Indep J)    (hIJ : Disjoint I J) (hE : I ∪ J = M.E) :    ∃ p : α → α, Function.Involutive p ∧      ∀ T ⊆ M.E, (∀ e ∈ T, p e ∈ T → p e = e) → M.Indep T := by  classical  obtain ⟨B₁, hB₁, hIB⟩ := hI.exists_isBase_superset  obtain ⟨B₂, hB₂, hJB⟩ := hJ.exists_isBase_superset  obtain ⟨φ₀, hφ₀⟩ := hM B₁ B₂ hB₁ hB₂  obtain ⟨φ, hφ, hfix⟩ := sbo_exchange_fix_common M (M.ground_finite.subset hB₁.subset_ground)    φ₀ hφ₀  set p : α → α := fun a =>    if h : a ∈ B₁ then (φ ⟨a, h⟩ : α) else if h2 : a ∈ B₂ then (φ.symm ⟨a, h2⟩ : α) else a    with hp  -- an element of `B₁ \ B₂` is sent outside `B₁`  have hout : ∀ (a : α) (h : a ∈ B₁), a ∉ B₂ → (φ ⟨a, h⟩ : α) ∉ B₁ := by    intro a h ha hb    have h2 : (φ ⟨a, h⟩ : α) ∈ B₂ := (φ ⟨a, h⟩).2    have := hfix ⟨_, hb⟩ h2    have hinj : φ ⟨(φ ⟨a, h⟩ : α), hb⟩ = φ ⟨a, h⟩ := Subtype.ext this    have := φ.injective hinj    have h3 : (φ ⟨a, h⟩ : α) = a := congrArg Subtype.val this    exact ha (h3 ▸ h2)  refine ⟨p, ?_, ?_⟩  · intro a    by_cases h : a ∈ B₁    · by_cases h2 : a ∈ B₂      · have hf := hfix ⟨a, h⟩ h2        simp only [hp, dif_pos h]        simp only [hf, dif_pos h]      · have hb := hout a h h2        have hb2 : (φ ⟨a, h⟩ : α) ∈ B₂ := (φ ⟨a, h⟩).2        simp only [hp, dif_pos h, dif_neg hb, dif_pos hb2]        simp    · by_cases h2 : a ∈ B₂      · have hc : (φ.symm ⟨a, h2⟩ : α) ∈ B₁ := (φ.symm ⟨a, h2⟩).2        simp only [hp, dif_neg h, dif_pos h2, dif_pos hc]        simp      · simp only [hp, dif_neg h, dif_neg h2]  · intro T hT hTp    set X : Set B₁ := {x | (φ x : α) ∈ T ∧ (x : α) ∉ B₂} with hX    refine (hφ X).indep.subset ?_    intro t ht    by_cases htB : t ∈ B₁    · refine Or.inl ⟨htB, ?_⟩      rintro ⟨x, ⟨hxT, hxB⟩, rfl⟩      have hpx : p x = (φ x : α) := by simp [hp, x.2]      have := hTp x ht (hpx ▸ hxT)      rw [hpx] at this      exact hxB (this ▸ (φ x).2)    · have htE : t ∈ I ∪ J := hE ▸ hT ht      have htB2 : t ∈ B₂ := by        rcases htE with h | h        · exact absurd (hIB h) htB        · exact hJB h      set x := φ.symm ⟨t, htB2⟩ with hx      have hφx : (φ x : α) = t := by simp [hx]      have hxB : (x : α) ∉ B₂ := by        intro h        have := hfix x h        rw [hφx] at this        exact htB (this ▸ x.2)      exact Or.inr ⟨x, ⟨hφx ▸ ht, hxB⟩, hφx⟩
See it in the graphDiscuss this resultChallenge it