exists_submultiset_card_eq
theoremverified
Any multiset contains a submultiset of any cardinality less than or equal to its own.
Statement
theorem exists_submultiset_card_eq {α : Type*} (S : Multiset α) (m : ℕ) (hm : m ≤ S.card) : ∃ T : Multiset α, T ≤ S ∧ T.card = m
- Source
- step towards additive_basis_bound_cp_cnp_conjecture
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- additive_basis_threshold_le_of_card_eqTo bound the additive basis threshold c_0(G) ≤ m, it suffices to show that every regular sequence S over G of cardinality exactly m is an…
Lean source view module on GitHub
/-- Any multiset contains a submultiset of any cardinality less than or equal to its own. -/ theorem exists_submultiset_card_eq {α : Type*} (S : Multiset α) (m : ℕ) (hm : m ≤ S.card) : ∃ T : Multiset α, T ≤ S ∧ T.card = m := by induction S using Multiset.induction_on generalizing m with | empty => have hm0 : m = 0 := by simpa using hm subst hm0 exact ⟨0, by simp, by simp⟩ | cons x s ih => rcases m with _ | m · exact ⟨0, by simp, rfl⟩ · have hm' : m ≤ s.card := by simp only [Multiset.card_cons] at hm; omega obtain ⟨T, hT, hTc⟩ := ih m hm' exact ⟨x ::ₘ T, Multiset.cons_le_cons x hT, by simp [hTc]⟩