AFTD Auto-Formalizing Theoretical Domains

permutation_partial_assignment_card_bound_of_switching

theoremverified

If a finite set of permutations is closed under undoing any one forced assignment by an image swap, its number extending an injective partial assignment, multiplied by the relevant falling factorial, is at most its total cardinality.

Statement

theorem permutation_partial_assignment_card_bound_of_switching
    {α : Type*} [Fintype α] [DecidableEq α]
    (D : Finset α) (f : α → α) (hf : Set.InjOn f (↑D : Set α))
    (A : Finset (Equiv.Perm α))
    (hA : ∀ a ∈ D, ∀ τ ∈ A, τ a = f a →
      ∀ y, Equiv.swap y (f a) * τ ∈ A) :
    (Fintype.card α).descFactorial D.card *
      (A.filter (fun τ => ∀ a ∈ D, τ a = f a)).card ≤ A.card
Source
Switching/counting helper for OP-306 and EJC 14 (2007) R63, DOI 10.37236/981, Theorem 1. Independent finite-cardinality formalization; no external Lean proof is reused.
Verified
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
Used by 2

The proof, explained

The theorem is proved by finite set induction on the subset S ⊆ D of pinned coordinates, establishing that |α|^{\underline{|S|}} * |{τ ∈ A | ∀ a ∈ S, τ a = f a}| ≤ |A|. In the inductive step, adding an element a ∈ D \ S contracts the set of extending permutations by a factor of at least |α| - |S|. This single-element bound is achieved by an injective switching map (y, τ) ↦ (y f(a)) ∘ τ from (α \ f(S)) × {τ ∈ A | τ agrees with f on S ∪ {a}} into {τ ∈ A | τ agrees with f on S}, where membership in A is preserved by the switching closure hypothesis. Specializing the inductive claim to S = D concludes the proof.

  1. For any S ⊆ D and a ∈ D \ S, we set up the auxiliary sets R, B, C, the switching map g, and the properties of elements in B.

    Working in classical logic, we fix a subset S ⊆ D and an element a ∈ D \ S. We define R = α \ f(S) as the elements outside the image of S under f, B ⊆ A as the permutations extending f on S ∪ {a}, and C ⊆ A as the permutations extending f on S. For any (y, τ), we define g(y, τ) = (y f(a)) ∘ τ. We also establish that any τ ∈ B is in A and satisfies τ(b) = f(b) for all b ∈ S ∪ {a}.

    lines 9–22

    uses Finset.mem_filter.mp

      classical
      have step : ∀ S ⊆ D, ∀ a ∈ D, a ∉ S →
          (Fintype.card α - S.card) *
            (A.filter (fun τ => ∀ b ∈ insert a S, τ b = f b)).card ≤
              (A.filter (fun τ => ∀ b ∈ S, τ b = f b)).card := by
        intro S hSD a ha haS
        let R : Finset α := Finset.univ \ S.image f
        let B := A.filter (fun τ => ∀ b ∈ insert a S, τ b = f b)
        let C := A.filter (fun τ => ∀ b ∈ S, τ b = f b)
        let g : α × Equiv.Perm α → Equiv.Perm α :=
          fun z => Equiv.swap z.1 (f a) * z.2
        have hB : ∀ τ ∈ B, τ ∈ A ∧ ∀ b ∈ insert a S, τ b = f b := by
          intro τ hτ
          exact Finset.mem_filter.mp hτ
  2. The switching map g maps R ×ˢ B into C.

    Given (y, τ) ∈ R ×ˢ B, τ ∈ A and τ(a) = f(a), so the switching hypothesis hA guarantees that g(y, τ) = (y f(a)) ∘ τ belongs to A. For any b ∈ S, τ(b) = f(b) because τ ∈ B. Since y ∈ R = α \ f(S), we have f(b) ≠ y; and since f is injective on D with a ∉ S, we have f(b) ≠ f(a). By Equiv.swap_apply_of_ne_of_ne, the transposition (y f(a)) fixes f(b), so g(y, τ)(b) = f(b). Thus g(y, τ) fixes f on S, placing it in C.

    lines 23–37

    uses Finset.mem_product.mp, Finset.mem_filter.mpr, Finset.mem_insert_self, Finset.mem_insert_of_mem, Equiv.swap_apply_of_ne_of_ne, Finset.mem_sdiff.mp, Finset.mem_image.mpr

        have hmap : Set.MapsTo g (↑(R ×ˢ B) : Set _) ↑C := by
          rintro ⟨y, τ⟩ hz
          obtain ⟨hy, hτ⟩ := Finset.mem_product.mp hz
          obtain ⟨hτA, hτfix⟩ := hB τ hτ
          apply Finset.mem_filter.mpr
          refine ⟨hA a ha τ hτA (hτfix a (Finset.mem_insert_self _ _)) y, ?_⟩
          intro b hb
          change Equiv.swap y (f a) (τ b) = f b
          rw [hτfix b (Finset.mem_insert_of_mem hb)]
          apply Equiv.swap_apply_of_ne_of_ne
          · intro h
            exact (Finset.mem_sdiff.mp hy).2
              (Finset.mem_image.mpr ⟨b, hb, h⟩)
          · intro h
            exact haS ((hf (hSD hb) ha h) ▸ hb)
  3. The switching map g is injective on R ×ˢ B.

    Suppose g(y, τ) = g(z, υ) for (y, τ), (z, υ) ∈ R ×ˢ B. Evaluating both permutations at a yields (y f(a))(τ(a)) = (z f(a))(υ(a)). Since τ, υ ∈ B, both map a to f(a), so this equality simplifies to y = z. Substituting z = y, applying the transposition (y f(a)) to both sides of (y f(a)) ∘ τ = (y f(a)) ∘ υ cancels the swap and yields τ = υ. Hence (y, τ) = (z, υ).

    lines 38–51

    uses Finset.mem_product.mp, Finset.mem_insert_self, congrArg, Equiv.Perm.mul_apply, Equiv.ext, Prod.ext

        have hginj : Set.InjOn g (↑(R ×ˢ B) : Set _) := by
          rintro ⟨y, τ⟩ hz ⟨z, υ⟩ hw heq
          have hτ := (hB τ (Finset.mem_product.mp hz).2).2 a (Finset.mem_insert_self _ _)
          have hυ := (hB υ (Finset.mem_product.mp hw).2).2 a (Finset.mem_insert_self _ _)
          have hyz : y = z := by
            have h := congrArg (fun σ : Equiv.Perm α => σ a) heq
            simpa [g, Equiv.Perm.mul_apply, hτ, hυ] using h
          subst z
          have hτυ : τ = υ := by
            apply Equiv.ext
            intro b
            have h := congrArg (fun σ : Equiv.Perm α => Equiv.swap y (f a) (σ b)) heq
            simpa [g, Equiv.Perm.mul_apply] using h
          exact Prod.ext rfl hτυ
  4. The single-step cardinality bound (|α| - |S|) * |B| ≤ |C| holds.

    Since g is an injection from R ×ˢ B to C, the cardinality of R ×ˢ B is at most |C|. Because f is injective on D and S ⊆ D, f is injective on S, giving |f(S)| = |S|. Thus |R| = |α \ f(S)| = |α| - |S|. Since |R ×ˢ B| = |R| * |B|, this yields (|α| - |S|) * |B| ≤ |C|.

    lines 52–57

    uses Finset.card_le_card_of_injOn, Finset.card_sdiff_of_subset, Finset.subset_univ, Finset.card_univ, Finset.card_image_of_injOn, Set.InjOn.mono, Finset.card_product

        have hcard := Finset.card_le_card_of_injOn g hmap hginj
        have hR : R.card = Fintype.card α - S.card := by
          rw [Finset.card_sdiff_of_subset (Finset.subset_univ _), Finset.card_univ,
            Finset.card_image_of_injOn]
          exact Set.InjOn.mono hSD hf
        simpa only [Finset.card_product, hR] using hcard
  5. The general inequality holds for the base case S = ∅.

    We state the main bound for all S ⊆ D by induction on S. When S = ∅, the falling factorial is |α|^{\underline{0}} = 1 and the condition on permutations is vacuous, so the filtered subset is all of A. The inequality 1 * |A| ≤ |A| holds immediately by simplification.

    lines 58–63

    uses Finset.induction_on

      have main : ∀ S ⊆ D,
          (Fintype.card α).descFactorial S.card *
            (A.filter (fun τ => ∀ a ∈ S, τ a = f a)).card ≤ A.card := by
        intro S
        induction S using Finset.induction_on with
        | empty => intro _; simp
  6. The general inequality holds for insert a S assuming it holds for S.

    Let S ⊆ D and a ∈ D \ S. By the induction hypothesis, the falling factorial product for S is at most |A|. Multiplying the single-step inequality (|α| - |S|) * |B| ≤ |C| by the falling factorial |α|^{\underline{|S|}} and applying the recurrence |α|^{\underline{|S| + 1}} = (|α| - |S|) * |α|^{\underline{|S|}}, non-linear arithmetic combines these bounds to conclude |α|^{\underline{|insert a S|}} * |B| ≤ |A|.

    lines 64–71

    uses Finset.subset_insert, Finset.mem_insert_self, Nat.mul_le_mul_left, Finset.card_insert_of_notMem, Nat.descFactorial_succ

        | @insert a S haS ih =>
          intro hsub
          have hSD : S ⊆ D := (Finset.subset_insert _ _).trans hsub
          have haD := hsub (Finset.mem_insert_self _ _)
          have hs := Nat.mul_le_mul_left ((Fintype.card α).descFactorial S.card)
            (step S hSD a haD haS)
          rw [Finset.card_insert_of_notMem haS, Nat.descFactorial_succ]
          nlinarith [ih hSD]
  7. The falling factorial cardinality bound holds for D.

    Specializing the inductive result to S = D using the reflexive inclusion D ⊆ D directly yields the theorem statement.

    line 72

      exact main D (fun _ h => h)
