AFTD Auto-Formalizing Theoretical Domains

wild_involution_partial_pattern_isomorphism_extends

theoremverified

An isomorphism of arbitrary injective finite patterns, preserving every partner equality including fixed points, extends to an isomorphism of ambient involutions each having a unique fixed point.

Statement

theorem wild_involution_partial_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)
    (v w : J → V) (hv : Function.Injective v) (hw : Function.Injective w)
    (hpattern : ∀ j k, f (v j) = v k ↔ g (w j) = w k) :
    ∃ 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
Used by 2

The proof, explained

The proof extends the partial pattern isomorphism v ↦ w to an ambient automorphism conjugating f to g by first completing the patterns to their involution closures. We define S = v(J) ∪ f(v(J)) and T = w(J) ∪ g(w(J)) and show that the pattern-preservation hypothesis implies that the natural parameterizations from J × Bool to S and T share identical fibers. This gives a well-defined equivariant bijection eS : S ≃ T, which necessarily relates the unique fixed points of f and g. Finally, applying the closed extension theorem wild_involution_closed_partial_isomorphism_extends extends eS to a global automorphism e of V conjugating f to g that sends each v(j) to w(j).

  1. The families uv and uw represent the pattern points and their involution partners, and flipping the boolean tag corresponds to applying the ambient involutions f and g.

    We define uv(j, c) to be f(v(j)) if c is true and v(j) if c is false, and define uw(j, c) similarly using g and w. Defining flip(j, c) = (j, ¬c), we check that uv(flip(z)) = f(uv(z)) and uw(flip(z)) = g(uw(z)); when c is false this is the definition, and when c is true it follows from f and g being involutions (f(f(x)) = x and g(g(x)) = x).

    lines 13–24

      classical
      let uv : J × Bool → V := fun z => if z.2 then f (v z.1) else v z.1
      let uw : J × Bool → V := fun z => if z.2 then g (w z.1) else w z.1
      let flip : J × Bool → J × Bool := fun z => (z.1,!z.2)
      have hvflip : ∀ z, uv (flip z) = f (uv z) := by
        rintro ⟨j,c⟩; cases c
        · rfl
        · exact (hf (v j)).symm
      have hwflip : ∀ z, uw (flip z) = g (uw z) := by
        rintro ⟨j,c⟩; cases c
        · rfl
        · exact (hg (w j)).symm
  2. The maps uv and uw have identical kernels: uv(z) = uv(z') if and only if uw(z) = uw(z') for all z, z' ∈ J × Bool.

    We split into cases on the boolean tags of z = (j, c) and z' = (k, d). If both are false, this is v(j) = v(k) ↔ w(j) = w(k), which holds by injectivity of v and w. If one is false and the other true, it reduces to f(v(j)) = v(k) ↔ g(w(j)) = w(k), which is the pattern preservation hypothesis hpattern. If both are true, it asserts f(v(j)) = f(v(k)) ↔ g(w(j)) = g(w(k)), which reduces to v(j) = v(k) ↔ w(j) = w(k) since f and g are permutations.

    lines 25–33

    uses Bool.false_eq_true, if_false, if_true, eq_comm

      have hkernel : ∀ z z', uv z = uv z' ↔ uw z = uw z' := by
        rintro ⟨j,c⟩ ⟨k,d⟩
        cases c <;> cases d
        · simp only [uv,uw,Bool.false_eq_true,if_false]
          exact hv.eq_iff.trans hw.eq_iff.symm
        · simpa only [uv,uw,Bool.false_eq_true,if_false,if_true,eq_comm] using hpattern k j
        · simpa only [uv,uw,Bool.false_eq_true,if_false,if_true] using hpattern j k
        · simp only [uv,uw,if_true,f.injective.eq_iff,g.injective.eq_iff]
          exact hv.eq_iff.trans hw.eq_iff.symm
  3. The images S = range(uv) and T = range(uw) are finite subsets of V closed under f and g, respectively.

    We define S and T as the finset images of uv and uw. For any x, if f(x) ∈ S, then f(x) = uv(z) for some z, so x = f(f(x)) = f(uv(z)) = uv(flip(z)) ∈ S. Conversely, if x = uv(z) ∈ S, then f(x) = uv(flip(z)) ∈ S. An identical calculation with g and uw shows that g(x) ∈ T ↔ x ∈ T.

    lines 34–57

    uses mem_univ

      let S : Finset V := univ.image uv
      let T : Finset V := univ.image uw
      have hvS : ∀ z, uv z ∈ S := fun z => mem_image.mpr ⟨z,mem_univ _,rfl⟩
      have hwT : ∀ z, uw z ∈ T := fun z => mem_image.mpr ⟨z,mem_univ _,rfl⟩
      have hS : ∀ x, f x ∈ S ↔ x ∈ S := by
        intro x
        constructor
        · intro hx
          obtain ⟨z,_,hz⟩ := mem_image.mp hx
          have hh : uv (flip z) = x := by rw [hvflip,hz,hf]
          exact mem_image.mpr ⟨flip z,mem_univ _,hh⟩
        · intro hx
          obtain ⟨z,_,rfl⟩ := mem_image.mp hx
          rw [← hvflip]; exact hvS _
      have hT : ∀ x, g x ∈ T ↔ x ∈ T := by
        intro x
        constructor
        · intro hx
          obtain ⟨z,_,hz⟩ := mem_image.mp hx
          have hh : uw (flip z) = x := by rw [hwflip,hz,hg]
          exact mem_image.mpr ⟨flip z,mem_univ _,hh⟩
        · intro hx
          obtain ⟨z,_,rfl⟩ := mem_image.mp hx
          rw [← hwflip]; exact hwT _
  4. There is a bijection eS : S ≃ T satisfying eS(uv(z)) = uw(z) for all z ∈ J × Bool.

    Viewing uv and uw as surjections sv : J × Bool ↠ S and tw : J × Bool ↠ T, their fibers coincide because they have the same kernel. Using choice, we pick for each x ∈ S a representative pick(x) in its preimage fiber under sv. Defining eS(x) = tw(pick(x)) gives a bijection via Equiv.ofBijective, and eS(sv(z)) = tw(z) holds for all z.

    lines 58–79

    uses Subtype.ext, Subtype.ext_iff, Classical.choose, Classical.choose_spec, Equiv.ofBijective

      let sv : J × Bool → {x // x ∈ S} := fun z => ⟨uv z,hvS z⟩
      let tw : J × Bool → {x // x ∈ T} := fun z => ⟨uw z,hwT z⟩
      have hsv : Function.Surjective sv := by
        intro x; obtain ⟨z,_,hz⟩ := mem_image.mp x.property
        exact ⟨z,Subtype.ext hz⟩
      have htw : Function.Surjective tw := by
        intro x; obtain ⟨z,_,hz⟩ := mem_image.mp x.property
        exact ⟨z,Subtype.ext hz⟩
      have hker : ∀ z z', sv z = sv z' ↔ tw z = tw z' := by
        intro z z'
        simpa only [Subtype.ext_iff] using hkernel z z'
      let pick : {x // x ∈ S} → J × Bool := fun x => Classical.choose (hsv x)
      have hpick : ∀ x, sv (pick x) = x := fun x => Classical.choose_spec (hsv x)
      let eS : {x // x ∈ S} ≃ {x // x ∈ T} := Equiv.ofBijective (fun x => tw (pick x)) (by
        constructor
        · intro x y h
          have hh := (hker (pick x) (pick y)).mpr h
          simpa only [hpick] using hh
        · intro y
          obtain ⟨z,rfl⟩ := htw y
          exact ⟨sv z,(hker _ _).mp (hpick (sv z))⟩)
      have heval : ∀ z, eS (sv z) = tw z := fun z => (hker _ _).mp (hpick (sv z))
  5. The bijection eS is an equivariant isomorphism: eS(f(x)) = g(eS(x)) for all x ∈ S.

    Every x ∈ S can be written as sv(z). The action of f on S corresponds to flip on J × Bool, since f(sv(z)) = sv(flip(z)). Since eS evaluates sv to tw, we compute eS(f(x)) = eS(sv(flip(z))) = tw(flip(z)) = g(tw(z)) = g(eS(x)).

    lines 80–87

    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 ⟨z,rfl⟩ := hsv x
        have hh : (⟨f (sv z).val,(hS (sv z).val).mpr (sv z).property⟩ : {x // x ∈ S}) =
            sv (flip z) := Subtype.ext (hvflip z).symm
        rw [hh,heval,heval]
        exact hwflip z
  6. The unique fixed point a of f lies in S if and only if the unique fixed point b of g lies in T.

    If a ∈ S, then f(a) = a implies g(eS(a)) = eS(f(a)) = eS(a). Because b is the unique fixed point of g, eS(a) = b, which shows b ∈ T. Conversely, if b ∈ T, by surjectivity of eS we have b = eS(x) for some x ∈ S. Then eS(f(x)) = g(eS(x)) = g(b) = b = eS(x). By injectivity of eS, f(x) = x, so x must be the unique fixed point a of f, proving a ∈ S.

    lines 88–110

    uses Subtype.ext, congrArg

      have hmem : a ∈ S ↔ b ∈ T := by
        constructor
        · intro ha
          let x : {x // x ∈ S} := ⟨a,ha⟩
          have heq : (⟨f x.val,(hS x.val).mpr x.property⟩ : {x // x ∈ S}) = x :=
            Subtype.ext ((hfa a).mpr rfl)
          have hh := heS x
          rw [heq] at hh
          have hb : (eS x).val = b := (hgb _).mp hh.symm
          exact hb ▸ (eS x).property
        · intro hb
          obtain ⟨x,hx⟩ := eS.surjective ⟨b,hb⟩
          have hh := heS x
          have hxval : (eS x).val = b := congrArg Subtype.val hx
          rw [hxval,(hgb b).mpr rfl] at hh
          have hfix : f x.val = x.val := by
            have hsub : (⟨f x.val,(hS x.val).mpr x.property⟩ : {x // x ∈ S}) = x := by
              apply eS.injective
              apply Subtype.ext
              exact hh.trans hxval.symm
            exact congrArg Subtype.val hsub
          have ha : x.val = a := (hfa _).mp hfix
          exact ha ▸ x.property
  7. The equivariant bijection eS extends to an ambient permutation e of V conjugating f to g and mapping each v(j) to w(j).

    Applying wild_involution_closed_partial_isomorphism_extends with invariant sets S and T and equivariant bijection eS yields a permutation e of V such that e(f(x)) = g(e(x)) for all x ∈ V, and e agrees with eS on S. For each j ∈ J, v(j) = uv(j, false) ∈ S, so e(v(j)) = eS(sv(j, false)) = tw(j, false) = w(j).

    lines 111–117

    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
      refine ⟨e,he,?_⟩
      intro j
      have hh := hext (sv (j,false))
      rw [heval] at hh
      exact hh
Bool.false_eq_true
The proposition (false = true) is False.
if_false
An if-then-else expression with condition False reduces to its else branch.
if_true
An if-then-else expression with condition True reduces to its then branch.
eq_comm
Equality is symmetric: a = b is equivalent to b = a.
mem_univ
Every element of a finite type belongs to the universal finset univ.
Subtype.ext
Two subtype elements are equal if their underlying values are equal.
Subtype.ext_iff
Two subtype elements are equal if and only if their underlying values are equal.
Classical.choose
Produces an explicit witness from an existential proof.
Classical.choose_spec
The witness chosen by Classical.choose satisfies the property.
Equiv.ofBijective
A bijective map between types forms an equivalence (bijection).
congrArg
If two inputs are equal, then applying any function to them yields equal outputs.
wild_involution_closed_partial_isomorphism_extends
An equivariant isomorphism between involution-closed finite subsets, which preserves the condition of containing the unique fixed points, extends to an ambient automorphism conjugating the two involutions.

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_partial_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)    (v w : J → V) (hv : Function.Injective v) (hw : Function.Injective w)    (hpattern : ∀ j k, f (v j) = v k ↔ g (w j) = w k) :    ∃ e : Equiv.Perm V, (∀ x, e (f x) = g (e x)) ∧ (∀ j, e (v j) = w j) := by  classical  let uv : J × Bool → V := fun z => if z.2 then f (v z.1) else v z.1  let uw : J × Bool → V := fun z => if z.2 then g (w z.1) else w z.1  let flip : J × Bool → J × Bool := fun z => (z.1,!z.2)  have hvflip : ∀ z, uv (flip z) = f (uv z) := by    rintro ⟨j,c⟩; cases c    · rfl    · exact (hf (v j)).symm  have hwflip : ∀ z, uw (flip z) = g (uw z) := by    rintro ⟨j,c⟩; cases c    · rfl    · exact (hg (w j)).symm  have hkernel : ∀ z z', uv z = uv z' ↔ uw z = uw z' := by    rintro ⟨j,c⟩ ⟨k,d⟩    cases c <;> cases d    · simp only [uv,uw,Bool.false_eq_true,if_false]      exact hv.eq_iff.trans hw.eq_iff.symm    · simpa only [uv,uw,Bool.false_eq_true,if_false,if_true,eq_comm] using hpattern k j    · simpa only [uv,uw,Bool.false_eq_true,if_false,if_true] using hpattern j k    · simp only [uv,uw,if_true,f.injective.eq_iff,g.injective.eq_iff]      exact hv.eq_iff.trans hw.eq_iff.symm  let S : Finset V := univ.image uv  let T : Finset V := univ.image uw  have hvS : ∀ z, uv z ∈ S := fun z => mem_image.mpr ⟨z,mem_univ _,rfl⟩  have hwT : ∀ z, uw z ∈ T := fun z => mem_image.mpr ⟨z,mem_univ _,rfl⟩  have hS : ∀ x, f x ∈ S ↔ x ∈ S := by    intro x    constructor    · intro hx      obtain ⟨z,_,hz⟩ := mem_image.mp hx      have hh : uv (flip z) = x := by rw [hvflip,hz,hf]      exact mem_image.mpr ⟨flip z,mem_univ _,hh⟩    · intro hx      obtain ⟨z,_,rfl⟩ := mem_image.mp hx      rw [← hvflip]; exact hvS _  have hT : ∀ x, g x ∈ T ↔ x ∈ T := by    intro x    constructor    · intro hx      obtain ⟨z,_,hz⟩ := mem_image.mp hx      have hh : uw (flip z) = x := by rw [hwflip,hz,hg]      exact mem_image.mpr ⟨flip z,mem_univ _,hh⟩    · intro hx      obtain ⟨z,_,rfl⟩ := mem_image.mp hx      rw [← hwflip]; exact hwT _  let sv : J × Bool → {x // x ∈ S} := fun z => ⟨uv z,hvS z⟩  let tw : J × Bool → {x // x ∈ T} := fun z => ⟨uw z,hwT z⟩  have hsv : Function.Surjective sv := by    intro x; obtain ⟨z,_,hz⟩ := mem_image.mp x.property    exact ⟨z,Subtype.ext hz⟩  have htw : Function.Surjective tw := by    intro x; obtain ⟨z,_,hz⟩ := mem_image.mp x.property    exact ⟨z,Subtype.ext hz⟩  have hker : ∀ z z', sv z = sv z' ↔ tw z = tw z' := by    intro z z'    simpa only [Subtype.ext_iff] using hkernel z z'  let pick : {x // x ∈ S} → J × Bool := fun x => Classical.choose (hsv x)  have hpick : ∀ x, sv (pick x) = x := fun x => Classical.choose_spec (hsv x)  let eS : {x // x ∈ S} ≃ {x // x ∈ T} := Equiv.ofBijective (fun x => tw (pick x)) (by    constructor    · intro x y h      have hh := (hker (pick x) (pick y)).mpr h      simpa only [hpick] using hh    · intro y      obtain ⟨z,rfl⟩ := htw y      exact ⟨sv z,(hker _ _).mp (hpick (sv z))⟩)  have heval : ∀ z, eS (sv z) = tw z := fun z => (hker _ _).mp (hpick (sv z))  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 ⟨z,rfl⟩ := hsv x    have hh : (⟨f (sv z).val,(hS (sv z).val).mpr (sv z).property⟩ : {x // x ∈ S}) =        sv (flip z) := Subtype.ext (hvflip z).symm    rw [hh,heval,heval]    exact hwflip z  have hmem : a ∈ S ↔ b ∈ T := by    constructor    · intro ha      let x : {x // x ∈ S} := ⟨a,ha⟩      have heq : (⟨f x.val,(hS x.val).mpr x.property⟩ : {x // x ∈ S}) = x :=        Subtype.ext ((hfa a).mpr rfl)      have hh := heS x      rw [heq] at hh      have hb : (eS x).val = b := (hgb _).mp hh.symm      exact hb ▸ (eS x).property    · intro hb      obtain ⟨x,hx⟩ := eS.surjective ⟨b,hb⟩      have hh := heS x      have hxval : (eS x).val = b := congrArg Subtype.val hx      rw [hxval,(hgb b).mpr rfl] at hh      have hfix : f x.val = x.val := by        have hsub : (⟨f x.val,(hS x.val).mpr x.property⟩ : {x // x ∈ S}) = x := by          apply eS.injective          apply Subtype.ext          exact hh.trans hxval.symm        exact congrArg Subtype.val hsub      have ha : x.val = a := (hfa _).mp hfix      exact ha ▸ x.property  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 (sv (j,false))  rw [heval] at hh  exact hh
See it in the graphDiscuss this resultChallenge it