AFTD Auto-Formalizing Theoretical Domains

temporal_target_state_table_sound

theoremverified

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

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.

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

    lines 11–14

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

    lines 15–20

        | 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)
  3. 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).

    lines 21–25

        | 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), ?_⟩
  4. 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.

    lines 26–32

    uses Finset.mem_insert_of_mem

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

    lines 33–34

          · obtain rfl : i = t + 1 := by omega
            simp [M', hui]
  6. 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.

    line 35

    uses le_rfl

      exact 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

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