prioritized_borel_record_injective
Compatible finite histories with equal length and equal records of opponent branching choices are identical.
Statement
theorem prioritized_borel_record_injective {A : Type} (own branch : List A → Bool) (policy forced : List A → A) (hist xs ys : List A) (hx : op1385Compatible own branch policy forced hist xs) (hy : op1385Compatible own branch policy forced hist ys) (hlen : xs.length = ys.length) (hrecord : op1385Record own branch hist xs = op1385Record own branch hist ys) : xs = ys
- Source
- Strategy reconstruction for arXiv:2611.10136, Conjecture 19.
- Verified
- 13 Nov 2026
- Axioms
propext- Built on 1
- prioritized_borel_record_replayA compatible finite history can be reconstructed from its length and the sequence of choices at opponent-controlled branching positions.
- Used by 1
- prioritized_borel_bounded_opponent_branching_compressionFix a winning strategy, possibly using infinite memory, in a finite-state prioritized tree game with k priorities. If along every legal…
The proof, explained
The proof reconstructs each history extension from its record and length using prioritized_borel_record_replay. Because the two extensions have equal lengths and identical records, deterministic replay yields identical results: some (hist ++ xs, []) = some (hist ++ ys, []). Extracting the first component of the pair and cancelling the common prefix hist concludes that xs = ys.
Replaying either extension from its recorded choices reconstructs the base history extended by that sequence.
By prioritized_borel_record_replay, because xs and ys are both compatible with the game policy (hypotheses hx and hy), simulating the game from hist using each sequence's record of opponent branching choices for its length reproduces the extended history: op1385Replay ... (record xs) xs.length = some (hist ++ xs, []) (saved as hx') and op1385Replay ... (record ys) ys.length = some (hist ++ ys, []) (saved as hy').
uses
prioritized_borel_record_replayhave hx' := prioritized_borel_record_replay own branch policy forced hist xs hx have hy' := prioritized_borel_record_replay own branch policy forced hist ys hy
The replay outputs for xs and ys coincide: some (hist ++ xs, []) = some (hist ++ ys, []).
Because xs and ys are assumed to have equal length (hlen) and equal records (hrecord), rewriting in hx' makes the left-hand side of hx' identical to that of hy'. By transitivity (hx'.symm.trans hy'), their right-hand sides are equal.
rw [hlen, hrecord] at hx' have h := hx'.symm.trans hy'
xs = ys
Stripping the some constructor using Option.some.inj yields (hist ++ xs, []) = (hist ++ ys, []). Projecting to the first component via congrArg Prod.fst gives hist ++ xs = hist ++ ys. Finally, cancelling the common prefix hist on the left with List.append_cancel_left concludes xs = ys.
uses
List.append_cancel_left,congrArg,Prod.fst,Option.some.injexact List.append_cancel_left (congrArg Prod.fst (Option.some.inj h))
prioritized_borel_record_replay- For any compatible history extension, replaying its recorded opponent branching choices for its length reconstructs the base history appended with that extension.
List.append_cancel_left- Left cancellation for list concatenation: if as ++ bs = as ++ cs, then bs = cs.
congrArg- Congruence for function application: if a₁ = a₂, then f a₁ = f a₂.
Prod.fst- The projection mapping an ordered pair (a, b) to its first component a.
Option.some.inj- Injectivity of the some constructor: if some v₁ = some v₂, then v₁ = v₂.
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 prioritized_borel_record_injective {A : Type} (own branch : List A → Bool) (policy forced : List A → A) (hist xs ys : List A) (hx : op1385Compatible own branch policy forced hist xs) (hy : op1385Compatible own branch policy forced hist ys) (hlen : xs.length = ys.length) (hrecord : op1385Record own branch hist xs = op1385Record own branch hist ys) : xs = ys := by have hx' := prioritized_borel_record_replay own branch policy forced hist xs hx have hy' := prioritized_borel_record_replay own branch policy forced hist ys hy rw [hlen, hrecord] at hx' have h := hx'.symm.trans hy' exact List.append_cancel_left (congrArg Prod.fst (Option.some.inj h))