AFTD Auto-Formalizing Theoretical Domains

pandora_threshold_policy_nil

theoremverified

Sanity: the threshold policy on the empty list stops at once.

Statement

theorem pandora_threshold_policy_nil {n : ℕ} (t : ℝ) :
    pandora_threshold_policy ([] : List (Fin n)) t = .stop
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…
  • AdaptivePolicyA fully adaptive search policy for Pandora's problem with n boxes, represented as a decision tree that at each step either stops or opens…
Used by 1
  • pandora_threshold_policy_validA threshold policy on a duplicate-free list whose j-th box has deadline at least j is a valid policy and is partially adaptive.

The proof, explained

The theorem states that when the list of candidate boxes is empty, the threshold policy stops immediately. The policy is defined as a right fold over the box list with base case `AdaptivePolicy.stop`. On the empty list, the fold evaluates definitionally to the base case, completing the proof by reflexivity.

  1. pandora_threshold_policy [] t = AdaptivePolicy.stop

    The threshold policy is defined as a right fold (`foldr`) over the list of candidate boxes, with the halting policy `AdaptivePolicy.stop` as the base case. On an empty list, the fold immediately evaluates to this base value, so the equality holds definitionally by reflexivity (`rfl`).

    line 2

        pandora_threshold_policy ([] : List (Fin n)) t = .stop := rfl

Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

theorem pandora_threshold_policy_nil {n : ℕ} (t : ℝ) :    pandora_threshold_policy ([] : List (Fin n)) t = .stop := rfl
See it in the graphDiscuss this resultChallenge it