AFTD Auto-Formalizing Theoretical Domains

card_piFinset_filter_apply_mem

theoremverified

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

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

    lines 6–23

    uses Finset.mem_filter, Fintype.mem_piFinset, Function.update_apply

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

    line 24

    uses Fintype.card_piFinset

      rw [h_set, Fintype.card_piFinset]
  3. 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`.

    lines 25–31

      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]
  4. 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₀}`.

    lines 32–33

    uses Finset.mem_univ, Finset.prod_update_of_mem

      have hmem : i₀ ∈ (Finset.univ : Finset (Fin n)) := Finset.mem_univ i₀
      rw [Finset.prod_update_of_mem hmem]
  5. 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`.

    lines 34–36

    uses Finset.sdiff_singleton_eq_erase, Finset.prod_const, Finset.card_erase_of_mem, Finset.card_univ, Fintype.card_fin

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

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

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