timelyItemToTuple_injective
The mapping timelyItemToTuple from timely items to lexicographically ordered tuples ℝ ×ₗ ℕ ×ₗ ℝ ×ₗ ℝ is injective.
Statement
theorem timelyItemToTuple_injective : Function.Injective timelyItemToTuple- Source
- folklore
- Verified
- 10 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- timelyItemToTupleThe tuple representation
timelyItemToTuplemapping each timely itempto the lexicographically ordered tuple… - TimelyItemA structure
TimelyItemrepresenting an item in online timely bin packing, with fieldsid : ℕ(a unique natural identifier),…
- timelyItemToTupleThe tuple representation
Read back from the Lean
The function timelyItemToTuple (which maps each TimelyItem p to the 4-tuple (p.deadline, p.id, p.arrival, p.size) in ℝ ×ₗ ℕ ×ₗ ℝ ×ₗ ℝ) is injective.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
To prove that timelyItemToTuple is injective, we assume two timely items p and q map to the same tuple. Deconstructing both items into their four constituent fields and unfolding the definition of timelyItemToTuple reduces the assumption to the equality of two 4-tuples. Since two tuples are equal only when all their components are equal, the corresponding fields of p and q coincide, showing p = q.
Let p and q be two timely items given by their fields (id1, arr1, dl1, sz1) and (id2, arr2, dl2, sz2); to show injectivity, assume timelyItemToTuple p = timelyItemToTuple q and show p = q.
By the definition of injectivity, we assume that p and q have identical images under timelyItemToTuple. Deconstructing both timely items into their constructor mk reveals their four constituent fields: identifier, arrival time, deadline, and size.
intro p q h cases p with | mk id1 arr1 dl1 sz1 => cases q with | mk id2 arr2 dl2 sz2 =>
The equality of the images becomes (dl1, id1, arr1, sz1) = (dl2, id2, arr2, sz2).
Unfolding the definition of timelyItemToTuple simplifies the assumption to the equality of the two 4-tuples formed by the items' deadlines, identifiers, arrival times, and sizes.
uses
timelyItemToTuplesimp only [timelyItemToTuple] at h
p = q
Equality between the two tuples implies that their corresponding components are equal (dl1 = dl2, id1 = id2, arr1 = arr2, and sz1 = sz2). Decomposing this equality substitutes the fields of q with those of p, making both items identical by reflexivity.
cases h rfl
timelyItemToTuple- maps a timely item p to the lexicographically ordered 4-tuple (p.deadline, p.id, p.arrival, p.size)
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.
/-- Injectivity of timelyItemToTuple. -/theorem timelyItemToTuple_injective : Function.Injective timelyItemToTuple := by intro p q h cases p with | mk id1 arr1 dl1 sz1 => cases q with | mk id2 arr2 dl2 sz2 => simp only [timelyItemToTuple] at h cases h rfl