exists_five_finsets_card
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
- card_generalized_kneser_graph_vertsThe vertex type of the generalized Kneser graph KG(2n, n, r), which consists of all n-element subsets of Fin (2 * n), has cardinality…
- five_diamond_copy_of_mono_levels_spanGeneralised level-copy lemma: if col-coloured sets B ⊆ T straddle a completely col-monochromatic level m (|B| < m < |T|), and the middle…
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.
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.
uses
Finset.card_powersetCard,Finset.card_univ,Fintype.card_finhave 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]
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.
uses
Finset.exists_subset_card_eqobtain ⟨G, hG_sub, hGc⟩ := Finset.exists_subset_card_eq hleDefine 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').
uses
Fin.castOrderIsolet 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
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.
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
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'.
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
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.
/-- 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