AFTD Auto-Formalizing Theoretical Domains

prioritized_borel_record_injective

theoremverified

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

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.

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

    lines 7–8

    uses prioritized_borel_record_replay

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

    lines 9–10

      rw [hlen, hrecord] at hx'
      have h := hx'.symm.trans hy'
  3. 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.

    line 11

    uses List.append_cancel_left, congrArg, Prod.fst, Option.some.inj

      exact 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

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