AFTD Auto-Formalizing Theoretical Domains

pandora_deadline_feasible_empty

theoremverified

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

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.

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

    line 3

      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

theorem pandora_deadline_feasible_empty (inst : PandoraDeadlineInstance) :    pandora_deadline_feasible inst ∅ := by  intro j; simp
See it in the graphDiscuss this resultChallenge it