Finset.mem_filter.mp
An element belongs to a filtered finset if and only if it belongs to the original finset and satisfies the predicate (forward direction).
Finset.mem_product.mp
An element belongs to a Cartesian product of two finsets if and only if its first component is in the first finset and its second component is in the second (forward direction).
Finset.mem_filter.mpr
If an element belongs to a finset and satisfies the filtering predicate, it belongs to the filtered finset (reverse direction).
Finset.mem_insert_self
An element a is a member of the finset insert a s.
Finset.mem_insert_of_mem
If an element a belongs to s, it also belongs to insert b s.
Equiv.swap_apply_of_ne_of_ne
The transposition (swap) of a and b fixes any element x different from both a and b.
Finset.mem_sdiff.mp
If an element belongs to s \\ t, then it belongs to s and not to t.
Finset.mem_image.mpr
If an element x is in s and f(x) = y, then y is in the image of s under f.
congrArg
Equal inputs yield equal function values: if x = y, then f(x) = f(y).
Equiv.Perm.mul_apply
Permutation multiplication applies permutations in sequence: (f * g)(x) = f(g(x)).
Equiv.ext
Two permutations (or equivalences) are equal if they produce the same value on every element.
Prod.ext
Two pairs are equal if their first components are equal and their second components are equal.
Finset.card_le_card_of_injOn
If f maps a finset s to a finset t and is injective on s, then the cardinality of s is at most the cardinality of t.
Finset.card_sdiff_of_subset
If s is a subset of t, the cardinality of the difference t \\ s is |t| - |s|.
Finset.subset_univ
Every finset on a finite type is a subset of the universal finset.
Finset.card_univ
The cardinality of the universal finset on a finite type equals the cardinality of that type.
Finset.card_image_of_injOn
If f is injective on a finset s, the image of s under f has the same cardinality as s.
Set.InjOn.mono
Injectivity on a set is preserved when restricting to any subset.
Finset.card_product
The cardinality of the Cartesian product of two finsets is the product of their cardinalities.
Finset.induction_on
Induction principle for finite sets: a predicate holds for all finsets if it holds for the empty set and is preserved under adjoining a new element.
Finset.subset_insert
A finset s is a subset of insert a s.
Nat.mul_le_mul_left
Multiplying both sides of an inequality of natural numbers by a constant on the left preserves the inequality.
Finset.card_insert_of_notMem
Adjoining an element not already in a finset s increases its cardinality by 1.
Nat.descFactorial_succ
The falling factorial satisfies n^{\underline{k + 1}} = (n - k) * n^{\underline{k}}.

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

