AFTD Auto-Formalizing Theoretical Domains

is_valid_timely_packing

def

A finite set of bins P : Finset TimelyBin is a valid timely packing of an item set I : Finset TimelyItem, written is_valid_timely_packing I P, if every bin b ∈ P is valid (timely_bin_is_valid b) and non-empty, the item sets of distinct bins in P are pairwise disjoint, and the union of the item sets across all bins in P equals I.

Statement

def is_valid_timely_packing (I : Finset TimelyItem) (P : Finset TimelyBin) : Prop
Defined in
arXiv:2611.09611, Section 1.1
Verified
09 Nov 2026
Axioms
none listed
Built on 4
  • TimelyBinA structure TimelyBin representing a bin in timely bin packing, with fields items : Finset TimelyItem (the finite set of items packed…
  • timely_bin_is_validA timely bin b : TimelyBin is valid, written timely_bin_is_valid b, if for every item p ∈ b.items the packing time b.time…
  • TimelyItemA structure TimelyItem representing an item in online timely bin packing, with fields id : ℕ (a unique natural identifier),…
  • instLinearOrderTimelyItemThe linear order on TimelyItem obtained by pulling back the lexicographic order on ℝ ×ₗ ℕ ×ₗ ℝ ×ₗ ℝ along the injective function…
Used by 1
  • optimal_timely_bin_countThe optimal offline number of bins optimal_timely_bin_count I for an instance I : Finset TimelyItem is the infimum in ℕ of the…

Read back from the Lean

Given a finite set of timely items I and a finite set of timely bins P, is_valid_timely_packing I P asserts that: 1. Every bin b ∈ P is valid—meaning that for every item p ∈ b.items, p.arrival ≤ b.time and b.time ≤ p.deadline, and the sum of sizes of items in b.items is at most 1—and b.items is non-empty; 2. For any two bins b₁, b₂ ∈ P, if b₁ ≠ b₂, then their item sets b₁.items and b₂.items are disjoint; 3. The union of the item sets b.items across all bins b ∈ P is equal to I.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- A set of bins is a valid timely packing of I if every bin is valid and nonempty, bins have disjoint items, and their union is I. -/
def is_valid_timely_packing (I : Finset TimelyItem) (P : Finset TimelyBin) : Prop :=
  open Classical in
  (∀ b ∈ P, timely_bin_is_valid b ∧ b.items.Nonempty) ∧
  (∀ b₁ ∈ P, ∀ b₂ ∈ P, b₁ ≠ b₂ → Disjoint b₁.items b₂.items) ∧
  P.biUnion (fun b => b.items) = I
See it in the graphDiscuss this resultChallenge it