permutation_partial_assignment_card_bound_of_switching
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 thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- TotalPreorderA total preorder: a preorder where
- Used by 2
- canonical_permutation_negative_dependency_card_boundFor canonical permutation events with disjoint domains and ranges from a fixed injective partial assignment, multiplying the avoiding…
- wild_number_complete_graph_upper_sub_four_add_parityFor every integer n>=13, every natural number k equal to the chromatic number of the line graph of K_n, and every proper edge coloring c…
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.
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}.
uses
Finset.mem_filter.mpclassical 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τ
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.
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.mprhave 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)
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, υ).
uses
Finset.mem_product.mp,Finset.mem_insert_self,congrArg,Equiv.Perm.mul_apply,Equiv.ext,Prod.exthave 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τυ
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|.
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_producthave 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
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.
uses
Finset.induction_onhave 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
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|.
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]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.
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
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.
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)