theorem permutation_partial_assignment_card_bound_of_switching    {α : Type*} [Fintype α] [DecidableEq α]    (D : Finset α) (f : α → α) (hf : Set.InjOn f (↑D : Set α))    (A : Finset (Equiv.Perm α))    (hA : ∀ a ∈ D, ∀ τ ∈ A, τ a = f a →      ∀ y, Equiv.swap y (f a) * τ ∈ A) :    (Fintype.card α).descFactorial D.card *      (A.filter (fun τ => ∀ a ∈ D, τ a = f a)).card ≤ A.card := by  classical  have step : ∀ S ⊆ D, ∀ a ∈ D, a ∉ S →      (Fintype.card α - S.card) *        (A.filter (fun τ => ∀ b ∈ insert a S, τ b = f b)).card ≤          (A.filter (fun τ => ∀ b ∈ S, τ b = f b)).card := by    intro S hSD a ha haS    let R : Finset α := Finset.univ \ S.image f    let B := A.filter (fun τ => ∀ b ∈ insert a S, τ b = f b)    let C := A.filter (fun τ => ∀ b ∈ S, τ b = f b)    let g : α × Equiv.Perm α → Equiv.Perm α :=      fun z => Equiv.swap z.1 (f a) * z.2    have hB : ∀ τ ∈ B, τ ∈ A ∧ ∀ b ∈ insert a S, τ b = f b := by      intro τ hτ      exact Finset.mem_filter.mp hτ    have hmap : Set.MapsTo g (↑(R ×ˢ B) : Set _) ↑C := by      rintro ⟨y, τ⟩ hz      obtain ⟨hy, hτ⟩ := Finset.mem_product.mp hz      obtain ⟨hτA, hτfix⟩ := hB τ hτ      apply Finset.mem_filter.mpr      refine ⟨hA a ha τ hτA (hτfix a (Finset.mem_insert_self _ _)) y, ?_⟩      intro b hb      change Equiv.swap y (f a) (τ b) = f b      rw [hτfix b (Finset.mem_insert_of_mem hb)]      apply Equiv.swap_apply_of_ne_of_ne      · intro h        exact (Finset.mem_sdiff.mp hy).2          (Finset.mem_image.mpr ⟨b, hb, h⟩)      · intro h        exact haS ((hf (hSD hb) ha h) ▸ hb)    have hginj : Set.InjOn g (↑(R ×ˢ B) : Set _) := by      rintro ⟨y, τ⟩ hz ⟨z, υ⟩ hw heq      have hτ := (hB τ (Finset.mem_product.mp hz).2).2 a (Finset.mem_insert_self _ _)      have hυ := (hB υ (Finset.mem_product.mp hw).2).2 a (Finset.mem_insert_self _ _)      have hyz : y = z := by        have h := congrArg (fun σ : Equiv.Perm α => σ a) heq        simpa [g, Equiv.Perm.mul_apply, hτ, hυ] using h      subst z      have hτυ : τ = υ := by        apply Equiv.ext        intro b        have h := congrArg (fun σ : Equiv.Perm α => Equiv.swap y (f a) (σ b)) heq        simpa [g, Equiv.Perm.mul_apply] using h      exact Prod.ext rfl hτυ    have hcard := Finset.card_le_card_of_injOn g hmap hginj    have hR : R.card = Fintype.card α - S.card := by      rw [Finset.card_sdiff_of_subset (Finset.subset_univ _), Finset.card_univ,        Finset.card_image_of_injOn]      exact Set.InjOn.mono hSD hf    simpa only [Finset.card_product, hR] using hcard  have main : ∀ S ⊆ D,      (Fintype.card α).descFactorial S.card *        (A.filter (fun τ => ∀ a ∈ S, τ a = f a)).card ≤ A.card := by    intro S    induction S using Finset.induction_on with    | empty => intro _; simp    | @insert a S haS ih =>      intro hsub      have hSD : S ⊆ D := (Finset.subset_insert _ _).trans hsub      have haD := hsub (Finset.mem_insert_self _ _)      have hs := Nat.mul_le_mul_left ((Fintype.card α).descFactorial S.card)        (step S hSD a haD haS)      rw [Finset.card_insert_of_notMem haS, Nat.descFactorial_succ]      nlinarith [ih hSD]  exact main D (fun _ h => h)
See it in the graphDiscuss this resultChallenge it