AFTD Auto-Formalizing Theoretical Domains

wild_two_matchings_six_closed_family_bound

theoremverified

A finite family F of six-element subsets of U, closed under two involutions whose actions on each member are fixed-point-free and distinct at every vertex, satisfies 6*card(F)<=card(U). This follows from pairwise disjointness and finite union cardinality.

Statement

theorem wild_two_matchings_six_closed_family_bound
    {α : Type*} [DecidableEq α] (f g : α → α)
    (hf : Function.Involutive f) (hg : Function.Involutive g)
    (F : Finset (Finset α)) (U : Finset α)
    (hsize : ∀ S ∈ F, S.card = 6)
    (hsub : ∀ S ∈ F, S ⊆ U)
    (hc : ∀ S ∈ F, ∀ x ∈ S, f x ∈ S ∧ g x ∈ S)
    (hn : ∀ S ∈ F, ∀ x ∈ S, f x ≠ x ∧ g x ≠ x ∧ f x ≠ g x) :
    6 * F.card ≤ U.card
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
Built on 1
Used by 1

The proof, explained

The proof shows that any two distinct six-element sets in the family F must be disjoint, using an auxiliary theorem that classifies two small closed sets under fixed-point-free involutions as either disjoint or equal. Because F is pairwise disjoint and each of its members has six elements, the union of all sets in F contains exactly 6 * |F| elements. Since each set is contained in U, their union is also a subset of U, which implies 6 * |F| ≤ |U|.

  1. The family F is pairwise disjoint.

    Let S and T be any two distinct sets in F. Both have cardinality 6 ≤ 7 and are closed under f and g. Furthermore, every element x in S ∪ T lies in S or in T (by mem_union.mp), so f and g have no fixed points and do not coincide on S ∪ T. Applying wild_two_matchings_small_closed_sets_disjoint_or_equal shows that S and T are disjoint or identical; since S ≠ T, they must be disjoint.

    lines 12–21

    uses wild_two_matchings_small_closed_sets_disjoint_or_equal, mem_union.mp

      have hd : (F : Set (Finset α)).PairwiseDisjoint id := by
        intro S hS T hT hne
        have h := wild_two_matchings_small_closed_sets_disjoint_or_equal f g hf hg
          S T (by rw [hsize S hS]; omega) (by rw [hsize T hT]; omega)
          (hc S hS) (hc T hT) (by
            intro x hx
            rcases mem_union.mp hx with hx | hx
            · exact hn S hS x hx
            · exact hn T hT x hx)
        exact h.resolve_right hne
  2. The union of all sets in F has cardinality 6 * |F|.

    Because the sets in F are pairwise disjoint, Finset.card_biUnion equates the cardinality of the union to the sum of the cardinalities of the individual sets. Simplifying the identity mapping with id_eq gives ∑_{S ∈ F} |S|. Since every S ∈ F has cardinality 6, this sum evaluates by Finset.sum_const_nat to |F| * 6, which equals 6 * |F| by Nat.mul_comm.

    lines 22–25

    uses Finset.card_biUnion, id_eq, Finset.sum_const_nat, Nat.mul_comm

      have hcard : (F.biUnion id).card = 6 * F.card := by
        rw [Finset.card_biUnion hd]
        simp only [id_eq]
        rw [Finset.sum_const_nat hsize, Nat.mul_comm]
  3. 6 * |F| ≤ |U|.

    Rewriting 6 * |F| as the cardinality of the union ⋃_{S ∈ F} S, it suffices by Finset.card_le_card to show this union is a subset of U. Any element x in the union belongs to some S ∈ F (by Finset.mem_biUnion.mp), and since every S ∈ F is a subset of U, x belongs to U.

    lines 26–30

    uses Finset.card_le_card, Finset.mem_biUnion.mp

      rw [← hcard]
      apply Finset.card_le_card
      intro x hx
      obtain ⟨S, hS, hxS⟩ := Finset.mem_biUnion.mp hx
      exact hsub S hS hxS
wild_two_matchings_small_closed_sets_disjoint_or_equal
Two sets of cardinality at most 7 that are closed under two involutions f and g, where both involutions have no fixed points and are distinct at every point of the union, are either disjoint or identical.
mem_union.mp
If an element belongs to the union S ∪ T, then it belongs to S or to T.
Finset.card_biUnion
The cardinality of a pairwise disjoint union of finite sets is the sum of the cardinalities of the individual sets.
id_eq
The identity function applied to any element yields that element: id(a) = a.
Finset.sum_const_nat
The sum of a constant natural number c over a finite set s is equal to |s| * c.
Nat.mul_comm
Multiplication of natural numbers is commutative: n * m = m * n.
Finset.card_le_card
If s ⊆ t for finite sets s and t, then |s| ≤ |t|.
Finset.mem_biUnion.mp
If an element belongs to a indexed union ⋃_{a ∈ s} t(a), then it belongs to t(a) for some a ∈ 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_matchings_six_closed_family_bound    {α : Type*} [DecidableEq α] (f g : α → α)    (hf : Function.Involutive f) (hg : Function.Involutive g)    (F : Finset (Finset α)) (U : Finset α)    (hsize : ∀ S ∈ F, S.card = 6)    (hsub : ∀ S ∈ F, S ⊆ U)    (hc : ∀ S ∈ F, ∀ x ∈ S, f x ∈ S ∧ g x ∈ S)    (hn : ∀ S ∈ F, ∀ x ∈ S, f x ≠ x ∧ g x ≠ x ∧ f x ≠ g x) :    6 * F.card ≤ U.card := by  have hd : (F : Set (Finset α)).PairwiseDisjoint id := by    intro S hS T hT hne    have h := wild_two_matchings_small_closed_sets_disjoint_or_equal f g hf hg      S T (by rw [hsize S hS]; omega) (by rw [hsize T hT]; omega)      (hc S hS) (hc T hT) (by        intro x hx        rcases mem_union.mp hx with hx | hx        · exact hn S hS x hx        · exact hn T hT x hx)    exact h.resolve_right hne  have hcard : (F.biUnion id).card = 6 * F.card := by    rw [Finset.card_biUnion hd]    simp only [id_eq]    rw [Finset.sum_const_nat hsize, Nat.mul_comm]  rw [← hcard]  apply Finset.card_le_card  intro x hx  obtain ⟨S, hS, hxS⟩ := Finset.mem_biUnion.mp hx  exact hsub S hS hxS
See it in the graphDiscuss this resultChallenge it