AFTD Auto-Formalizing Theoretical Domains

op_258_pigeonhole_blocks

theoremverified

Let s be a finite set and f : α → Fin γ. If γ * k ≤ |s| and γ ≥ 1, then there exists b ∈ Fin γ with |{x ∈ s | f x = b}| ≥ k.

Statement

theorem op_258_pigeonhole_blocks {α : Type*} (s : Finset α)
    (γ k : ℕ) (hγ : 1 ≤ γ) (f : α → Fin γ) (hs : γ * k ≤ s.card) :
    ∃ b : Fin γ, k ≤ (s.filter (fun x => f x = b)).card
Source
step towards op_258_forces_of_forces_smul_blowup
Verified
21 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

The proof, explained

The proof applies the pigeonhole principle for finite sets to the map `f : α → Fin γ` targeting the full universe of `Fin γ`. It first confirms the prerequisites: the codomain universe is nonempty because `γ ≥ 1`, and its size times `k` is at most `|s|` because `|Fin γ| = γ` and `γ * k ≤ |s|`. Invoking the library lemma `Finset.exists_le_card_fiber_of_mul_le_card_of_maps_to` then produces the desired element `b ∈ Fin γ` with fiber cardinality at least `k`.

  1. The universe `Finset.univ` on `Fin γ` is nonempty.

    A finite set is nonempty if and only if its cardinality is strictly greater than zero (`Finset.card_pos`). Because the universe of `Fin γ` has cardinality `γ` (`Finset.card_fin`), this condition reduces to `0 < γ`, which follows by linear arithmetic (`omega`) from the assumption `1 ≤ γ`.

    lines 5–7

    uses Finset.card_pos, Finset.card_fin

      have ht : (Finset.univ : Finset (Fin γ)).Nonempty := by
        rw [← Finset.card_pos, Finset.card_fin]
        omega
  2. The product `|Finset.univ| * k` is at most `|s|`.

    Substituting the cardinality of `Finset.univ` with `γ` via `Finset.card_fin` reduces the inequality to `γ * k ≤ |s|`, which is directly provided by the hypothesis `hs`.

    lines 8–10

    uses Finset.card_fin

      have hmul : (Finset.univ : Finset (Fin γ)).card * k ≤ s.card := by
        rw [Finset.card_fin]
        exact hs
  3. There exists `b ∈ Fin γ` such that the fiber `{x ∈ s | f x = b}` has cardinality at least `k`.

    By the pigeonhole principle for maps between finite sets (`Finset.exists_le_card_fiber_of_mul_le_card_of_maps_to`), since `f` maps all elements of `s` into `Finset.univ` (using `Finset.mem_univ`), `Finset.univ` is nonempty (`ht`), and `|Finset.univ| * k ≤ |s|` (`hmul`), there must exist a block `b ∈ Fin γ` whose fiber has size at least `k`. Providing this `b` and its fiber bound closes the existential goal.

    lines 11–13

    uses Finset.exists_le_card_fiber_of_mul_le_card_of_maps_to, Finset.mem_univ

      obtain ⟨b, -, hb⟩ := Finset.exists_le_card_fiber_of_mul_le_card_of_maps_to
        (fun a _ => Finset.mem_univ (f a)) ht hmul
      exact ⟨b, hb⟩
Finset.card_pos
A finite set is nonempty if and only if its cardinality is strictly positive.
Finset.card_fin
The universal finite set of `Fin n` has cardinality `n`.
Finset.exists_le_card_fiber_of_mul_le_card_of_maps_to
If a function maps a finite set `s` into a nonempty finite set `t` and `|t| * n ≤ |s|`, then some element of `t` has a fiber in `s` of cardinality at least `n`.
Finset.mem_univ
Every element of a finite type belongs to its universal finite set.

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

/-- Pigeonhole principle on finsets partitioned into γ classes: if s has cardinality at least γ * k, then some fiber under f : α → Fin γ has cardinality at least k. -/theorem op_258_pigeonhole_blocks {α : Type*} (s : Finset α)    (γ k : ℕ) (hγ : 1 ≤ γ) (f : α → Fin γ) (hs : γ * k ≤ s.card) :    ∃ b : Fin γ, k ≤ (s.filter (fun x => f x = b)).card := by  have ht : (Finset.univ : Finset (Fin γ)).Nonempty := by    rw [← Finset.card_pos, Finset.card_fin]    omega  have hmul : (Finset.univ : Finset (Fin γ)).card * k ≤ s.card := by    rw [Finset.card_fin]    exact hs  obtain ⟨b, -, hb⟩ := Finset.exists_le_card_fiber_of_mul_le_card_of_maps_to    (fun a _ => Finset.mem_univ (f a)) ht hmul  exact ⟨b, hb⟩
See it in the graphDiscuss this resultChallenge it