wild_two_matchings_small_closed_sets_disjoint_or_equal
For two involutions on a decidable type, finite sets S,T of cardinality at most7 that are closed under both maps are disjoint or equal, provided both maps have no fixed points on S union T and have distinct values at each point there. Each nonempty closed set has at least4 points, so intersection and difference cannot both be nonempty.
Statement
theorem wild_two_matchings_small_closed_sets_disjoint_or_equal {α : Type*} [DecidableEq α] (f g : α → α) (hf : Function.Involutive f) (hg : Function.Involutive g) (S T : Finset α) (hSsize : S.card ≤ 7) (hTsize : T.card ≤ 7) (hS : ∀ x ∈ S, f x ∈ S ∧ g x ∈ S) (hT : ∀ x ∈ T, f x ∈ T ∧ g x ∈ T) (hn : ∀ x ∈ S ∪ T, f x ≠ x ∧ g x ≠ x ∧ f x ≠ g x) : Disjoint S T ∨ S = T
- Source
- IN-374 / OP-306, dependence estimates for the weighted partition route to https://arxiv.org/html/2610.22142v1. Elementary matching support consequence of the standard even-cycle decomposition of two disjoint perfect matchings; matching background https://dspacemainprd01.lib.uwaterloo.ca/server/api/core/bitstreams/9d33772f-c7dc-409f-a4ed-521da8d87890/content . Exact experiment9362 audits six saved15 arrays and cyclic9,13,21,27,39,61. No new wild-number bound, sharpness case or research advance is claimed.
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- wild_two_matchings_six_closed_family_boundA finite family F of six-element subsets of U, closed under two involutions whose actions on each member are fixed-point-free and distinct…
The proof, explained
To prove that two closed subsets S and T of size at most 7 are either disjoint or equal, we assume they are not disjoint and prove S = T by antisymmetry. Any nonempty set closed under two fixed-point-free involutions with distinct values must contain at least 4 elements. If S were not a subset of T, both the intersection S ∩ T and difference S \ T would be nonempty and closed under both involutions, forcing |S| = |S \ T| + |S ∩ T| ≥ 4 + 4 = 8, which contradicts |S| ≤ 7. Hence S ⊆ T and symmetrically T ⊆ S, so S = T.
There exists an element x ∈ S such that f(x), g(x), and f(g(x)) belong to S, with x, f(x), and g(x) pairwise distinct.
Because S is nonempty, we choose an element x ∈ S. Since S is closed under both f and g, the elements f(x), g(x), and f(g(x)) all belong to S. By hypothesis, neither map has a fixed point in S and their values differ at x, so f(x) ≠ x, g(x) ≠ x, and f(x) ≠ g(x).
obtain ⟨x, hx⟩ := hne have hfx := (hc x hx).1 have hgx := (hc x hx).2 have hfgx := (hc (g x) hgx).1 obtain ⟨h1, h2, h3⟩ := hn x hx
The element f(g(x)) is distinct from x, f(x), and g(x).
If f(g(x)) = x, applying f to both sides and using that f is an involution gives g(x) = f(x), contradicting f(x) ≠ g(x). If f(g(x)) = f(x), injectivity of f implies g(x) = x, contradicting g(x) ≠ x. Finally, f(g(x)) ≠ g(x) holds because g(x) ∈ S and f has no fixed points on S.
uses
congrArghave h4 : f (g x) ≠ x := by intro h have h' := congrArg f h rw [hf (g x)] at h' exact h3 h'.symm have h5 : f (g x) ≠ f x := by intro h exact h2 (hf.injective h) have h6 : f (g x) ≠ g x := (hn (g x) hgx).1
The four elements x, f(x), g(x), and f(g(x)) form a subset of cardinality 4.
All six pairwise inequalities among the four elements hold, so simplifying the set insertion proves that {x, f(x), g(x), f(g(x))} contains exactly 4 distinct elements.
uses
Ne.symmhave hcard : ({x, f x, g x, f (g x)} : Finset α).card = 4 := by simp [h1, h2, h3, h4, h5, h6, Ne.symm h1, Ne.symm h2, Ne.symm h3, Ne.symm h4, Ne.symm h5, Ne.symm h6]
Every nonempty closed set S under f and g satisfying the hypotheses has cardinality at least 4.
Each of the four distinct elements x, f(x), g(x), and f(g(x)) is in S, so {x, f(x), g(x), f(g(x))} is a subset of S. By monotonicity of cardinality for finite sets, |S| ≥ 4.
uses
Finset.card_le_card,mem_insert,mem_singletonrw [← hcard] apply Finset.card_le_card intro y hy simp only [mem_insert, mem_singleton] at hy rcases hy with rfl | rfl | rfl | rfl <;> assumption
The intersection S ∩ T has cardinality at least 4.
The intersection S ∩ T is nonempty by assumption. Because both S and T are closed under f and g, their intersection is also closed under both maps. The elements of S ∩ T inherit the fixed-point-free and distinctness conditions from S. Applying wild_two_involutions_closed_card_ge_four yields |S ∩ T| ≥ 4.
uses
wild_two_involutions_closed_card_ge_four,mem_inter.mp,mem_inter.mprhave hi4 : 4 ≤ (S ∩ T).card := by apply wild_two_involutions_closed_card_ge_four f g hf _ _ _ hi · intro x hx obtain ⟨hs, ht⟩ := mem_inter.mp hx exact ⟨mem_inter.mpr ⟨(hS x hs).1, (hT x ht).1⟩, mem_inter.mpr ⟨(hS x hs).2, (hT x ht).2⟩⟩ · intro x hx exact hn x (mem_inter.mp hx).1
Assuming for contradiction that S is not a subset of T, the set difference S \ T is nonempty.
If S ⊈ T, there exists some element x ∈ S with x ∉ T. This element witnesses that S \ T is nonempty.
uses
Finset.not_subset.mp,mem_sdiff.mprby_contra hsub have hd : (S \ T).Nonempty := by obtain ⟨x, hx, hxt⟩ := Finset.not_subset.mp hsub exact ⟨x, mem_sdiff.mpr ⟨hx, hxt⟩⟩
The set difference S \ T has cardinality at least 4.
We show S \ T satisfies the hypotheses of wild_two_involutions_closed_card_ge_four. It is nonempty. If x ∈ S \ T, then f(x) ∈ S; if f(x) were in T, then f(f(x)) = x would be in T (since T is closed under f), contradicting x ∉ T. Thus f(x) ∈ S \ T. The same argument using the involution property of g shows g(x) ∈ S \ T. The distinctness hypotheses are inherited from S. Hence |S \ T| ≥ 4.
uses
wild_two_involutions_closed_card_ge_four,mem_sdiff.mp,mem_sdiff.mprhave hd4 : 4 ≤ (S \ T).card := by apply wild_two_involutions_closed_card_ge_four f g hf _ _ _ hd · intro x hx obtain ⟨hs, ht⟩ := mem_sdiff.mp hx constructor · apply mem_sdiff.mpr refine ⟨(hS x hs).1, ?_⟩ intro h have h' := (hT (f x) h).1 rw [hf x] at h' exact ht h' · apply mem_sdiff.mpr refine ⟨(hS x hs).2, ?_⟩ intro h have h' := (hT (g x) h).2 rw [hg x] at h' exact ht h' · intro x hx exact hn x (mem_sdiff.mp hx).1
The assumption S ⊈ T leads to a contradiction, establishing S ⊆ T. automation
The cardinality of S partitions as |S| = |S \ T| + |S ∩ T|. Since |S \ T| ≥ 4 and |S ∩ T| ≥ 4, this implies |S| ≥ 8, directly contradicting |S| ≤ 7. The contradiction is resolved by linear arithmetic.
uses
Finset.card_sdiff_add_card_interhave heq := Finset.card_sdiff_add_card_inter S T omega
If S and T are disjoint, the disjunction holds; otherwise, it suffices to prove S = T.
We split into cases on whether S and T are disjoint. If they are, the left branch of the disjunction Disjoint S T ∨ S = T is established immediately. In the remaining case, we assume ¬Disjoint S T and reduce the goal to showing S = T.
uses
Or.inlby_cases hd : Disjoint S T · exact Or.inl hd right
The intersection S ∩ T is nonempty.
Because S and T are not disjoint, there exists an element belonging to both S and T, which provides a witness that S ∩ T is nonempty.
uses
Finset.not_disjoint_iff.mp,mem_inter.mprhave hi : (S ∩ T).Nonempty := by obtain ⟨x, hxS, hxT⟩ := Finset.not_disjoint_iff.mp hd exact ⟨x, mem_inter.mpr ⟨hxS, hxT⟩⟩
S = T, completing the proof.
By antisymmetry of set inclusion, it suffices to prove S ⊆ T and T ⊆ S. The inclusion S ⊆ T holds by wild_two_involutions_small_closed_subset, using |S| ≤ 7, nonemptiness of S ∩ T, and the distinctness condition restricted to S. Symmetrically, T ⊆ S holds by applying the same lemma with the roles of S and T swapped, using |T| ≤ 7 and nonemptiness of T ∩ S = S ∩ T. Therefore S = T.
uses
Finset.Subset.antisymm,wild_two_involutions_small_closed_subset,mem_union_left,mem_union_right,inter_commapply Finset.Subset.antisymm · exact wild_two_involutions_small_closed_subset f g hf hg S T hSsize hS hT (fun x hx => hn x (mem_union_left T hx)) hi · exact wild_two_involutions_small_closed_subset f g hf hg T S hTsize hT hS (fun x hx => hn x (mem_union_right S hx)) (by simpa [inter_comm] using hi)
congrArg- Applying a function to equal arguments produces equal values: if a = b, then f a = f b.
Ne.symm- Symmetry of inequality: if a ≠ b, then b ≠ a.
Finset.card_le_card- Monotonicity of finite set cardinality: if s ⊆ t, then |s| ≤ |t|.
mem_insert- Membership in an inserted set: a ∈ insert b s if and only if a = b or a ∈ s.
mem_singleton- Membership in a singleton set: b ∈ {a} if and only if b = a.
wild_two_involutions_closed_card_ge_four- A nonempty finite set closed under an involution and another map, with no fixed points and distinct values, has cardinality at least 4.
mem_inter.mp- An element belongs to the intersection of two finite sets only if it belongs to both sets.
mem_inter.mpr- An element belongs to the intersection of two finite sets if it belongs to both sets.
Finset.not_subset.mp- If s is not a subset of t, there exists an element x ∈ s such that x ∉ t.
mem_sdiff.mp- An element belongs to the difference s \ t only if it belongs to s and does not belong to t.
mem_sdiff.mpr- An element belongs to the difference s \ t if it belongs to s and does not belong to t.
Finset.card_sdiff_add_card_inter- The cardinality of s is the sum of the cardinalities of s \ t and s ∩ t.
Or.inl- The left introduction rule for disjunction: if A holds, then A ∨ B holds.
Finset.not_disjoint_iff.mp- If two finite sets are not disjoint, they have an element in common.
Finset.Subset.antisymm- Antisymmetry of set inclusion: if s ⊆ t and t ⊆ s, then s = t.
wild_two_involutions_small_closed_subset- If two involutions have no fixed points and distinct values, any closed set S of size at most 7 that intersects another closed set T must be a subset of T.
mem_union_left- If an element belongs to s, then it belongs to s ∪ t.
mem_union_right- If an element belongs to t, then it belongs to s ∪ t.
inter_comm- Commutativity of set intersection: s ∩ t = t ∩ s.
- The proof relies on two helper lemmas established earlier in the source: wild_two_involutions_closed_card_ge_four (any nonempty closed set has at least 4 elements) and wild_two_involutions_small_closed_subset (a closed set of size at most 7 intersecting another closed set is a subset of it).
- In line 72, the contradiction 4 + 4 ≤ 7 is resolved automatically by the omega tactic for linear integer arithmetic.
- In lines 91-92, symmetry is handled by rewriting the intersection commutativity and applying the subset lemma with S and T swapped.
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 Finsettheorem wild_two_involutions_closed_card_ge_four {α : Type*} [DecidableEq α] (f g : α → α) (hf : Function.Involutive f) (S : Finset α) (hc : ∀ x ∈ S, f x ∈ S ∧ g x ∈ S) (hn : ∀ x ∈ S, f x ≠ x ∧ g x ≠ x ∧ f x ≠ g x) (hne : S.Nonempty) : 4 ≤ S.card := by obtain ⟨x, hx⟩ := hne have hfx := (hc x hx).1 have hgx := (hc x hx).2 have hfgx := (hc (g x) hgx).1 obtain ⟨h1, h2, h3⟩ := hn x hx have h4 : f (g x) ≠ x := by intro h have h' := congrArg f h rw [hf (g x)] at h' exact h3 h'.symm have h5 : f (g x) ≠ f x := by intro h exact h2 (hf.injective h) have h6 : f (g x) ≠ g x := (hn (g x) hgx).1 have hcard : ({x, f x, g x, f (g x)} : Finset α).card = 4 := by simp [h1, h2, h3, h4, h5, h6, Ne.symm h1, Ne.symm h2, Ne.symm h3, Ne.symm h4, Ne.symm h5, Ne.symm h6] rw [← hcard] apply Finset.card_le_card intro y hy simp only [mem_insert, mem_singleton] at hy rcases hy with rfl | rfl | rfl | rfl <;> assumptiontheorem wild_two_involutions_small_closed_subset {α : Type*} [DecidableEq α] (f g : α → α) (hf : Function.Involutive f) (hg : Function.Involutive g) (S T : Finset α) (hsize : S.card ≤ 7) (hS : ∀ x ∈ S, f x ∈ S ∧ g x ∈ S) (hT : ∀ x ∈ T, f x ∈ T ∧ g x ∈ T) (hn : ∀ x ∈ S, f x ≠ x ∧ g x ≠ x ∧ f x ≠ g x) (hi : (S ∩ T).Nonempty) : S ⊆ T := by have hi4 : 4 ≤ (S ∩ T).card := by apply wild_two_involutions_closed_card_ge_four f g hf _ _ _ hi · intro x hx obtain ⟨hs, ht⟩ := mem_inter.mp hx exact ⟨mem_inter.mpr ⟨(hS x hs).1, (hT x ht).1⟩, mem_inter.mpr ⟨(hS x hs).2, (hT x ht).2⟩⟩ · intro x hx exact hn x (mem_inter.mp hx).1 by_contra hsub have hd : (S \ T).Nonempty := by obtain ⟨x, hx, hxt⟩ := Finset.not_subset.mp hsub exact ⟨x, mem_sdiff.mpr ⟨hx, hxt⟩⟩ have hd4 : 4 ≤ (S \ T).card := by apply wild_two_involutions_closed_card_ge_four f g hf _ _ _ hd · intro x hx obtain ⟨hs, ht⟩ := mem_sdiff.mp hx constructor · apply mem_sdiff.mpr refine ⟨(hS x hs).1, ?_⟩ intro h have h' := (hT (f x) h).1 rw [hf x] at h' exact ht h' · apply mem_sdiff.mpr refine ⟨(hS x hs).2, ?_⟩ intro h have h' := (hT (g x) h).2 rw [hg x] at h' exact ht h' · intro x hx exact hn x (mem_sdiff.mp hx).1 have heq := Finset.card_sdiff_add_card_inter S T omegatheorem wild_two_matchings_small_closed_sets_disjoint_or_equal {α : Type*} [DecidableEq α] (f g : α → α) (hf : Function.Involutive f) (hg : Function.Involutive g) (S T : Finset α) (hSsize : S.card ≤ 7) (hTsize : T.card ≤ 7) (hS : ∀ x ∈ S, f x ∈ S ∧ g x ∈ S) (hT : ∀ x ∈ T, f x ∈ T ∧ g x ∈ T) (hn : ∀ x ∈ S ∪ T, f x ≠ x ∧ g x ≠ x ∧ f x ≠ g x) : Disjoint S T ∨ S = T := by by_cases hd : Disjoint S T · exact Or.inl hd right have hi : (S ∩ T).Nonempty := by obtain ⟨x, hxS, hxT⟩ := Finset.not_disjoint_iff.mp hd exact ⟨x, mem_inter.mpr ⟨hxS, hxT⟩⟩ apply Finset.Subset.antisymm · exact wild_two_involutions_small_closed_subset f g hf hg S T hSsize hS hT (fun x hx => hn x (mem_union_left T hx)) hi · exact wild_two_involutions_small_closed_subset f g hf hg T S hTsize hT hS (fun x hx => hn x (mem_union_right S hx)) (by simpa [inter_comm] using hi)