AFTD Auto-Formalizing Theoretical Domains

wild_involution_finite_pattern_isomorphism_extends

theoremverified

Two injectively embedded copies of the same closed finite involution pattern are aligned by a global matching isomorphism, when each ambient involution has one fixed point.

Statement

theorem wild_involution_finite_pattern_isomorphism_extends
    {V J : Type*} [Fintype V] [Fintype J] [DecidableEq V]
    (f g : Equiv.Perm V) (hf : Function.Involutive f) (hg : Function.Involutive g)
    (a b : V) (hfa : ∀ x, f x = x ↔ x = a) (hgb : ∀ x, g x = x ↔ x = b)
    (π : Equiv.Perm J) (v w : J → V)
    (hv : Function.Injective v) (hw : Function.Injective w)
    (hfv : ∀ j, f (v j) = v (π j)) (hgw : ∀ j, g (w j) = w (π j)) :
    ∃ e : Equiv.Perm V, (∀ x, e (f x) = g (e x)) ∧ (∀ j, e (v j) = w j)
Source
IN-382 / OP-306 campaign9, 2026-10-30. Standard finite involution conjugacy and permutation transport, supporting the moment route for https://arxiv.org/html/2610.22142v1. Background https://arxiv.org/abs/0911.3604 . No new wild-number bound or research advance is claimed.
Verified
30 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1

The proof, explained

