AFTD Auto-Formalizing Theoretical Domains

wild_involution_three_set_isomorphism

theoremverified

For two finite involutions with unique fixed points, two three-element subsets can be carried to one another by a global intertwining permutation if they agree on containing the fixed point and on containing a non-loop matching edge.

Statement

theorem wild_involution_three_set_isomorphism
    {V : Type*} [Fintype V] [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)
    (S T : Finset V) (hS : S.card = 3) (hT : T.card = 3)
    (hfixed : a ∈ S ↔ b ∈ T)
    (hedge : (∃ x ∈ S, ∃ y ∈ S, x ≠ y ∧ f x = y) ↔
      ∃ x ∈ T, ∃ y ∈ T, x ≠ y ∧ g x = y) :
    ∃ e : Equiv.Perm V, (∀ x, e (f x) = g (e x)) ∧ S.image e = T
Source
IN-382 / OP-306 campaign9, 2026-10-30. Standard finite matching symmetry supporting the mixed-moment route for https://arxiv.org/html/2610.22142v1. Exact experiment9566 exposed the missing parity assumption. The original false helper remains retired and its proof record is preserved. No wild-number bound or research advance is claimed.
Verified
30 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
Used by 1

The proof, explained

To find a global intertwining permutation carrying S to T, the proof first encodes the induced actions of f on S and g on T as partial maps on Fin 3. By the hypotheses that S and T agree on containing the unique fixed points and on containing a 2-cycle, these two partial involutions share the same invariant data. A classification lemma (wild_three_partial_involution_classification) produces an isomorphism between the two partial patterns, which is then extended to a global conjugating permutation of V mapping S to T using wild_involution_partial_pattern_isomorphism_extends.

  1. The subsets S and T are parameterized as injective sequences v, w : Fin 3 → V whose ranges are exactly S and T.

    Since |S| = 3 and |T| = 3, Fintype.equivFinOfCardEq provides bijections between Fin 3 and S, T. Composing their inverses with the inclusion into V yields injections v and w whose images are precisely S and T.

    lines 16–30

    uses Fintype.equivFinOfCardEq, Subtype.ext, congrArg

      classical
      let eS : S ≃ Fin 3 := Fintype.equivFinOfCardEq (by simpa using hS)
      let eT : T ≃ Fin 3 := Fintype.equivFinOfCardEq (by simpa using hT)
      let v : Fin 3 → V := fun j => (eS.symm j).val
      let w : Fin 3 → V := fun j => (eT.symm j).val
      have hv : Function.Injective v := by
        intro j k h; exact eS.symm.injective (Subtype.ext h)
      have hw : Function.Injective w := by
        intro j k h; exact eT.symm.injective (Subtype.ext h)
      have hvS : ∀ j, v j ∈ S := fun j => (eS.symm j).property
      have hwT : ∀ j, w j ∈ T := fun j => (eT.symm j).property
      have hSv : ∀ x ∈ S, ∃ j, v j = x := by
        intro x hx; exact ⟨eS ⟨x,hx⟩,congrArg Subtype.val (eS.symm_apply_apply _)⟩
      have hTw : ∀ x ∈ T, ∃ j, w j = x := by
        intro x hx; exact ⟨eT ⟨x,hx⟩,congrArg Subtype.val (eT.symm_apply_apply _)⟩
  2. The partial action enc h u of a map h on the sequence u is well-defined and satisfies enc h u j = some k ↔ h (u j) = u k.

    The encoding enc h u j checks whether h (u j) equals u k for some index k in Fin 3, returning some k if so and none otherwise. Since u is injective, the index k is unique when it exists.

    lines 31–43

    uses Option.some.injEq

      let enc (h : V → V) (u : Fin 3 → V) (j : Fin 3) : Option (Fin 3) :=
        if hh : ∃ k, h (u j) = u k then some hh.choose else none
      have henc (h : V → V) (u : Fin 3 → V) (hu : Function.Injective u) (j k : Fin 3) :
          enc h u j = some k ↔ h (u j) = u k := by
        dsimp only [enc]
        split_ifs with hh
        · simp only [Option.some.injEq]
          constructor
          · intro he; exact he ▸ hh.choose_spec
          · intro he; apply hu; exact hh.choose_spec.symm.trans he
        · constructor
          · intro he; cases he
          · intro he; exact (hh ⟨k,he⟩).elim
  3. The partial action enc h u inherits involution symmetry and has at most one fixed point.

    Because h is an involution, h (u j) = u k implies h (u k) = u j, giving symmetry of enc. Moreover, since h has a unique fixed point c and u is injective, enc h u can have at most one fixed point index.

    lines 44–58

      have hsym (h : Equiv.Perm V) (hh : Function.Involutive h)
          (u : Fin 3 → V) (hu : Function.Injective u) :
          ∀ j k, enc h u j = some k ↔ enc h u k = some j := by
        intro j k
        rw [henc h u hu,henc h u hu]
        constructor
        · intro he; rw [← he,hh]
        · intro he; rw [← he,hh]
      have huniq (h : Equiv.Perm V) (c : V) (hc : ∀ x, h x = x ↔ x = c)
          (u : Fin 3 → V) (hu : Function.Injective u) :
          ∀ j k, enc h u j = some j → enc h u k = some k → j = k := by
        intro j k hj hk
        apply hu
        exact ((hc _).mp ((henc h u hu j j).mp hj)).trans
          ((hc _).mp ((henc h u hu k k).mp hk)).symm
  4. The partial action enc f v has a fixed point if and only if a ∈ S, and similarly enc g w has a fixed point if and only if b ∈ T.

    A fixed point of the encoded action corresponds to f (v j) = v j, which by the characterization of fixed points of f is equivalent to v j = a, meaning a ∈ S. The same reasoning applies to g, w, and b ∈ T.

    lines 59–74

      have hfixv : (∃ j, enc f v j = some j) ↔ a ∈ S := by
        constructor
        · rintro ⟨j,hj⟩
          have he := (hfa _).mp ((henc f v hv j j).mp hj)
          exact he ▸ hvS j
        · intro ha
          obtain ⟨j,hj⟩ := hSv a ha
          exact ⟨j,(henc f v hv j j).mpr ((hfa _).mpr hj)⟩
      have hfixw : (∃ j, enc g w j = some j) ↔ b ∈ T := by
        constructor
        · rintro ⟨j,hj⟩
          have he := (hgb _).mp ((henc g w hw j j).mp hj)
          exact he ▸ hwT j
        · intro hb
          obtain ⟨j,hj⟩ := hTw b hb
          exact ⟨j,(henc g w hw j j).mpr ((hgb _).mpr hj)⟩
  5. The partial action enc f v contains an off-diagonal 2-cycle if and only if S contains a 2-cycle of f, and similarly for g and T.

    An off-diagonal match enc f v j = some k with j ≠ k corresponds directly to a pair of distinct elements x = v j and y = v k in S such that f x = y. The equivalent equivalence holds for g and T.

    lines 75–92

    uses congrArg

      have hedgev : (∃ j k, j ≠ k ∧ enc f v j = some k) ↔
          ∃ x ∈ S, ∃ y ∈ S, x ≠ y ∧ f x = y := by
        constructor
        · rintro ⟨j,k,hjk,hjk'⟩
          exact ⟨v j,hvS j,v k,hvS k,fun h => hjk (hv h),(henc f v hv j k).mp hjk'⟩
        · rintro ⟨x,hx,y,hy,hxy,hfxy⟩
          obtain ⟨j,rfl⟩ := hSv x hx
          obtain ⟨k,rfl⟩ := hSv y hy
          exact ⟨j,k,fun h => hxy (congrArg v h),(henc f v hv j k).mpr hfxy⟩
      have hedgew : (∃ j k, j ≠ k ∧ enc g w j = some k) ↔
          ∃ x ∈ T, ∃ y ∈ T, x ≠ y ∧ g x = y := by
        constructor
        · rintro ⟨j,k,hjk,hjk'⟩
          exact ⟨w j,hwT j,w k,hwT k,fun h => hjk (hw h),(henc g w hw j k).mp hjk'⟩
        · rintro ⟨x,hx,y,hy,hxy,hgxy⟩
          obtain ⟨j,rfl⟩ := hTw x hx
          obtain ⟨k,rfl⟩ := hTw y hy
          exact ⟨j,k,fun h => hxy (congrArg w h),(henc g w hw j k).mpr hgxy⟩
  6. There exists a permutation r of Fin 3 conjugating the partial pattern of f on v to the partial pattern of g on w.

    By the assumptions hfixed and hedge, the encoded actions enc f v and enc g w have the same number of fixed points (both either 0 or 1) and agree on whether they contain an edge. Applying the classification lemma wild_three_partial_involution_classification yields a bijection r : Fin 3 → Fin 3 matching the two partial patterns: f (v j) = v k ↔ g (w (r j)) = w (r k).

    lines 93–98

    uses wild_three_partial_involution_classification

      obtain ⟨r,hr,hrp⟩ := wild_three_partial_involution_classification (enc f v) (enc g w)
        (hsym f hf v hv) (hsym g hg w hw) (huniq f a hfa v hv) (huniq g b hgb w hw)
        (hfixv.trans (hfixed.trans hfixw.symm)) (hedgev.trans (hedge.trans hedgew.symm))
      have hp : ∀ j k, f (v j) = v k ↔ g (w (r j)) = w (r k) := by
        intro j k
        exact (henc f v hv j k).symm.trans ((hrp j k).trans (henc g w hw (r j) (r k)))
  7. The local isomorphism r extends to a global permutation e of V conjugating f to g and mapping v j to w (r j).

    Applying wild_involution_partial_pattern_isomorphism_extends to v and w ∘ r lifts the 3-element pattern isomorphism to a global permutation e such that e (f x) = g (e x) for all x ∈ V and e (v j) = w (r j) for all j ∈ Fin 3.

    lines 99–101

    uses wild_involution_partial_pattern_isomorphism_extends

      obtain ⟨e,he,hev⟩ := wild_involution_partial_pattern_isomorphism_extends
        f g hf hg a b hfa hgb v (w ∘ r) hv (hw.comp hr.1) hp
      refine ⟨e,he,?_⟩
  8. The global intertwining permutation e maps S onto T, completing the proof.

    Every element of S is v j for some j, so its image under e is w (r j) ∈ T. Conversely, every element of T is w k, and by surjectivity of r, k = r j, so w k = e (v j) with v j ∈ S. Thus e(S) = T.

    lines 102–112

      ext x
      constructor
      · intro hx
        obtain ⟨y,hy,rfl⟩ := mem_image.mp hx
        obtain ⟨j,rfl⟩ := hSv y hy
        rw [hev]
        exact hwT (r j)
      · intro hx
        obtain ⟨k,rfl⟩ := hTw x hx
        obtain ⟨j,rfl⟩ := hr.2 k
        exact mem_image.mpr ⟨v j,hvS j,hev j⟩
