wild_involution_closed_partial_isomorphism_extends
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
- wild_involutions_equiv_of_card_and_fixed_countCross-type version of finite involution conjugacy: equal finite cardinalities and equal fixed-point counts give an intertwining equivalence.
- Used by 2
- wild_involution_finite_pattern_isomorphism_extendsTwo injectively embedded copies of the same closed finite involution pattern are aligned by a global matching isomorphism, when each…
- wild_involution_partial_pattern_isomorphism_extendsAn isomorphism of arbitrary injective finite patterns, preserving every partner equality including fixed points, extends to an isomorphism…
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.
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.
uses
not_congr,Subtype.extclassical 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
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|$.
uses
Fintype.card_subtype_compl,Fintype.card_congrhave 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]
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$.
uses
card_bij,Subtype.ext,congrArghave 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
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$.
uses
card_bij,Subtype.ext,congrArghave 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
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.
uses
filter_and,filter_eq',mem_univ,inter_comm,singleton_interhave 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
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$.
uses
wild_involutions_equiv_of_card_and_fixed_countobtain ⟨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)
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$.
uses
Equiv.sumCompl,Equiv.sumCongr,Equiv.sumCompl_symm_apply_of_pos,Equiv.sumCompl_symm_apply_of_neglet 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]
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$.
uses
not_congr,congrArgrefine ⟨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`.
- The proof uses `Equiv.sumCompl` to formally represent the decomposition of the finite type $V$ into the disjoint sum of a subtype and its complement, and glues the partial bijections $e_S$ and $e_C$ by composing `Equiv.sumCongr eS eC` with these decompositions.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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⟩)