AFTD Auto-Formalizing Theoretical Domains

exists_five_finsets_card

theoremverified

If the binomial coefficient C(m,r) is at least 5, there are five pairwise distinct r-element subsets of Fin m.

Statement

theorem exists_five_finsets_card {m r : ℕ} (h5 : 5 ≤ Nat.choose m r) :
    ∃ S : Fin 5 → Finset (Fin m), (∀ k, (S k).card = r) ∧ ∀ k k', k ≠ k' → S k ≠ S k'
Source
step towards five_diamond_ramsey_property_step
Verified
24 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 2

The proof, explained

The collection of all r-element subsets of Fin m has cardinality C(m, r). Because C(m, r) ≥ 5 by assumption, this collection contains a subcollection G of exactly 5 distinct r-subsets. By enumerating G via a bijection with Fin 5, we obtain an indexed family of five subsets of Fin m that are pairwise distinct and each have cardinality r.

  1. The collection of r-element subsets of Fin m has cardinality C(m, r), which is at least 5.

    The number of r-element subsets of any finite set s is C(|s|, r) by Finset.card_powersetCard. Since the universe Fin m has size m (by Finset.card_univ and Fintype.card_fin), the total number of r-element subsets of Fin m is C(m, r). Rewriting with this equality and using the hypothesis 5 ≤ C(m, r) shows that this collection has at least 5 elements.

    lines 4–7

    uses Finset.card_powersetCard, Finset.card_univ, Fintype.card_fin

      have hcard : ((Finset.univ : Finset (Fin m)).powersetCard r).card = Nat.choose m r := by
        rw [Finset.card_powersetCard, Finset.card_univ, Fintype.card_fin]
      have hle : 5 ≤ ((Finset.univ : Finset (Fin m)).powersetCard r).card := by
        rwa [hcard]
  2. There exists a subcollection G of exactly 5 distinct r-element subsets of Fin m.

    Since any finite set of cardinality at least 5 contains a subset of cardinality 5 (by Finset.exists_subset_card_eq), we obtain a subset G of the collection of r-subsets such that |G| = 5.

    line 8

    uses Finset.exists_subset_card_eq

      obtain ⟨G, hG_sub, hGc⟩ := Finset.exists_subset_card_eq hle
  3. Define an indexed family S : Fin 5 → Finset (Fin m) enumerating G, and reduce to showing that each S(k) has size r and that S is injective.

    Because |G| = 5, we can construct an equivalence e between Fin 5 and G using Fin.castOrderIso. We then define S(k) to be the underlying set of e(k). Proposing S as the witness reduces the goal to verifying two claims: every S(k) has size r, and distinct indices k ≠ k' give distinct sets S(k) ≠ S(k').

    lines 9–12

    uses Fin.castOrderIso

      let e : Fin 5 ≃ ↥G := (Fin.castOrderIso hGc.symm).toEquiv.trans G.equivFin.symm
      let S : Fin 5 → Finset (Fin m) := fun k => (e k).1
      use S
      constructor
  4. Each subset S(k) has cardinality r.

    By construction, each S(k) is an element of G, and G is a subset of the r-element powerset of Fin m. Applying Finset.mem_powersetCard, any element of this collection has cardinality r.

    lines 13–16

    uses Finset.mem_powersetCard

      · intro k
        have hk : (e k).1 ∈ (Finset.univ : Finset (Fin m)).powersetCard r := hG_sub (e k).2
        rw [Finset.mem_powersetCard] at hk
        exact hk.2
  5. The subsets S(k) are pairwise distinct: if k ≠ k', then S(k) ≠ S(k').

    Assume for contradiction that S(k) = S(k') for k ≠ k'. Since S(k) and S(k') are the underlying sets of e(k) and e(k') in G, subtype extensionality (Subtype.ext) gives e(k) = e(k'). Because e is a bijection, it is injective, which forces k = k', contradicting k ≠ k'.

    lines 17–20

    uses Subtype.ext

      · intro k k' hne heq
        apply hne
        have : e k = e k' := Subtype.ext heq
        exact e.injective this
Finset.card_powersetCard
The number of n-element subsets of a finite set s is given by the binomial coefficient C(|s|, n).
Finset.card_univ
The cardinality of the universal finset of a finite type α equals the cardinality of α.
Fintype.card_fin
The standard finite type Fin n has cardinality n.
Finset.exists_subset_card_eq
If a finite set has at least n elements, it has a subset of cardinality n.
Fin.castOrderIso
An equality n = m induces an order isomorphism (and hence an equivalence) between Fin n and Fin m.
Finset.mem_powersetCard
A set s belongs to the collection of n-element subsets of t if and only if s ⊆ t and |s| = n.
Subtype.ext
Two elements of a subtype are equal if their underlying values are equal.

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

/-- Five distinct r-subsets of Fin m exist as soon as C(m,r) ≥ 5. -/theorem exists_five_finsets_card {m r : ℕ} (h5 : 5 ≤ Nat.choose m r) :    ∃ S : Fin 5 → Finset (Fin m), (∀ k, (S k).card = r) ∧ ∀ k k', k ≠ k' → S k ≠ S k' := by  have hcard : ((Finset.univ : Finset (Fin m)).powersetCard r).card = Nat.choose m r := by    rw [Finset.card_powersetCard, Finset.card_univ, Fintype.card_fin]  have hle : 5 ≤ ((Finset.univ : Finset (Fin m)).powersetCard r).card := by    rwa [hcard]  obtain ⟨G, hG_sub, hGc⟩ := Finset.exists_subset_card_eq hle  let e : Fin 5 ≃ ↥G := (Fin.castOrderIso hGc.symm).toEquiv.trans G.equivFin.symm  let S : Fin 5 → Finset (Fin m) := fun k => (e k).1  use S  constructor  · intro k    have hk : (e k).1 ∈ (Finset.univ : Finset (Fin m)).powersetCard r := hG_sub (e k).2    rw [Finset.mem_powersetCard] at hk    exact hk.2  · intro k k' hne heq    apply hne    have : e k = e k' := Subtype.ext heq    exact e.injective this
See it in the graphDiscuss this resultChallenge it