is_feasible_packing_zero
The empty multiset of finite sets is a feasible packing for any parameters r, s, t, h.
Statement
theorem is_feasible_packing_zero (r s t h : ℕ) : is_feasible_packing r s t h 0- Source
- folklore
- Verified
- 14 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- is_feasible_packingA multiset M of s-subsets of Fin r is a feasible packing for parameters (r, s, t, h) if every member of M has cardinality s and every…
- two_pow_eq_succ_iffFor a natural d, two to the power d equals d+1 exactly when d is zero or one.
Read back from the Lean
For all natural numbers r, s, t, and h, the empty multiset of subsets of Fin r satisfies is_feasible_packing r s t h 0.
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 empty multiset is a feasible packing for any parameters r, s, t, and h. Unfolding the definition of a feasible packing, the condition that every element has size s is vacuously true, and the condition that at most h elements contain any given t-element subset holds because the count is zero. The proof search script accomplishes this by unfolding the definition and invoking the simplifier.
The empty multiset 0 is a feasible packing for any parameters r, s, t, h. automation
Unfolding the definition of `is_feasible_packing`, we must show that: (1) every set in the empty multiset has cardinality s, which holds vacuously since the multiset has no elements; and (2) for any t-element subset T, the number of sets containing T is at most h, which holds trivially because filtering the empty multiset yields the empty multiset of size 0, and 0 ≤ h. The tactic `simpa` simplifies both conditions to True.
uses
two_pow_eq_succ_ifftheorem is_feasible_packing_zero (r s t h : ℕ) : is_feasible_packing r s t h 0 := by first | exact two_pow_eq_succ_iff | (apply two_pow_eq_succ_iff <;> assumption) | (apply two_pow_eq_succ_iff <;> simp_all) | simpa using two_pow_eq_succ_iff | (simp only [is_feasible_packing] at *; first | exact two_pow_eq_succ_iff | (apply two_pow_eq_succ_iff <;> assumption) | (apply two_pow_eq_succ_iff <;> simp_all) | simpa using two_pow_eq_succ_iff)
two_pow_eq_succ_iff- For any natural number d, 2^d = d + 1 if and only if d = 0 or d = 1.
- The proof source uses an automated search pattern `first | ...` that passes the irrelevant lemma `two_pow_eq_succ_iff` to `simpa`. This lemma is not actually needed: the simplifier closes the goal on its own once `is_feasible_packing` is unfolded.
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.
/-- The empty multiset is a feasible packing for any parameters. -/theorem is_feasible_packing_zero (r s t h : ℕ) : is_feasible_packing r s t h 0 := by first | exact two_pow_eq_succ_iff | (apply two_pow_eq_succ_iff <;> assumption) | (apply two_pow_eq_succ_iff <;> simp_all) | simpa using two_pow_eq_succ_iff | (simp only [is_feasible_packing] at *; first | exact two_pow_eq_succ_iff | (apply two_pow_eq_succ_iff <;> assumption) | (apply two_pow_eq_succ_iff <;> simp_all) | simpa using two_pow_eq_succ_iff)