pandora_deadline_feasible_empty
Sanity: the empty set of boxes is deadline-feasible.
Statement
theorem pandora_deadline_feasible_empty (inst : PandoraDeadlineInstance) :
pandora_deadline_feasible inst ∅- Source
- Sanity lemma for the definitions of arXiv:2610.13775 Section 3
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- pandora_threshold_policyThe threshold policy on a list of boxes: open them in the given order and stop as soon as an opened value exceeds t (stop after the last…
- pandora_deadline_feasibleA set S of boxes is deadline-feasible if for every j at most j of its boxes have deadline at most j (equivalently, by Lemma 2, its boxes…
- PandoraDeadlineInstanceAn instance of Pandora's problem with deadlines consisting of n boxes, each with a non-negative opening cost, a positive integer deadline,…
- Used by 2
- op184_partially_adaptive_half_approximationFor every Pandora's problem instance with deadlines
inst : PandoraDeadlineInstance, there exists a valid partially adaptive policy… - pandora_exists_balancing_thresholdThere is a threshold t >= 0 at which the maximum total capped surplus over deadline-feasible sets equals t, attained by some feasible set.
- op184_partially_adaptive_half_approximationFor every Pandora's problem instance with deadlines
The proof, explained
To show that the empty set of boxes is deadline-feasible, we must verify that for any deadline threshold $j \in \mathbb{N}$, the number of boxes in $\emptyset$ with deadline at most $j$ is at most $j$. Unfolding the definition and fixing an arbitrary $j$, filtering the empty set yields the empty set with cardinality $0$. Since $0 \le j$ holds for every natural number, the condition is satisfied.
The empty set of boxes is deadline-feasible: `pandora_deadline_feasible inst ∅`.
By definition of `pandora_deadline_feasible`, we must show that for any threshold $j \in \mathbb{N}$, the number of elements in $\emptyset$ with deadline at most $j$ is at most $j$. We introduce an arbitrary $j$; filtering the empty set yields the empty set, which has cardinality $0$. The simplifier evaluates the cardinality to $0$ and verifies that $0 \le j$ for any natural number $j$.
intro j; simp
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.
theorem pandora_deadline_feasible_empty (inst : PandoraDeadlineInstance) : pandora_deadline_feasible inst ∅ := by intro j; simp