AFTD Auto-Formalizing Theoretical Domains

timelyItemToTuple_injective

theoremverified

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 timelyItemToTuple mapping each timely item p to the lexicographically ordered tuple…
  • TimelyItemA structure TimelyItem representing an item in online timely bin packing, with fields id : ℕ (a unique natural identifier),…

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.

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

    lines 3–7

      intro p q h
      cases p with
      | mk id1 arr1 dl1 sz1 =>
      cases q with
      | mk id2 arr2 dl2 sz2 =>
  2. 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.

    line 8

    uses timelyItemToTuple

      simp only [timelyItemToTuple] at h
  3. 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.

    lines 9–10

      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

/-- 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
See it in the graphDiscuss this resultChallenge it