temporal_target_state_table_sound
If a finite table of endpoint/target-set pairs contains the initial state and is closed under every legal temporal step, then every temporal walk has a table state whose set contains all targets it has visited.
Statement
theorem temporal_target_state_table_sound {n : ℕ} (G : ℕ → SimpleGraph (Fin n)) (U : Finset (Fin n)) (s : Fin n) (T : ℕ) (S : ℕ → Finset (Fin n × Finset (Fin n))) (M0 : Finset (Fin n)) (hinit : (s, M0) ∈ S 0) (hstart : s ∈ U → s ∈ M0) (hstep : ∀ t : Fin T, ∀ p ∈ S t.val, ∀ u : Fin n, u = p.1 ∨ (G t.val).Adj p.1 u → (u, if u ∈ U then insert u p.2 else p.2) ∈ S (t.val + 1)) (w : ℕ → Fin n) (hw0 : w 0 = s) (hw : is_temporal_walk G w) : ∃ M : Finset (Fin n), (w T, M) ∈ S T ∧ ∀ i ≤ T, w i ∈ U → w i ∈ M
- Source
- Finite invariant-table soundness lemma for certificates used in the OP-80 deep session, arXiv:2610.06228 Sec. 7.
- Verified
- 25 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- is_temporal_walkA temporal walk in a temporal graph (G_t)_t: at every time step t the agent either waits or traverses one edge of the snapshot G_t.
- Used by 2
- temporal_path_twelve_one_frame_target_trapThere is a temporal graph on twelve vertices, every snapshot a spanning path, such that every walk from vertex 0 visits at most one of the…
- temporal_path_five_requires_nineThere is a temporal graph on five vertices with spanning-path snapshots such that every walk from vertex 0 needs at least nine steps to…
The proof, explained
The proof proceeds by induction on time t ≤ T to show that at each step, there is a set M such that the pair (w t, M) belongs to the table S t and M contains all target vertices visited so far. At step 0, the initial condition ensures that (w 0, M0) is in S 0 and covers w 0 if it is a target. For the inductive step, the definition of a temporal walk guarantees that the transition from w t to w (t + 1) is a legal move, so the table's step-closure property yields a valid successor pair in S (t + 1) that accumulates any newly visited target. Evaluating this invariant at t = T completes the proof.
To prove the theorem, it suffices to show by induction on t that for all t ≤ T, there exists a target set M such that (w t, M) ∈ S t and M contains every target w i ∈ U visited at times i ≤ t.
We set up an inductive invariant strengthening the goal to all time steps t ≤ T, and begin induction on t.
have hinv : ∀ t ≤ T, ∃ M : Finset (Fin n), (w t, M) ∈ S t ∧ ∀ i ≤ t, w i ∈ U → w i ∈ M := by intro t induction t with
The invariant holds at the base step t = 0 using the initial target set M0.
At time 0, the walk is at w 0 = s, so (w 0, M0) ∈ S 0 by the initial condition hinit. Any index i ≤ 0 must equal 0, and if w 0 ∈ U, the hypothesis hstart ensures that w 0 = s ∈ M0.
| zero => intro ht refine ⟨M0, by simpa [hw0] using hinit, ?_⟩ intro i hi hui obtain rfl : i = 0 := by omega simpa [hw0] using hstart (by simpa [hw0] using hui)Given a valid state (w t, M) ∈ S t, updating M with w (t + 1) produces a valid successor state (w (t + 1), M') ∈ S (t + 1).
By the induction hypothesis at time t < T, there is a set M such that (w t, M) ∈ S t covering all targets visited through step t. We define M' by adding w (t + 1) to M if w (t + 1) ∈ U, and leaving M unchanged otherwise. Since w is a temporal walk, the step from w t to w (t + 1) is either stationary or along an edge of G t; thus the transition hypothesis hstep guarantees that (w (t + 1), M') ∈ S (t + 1).
| succ t ih => intro ht obtain ⟨M, hM, hcover⟩ := ih (by omega) let M' := if w (t + 1) ∈ U then insert (w (t + 1)) M else M refine ⟨M', hstep ⟨t, by omega⟩ (w t, M) hM (w (t + 1)) (hw t), ?_⟩The updated set M' contains all targets visited at earlier steps i ≤ t.
If i ≤ t and w i ∈ U, the induction hypothesis guarantees that w i ∈ M. When w (t + 1) ∈ U, M' is the insertion of w (t + 1) into M, which contains w i by Finset.mem_insert_of_mem; when w (t + 1) ∉ U, M' is simply M.
uses
Finset.mem_insert_of_memintro i hi hui by_cases h : i ≤ t · have hm := hcover i h hui dsimp [M'] split_ifs · exact Finset.mem_insert_of_mem hm · exact hm
The updated set M' contains the target visited at time t + 1 if w (t + 1) ∈ U.
If i is not at most t, then i = t + 1. Since w (t + 1) ∈ U, M' is defined by inserting w (t + 1) into M, which contains w (t + 1) directly.
· obtain rfl : i = t + 1 := by omega simp [M', hui]
The theorem holds at time T.
Specialising the inductive invariant to t = T using the reflexivity of ≤ (le_rfl) yields the desired target set M.
uses
le_rflexact hinv T le_rfl
Finset.mem_insert_of_mem- If an element belongs to a finite set, it also belongs to the set with another element inserted.
le_rfl- The inequality relation ≤ is reflexive (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 temporal_target_state_table_sound {n : ℕ} (G : ℕ → SimpleGraph (Fin n)) (U : Finset (Fin n)) (s : Fin n) (T : ℕ) (S : ℕ → Finset (Fin n × Finset (Fin n))) (M0 : Finset (Fin n)) (hinit : (s, M0) ∈ S 0) (hstart : s ∈ U → s ∈ M0) (hstep : ∀ t : Fin T, ∀ p ∈ S t.val, ∀ u : Fin n, u = p.1 ∨ (G t.val).Adj p.1 u → (u, if u ∈ U then insert u p.2 else p.2) ∈ S (t.val + 1)) (w : ℕ → Fin n) (hw0 : w 0 = s) (hw : is_temporal_walk G w) : ∃ M : Finset (Fin n), (w T, M) ∈ S T ∧ ∀ i ≤ T, w i ∈ U → w i ∈ M := by have hinv : ∀ t ≤ T, ∃ M : Finset (Fin n), (w t, M) ∈ S t ∧ ∀ i ≤ t, w i ∈ U → w i ∈ M := by intro t induction t with | zero => intro ht refine ⟨M0, by simpa [hw0] using hinit, ?_⟩ intro i hi hui obtain rfl : i = 0 := by omega simpa [hw0] using hstart (by simpa [hw0] using hui) | succ t ih => intro ht obtain ⟨M, hM, hcover⟩ := ih (by omega) let M' := if w (t + 1) ∈ U then insert (w (t + 1)) M else M refine ⟨M', hstep ⟨t, by omega⟩ (w t, M) hM (w (t + 1)) (hw t), ?_⟩ intro i hi hui by_cases h : i ≤ t · have hm := hcover i h hui dsimp [M'] split_ifs · exact Finset.mem_insert_of_mem hm · exact hm · obtain rfl : i = t + 1 := by omega simp [M', hui] exact hinv T le_rfl