To extend the pattern isomorphism between two embeddings v, w : J → V, we consider their images S = v(J) and T = w(J). Using the equivariance of v and w with respect to π, we show that S is f-invariant and T is g-invariant, and that the induced bijection eS : S ≃ T intertwines f and g. Furthermore, the unique fixed points satisfy a ∈ S ↔ b ∈ T because any index fixing one embedding must fix π and therefore fix the other. Applying the partial isomorphism extension theorem wild_involution_closed_partial_isomorphism_extends yields a global automorphism e conjugating f to g that extends eS, and hence sends each v(j) to w(j).

  1. Define the image finsets S = v(J) and T = w(J) in V, confirming that each v(j) ∈ S and each w(j) ∈ T.

    We define S and T as the images of the universal set univ under the embeddings v and w. For every index j ∈ J, its image v(j) belongs to S because j ∈ univ, and similarly w(j) belongs to T.

    lines 14–18

    uses mem_image.mpr, mem_univ

      classical
      let S : Finset V := univ.image v
      let T : Finset V := univ.image w
      have hvS : ∀ j, v j ∈ S := fun j => mem_image.mpr ⟨j,mem_univ _,rfl⟩
      have hwT : ∀ j, w j ∈ T := fun j => mem_image.mpr ⟨j,mem_univ _,rfl⟩
  2. The finset S is invariant under the involution f, that is, f(x) ∈ S if and only if x ∈ S.

    If f(x) ∈ S, then f(x) = v(j) for some j. Applying the involution f to both sides and using f(v(j)) = v(π(j)) gives x = f(f(x)) = f(v(j)) = v(π(j)) ∈ S. Conversely, if x ∈ S, then x = v(j) for some j, so f(x) = f(v(j)) = v(π(j)) ∈ S.

    lines 19–28

    uses mem_image.mp

      have hS : ∀ x, f x ∈ S ↔ x ∈ S := by
        intro x
        constructor
        · rintro hx
          obtain ⟨j,_,hj⟩ := mem_image.mp hx
          have heq : x = v (π j) := by rw [← hfv, hj, hf]
          rw [heq]; exact hvS _
        · intro hx
          obtain ⟨j,_,rfl⟩ := mem_image.mp hx
          rw [hfv]; exact hvS _
  3. The finset T is invariant under the involution g, that is, g(x) ∈ T if and only if x ∈ T.

    Analogously to S, if g(x) ∈ T, then g(x) = w(j) for some j, which implies x = g(w(j)) = w(π(j)) ∈ T using g(g(x)) = x. Conversely, if x = w(j) ∈ T, then g(x) = w(π(j)) ∈ T.

    lines 29–38

    uses mem_image.mp

      have hT : ∀ x, g x ∈ T ↔ x ∈ T := by
        intro x
        constructor
        · intro hx
          obtain ⟨j,_,hj⟩ := mem_image.mp hx
          have heq : x = w (π j) := by rw [← hgw, hj, hg]
          rw [heq]; exact hwT _
        · intro hx
          obtain ⟨j,_,rfl⟩ := mem_image.mp hx
          rw [hgw]; exact hwT _
  4. Construct an equivalence eS : S ≃ T mapping each v(j) to w(j).

    Because v is injective and maps onto S by definition, it defines a bijection ev : J ≃ S. Similarly, w defines a bijection ew : J ≃ T. Composing the inverse of ev with ew gives the equivalence eS = ew ∘ ev⁻¹ from S to T, which satisfies eS(v(j)) = w(j) for all j ∈ J.

    lines 39–52

    uses Equiv.ofBijective, congrArg, Subtype.val, mem_image.mp, Subtype.ext

      let ev : J ≃ {x // x ∈ S} := Equiv.ofBijective (fun j => ⟨v j,hvS j⟩) (by
        constructor
        · intro i j h; exact hv (congrArg Subtype.val h)
        · intro x
          obtain ⟨j,_,hj⟩ := mem_image.mp x.property
          exact ⟨j,Subtype.ext hj⟩)
      let ew : J ≃ {x // x ∈ T} := Equiv.ofBijective (fun j => ⟨w j,hwT j⟩) (by
        constructor
        · intro i j h; exact hw (congrArg Subtype.val h)
        · intro x
          obtain ⟨j,_,hj⟩ := mem_image.mp x.property
          exact ⟨j,Subtype.ext hj⟩)
      let eS : {x // x ∈ S} ≃ {x // x ∈ T} := ev.symm.trans ew
      have hev : ∀ j, eS (ev j) = ew j := by intro j; simp [eS]
  5. The bijection eS intertwines f on S and g on T: eS(f(x)) = g(eS(x)) for all x ∈ S.

    Any x ∈ S can be written as ev(j) = v(j) for some j ∈ J. Then f(x) = f(v(j)) = v(π(j)) = ev(π(j)). Applying eS gives eS(ev(π(j))) = ew(π(j)) = w(π(j)). Since g(w(j)) = w(π(j)), this equals g(ew(j)) = g(eS(x)).

    lines 53–61

    uses Subtype.ext

      have heS : ∀ x : {x // x ∈ S},
          (eS ⟨f x.val,(hS x.val).mpr x.property⟩).val = g (eS x).val := by
        intro x
        obtain ⟨j,rfl⟩ := ev.surjective x
        have hval : (ev j).val = v j := rfl
        have heq : (⟨f (ev j).val,(hS (ev j).val).mpr (ev j).property⟩ : {x // x ∈ S}) =
            ev (π j) := Subtype.ext (hfv j)
        rw [heq,hev,hev]
        exact (hgw j).symm
  6. The fixed point a of f lies in S if and only if the fixed point b of g lies in T.

    If a ∈ S, then a = v(j) for some j. Since a is the unique fixed point of f, f(v(j)) = v(j). But f(v(j)) = v(π(j)), so injectivity of v implies π(j) = j. Then g(w(j)) = w(π(j)) = w(j), meaning w(j) is fixed by g, hence w(j) = b and b ∈ T. The reverse implication is symmetric, using the injectivity of w.

    lines 62–73

    uses mem_image.mp, mem_image.mpr, mem_univ

      have hmem : a ∈ S ↔ b ∈ T := by
        constructor
        · intro ha
          obtain ⟨j,_,hj⟩ := mem_image.mp ha
          have hp : π j = j := hv (by rw [← hfv,hj,(hfa a).mpr rfl])
          have hjb : w j = b := (hgb _).mp (by rw [hgw,hp])
          exact mem_image.mpr ⟨j,mem_univ _,hjb⟩
        · intro hb
          obtain ⟨j,_,hj⟩ := mem_image.mp hb
          have hp : π j = j := hw (by rw [← hgw,hj,(hgb b).mpr rfl])
          have hja : v j = a := (hfa _).mp (by rw [hfv,hp])
          exact mem_image.mpr ⟨j,mem_univ _,hja⟩
  7. Extend eS to a global permutation e of V commuting with f and g.

    Since S and T are invariant under f and g, eS commutes with the involutions on S and T, and the unique fixed points satisfy a ∈ S ↔ b ∈ T, the lemma wild_involution_closed_partial_isomorphism_extends provides a global permutation e of V such that e(f(x)) = g(e(x)) for all x and e coincides with eS on S.

    lines 74–75

    uses wild_involution_closed_partial_isomorphism_extends

      obtain ⟨e,he,hext⟩ := wild_involution_closed_partial_isomorphism_extends
        f g hf hg a b hfa hgb S T hS hT hmem eS heS
  8. The global permutation e satisfies e(v(j)) = w(j) for all j ∈ J.

    For any j ∈ J, the extension property gives e(v(j)) = eS(v(j)). By definition of eS, eS(v(j)) = w(j), completing the proof.

    lines 76–80

      refine ⟨e,he,?_⟩
      intro j
      have hh := hext (ev j)
      rw [hev] at hh
      exact hh
mem_image.mpr
An element b belongs to the image of a finset s under a function if there is some a ∈ s mapping to b.
mem_image.mp
If an element b belongs to the image of a finset s under a function, then there is some a ∈ s mapping to b.
mem_univ
Every element of a finite type belongs to the universal finset univ.
Equiv.ofBijective
A bijective function between types gives rise to an equivalence (bijection).
congrArg
Applying a function to equal inputs yields equal outputs.
Subtype.val
Extracts the underlying value from a subtype element.
Subtype.ext
Two subtype elements are equal if their underlying values are equal.
wild_involution_closed_partial_isomorphism_extends
A partial isomorphism between closed invariant finite subsets under involutions with unique fixed points extends to a global conjugacy permutation, provided the unique fixed points either both belong to or both lie outside the invariant subsets.

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

open Finsetopen scoped BigOperators Classicalset_option maxHeartbeats 4000000set_option maxRecDepth 10000theorem wild_involution_finite_pattern_isomorphism_extends    {V J : Type*} [Fintype V] [Fintype J] [DecidableEq V]    (f g : Equiv.Perm V) (hf : Function.Involutive f) (hg : Function.Involutive g)    (a b : V) (hfa : ∀ x, f x = x ↔ x = a) (hgb : ∀ x, g x = x ↔ x = b)    (π : Equiv.Perm J) (v w : J → V)    (hv : Function.Injective v) (hw : Function.Injective w)    (hfv : ∀ j, f (v j) = v (π j)) (hgw : ∀ j, g (w j) = w (π j)) :    ∃ e : Equiv.Perm V, (∀ x, e (f x) = g (e x)) ∧ (∀ j, e (v j) = w j) := by  classical  let S : Finset V := univ.image v  let T : Finset V := univ.image w  have hvS : ∀ j, v j ∈ S := fun j => mem_image.mpr ⟨j,mem_univ _,rfl⟩  have hwT : ∀ j, w j ∈ T := fun j => mem_image.mpr ⟨j,mem_univ _,rfl⟩  have hS : ∀ x, f x ∈ S ↔ x ∈ S := by    intro x    constructor    · rintro hx      obtain ⟨j,_,hj⟩ := mem_image.mp hx      have heq : x = v (π j) := by rw [← hfv, hj, hf]      rw [heq]; exact hvS _    · intro hx      obtain ⟨j,_,rfl⟩ := mem_image.mp hx      rw [hfv]; exact hvS _  have hT : ∀ x, g x ∈ T ↔ x ∈ T := by    intro x    constructor    · intro hx      obtain ⟨j,_,hj⟩ := mem_image.mp hx      have heq : x = w (π j) := by rw [← hgw, hj, hg]      rw [heq]; exact hwT _    · intro hx      obtain ⟨j,_,rfl⟩ := mem_image.mp hx      rw [hgw]; exact hwT _  let ev : J ≃ {x // x ∈ S} := Equiv.ofBijective (fun j => ⟨v j,hvS j⟩) (by    constructor    · intro i j h; exact hv (congrArg Subtype.val h)    · intro x      obtain ⟨j,_,hj⟩ := mem_image.mp x.property      exact ⟨j,Subtype.ext hj⟩)  let ew : J ≃ {x // x ∈ T} := Equiv.ofBijective (fun j => ⟨w j,hwT j⟩) (by    constructor    · intro i j h; exact hw (congrArg Subtype.val h)    · intro x      obtain ⟨j,_,hj⟩ := mem_image.mp x.property      exact ⟨j,Subtype.ext hj⟩)  let eS : {x // x ∈ S} ≃ {x // x ∈ T} := ev.symm.trans ew  have hev : ∀ j, eS (ev j) = ew j := by intro j; simp [eS]  have heS : ∀ x : {x // x ∈ S},      (eS ⟨f x.val,(hS x.val).mpr x.property⟩).val = g (eS x).val := by    intro x    obtain ⟨j,rfl⟩ := ev.surjective x    have hval : (ev j).val = v j := rfl    have heq : (⟨f (ev j).val,(hS (ev j).val).mpr (ev j).property⟩ : {x // x ∈ S}) =        ev (π j) := Subtype.ext (hfv j)    rw [heq,hev,hev]    exact (hgw j).symm  have hmem : a ∈ S ↔ b ∈ T := by    constructor    · intro ha      obtain ⟨j,_,hj⟩ := mem_image.mp ha      have hp : π j = j := hv (by rw [← hfv,hj,(hfa a).mpr rfl])      have hjb : w j = b := (hgb _).mp (by rw [hgw,hp])      exact mem_image.mpr ⟨j,mem_univ _,hjb⟩    · intro hb      obtain ⟨j,_,hj⟩ := mem_image.mp hb      have hp : π j = j := hw (by rw [← hgw,hj,(hgb b).mpr rfl])      have hja : v j = a := (hfa _).mp (by rw [hfv,hp])      exact mem_image.mpr ⟨j,mem_univ _,hja⟩  obtain ⟨e,he,hext⟩ := wild_involution_closed_partial_isomorphism_extends    f g hf hg a b hfa hgb S T hS hT hmem eS heS  refine ⟨e,he,?_⟩  intro j  have hh := hext (ev j)  rw [hev] at hh  exact hh
See it in the graphDiscuss this resultChallenge it