AFTD Auto-Formalizing Theoretical Domains

wild_involution_closed_partial_isomorphism_extends

theoremverified

A matching isomorphism on closed finite subsets extends globally when both involutions have a unique fixed point and the subsets either both contain or both omit that point.

Statement

theorem wild_involution_closed_partial_isomorphism_extends
    {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 : ∀ x, f x ∈ S ↔ x ∈ S)
    (hT : ∀ x, g x ∈ T ↔ x ∈ T)
    (hmem : a ∈ S ↔ b ∈ T)
    (eS : {x // x ∈ S} ≃ {x // x ∈ T})
    (heS : ∀ x : {x // x ∈ S},
      (eS ⟨f x.val,(hS x.val).mpr x.property⟩).val = g (eS x).val) :
    ∃ e : Equiv.Perm V, (∀ x, e (f x) = g (e x)) ∧
      (∀ x : {x // x ∈ S}, e x.val = (eS x).val)
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 given partial isomorphism $e_S : S \simeq T$ between $f$-stable and $g$-stable subsets to a global isomorphism by decomposing the finite type $V$ into the disjoint sum of $S$ and its complement $V \setminus S$ (and similarly for $T$). To find an equivariant bijection between the complements $V \setminus S$ and $V \setminus T$, the proof appeals to the classification theorem `wild_involutions_equiv_of_card_and_fixed_count`, which guarantees conjugacy of finite involutions having the same domain cardinality and the same number of fixed points. Because $|S| = |T|$, the complements have equal cardinality; and because $f$ and $g$ each have a unique global fixed point ($a$ and $b$ respectively) with $a \in S \leftrightarrow b \in T$, the restricted involutions on the complements each contain either both 0 or both 1 fixed points. Gluing $e_S$ on $S$ and the complement isomorphism $e_C$ on $V \setminus S$ yields the desired global permutation $e$ commuting with the involutions.

  1. The restrictions of $f$ to $V \setminus S$ and $g$ to $V \setminus T$ are well-defined involutions.

    Because $S$ is invariant under $f$, its complement $V \setminus S$ is also invariant under $f$ (using `not_congr`), defining a permutation $f_C$ on the subtype $\{x : V // x \notin S\}$. Symmetrically, $g$ restricts to a permutation $g_C$ on $\{x : V // x \notin T\}$. Because $f$ and $g$ are involutions on $V$, evaluating on underlying elements shows via `Subtype.ext` that $f_C$ and $g_C$ are also involutions.

    lines 18–26

    uses not_congr, Subtype.ext

      classical
      let fC : Equiv.Perm {x : V // x ∉ S} :=
        f.subtypeEquiv (fun x => (not_congr (hS x)).symm)
      let gC : Equiv.Perm {x : V // x ∉ T} :=
        g.subtypeEquiv (fun x => (not_congr (hT x)).symm)
      have hfC : Function.Involutive fC := by
        intro x; apply Subtype.ext; exact hf x.val
      have hgC : Function.Involutive gC := by
        intro x; apply Subtype.ext; exact hg x.val
  2. The complements $V \setminus S$ and $V \setminus T$ have equal cardinality.

    By `Fintype.card_subtype_compl`, the cardinality of the complement of any subset $X \subseteq V$ is $|V| - |X|$. Since $e_S$ provides a bijection between $S$ and $T$, $|S| = |T|$ by `Fintype.card_congr`. Hence, $|V \setminus S| = |V| - |S| = |V| - |T| = |V \setminus T|$.

    lines 27–28

    uses Fintype.card_subtype_compl, Fintype.card_congr

      have hcard : Fintype.card {x : V // x ∉ S} = Fintype.card {x : V // x ∉ T} := by
        rw [Fintype.card_subtype_compl,Fintype.card_subtype_compl,Fintype.card_congr eS]
  3. The number of fixed points of $f_C$ on $V \setminus S$ equals the cardinality of $\{x \in V \mid x \notin S \land x = a\}$.

    Using `card_bij`, we define a bijection between the fixed points of $f_C$ and the elements of $\{x \in V \mid x \notin S \land x = a\}$ via the projection $x \mapsto x.val$. If $x \in V \setminus S$ is fixed by $f_C$, then $f(x) = x$, which by the uniqueness hypothesis `hfa` means $x = a$. Conversely, if $x \notin S$ and $x = a$, then $f(x) = a = x$, so $x$ is a fixed point of $f_C$.

    lines 29–41

    uses card_bij, Subtype.ext, congrArg

      have hfixedS : (univ.filter fun x : {x : V // x ∉ S} => fC x = x).card =
          (univ.filter fun x : V => x ∉ S ∧ x = a).card := by
        apply card_bij (fun x _ => x.val)
        · intro x hx
          simp only [mem_filter,mem_univ,true_and] at hx ⊢
          exact ⟨x.property,(hfa x.val).mp (congrArg Subtype.val hx)⟩
        · intro x _ y _ h; exact Subtype.ext h
        · intro x hx
          simp only [mem_filter,mem_univ,true_and] at hx
          refine ⟨⟨x,hx.1⟩,?_,rfl⟩
          simp only [mem_filter,mem_univ,true_and]
          apply Subtype.ext
          exact (hfa x).mpr hx.2
  4. The number of fixed points of $g_C$ on $V \setminus T$ equals the cardinality of $\{x \in V \mid x \notin T \land x = b\}$.

    Symmetrically, `card_bij` establishes a bijection between the fixed points of $g_C$ on $V \setminus T$ and the elements of $\{x \in V \mid x \notin T \land x = b\}$ via $x \mapsto x.val$, using the uniqueness hypothesis `hgb` that $b$ is the unique fixed point of $g$.

    lines 42–54

    uses card_bij, Subtype.ext, congrArg

      have hfixedT : (univ.filter fun x : {x : V // x ∉ T} => gC x = x).card =
          (univ.filter fun x : V => x ∉ T ∧ x = b).card := by
        apply card_bij (fun x _ => x.val)
        · intro x hx
          simp only [mem_filter,mem_univ,true_and] at hx ⊢
          exact ⟨x.property,(hgb x.val).mp (congrArg Subtype.val hx)⟩
        · intro x _ y _ h; exact Subtype.ext h
        · intro x hx
          simp only [mem_filter,mem_univ,true_and] at hx
          refine ⟨⟨x,hx.1⟩,?_,rfl⟩
          simp only [mem_filter,mem_univ,true_and]
          apply Subtype.ext
          exact (hgb x).mpr hx.2
  5. The restricted involutions $f_C$ and $g_C$ have the same number of fixed points.

    Rewriting with `hfixedS` and `hfixedT`, the fixed-point sets of $f_C$ and $g_C$ simplify via `filter_and`, `filter_eq'`, `mem_univ`, `inter_comm`, and `singleton_inter` to $\{a\} \cap (V \setminus S)$ and $\{b\} \cap (V \setminus T)$. By the hypothesis `hmem` ($a \in S \leftrightarrow b \in T$), a case split shows that if $b \in T$, both sets are empty, while if $b \notin T$, both sets are singletons ($\{a\}$ and $\{b\}$). In either case, the counts are equal.

    lines 55–60

    uses filter_and, filter_eq', mem_univ, inter_comm, singleton_inter

      have hfixed : (univ.filter fun x : {x : V // x ∉ S} => fC x = x).card =
          (univ.filter fun x : {x : V // x ∉ T} => gC x = x).card := by
        rw [hfixedS,hfixedT]
        simp only [filter_and,filter_eq',mem_univ]
        simp [inter_comm,singleton_inter,hmem]
        split <;> simp
  6. There exists an equivalence $e_C : (V \setminus S) \simeq (V \setminus T)$ conjugating $f_C$ to $g_C$.

    Because $f_C$ and $g_C$ are involutions on finite types of equal cardinality and with the same number of fixed points, the classification theorem `wild_involutions_equiv_of_card_and_fixed_count` yields a bijection $e_C : (V \setminus S) \simeq (V \setminus T)$ satisfying $e_C(f_C(x)) = g_C(e_C(x))$ for all $x$.

    lines 61–63

    uses wild_involutions_equiv_of_card_and_fixed_count

      obtain ⟨eC,heC⟩ := wild_involutions_equiv_of_card_and_fixed_count
        fC gC hfC hgC hcard (by
          convert hfixed using 1 <;> congr 1 <;> ext x <;> simp)
  7. Gluing $e_S$ and $e_C$ defines a permutation $e$ of $V$ that coincides with $e_S$ on $S$ and with $e_C$ on $V \setminus S$.

    Using `Equiv.sumCompl` to identify $V$ with $S \oplus (V \setminus S)$ and with $T \oplus (V \setminus T)$, the sum equivalence $e_S \oplus e_C$ (constructed by `Equiv.sumCongr`) induces a permutation $e$ of $V$. By `Equiv.sumCompl_symm_apply_of_pos` and `Equiv.sumCompl_symm_apply_of_neg`, $e(x) = e_S(x)$ for all $x \in S$ and $e(x) = e_C(x)$ for all $x \notin S$.

    lines 64–71

    uses Equiv.sumCompl, Equiv.sumCongr, Equiv.sumCompl_symm_apply_of_pos, Equiv.sumCompl_symm_apply_of_neg

      let e : Equiv.Perm V := ((Equiv.sumCompl (fun x => x ∈ S)).symm.trans
        (Equiv.sumCongr eS eC)).trans (Equiv.sumCompl (fun x => x ∈ T))
      have hleft : ∀ x (hx : x ∈ S), e x = (eS ⟨x,hx⟩).val := by
        intro x hx
        simp [e,Equiv.sumCompl_symm_apply_of_pos hx]
      have hright : ∀ x (hx : x ∉ S), e x = (eC ⟨x,hx⟩).val := by
        intro x hx
        simp [e,Equiv.sumCompl_symm_apply_of_neg hx]
  8. The permutation $e$ extends $e_S$ and conjugates $f$ to $g$ everywhere on $V$.

    The permutation $e$ agrees with $e_S$ on $S$ by construction. To show $e(f(x)) = g(e(x))$ for all $x \in V$, we split into two cases: if $x \in S$, then $f(x) \in S$ by $f$-invariance, so $e(f(x)) = e_S(f(x)) = g(e_S(x)) = g(e(x))$ by the equivariance hypothesis `heS`; if $x \notin S$, then $f(x) \notin S$ as well (using `not_congr`), so $e(f(x)) = e_C(f_C(x)) = g(e_C(x)) = g(e(x))$ by the equivariance of $e_C$.

    lines 72–79

    uses not_congr, congrArg

      refine ⟨e,?_,fun x => hleft x.val x.property⟩
      intro x
      by_cases hx : x ∈ S
      · rw [hleft x hx,hleft (f x) ((hS x).mpr hx)]
        exact heS ⟨x,hx⟩
      · have hfx : f x ∉ S := (not_congr (hS x)).mpr hx
        rw [hright x hx,hright (f x) hfx]
        exact congrArg Subtype.val (heC ⟨x,hx⟩)
not_congr
If two propositions are equivalent, then their negations are equivalent: $(P \leftrightarrow Q) \to (\neg P \leftrightarrow \neg Q)$.
Subtype.ext
Two elements of a subtype are equal if and only if their underlying values are equal.
Fintype.card_subtype_compl
For a finite type $\alpha$ and predicate $p$, the cardinality of the complement subtype $\{x // \neg p(x)\}$ equals $|\alpha| - |\{x // p(x)\}|$.
Fintype.card_congr
An equivalence (bijection) between two finite types implies that they have the same cardinality.
card_bij
Two finite sets have equal cardinality if there is a function between them that is well-defined, injective, and surjective on the sets.
congrArg
If two arguments are equal, applying any function to them yields equal results: $x = y \to h(x) = h(y)$.
filter_and
Filtering a finite set by a conjunction $p \land q$ is the intersection of filtering by $p$ and filtering by $q$.
filter_eq'
Filtering a finite set by equality to an element $b$ yields the singleton $\{b\}$ if $b$ is in the set, and the empty set otherwise.
mem_univ
Every element of a finite type belongs to the universal finset `univ`.
inter_comm
Intersection of two finite sets is commutative: $s_1 \cap s_2 = s_2 \cap s_1$.
singleton_inter
The intersection of a singleton $\{a\}$ with a set $s$ is $\{a\}$ if $a \in s$, and $\emptyset$ otherwise.
wild_involutions_equiv_of_card_and_fixed_count
Two involutions on finite types are isomorphic (conjugate via a bijection) if and only if their domain types have the same cardinality and the involutions have the same number of fixed points.
Equiv.sumCompl
The canonical equivalence identifying a type $\alpha$ with the sum of a subtype $\{x // p(x)\}$ and its complement $\{x // \neg p(x)\}$.
Equiv.sumCongr
Given bijections $\alpha_1 \simeq \alpha_2$ and $\beta_1 \simeq \beta_2$, their direct sum defines a bijection $\alpha_1 \oplus \beta_1 \simeq \alpha_2 \oplus \beta_2$.
Equiv.sumCompl_symm_apply_of_pos
The inverse of `sumCompl` sends an element satisfying $p$ to the left summand `Sum.inl`.
Equiv.sumCompl_symm_apply_of_neg
The inverse of `sumCompl` sends an element not satisfying $p$ to the right summand `Sum.inr`.

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_closed_partial_isomorphism_extends    {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 : ∀ x, f x ∈ S ↔ x ∈ S)    (hT : ∀ x, g x ∈ T ↔ x ∈ T)    (hmem : a ∈ S ↔ b ∈ T)    (eS : {x // x ∈ S} ≃ {x // x ∈ T})    (heS : ∀ x : {x // x ∈ S},      (eS ⟨f x.val,(hS x.val).mpr x.property⟩).val = g (eS x).val) :    ∃ e : Equiv.Perm V, (∀ x, e (f x) = g (e x)) ∧      (∀ x : {x // x ∈ S}, e x.val = (eS x).val) := by  classical  let fC : Equiv.Perm {x : V // x ∉ S} :=    f.subtypeEquiv (fun x => (not_congr (hS x)).symm)  let gC : Equiv.Perm {x : V // x ∉ T} :=    g.subtypeEquiv (fun x => (not_congr (hT x)).symm)  have hfC : Function.Involutive fC := by    intro x; apply Subtype.ext; exact hf x.val  have hgC : Function.Involutive gC := by    intro x; apply Subtype.ext; exact hg x.val  have hcard : Fintype.card {x : V // x ∉ S} = Fintype.card {x : V // x ∉ T} := by    rw [Fintype.card_subtype_compl,Fintype.card_subtype_compl,Fintype.card_congr eS]  have hfixedS : (univ.filter fun x : {x : V // x ∉ S} => fC x = x).card =      (univ.filter fun x : V => x ∉ S ∧ x = a).card := by    apply card_bij (fun x _ => x.val)    · intro x hx      simp only [mem_filter,mem_univ,true_and] at hx ⊢      exact ⟨x.property,(hfa x.val).mp (congrArg Subtype.val hx)⟩    · intro x _ y _ h; exact Subtype.ext h    · intro x hx      simp only [mem_filter,mem_univ,true_and] at hx      refine ⟨⟨x,hx.1⟩,?_,rfl⟩      simp only [mem_filter,mem_univ,true_and]      apply Subtype.ext      exact (hfa x).mpr hx.2  have hfixedT : (univ.filter fun x : {x : V // x ∉ T} => gC x = x).card =      (univ.filter fun x : V => x ∉ T ∧ x = b).card := by    apply card_bij (fun x _ => x.val)    · intro x hx      simp only [mem_filter,mem_univ,true_and] at hx ⊢      exact ⟨x.property,(hgb x.val).mp (congrArg Subtype.val hx)⟩    · intro x _ y _ h; exact Subtype.ext h    · intro x hx      simp only [mem_filter,mem_univ,true_and] at hx      refine ⟨⟨x,hx.1⟩,?_,rfl⟩      simp only [mem_filter,mem_univ,true_and]      apply Subtype.ext      exact (hgb x).mpr hx.2  have hfixed : (univ.filter fun x : {x : V // x ∉ S} => fC x = x).card =      (univ.filter fun x : {x : V // x ∉ T} => gC x = x).card := by    rw [hfixedS,hfixedT]    simp only [filter_and,filter_eq',mem_univ]    simp [inter_comm,singleton_inter,hmem]    split <;> simp  obtain ⟨eC,heC⟩ := wild_involutions_equiv_of_card_and_fixed_count    fC gC hfC hgC hcard (by      convert hfixed using 1 <;> congr 1 <;> ext x <;> simp)  let e : Equiv.Perm V := ((Equiv.sumCompl (fun x => x ∈ S)).symm.trans    (Equiv.sumCongr eS eC)).trans (Equiv.sumCompl (fun x => x ∈ T))  have hleft : ∀ x (hx : x ∈ S), e x = (eS ⟨x,hx⟩).val := by    intro x hx    simp [e,Equiv.sumCompl_symm_apply_of_pos hx]  have hright : ∀ x (hx : x ∉ S), e x = (eC ⟨x,hx⟩).val := by    intro x hx    simp [e,Equiv.sumCompl_symm_apply_of_neg hx]  refine ⟨e,?_,fun x => hleft x.val x.property⟩  intro x  by_cases hx : x ∈ S  · rw [hleft x hx,hleft (f x) ((hS x).mpr hx)]    exact heS ⟨x,hx⟩  · have hfx : f x ∉ S := (not_congr (hS x)).mpr hx    rw [hright x hx,hright (f x) hfx]    exact congrArg Subtype.val (heC ⟨x,hx⟩)
See it in the graphDiscuss this resultChallenge it