AFTD Auto-Formalizing Theoretical Domains

wild_two_matchings_small_closed_sets_disjoint_or_equal

theoremverified

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

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.

  1. 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).

    lines 9–13

      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
  2. 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.

    lines 14–22

    uses congrArg

      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
  3. 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.

    lines 23–25

    uses Ne.symm

      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]
  4. 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.

    lines 26–30

    uses Finset.card_le_card, mem_insert, mem_singleton

      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 <;> assumption
  5. 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.

    lines 40–47

    uses wild_two_involutions_closed_card_ge_four, mem_inter.mp, mem_inter.mpr

      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
  6. 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.

    lines 48–51

    uses Finset.not_subset.mp, mem_sdiff.mpr

      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⟩⟩
  7. 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.

    lines 52–70

    uses wild_two_involutions_closed_card_ge_four, mem_sdiff.mp, mem_sdiff.mpr

      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
  8. 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.

    lines 71–72

    uses Finset.card_sdiff_add_card_inter

      have heq := Finset.card_sdiff_add_card_inter S T
      omega
  9. 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.

    lines 82–84

    uses Or.inl

      by_cases hd : Disjoint S T
      · exact Or.inl hd
      right
  10. 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.

    lines 85–87

    uses Finset.not_disjoint_iff.mp, mem_inter.mpr

      have hi : (S ∩ T).Nonempty := by
        obtain ⟨x, hxS, hxT⟩ := Finset.not_disjoint_iff.mp hd
        exact ⟨x, mem_inter.mpr ⟨hxS, hxT⟩⟩
  11. 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.

    lines 88–92

    uses Finset.Subset.antisymm, wild_two_involutions_small_closed_subset, mem_union_left, mem_union_right, inter_comm

      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)
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.

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 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)
See it in the graphDiscuss this resultChallenge it