Subtype.ext
Two elements of a subtype are equal if their underlying values are equal.
congrArg
Applying a function to equal inputs yields equal outputs: if a = b then f a = f b.
Fintype.equivFinOfCardEq
A finite type with cardinality n is in bijection with Fin n.
Option.some.injEq
The Option constructor some is injective: some x = some y if and only if x = y.
wild_three_partial_involution_classification
Two partial involutive maps on Fin 3 with at most one fixed point are isomorphic via a permutation of Fin 3 if and only if they agree on the existence of a fixed point and on the existence of a 2-cycle.
wild_involution_partial_pattern_isomorphism_extends
Any pattern-preserving injection between indexed subsets under two finite involutions with unique fixed points extends to a global permutation 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 6000000set_option maxRecDepth 100000set_option synthInstance.maxSize 10000theorem wild_involution_three_set_isomorphism    {V : Type*} [Fintype V] [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)    (S T : Finset V) (hS : S.card = 3) (hT : T.card = 3)    (hfixed : a ∈ S ↔ b ∈ T)    (hedge : (∃ x ∈ S, ∃ y ∈ S, x ≠ y ∧ f x = y) ↔      ∃ x ∈ T, ∃ y ∈ T, x ≠ y ∧ g x = y) :    ∃ e : Equiv.Perm V, (∀ x, e (f x) = g (e x)) ∧ S.image e = T := by  classical  let eS : S ≃ Fin 3 := Fintype.equivFinOfCardEq (by simpa using hS)  let eT : T ≃ Fin 3 := Fintype.equivFinOfCardEq (by simpa using hT)  let v : Fin 3 → V := fun j => (eS.symm j).val  let w : Fin 3 → V := fun j => (eT.symm j).val  have hv : Function.Injective v := by    intro j k h; exact eS.symm.injective (Subtype.ext h)  have hw : Function.Injective w := by    intro j k h; exact eT.symm.injective (Subtype.ext h)  have hvS : ∀ j, v j ∈ S := fun j => (eS.symm j).property  have hwT : ∀ j, w j ∈ T := fun j => (eT.symm j).property  have hSv : ∀ x ∈ S, ∃ j, v j = x := by    intro x hx; exact ⟨eS ⟨x,hx⟩,congrArg Subtype.val (eS.symm_apply_apply _)⟩  have hTw : ∀ x ∈ T, ∃ j, w j = x := by    intro x hx; exact ⟨eT ⟨x,hx⟩,congrArg Subtype.val (eT.symm_apply_apply _)⟩  let enc (h : V → V) (u : Fin 3 → V) (j : Fin 3) : Option (Fin 3) :=    if hh : ∃ k, h (u j) = u k then some hh.choose else none  have henc (h : V → V) (u : Fin 3 → V) (hu : Function.Injective u) (j k : Fin 3) :      enc h u j = some k ↔ h (u j) = u k := by    dsimp only [enc]    split_ifs with hh    · simp only [Option.some.injEq]      constructor      · intro he; exact he ▸ hh.choose_spec      · intro he; apply hu; exact hh.choose_spec.symm.trans he    · constructor      · intro he; cases he      · intro he; exact (hh ⟨k,he⟩).elim  have hsym (h : Equiv.Perm V) (hh : Function.Involutive h)      (u : Fin 3 → V) (hu : Function.Injective u) :      ∀ j k, enc h u j = some k ↔ enc h u k = some j := by    intro j k    rw [henc h u hu,henc h u hu]    constructor    · intro he; rw [← he,hh]    · intro he; rw [← he,hh]  have huniq (h : Equiv.Perm V) (c : V) (hc : ∀ x, h x = x ↔ x = c)      (u : Fin 3 → V) (hu : Function.Injective u) :      ∀ j k, enc h u j = some j → enc h u k = some k → j = k := by    intro j k hj hk    apply hu    exact ((hc _).mp ((henc h u hu j j).mp hj)).trans      ((hc _).mp ((henc h u hu k k).mp hk)).symm  have hfixv : (∃ j, enc f v j = some j) ↔ a ∈ S := by    constructor    · rintro ⟨j,hj⟩      have he := (hfa _).mp ((henc f v hv j j).mp hj)      exact he ▸ hvS j    · intro ha      obtain ⟨j,hj⟩ := hSv a ha      exact ⟨j,(henc f v hv j j).mpr ((hfa _).mpr hj)⟩  have hfixw : (∃ j, enc g w j = some j) ↔ b ∈ T := by    constructor    · rintro ⟨j,hj⟩      have he := (hgb _).mp ((henc g w hw j j).mp hj)      exact he ▸ hwT j    · intro hb      obtain ⟨j,hj⟩ := hTw b hb      exact ⟨j,(henc g w hw j j).mpr ((hgb _).mpr hj)⟩  have hedgev : (∃ j k, j ≠ k ∧ enc f v j = some k) ↔      ∃ x ∈ S, ∃ y ∈ S, x ≠ y ∧ f x = y := by    constructor    · rintro ⟨j,k,hjk,hjk'⟩      exact ⟨v j,hvS j,v k,hvS k,fun h => hjk (hv h),(henc f v hv j k).mp hjk'⟩    · rintro ⟨x,hx,y,hy,hxy,hfxy⟩      obtain ⟨j,rfl⟩ := hSv x hx      obtain ⟨k,rfl⟩ := hSv y hy      exact ⟨j,k,fun h => hxy (congrArg v h),(henc f v hv j k).mpr hfxy⟩  have hedgew : (∃ j k, j ≠ k ∧ enc g w j = some k) ↔      ∃ x ∈ T, ∃ y ∈ T, x ≠ y ∧ g x = y := by    constructor    · rintro ⟨j,k,hjk,hjk'⟩      exact ⟨w j,hwT j,w k,hwT k,fun h => hjk (hw h),(henc g w hw j k).mp hjk'⟩    · rintro ⟨x,hx,y,hy,hxy,hgxy⟩      obtain ⟨j,rfl⟩ := hTw x hx      obtain ⟨k,rfl⟩ := hTw y hy      exact ⟨j,k,fun h => hxy (congrArg w h),(henc g w hw j k).mpr hgxy⟩  obtain ⟨r,hr,hrp⟩ := wild_three_partial_involution_classification (enc f v) (enc g w)    (hsym f hf v hv) (hsym g hg w hw) (huniq f a hfa v hv) (huniq g b hgb w hw)    (hfixv.trans (hfixed.trans hfixw.symm)) (hedgev.trans (hedge.trans hedgew.symm))  have hp : ∀ j k, f (v j) = v k ↔ g (w (r j)) = w (r k) := by    intro j k    exact (henc f v hv j k).symm.trans ((hrp j k).trans (henc g w hw (r j) (r k)))  obtain ⟨e,he,hev⟩ := wild_involution_partial_pattern_isomorphism_extends    f g hf hg a b hfa hgb v (w ∘ r) hv (hw.comp hr.1) hp  refine ⟨e,he,?_⟩  ext x  constructor  · intro hx    obtain ⟨y,hy,rfl⟩ := mem_image.mp hx    obtain ⟨j,rfl⟩ := hSv y hy    rw [hev]    exact hwT (r j)  · intro hx    obtain ⟨k,rfl⟩ := hTw x hx    obtain ⟨j,rfl⟩ := hr.2 k    exact mem_image.mpr ⟨v j,hvS j,hev j⟩
See it in the graphDiscuss this resultChallenge it