AFTD Auto-Formalizing Theoretical Domains

deadline_schedule_exists_iff_sorted_deadline_ge

theoremverifiedformalization

Boxes i₁, …, i_k with nondecreasing integer deadlines d_{i₁} ≤ … ≤ d_{i_k} can be opened one per round (rounds 1, 2, …), each box i in a round t ≤ d_i, if and only if d_{i_j} ≥ j for every j. (Here box j is indexed from 0, so the condition reads j + 1 ≤ d j.)

Statement

theorem deadline_schedule_exists_iff_sorted_deadline_ge (k : ℕ) (d : Fin k → ℕ)
    (hd : Monotone d) :
    (∃ σ : Fin k → ℕ, Function.Injective σ ∧ ∀ j, 1 ≤ σ j ∧ σ j ≤ d j) ↔
      ∀ j : Fin k, j.val + 1 ≤ d j
Formalizes
arXiv:2610.13775 (A 1/2-Approximation for Pandora's Problem with Deadlines), Lemma 2, first part (the feasibility characterization; the O(n²) dynamic program of the second part is not stated).
Verified
13 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…

The proof, explained

The theorem establishes that boxes with nondecreasing deadlines can be opened one per round within their deadlines if and only if each box j satisfies j + 1 ≤ d(j). For the forward direction, an injective schedule maps the first j + 1 boxes into the rounds {1, …, d(j)}, so the pigeonhole principle forces j + 1 ≤ d(j). For the backward direction, assigning box j to round j + 1 provides an explicit injective schedule meeting all deadlines.

  1. To prove the equivalence, we first consider the forward direction: assuming a valid schedule exists, we fix an arbitrary box index j.

    We split the equivalence into both directions. For the forward direction (⇒), we assume there exists an injective schedule σ : Fin k → ℕ opening each box x in a round between 1 and d(x), and take an arbitrary box index j : Fin k.

    lines 5–6

      constructor
      · rintro ⟨σ, h_inj, h_bound⟩ j
  2. The schedule σ maps the first j + 1 boxes {x : Fin k | x ≤ j} into the round interval {1, …, d(j)}.

    For any box x ≤ j, its round σ(x) is at least 1, and by monotonicity of deadlines, σ(x) ≤ d(x) ≤ d(j). Rewriting membership conditions using Finset.mem_coe, Finset.mem_Iic, and Finset.mem_Icc shows that σ maps Finset.Iic j into Finset.Icc 1 (d j).

    lines 7–11

    uses Finset.mem_coe, Finset.mem_Iic, Finset.mem_Icc

        have h_maps : Set.MapsTo σ (Finset.Iic j : Set (Fin k)) (Finset.Icc 1 (d j) : Set ℕ) := by
          intro x hx
          rw [Finset.mem_coe, Finset.mem_Iic] at hx
          rw [Finset.mem_coe, Finset.mem_Icc]
          exact ⟨(h_bound x).1, (h_bound x).2.trans (hd hx)⟩
  3. By the pigeonhole principle on cardinalities, j + 1 ≤ d(j).

    Because σ is injective on Finset.Iic j, Finset.card_le_card_of_injOn implies that the cardinality of Finset.Iic j is at most that of Finset.Icc 1 (d j). Evaluating the cardinalities with Fin.card_Iic and Nat.card_Icc gives j + 1 ≤ d(j) + 1 - 1, from which linear arithmetic (omega) yields j + 1 ≤ d(j).

    lines 12–14

    uses Finset.card_le_card_of_injOn, Fin.card_Iic, Nat.card_Icc

        have h_card := Finset.card_le_card_of_injOn σ h_maps h_inj.injOn
        rw [Fin.card_Iic, Nat.card_Icc] at h_card
        omega
  4. For the backward direction, we propose the candidate schedule σ(j) = j + 1.

    Assuming j + 1 ≤ d(j) for all j, we schedule box j in round j + 1. This reduces the backward direction to verifying that this assignment is injective and satisfies the deadline bounds.

    lines 15–17

      · intro h
        use fun j => j.val + 1
        refine ⟨?_, ?_⟩
  5. The schedule σ(j) = j + 1 is injective.

    If a + 1 = b + 1, linear integer arithmetic (omega) simplifies this to a = b in ℕ, and Fin.ext concludes that the Fin k indices a and b are equal.

    lines 18–21

    uses Fin.ext

        · intro a b hab
          apply Fin.ext
          dsimp at hab
          omega
  6. The schedule σ(j) = j + 1 satisfies 1 ≤ σ(j) ≤ d(j) for every box j.

    For any j, the lower bound 1 ≤ j + 1 holds by Nat.le_add_left, and the upper bound j + 1 ≤ d(j) holds directly by the hypothesis h.

    lines 22–23

    uses Nat.le_add_left

        · intro j
          exact ⟨Nat.le_add_left 1 j.val, h j⟩
Fin.ext
Two elements of Fin n are equal if their underlying natural values are equal.
Fin.card_Iic
The closed lower interval Finset.Iic b in Fin n contains b + 1 elements.
Finset.mem_coe
An element belongs to the set coercion of a finite set if and only if it belongs to the finite set.
Finset.mem_Icc
An element x belongs to the closed interval Finset.Icc a b if and only if a ≤ x and x ≤ b.
Finset.mem_Iic
An element x belongs to the lower interval Finset.Iic a if and only if x ≤ a.
Finset.card_le_card_of_injOn
If a function maps a finite set s into a finite set t and is injective on s, then the cardinality of s is at most that of t.
Nat.card_Icc
For natural numbers a and b, the number of elements in the closed interval Finset.Icc a b is b + 1 - a.
Nat.le_add_left
For any natural numbers n and m, n ≤ m + n.

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 deadline_schedule_exists_iff_sorted_deadline_ge (k : ℕ) (d : Fin k → ℕ)    (hd : Monotone d) :    (∃ σ : Fin k → ℕ, Function.Injective σ ∧ ∀ j, 1 ≤ σ j ∧ σ j ≤ d j) ↔      ∀ j : Fin k, j.val + 1 ≤ d j := by  constructor  · rintro ⟨σ, h_inj, h_bound⟩ j    have h_maps : Set.MapsTo σ (Finset.Iic j : Set (Fin k)) (Finset.Icc 1 (d j) : Set ℕ) := by      intro x hx      rw [Finset.mem_coe, Finset.mem_Iic] at hx      rw [Finset.mem_coe, Finset.mem_Icc]      exact ⟨(h_bound x).1, (h_bound x).2.trans (hd hx)⟩    have h_card := Finset.card_le_card_of_injOn σ h_maps h_inj.injOn    rw [Fin.card_Iic, Nat.card_Icc] at h_card    omega  · intro h    use fun j => j.val + 1    refine ⟨?_, ?_⟩    · intro a b hab      apply Fin.ext      dsimp at hab      omega    · intro j      exact ⟨Nat.le_add_left 1 j.val, h j⟩
See it in the graphDiscuss this resultChallenge it