picking_prefix_state_update_of_not_mem_take
Changing agent i's ranking does not change the state of a picking sequence after the first t turns if agent i does not pick in those turns.
Statement
theorem picking_prefix_state_update_of_not_mem_take {N G : Type*} [DecidableEq N] [DecidableEq G] {m : ℕ} (seq : List N) (rank : N → Fin m ≃ G) (i : N) (r : Fin m ≃ G) (t : ℕ) (h : i ∉ seq.take t) : picking_prefix_state seq (Function.update rank i r) t = picking_prefix_state seq rank t
- Source
- step for round_robin_two_mul_add_one_deviation_certificate (research thread RT-3)
- Verified
- 21 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- picking_prefix_stateThe state of a picking-sequence run after its first s turns: the bundle map together with the set of already allocated items, obtained by…
- picking_turnOne turn of a picking-sequence mechanism: the active agent i receives the first good of its reported ranking l (best first) that is not…
- Used by 4
- picking_sequence_outcome_update_mem_of_first_freeIn a picking-sequence run, if agent i's first turn is turn t and the good g that i's new report r ranks first is still unallocated after…
- picking_prefix_two_named_first_dev_bundleIn a picking sequence with at most as many turns as goods, suppose agent i acts at turns t1 < t2 and nowhere in between, x is unallocated…
- round_robin_two_mul_add_one_cover_pairsRound-Robin with n agents and 2n+1 goods, agent i ≠ 0: let a1 be agent 0's top-ranked good, a2 and a3 the goods it picks at turns n and…
- round_robin_two_mul_add_one_window_traceRound-Robin with n agents and 2n+1 goods: change only agent i's report to r. Then at every time s between i's first turn and i's second…
The proof, explained
The prefix state after t turns is computed as a left fold over the first t agents in the sequence. Since agent i is assumed not to appear in this prefix, every agent who picks during these turns is distinct from i. Consequently, modifying agent i's ranking does not affect any turn's ranking, and the equality of the overall folded state follows by extensionality of foldl (`List.foldl_ext`).
It suffices to show that for any state and any agent appearing in the prefix of the sequence, the picking transition function is the same under both ranking functions.
By definition, `picking_prefix_state` is computed by folding `picking_turn` across the prefix `seq.take t` starting from the empty allocation state. By `List.foldl_ext`, two folds produce identical outcomes if their step functions agree for every element in the list and every accumulator state. Introducing an arbitrary state `st`, an agent `a`, and the membership assumption `ha : a ∈ seq.take t` leaves this step-wise equality as the goal.
uses
List.foldl_extunfold picking_prefix_state apply List.foldl_ext intro st a ha
The agent a is not equal to i.
Suppose, for contradiction, that a = i. Then the assumption that a is in the prefix (`ha`) means i ∈ seq.take t, which directly contradicts the hypothesis h that i does not appear in seq.take t.
have hne : a ≠ i := by rintro rfl exact h ha
The picking transition at agent a with the updated ranking is identical to the transition with the original ranking.
Since a ≠ i, updating rank at i does not change its evaluation at a (`Function.update_of_ne`). Rewriting with this identity substitutes `rank a` for `Function.update rank i r a`, making both sides of the equation identical and completing the proof.
uses
Function.update_of_nerw [Function.update_of_ne hne]
List.foldl_ext- Two left folds over the same list starting from the same accumulator yield the same result if their step functions produce identical outputs on every element in the list.
Function.update_of_ne- Updating a function at a point a' does not change its value at any distinct input a ≠ a'.
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.
theorem picking_prefix_state_update_of_not_mem_take {N G : Type*} [DecidableEq N] [DecidableEq G] {m : ℕ} (seq : List N) (rank : N → Fin m ≃ G) (i : N) (r : Fin m ≃ G) (t : ℕ) (h : i ∉ seq.take t) : picking_prefix_state seq (Function.update rank i r) t = picking_prefix_state seq rank t := by unfold picking_prefix_state apply List.foldl_ext intro st a ha have hne : a ≠ i := by rintro rfl exact h ha rw [Function.update_of_ne hne]