AFTD Auto-Formalizing Theoretical Domains

is_feasible_packing_zero

theoremverified

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.

  1. 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.

    line 2

    uses two_pow_eq_succ_iff

    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)
two_pow_eq_succ_iff
For any natural number d, 2^d = d + 1 if and only if d = 0 or d = 1.

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

/-- 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)
See it in the graphDiscuss this resultChallenge it