prioritized_borel_reverse_edge_deterministic_positional
If the current node and target state uniquely determine the previous state, and the node, source state, direction and target state uniquely determine each edge priority, then any winning strategy can be replaced by a positional one. The state space and memory type may be arbitrary.
Statement
theorem prioritized_borel_reverse_edge_deterministic_positional {Q : Type} {k : ℕ} (G : PrioritizedBorelGame Q k) (pl : BorelGamePlayer) (M : Type) (σ : FiniteMemoryStrategy G pl M) (hwin : PrioritizedBorelStrategyWins G pl σ) (hreverse : ∀ e ∈ G.edges, ∀ e' ∈ G.edges, e.source_node = e'.source_node → e.dir = e'.dir → e.target_state = e'.target_state → e.source_state = e'.source_state) (hpriority : ∀ e ∈ G.edges, ∀ e' ∈ G.edges, e.source_node = e'.source_node → e.source_state = e'.source_state → e.dir = e'.dir → e.target_state = e'.target_state → e.prio = e'.prio) : ∃ τ : FiniteMemoryStrategy G pl Unit, PrioritizedBorelStrategyWins G pl τ
- Related work
- Reverse edge-history reconstruction related to arXiv:2611.10136, Conjecture 19.
- Verified
- 14 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- PrioritizedBorelGameA structure PrioritizedBorelGame (Q : Type*) (k : ℕ) representing a prioritized Borel game with state space Q and k priorities, with…
- FiniteMemoryStrategyA structure FiniteMemoryStrategy {Q : Type*} {k : ℕ} (G : PrioritizedBorelGame Q k) (pl : BorelGamePlayer) (M : Type*) representing a…
- PrioritizedBorelStrategyWinsA strategy wins for its player if every legal play from the initial position consistent with its memory update and choices is won by that…
- TreeGameEdgeA structure TreeGameEdge (Q : Type*) (k : ℕ) representing an edge in a binary tree game arena with state space Q and k priorities, with…
- BorelGamePlayerThe two players in a prioritized Borel game, Eve and Adam.
- prioritized_borel_reverse_state_histories_uniqueIf a tree-game edge is reverse-deterministic in the state at each fixed parent node and child direction, then at most one state history…
Read back from the Lean
Given a type Q, a natural number k, a prioritized Borel game G over Q with k priorities, a player pl (Eve or Adam), an arbitrary memory type M, and a strategy σ with memory type M for player pl in G, assume:
1. σ is a winning strategy for pl in G (PrioritizedBorelStrategyWins G pl σ).
2. Reverse edge determinism (hreverse): for any two edges e, e' ∈ G.edges, if e.source_node = e'.source_node, e.dir = e'.dir, and e.target_state = e'.target_state, then e.source_state = e'.source_state.
3. Priority determinism (hpriority): for any two edges e, e' ∈ G.edges, if e.source_node = e'.source_node, e.source_state = e'.source_state, e.dir = e'.dir, and e.target_state = e'.target_state, then e.prio = e'.prio.
Then there exists a strategy τ for player pl with memory type Unit (i.e. with trivial internal memory) that is also a winning strategy for pl in G (PrioritizedBorelStrategyWins G pl τ).
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
Under reverse edge determinism and priority determinism, the history of any legal play leading to a node and state is uniquely determined. Therefore, the memory state of any finite-memory winning strategy can be statically reconstructed from the current vertex alone. Replacing the strategy's memory with this reconstructed memory yields a memoryless (positional) winning strategy.
Node length is n
By induction on n. In the base case, the node at step 0 is the empty list by node_zero, which has length 0. In the inductive step, appending the chosen direction increases the length by 1.
uses
List.length_appendintro n induction n with | zero => rw [hp.node_zero]; rfl | succ n ih => rw [(hp.step n).1, List.length_append, ih]; rfl
Prefix of node
By induction on n. For m <= n, taking m elements from the node at step n+1 reduces to taking m from the node at step n because m <= n, and for m = n+1 it takes the entire list.
uses
Nat.lt_or_ge,List.take_append,List.take_zero,List.append_nil,prioritized_borel_reverse_edge_deterministic_positional_node_length,List.take_of_length_le,le_of_eqintro n induction n with | zero => intro m hm have hm0 : m = 0 := by omega subst hm0 rw [hp.node_zero] rfl | succ n ih => intro m hm rcases Nat.lt_or_ge m (n+1) with hlt | hge · have hm' : m ≤ n := by omega rw [(hp.step n).1, List.take_append] have hzero : m - (p n).source_node.length = 0 := by rw [prioritized_borel_reverse_edge_deterministic_positional_node_length hp n]; omega rw [hzero, List.take_zero, List.append_nil] exact ih m hm' · have hm2 : m = n + 1 := by omega subst hm2 exact List.take_of_length_le (le_of_eq (prioritized_borel_reverse_edge_deterministic_positional_node_length hp (n+1)))
Agreement of plays
By backwards induction on the distance j = n - i from the current step n down to 0. At step n the states match by hypothesis. For the step from i+1 down to i, tree structure ensures the source nodes and directions match, and the inductive hypothesis gives matching target states. Determinism hypotheses then uniquely determine the source state and the priority.
uses
prioritized_borel_reverse_edge_deterministic_positional_take,List.append_cancel_left,TreeGameEdge.mk.injEqhave key : ∀ j i, n - i = j → i ≤ n → ((p i).source_state = (p' i).source_state ∧ (i < n → p i = p' i)) := by intro j induction j with | zero => intro i hi hj have hin : i = n := by omega subst hin refine ⟨hstate, ?_⟩ omega | succ j ih => intro i hi hj have hin : i < n := by omega have hrec : n - (i+1) = j := by omega have hIH := (ih (i+1) hrec (by omega)).1 have hsn : (p i).source_node = (p' i).source_node := by rw [← prioritized_borel_reverse_edge_deterministic_positional_take hp n i (by omega), ← prioritized_borel_reverse_edge_deterministic_positional_take hp' n i (by omega), hnode] have hdir : (p i).dir = (p' i).dir := by have e1 : (p i).source_node ++ [(p i).dir] = (p' i).source_node ++ [(p' i).dir] := by rw [← (hp.step i).1, ← (hp'.step i).1, ← prioritized_borel_reverse_edge_deterministic_positional_take hp n (i+1) (by omega), ← prioritized_borel_reverse_edge_deterministic_positional_take hp' n (i+1) (by omega), hnode] rw [hsn] at e1 simpa using List.append_cancel_left e1 have htgt : (p i).target_state = (p' i).target_state := by rw [← (hp.step i).2, ← (hp'.step i).2] exact hIH have hsrc : (p i).source_state = (p' i).source_state := hreverse (p i) (hp.edge i) (p' i) (hp'.edge i) hsn hdir htgt have hprio : (p i).prio = (p' i).prio := hpriority (p i) (hp.edge i) (p' i) (hp'.edge i) hsn hsrc hdir htgt refine ⟨hsrc, ?_⟩ intro _ have h1 : p i = ⟨(p i).source_node, (p i).source_state, (p i).dir, (p i).prio, (p i).target_state⟩ := rfl have h2 : p' i = ⟨(p' i).source_node, (p' i).source_state, (p' i).dir, (p' i).prio, (p' i).target_state⟩ := rfl rw [h1, h2, TreeGameEdge.mk.injEq] exact ⟨hsn, hsrc, hdir, hprio, htgt⟩ exact ⟨fun i hi => (key (n - i) i rfl hi).1, fun i hi => (key (n - i) i rfl (by omega)).2 hi⟩
Congruence of memory sequences
By induction on n. If the two plays agree on all edges before n+1, by induction they have the same memory state at step n, and since the n-th edges also agree, the updated memory states at step n+1 coincide.
intro n induction n with | zero => intro _; rfl | succ n ih => intro h show σ.update (prioritized_borel_reverse_edge_deterministic_positional_memseq σ p n) (p n) = σ.update (prioritized_borel_reverse_edge_deterministic_positional_memseq σ p' n) (p' n) rw [ih (fun i hi => h i (by omega)), h n (by omega)]
Index congruence
Substituting the equality m1 = m2 allows direct application of memseq_congr.
uses
prioritized_borel_reverse_edge_deterministic_positional_memseq_congrsubst hm exact prioritized_borel_reverse_edge_deterministic_positional_memseq_congr σ m₁ hp
Positional memory definition
We choose a witness play reaching the position (v, q) if one exists and evaluate the memory sequence along that play, otherwise falling back to the initial memory.
uses
prioritized_borel_reverse_edge_deterministic_positional_memseq,Classical.chooseclassical exact if h : ∃ p : ℕ → TreeGameEdge Q k, prioritized_borel_reverse_edge_deterministic_positional_legal G p ∧ (p v.length).source_node = v ∧ (p v.length).source_state = q then prioritized_borel_reverse_edge_deterministic_positional_memseq σ (Classical.choose h) v.length
Positional memory specification
For any legal play reaching (v, q) at step n, any other legal play reaching the same node and state must agree on all previous edges by the agreement lemma, hence produces the same memory state.
uses
prioritized_borel_reverse_edge_deterministic_positional_node_length,prioritized_borel_reverse_edge_deterministic_positional_posmem,dif_pos,prioritized_borel_reverse_edge_deterministic_positional_memseq_index_congr,Classical.choose_spec,prioritized_borel_reverse_edge_deterministic_positional_agreeclassical have hlen : (p n).source_node.length = n := prioritized_borel_reverse_edge_deterministic_positional_node_length hp n have hex : ∃ p' : ℕ → TreeGameEdge Q k, prioritized_borel_reverse_edge_deterministic_positional_legal G p' ∧ (p' (p n).source_node.length).source_node = (p n).source_node ∧ (p' (p n).source_node.length).source_state = (p n).source_state := by refine ⟨p, hp, ?_, ?_⟩ <;> rw [hlen] rw [prioritized_borel_reverse_edge_deterministic_positional_posmem] rw [dif_pos hex] refine prioritized_borel_reverse_edge_deterministic_positional_memseq_index_congr σ hlen.symm (fun i hi => ?_) obtain ⟨hleg, hnd, hst⟩ := Classical.choose_spec hex have hpeq : p (p n).source_node.length = p n := by rw [prioritized_borel_reverse_edge_deterministic_positional_node_length hp n] have hnd2 : (p (p n).source_node.length).source_node = (Classical.choose hex (p n).source_node.length).source_node := by rw [hpeq]; exact hnd.symm have hst2 : (p (p n).source_node.length).source_state = (Classical.choose hex (p n).source_node.length).source_state := by rw [hpeq]; exact hst.symm exact (prioritized_borel_reverse_edge_deterministic_positional_agree hreverse hpriority hp hleg (p n).source_node.length hnd2 hst2).2 i (by omega)
Positional strategy construction and win
We construct the positional strategy tau using Unit memory by evaluating sigma on the reconstructed memory at each position. Any play consistent with tau induces the exact same memory sequence for sigma, so sigma would make the identical choices. Since sigma wins, tau also wins.
uses
dif_pos,prioritized_borel_reverse_edge_deterministic_positional_posmem_specclassical let τ : FiniteMemoryStrategy G pl Unit := { init_mem := () update := fun _ _ => () choice := fun _ v q => if h : G.owner (v, q) = pl then σ.choice (prioritized_borel_reverse_edge_deterministic_positional_posmem σ v q) v q else Classical.choose (G.edges_outgoing v q) choice_edge := by intro m v q hq rw [dif_pos hq] exact σ.choice_edge _ v q hq } have hτchoice : ∀ (m : Unit) (v : List Bool) (q : Q), τ.choice m v q = if h : G.owner (v, q) = pl then σ.choice (prioritized_borel_reverse_edge_deterministic_positional_posmem σ v q) v q else Classical.choose (G.edges_outgoing v q) := fun _ _ _ => rfl have hkey : ∀ (play : ℕ → TreeGameEdge Q k), (∀ n, play n ∈ G.edges) → (play 0).source_node = [] → (∀ n, (play (n+1)).source_node = (play n).source_node ++ [(play n).dir] ∧ (play (n+1)).source_state = (play n).target_state) → (∃ (mτ : ℕ → Unit), mτ 0 = τ.init_mem ∧ (∀ n, mτ (n+1) = τ.update (mτ n) (play n)) ∧ ∀ n, G.owner ((play n).source_node, (play n).source_state) = pl → play n = τ.choice (mτ n) (play n).source_node (play n).source_state) → ∃ (mem : ℕ → M), mem 0 = σ.init_mem ∧ (∀ n, mem (n+1) = σ.update (mem n) (play n)) ∧ ∀ n, G.owner ((play n).source_node, (play n).source_state) = pl → play n = σ.choice (mem n) (play n).source_node (play n).source_state := by intro play hedge hinit hsucc hconsist obtain ⟨mτ, -, -, hmchoice⟩ := hconsist have hpl : prioritized_borel_reverse_edge_deterministic_positional_legal G play := ⟨hedge, hinit, hsucc⟩ refine ⟨fun n => prioritized_borel_reverse_edge_deterministic_positional_memseq σ play n, rfl, fun n => rfl, ?_⟩ intro n hn have h1 : play n = τ.choice (mτ n) (play n).source_node (play n).source_state := hmchoice n hn have hτc : τ.choice (mτ n) (play n).source_node (play n).source_state = σ.choice (prioritized_borel_reverse_edge_deterministic_positional_memseq σ play n) (play n).source_node (play n).source_state := by rw [hτchoice (mτ n) (play n).source_node (play n).source_state, dif_pos hn, ← prioritized_borel_reverse_edge_deterministic_positional_posmem_spec hreverse hpriority σ hpl n] exact h1.trans hτc refine ⟨τ, ?_⟩ intro play hedge hinit hsucc hconsist have hwit := hkey play hedge hinit.1 hsucc hconsist cases pl with | Eve => exact hwin play hedge hinit hsucc hwit | Adam => exact hwin play hedge hinit hsucc hwit
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.
/-- A legal play prefix: all edges are in the arena, it starts at the empty node, and successive edges are linked by the tree structure. -/structure prioritized_borel_reverse_edge_deterministic_positional_legal {Q : Type} {k : ℕ} (G : PrioritizedBorelGame Q k) (p : ℕ → TreeGameEdge Q k) : Prop where edge : ∀ n, p n ∈ G.edges node_zero : (p 0).source_node = [] step : ∀ n, (p (n+1)).source_node = (p n).source_node ++ [(p n).dir] ∧ (p (n+1)).source_state = (p n).target_state/-- The node of step `n` of a legal play has length `n`. -/lemma prioritized_borel_reverse_edge_deterministic_positional_node_length {Q : Type} {k : ℕ} {G : PrioritizedBorelGame Q k} {p : ℕ → TreeGameEdge Q k} (hp : prioritized_borel_reverse_edge_deterministic_positional_legal G p) : ∀ n, (p n).source_node.length = n := by intro n induction n with | zero => rw [hp.node_zero]; rfl | succ n ih => rw [(hp.step n).1, List.length_append, ih]; rfl/-- The node at step `n` of a legal play restricts to the node at any earlier step. -/lemma prioritized_borel_reverse_edge_deterministic_positional_take {Q : Type} {k : ℕ} {G : PrioritizedBorelGame Q k} {p : ℕ → TreeGameEdge Q k} (hp : prioritized_borel_reverse_edge_deterministic_positional_legal G p) : ∀ (n m : ℕ), m ≤ n → (p n).source_node.take m = (p m).source_node := by intro n induction n with | zero => intro m hm have hm0 : m = 0 := by omega subst hm0 rw [hp.node_zero] rfl | succ n ih => intro m hm rcases Nat.lt_or_ge m (n+1) with hlt | hge · have hm' : m ≤ n := by omega rw [(hp.step n).1, List.take_append] have hzero : m - (p n).source_node.length = 0 := by rw [prioritized_borel_reverse_edge_deterministic_positional_node_length hp n]; omega rw [hzero, List.take_zero, List.append_nil] exact ih m hm' · have hm2 : m = n + 1 := by omega subst hm2 exact List.take_of_length_le (le_of_eq (prioritized_borel_reverse_edge_deterministic_positional_node_length hp (n+1)))/-- Two legal plays that agree on node and state at step `n` agree on every state up to `n` and on every edge before `n`. -/lemma prioritized_borel_reverse_edge_deterministic_positional_agree {Q : Type} {k : ℕ} {G : PrioritizedBorelGame Q k} (hreverse : ∀ e ∈ G.edges, ∀ e' ∈ G.edges, e.source_node = e'.source_node → e.dir = e'.dir → e.target_state = e'.target_state → e.source_state = e'.source_state) (hpriority : ∀ e ∈ G.edges, ∀ e' ∈ G.edges, e.source_node = e'.source_node → e.source_state = e'.source_state → e.dir = e'.dir → e.target_state = e'.target_state → e.prio = e'.prio) {p p' : ℕ → TreeGameEdge Q k} (hp : prioritized_borel_reverse_edge_deterministic_positional_legal G p) (hp' : prioritized_borel_reverse_edge_deterministic_positional_legal G p') (n : ℕ) (hnode : (p n).source_node = (p' n).source_node) (hstate : (p n).source_state = (p' n).source_state) : (∀ i, i ≤ n → (p i).source_state = (p' i).source_state) ∧ (∀ i, i < n → p i = p' i) := by have key : ∀ j i, n - i = j → i ≤ n → ((p i).source_state = (p' i).source_state ∧ (i < n → p i = p' i)) := by intro j induction j with | zero => intro i hi hj have hin : i = n := by omega subst hin refine ⟨hstate, ?_⟩ omega | succ j ih => intro i hi hj have hin : i < n := by omega have hrec : n - (i+1) = j := by omega have hIH := (ih (i+1) hrec (by omega)).1 have hsn : (p i).source_node = (p' i).source_node := by rw [← prioritized_borel_reverse_edge_deterministic_positional_take hp n i (by omega), ← prioritized_borel_reverse_edge_deterministic_positional_take hp' n i (by omega), hnode] have hdir : (p i).dir = (p' i).dir := by have e1 : (p i).source_node ++ [(p i).dir] = (p' i).source_node ++ [(p' i).dir] := by rw [← (hp.step i).1, ← (hp'.step i).1, ← prioritized_borel_reverse_edge_deterministic_positional_take hp n (i+1) (by omega), ← prioritized_borel_reverse_edge_deterministic_positional_take hp' n (i+1) (by omega), hnode] rw [hsn] at e1 simpa using List.append_cancel_left e1 have htgt : (p i).target_state = (p' i).target_state := by rw [← (hp.step i).2, ← (hp'.step i).2] exact hIH have hsrc : (p i).source_state = (p' i).source_state := hreverse (p i) (hp.edge i) (p' i) (hp'.edge i) hsn hdir htgt have hprio : (p i).prio = (p' i).prio := hpriority (p i) (hp.edge i) (p' i) (hp'.edge i) hsn hsrc hdir htgt refine ⟨hsrc, ?_⟩ intro _ have h1 : p i = ⟨(p i).source_node, (p i).source_state, (p i).dir, (p i).prio, (p i).target_state⟩ := rfl have h2 : p' i = ⟨(p' i).source_node, (p' i).source_state, (p' i).dir, (p' i).prio, (p' i).target_state⟩ := rfl rw [h1, h2, TreeGameEdge.mk.injEq] exact ⟨hsn, hsrc, hdir, hprio, htgt⟩ exact ⟨fun i hi => (key (n - i) i rfl hi).1, fun i hi => (key (n - i) i rfl (by omega)).2 hi⟩/-- The memory of `σ` after the first `n` moves of a play. -/def prioritized_borel_reverse_edge_deterministic_positional_memseq {Q : Type} {k : ℕ} {G : PrioritizedBorelGame Q k} {pl : BorelGamePlayer} {M : Type} (σ : FiniteMemoryStrategy G pl M) (p : ℕ → TreeGameEdge Q k) (n : ℕ) : M := Nat.rec σ.init_mem (fun j ih => σ.update ih (p j)) n/-- Plays with the same first `n` edges induce the same memory after `n` moves. -/lemma prioritized_borel_reverse_edge_deterministic_positional_memseq_congr {Q : Type} {k : ℕ} {G : PrioritizedBorelGame Q k} {pl : BorelGamePlayer} {M : Type} (σ : FiniteMemoryStrategy G pl M) {p p' : ℕ → TreeGameEdge Q k} : ∀ (n : ℕ), (∀ i, i < n → p i = p' i) → prioritized_borel_reverse_edge_deterministic_positional_memseq σ p n = prioritized_borel_reverse_edge_deterministic_positional_memseq σ p' n := by intro n induction n with | zero => intro _; rfl | succ n ih => intro h show σ.update (prioritized_borel_reverse_edge_deterministic_positional_memseq σ p n) (p n) = σ.update (prioritized_borel_reverse_edge_deterministic_positional_memseq σ p' n) (p' n) rw [ih (fun i hi => h i (by omega)), h n (by omega)]/-- Version of `memseq_congr` allowing the two step indices to differ by an equation. -/lemma prioritized_borel_reverse_edge_deterministic_positional_memseq_index_congr {Q : Type} {k : ℕ} {G : PrioritizedBorelGame Q k} {pl : BorelGamePlayer} {M : Type} (σ : FiniteMemoryStrategy G pl M) {p p' : ℕ → TreeGameEdge Q k} {m₁ m₂ : ℕ} (hm : m₁ = m₂) (hp : ∀ i, i < m₁ → p i = p' i) : prioritized_borel_reverse_edge_deterministic_positional_memseq σ p m₁ = prioritized_borel_reverse_edge_deterministic_positional_memseq σ p' m₂ := by subst hm exact prioritized_borel_reverse_edge_deterministic_positional_memseq_congr σ m₁ hp/-- The memory of `σ` at a position, reconstructed from a legal play reaching that position. -/noncomputable def prioritized_borel_reverse_edge_deterministic_positional_posmem {Q : Type} {k : ℕ} {G : PrioritizedBorelGame Q k} {pl : BorelGamePlayer} {M : Type} (σ : FiniteMemoryStrategy G pl M) (v : List Bool) (q : Q) : M := by classical exact if h : ∃ p : ℕ → TreeGameEdge Q k, prioritized_borel_reverse_edge_deterministic_positional_legal G p ∧ (p v.length).source_node = v ∧ (p v.length).source_state = q then prioritized_borel_reverse_edge_deterministic_positional_memseq σ (Classical.choose h) v.length else σ.init_mem/-- At any position actually reached by a legal play, the reconstructed memory is the memory of `σ` along that play. -/lemma prioritized_borel_reverse_edge_deterministic_positional_posmem_spec {Q : Type} {k : ℕ} {G : PrioritizedBorelGame Q k} {pl : BorelGamePlayer} {M : Type} (hreverse : ∀ e ∈ G.edges, ∀ e' ∈ G.edges, e.source_node = e'.source_node → e.dir = e'.dir → e.target_state = e'.target_state → e.source_state = e'.source_state) (hpriority : ∀ e ∈ G.edges, ∀ e' ∈ G.edges, e.source_node = e'.source_node → e.source_state = e'.source_state → e.dir = e'.dir → e.target_state = e'.target_state → e.prio = e'.prio) (σ : FiniteMemoryStrategy G pl M) {p : ℕ → TreeGameEdge Q k} (hp : prioritized_borel_reverse_edge_deterministic_positional_legal G p) (n : ℕ) : prioritized_borel_reverse_edge_deterministic_positional_memseq σ p n = prioritized_borel_reverse_edge_deterministic_positional_posmem σ (p n).source_node (p n).source_state := by classical have hlen : (p n).source_node.length = n := prioritized_borel_reverse_edge_deterministic_positional_node_length hp n have hex : ∃ p' : ℕ → TreeGameEdge Q k, prioritized_borel_reverse_edge_deterministic_positional_legal G p' ∧ (p' (p n).source_node.length).source_node = (p n).source_node ∧ (p' (p n).source_node.length).source_state = (p n).source_state := by refine ⟨p, hp, ?_, ?_⟩ <;> rw [hlen] rw [prioritized_borel_reverse_edge_deterministic_positional_posmem] rw [dif_pos hex] refine prioritized_borel_reverse_edge_deterministic_positional_memseq_index_congr σ hlen.symm (fun i hi => ?_) obtain ⟨hleg, hnd, hst⟩ := Classical.choose_spec hex have hpeq : p (p n).source_node.length = p n := by rw [prioritized_borel_reverse_edge_deterministic_positional_node_length hp n] have hnd2 : (p (p n).source_node.length).source_node = (Classical.choose hex (p n).source_node.length).source_node := by rw [hpeq]; exact hnd.symm have hst2 : (p (p n).source_node.length).source_state = (Classical.choose hex (p n).source_node.length).source_state := by rw [hpeq]; exact hst.symm exact (prioritized_borel_reverse_edge_deterministic_positional_agree hreverse hpriority hp hleg (p n).source_node.length hnd2 hst2).2 i (by omega)theorem prioritized_borel_reverse_edge_deterministic_positional {Q : Type} {k : ℕ} (G : PrioritizedBorelGame Q k) (pl : BorelGamePlayer) (M : Type) (σ : FiniteMemoryStrategy G pl M) (hwin : PrioritizedBorelStrategyWins G pl σ) (hreverse : ∀ e ∈ G.edges, ∀ e' ∈ G.edges, e.source_node = e'.source_node → e.dir = e'.dir → e.target_state = e'.target_state → e.source_state = e'.source_state) (hpriority : ∀ e ∈ G.edges, ∀ e' ∈ G.edges, e.source_node = e'.source_node → e.source_state = e'.source_state → e.dir = e'.dir → e.target_state = e'.target_state → e.prio = e'.prio) : ∃ τ : FiniteMemoryStrategy G pl Unit, PrioritizedBorelStrategyWins G pl τ := by classical let τ : FiniteMemoryStrategy G pl Unit := { init_mem := () update := fun _ _ => () choice := fun _ v q => if h : G.owner (v, q) = pl then σ.choice (prioritized_borel_reverse_edge_deterministic_positional_posmem σ v q) v q else Classical.choose (G.edges_outgoing v q) choice_edge := by intro m v q hq rw [dif_pos hq] exact σ.choice_edge _ v q hq } have hτchoice : ∀ (m : Unit) (v : List Bool) (q : Q), τ.choice m v q = if h : G.owner (v, q) = pl then σ.choice (prioritized_borel_reverse_edge_deterministic_positional_posmem σ v q) v q else Classical.choose (G.edges_outgoing v q) := fun _ _ _ => rfl have hkey : ∀ (play : ℕ → TreeGameEdge Q k), (∀ n, play n ∈ G.edges) → (play 0).source_node = [] → (∀ n, (play (n+1)).source_node = (play n).source_node ++ [(play n).dir] ∧ (play (n+1)).source_state = (play n).target_state) → (∃ (mτ : ℕ → Unit), mτ 0 = τ.init_mem ∧ (∀ n, mτ (n+1) = τ.update (mτ n) (play n)) ∧ ∀ n, G.owner ((play n).source_node, (play n).source_state) = pl → play n = τ.choice (mτ n) (play n).source_node (play n).source_state) → ∃ (mem : ℕ → M), mem 0 = σ.init_mem ∧ (∀ n, mem (n+1) = σ.update (mem n) (play n)) ∧ ∀ n, G.owner ((play n).source_node, (play n).source_state) = pl → play n = σ.choice (mem n) (play n).source_node (play n).source_state := by intro play hedge hinit hsucc hconsist obtain ⟨mτ, -, -, hmchoice⟩ := hconsist have hpl : prioritized_borel_reverse_edge_deterministic_positional_legal G play := ⟨hedge, hinit, hsucc⟩ refine ⟨fun n => prioritized_borel_reverse_edge_deterministic_positional_memseq σ play n, rfl, fun n => rfl, ?_⟩ intro n hn have h1 : play n = τ.choice (mτ n) (play n).source_node (play n).source_state := hmchoice n hn have hτc : τ.choice (mτ n) (play n).source_node (play n).source_state = σ.choice (prioritized_borel_reverse_edge_deterministic_positional_memseq σ play n) (play n).source_node (play n).source_state := by rw [hτchoice (mτ n) (play n).source_node (play n).source_state, dif_pos hn, ← prioritized_borel_reverse_edge_deterministic_positional_posmem_spec hreverse hpriority σ hpl n] exact h1.trans hτc refine ⟨τ, ?_⟩ intro play hedge hinit hsucc hconsist have hwit := hkey play hedge hinit.1 hsucc hconsist cases pl with | Eve => exact hwin play hedge hinit hsucc hwit | Adam => exact hwin play hedge hinit hsucc hwit