card_piFinset_filter_apply_mem
For any type α with decidable equality, any positive integer n, any finite subset S of α, any subset T of α with T ⊆ S, and any coordinate index i₀ : Fin n, the cardinality of the set of points in the product S^n whose i₀-th coordinate belongs to T equals T.card * S.card ^ (n - 1).
Statement
theorem card_piFinset_filter_apply_mem {α : Type*} [DecidableEq α] {n : ℕ} (hn : 0 < n) (S : Finset α) (T : Finset α) (hT : T ⊆ S) (i₀ : Fin n) : Finset.card (Finset.filter (fun x => x i₀ ∈ T) (Fintype.piFinset (fun _ : Fin n => S))) = T.card * S.card ^ (n - 1)
- Source
- folklore
- Verified
- 08 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- schwartz_zippel_zero_count_tightFor any integral domain F with decidable equality, any positive integer n, any finite subset S of F, and any natural number d with d ≤…
Read back from the Lean
Let α be a type with decidable equality, and let n be a natural number such that 0 < n. Let S and T be finite sets of elements of α such that T ⊆ S, and let i₀ : Fin n be an index. Then the cardinality of the set of functions x : Fin n → α (taking values in S at every coordinate) such that x i₀ ∈ T is equal to T.card * S.card ^ (n - 1).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof recognizes the filtered subset of points in S^n whose i₀-th coordinate belongs to T as a generalized Cartesian product where the i₀-th factor is replaced by T and all other n - 1 factors remain S. By the product rule for finite sets, its cardinality is the product of the cardinalities of the individual factors. Factoring out |T| at index i₀ leaves a constant product of |S| over the remaining n - 1 indices, yielding |T| * |S|^(n - 1).
The filtered set `{x ∈ S^n | x i₀ ∈ T}` is identical to the Cartesian product `∏ (i : Fin n) Sᵢ`, where `Sᵢ = T` when `i = i₀` and `Sᵢ = S` otherwise.
We first bring `hn` into scope, then prove by set extensionality that the filtered set equals `Fintype.piFinset (Function.update (fun _ => S) i₀ T)`. A point `x` belongs to the filtered set if and only if `x i ∈ S` for all `i` and `x i₀ ∈ T`. In the forward direction, setting `i = i₀` yields `x i₀ ∈ T`, while for `i ≠ i₀` we have `x i ∈ S`. In the reverse direction, specializing at `i₀` gives `x i₀ ∈ T`, and for any index `i`, either `i = i₀` (so `x i ∈ T ⊆ S` using the hypothesis `hT : T ⊆ S`) or `i ≠ i₀` (so `x i ∈ S`), confirming that `x ∈ S^n`.
uses
Finset.mem_filter,Fintype.mem_piFinset,Function.update_applyhave _ := hn have h_set : Finset.filter (fun x => x i₀ ∈ T) (Fintype.piFinset (fun _ : Fin n => S)) = Fintype.piFinset (Function.update (fun _ : Fin n => S) i₀ T) := by ext x simp only [Finset.mem_filter, Fintype.mem_piFinset, Function.update_apply] constructor · rintro ⟨h1, h2⟩ i split_ifs with h · subst h; exact h2 · exact h1 i · intro h refine ⟨fun i => ?_, ?_⟩ · specialize h i split_ifs at h with hi · subst hi; exact hT h · exact h · specialize h i₀ simpa using h
The cardinality of the filtered set equals the product `∏ (i : Fin n) |Sᵢ|` of the cardinalities of its factor sets.
Rewriting the filtered set with the Cartesian product equality `h_set`, we apply `Fintype.card_piFinset` to express the size of the product as the product of the sizes of the coordinate sets.
uses
Fintype.card_piFinsetrw [h_set, Fintype.card_piFinset]The factor-cardinality function `i ↦ |Sᵢ|` equals the constant function `|S|` updated to `|T|` at `i₀`.
By function extensionality and case distinction on whether `i = i₀` or `i ≠ i₀`, we show that `(i ↦ |Sᵢ|) = Function.update (fun _ => |S|) i₀ |T|`. Rewriting with this identity expresses the goal as the product of this updated function over `Finset.univ`.
have h1 : (fun i : Fin n => (Function.update (fun _ : Fin n => S) i₀ T i).card) = Function.update (fun _ : Fin n => S.card) i₀ T.card := by ext i by_cases h : i = i₀ · subst h; simp · simp [h] rw [h1]
The product factors into `|T|` times the product of `|S|` over all other coordinates `Finset.univ \ {i₀}`.
Since `i₀` is in the universe of coordinates (`Finset.mem_univ`), `Finset.prod_update_of_mem` pulls out the factor `|T|` at `i₀`, leaving the product of the constant `|S|` over the punctured universe `Finset.univ \ {i₀}`.
uses
Finset.mem_univ,Finset.prod_update_of_memhave hmem : i₀ ∈ (Finset.univ : Finset (Fin n)) := Finset.mem_univ i₀ rw [Finset.prod_update_of_mem hmem]
The product of `|S|` over the remaining `n - 1` coordinates equals `|S| ^ (n - 1)`, completing the proof.
The complement `Finset.univ \ {i₀}` is rewritten as `Finset.univ.erase i₀` via `Finset.sdiff_singleton_eq_erase`. By `Finset.prod_const`, the constant product over this set equals `|S|` raised to the cardinality of the erased set. Finally, erasing `i₀` from the universe leaves `|Finset.univ| - 1` elements (`Finset.card_erase_of_mem`), and `Finset.univ` has size `n` (`Finset.card_univ`, `Fintype.card_fin`), leaving exponent `n - 1`.
uses
Finset.sdiff_singleton_eq_erase,Finset.prod_const,Finset.card_erase_of_mem,Finset.card_univ,Fintype.card_finhave h_sdiff : ((Finset.univ : Finset (Fin n)) \ {i₀}) = Finset.univ.erase i₀ := Finset.sdiff_singleton_eq_erase i₀ Finset.univ rw [h_sdiff, Finset.prod_const, Finset.card_erase_of_mem hmem, Finset.card_univ, Fintype.card_fin]
Finset.mem_filter- An element belongs to a filtered set `{x ∈ s | p x}` if and only if it belongs to `s` and satisfies `p`.
Fintype.mem_piFinset- A dependent function `f` belongs to a product of finite sets `Fintype.piFinset t` if and only if `f a ∈ t a` for every coordinate `a`.
Function.update_apply- Evaluating a function updated at `a'` at an input `a` yields the new value if `a = a'` and the original function value otherwise.
Fintype.card_piFinset- The cardinality of a Cartesian product of finite sets equals the product of the cardinalities of the individual factor sets.
Finset.mem_univ- Every element of a finite type belongs to its universal set `Finset.univ`.
Finset.prod_update_of_mem- The product of a function updated at an element `i ∈ s` equals the updated value at `i` times the product of the original function over `s \ {i}`.
Finset.sdiff_singleton_eq_erase- Removing a singleton `{a}` from a finite set `s` by set difference is equal to erasing `a` from `s`.
Finset.prod_const- The product of a constant value `b` over a finite set `s` equals `b ^ |s|`.
Finset.card_erase_of_mem- Removing an element `a ∈ s` from a finite set `s` decreases its cardinality by 1.
Finset.card_univ- The cardinality of `Finset.univ` for a finite type equals the cardinality of the type.
Fintype.card_fin- The cardinality of the standard finite type `Fin n` is `n`.
- The hypothesis `hn : 0 < n` is formally redundant: the existence of the coordinate `i₀ : Fin n` already implies that `n > 0` (since `Fin 0` is empty), and natural number subtraction saturates at zero. Line 6 (`have _ := hn`) serves only to prevent an unused variable warning.
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.
/-- The number of points in S^n whose i₀-th coordinate belongs to a subset T ⊆ S equals |T| * |S|^(n-1). -/theorem card_piFinset_filter_apply_mem {α : Type*} [DecidableEq α] {n : ℕ} (hn : 0 < n) (S : Finset α) (T : Finset α) (hT : T ⊆ S) (i₀ : Fin n) : Finset.card (Finset.filter (fun x => x i₀ ∈ T) (Fintype.piFinset (fun _ : Fin n => S))) = T.card * S.card ^ (n - 1) := by have _ := hn have h_set : Finset.filter (fun x => x i₀ ∈ T) (Fintype.piFinset (fun _ : Fin n => S)) = Fintype.piFinset (Function.update (fun _ : Fin n => S) i₀ T) := by ext x simp only [Finset.mem_filter, Fintype.mem_piFinset, Function.update_apply] constructor · rintro ⟨h1, h2⟩ i split_ifs with h · subst h; exact h2 · exact h1 i · intro h refine ⟨fun i => ?_, ?_⟩ · specialize h i split_ifs at h with hi · subst hi; exact hT h · exact h · specialize h i₀ simpa using h rw [h_set, Fintype.card_piFinset] have h1 : (fun i : Fin n => (Function.update (fun _ : Fin n => S) i₀ T i).card) = Function.update (fun _ : Fin n => S.card) i₀ T.card := by ext i by_cases h : i = i₀ · subst h; simp · simp [h] rw [h1] have hmem : i₀ ∈ (Finset.univ : Finset (Fin n)) := Finset.mem_univ i₀ rw [Finset.prod_update_of_mem hmem] have h_sdiff : ((Finset.univ : Finset (Fin n)) \ {i₀}) = Finset.univ.erase i₀ := Finset.sdiff_singleton_eq_erase i₀ Finset.univ rw [h_sdiff, Finset.prod_const, Finset.card_erase_of_mem hmem, Finset.card_univ, Fintype.card_fin]