AFTD Auto-Formalizing Theoretical Domains

temporal_path_twelve_one_frame_target_trap

theoremverifiedoriginal

There 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 four designated targets 8, 9, 10, 11 by time 11. This refutes the auxiliary one-frame half-target-coverage lemma from a prescribed start; it does not refute OP-80.

Statement

theorem temporal_path_twelve_one_frame_target_trap :
    ∃ G : ℕ → SimpleGraph (Fin 12),
      (∀ t, is_spanning_path_graph (G t)) ∧
      ∀ w : ℕ → Fin 12, w 0 = 0 → is_temporal_walk G w →
        ∃ M : Finset (Fin 12), M.card ≤ 1 ∧
          ∀ i ≤ 11, 8 ≤ (w i).val → w i ∈ M
Related work
OP-80, arXiv:2610.06228 Sec. 7. An explicit finite obstruction from this deep session; no asymptotic advance is claimed.
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • temporal_target_state_table_soundIf a finite table of endpoint/target-set pairs contains the initial state and is closed under every legal temporal step, then every…
  • is_spanning_path_graphA graph on n vertices is a spanning path if its vertices can be ordered so that exactly consecutive vertices are adjacent.
  • 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.

The proof, explained

The theorem is proved by constructing an explicit 12-vertex temporal graph where every snapshot is a spanning path, such that any temporal walk starting at vertex 0 visits at most one of the four targets {8, 9, 10, 11} by time 11. Each snapshot is obtained by pulling back the standard path graph along a time-dependent permutation that strategically delays access to higher-indexed vertices. An inductive reachability table, `twelveTable`, tracks reachable pairs of current locations and visited target sets, verified step by step using Lean's decision procedure `decide`. Finally, applying the general soundness lemma `temporal_target_state_table_sound` guarantees that the visited targets of any walk are contained in a final table state, which is verified to have size at most 1.

  1. The reachability table `twelveTable` is inductive: from any reachable state at time t < 11, any valid move or idle step in `twelveGraph t` yields a reachable state at time t + 1 with the visited target set correctly updated. automation

    We introduce the time parameter t : Fin 11 and perform an exhaustive case split into all 11 time steps (0 through 10) using `fin_cases`. For each case, we expand the definitions of `twelveTable`, `twelveGraph`, and path graph adjacency, converting the set membership and adjacency conditions into conjunctions of implications via `Finset.forall_mem_insert`, `Finset.mem_singleton`, `forall_eq`, `SimpleGraph.comap_adj`, and `SimpleGraph.pathGraph_adj`. Each conjunct is introduced with `And.intro` and verified by kernel computation via `decide`.

    lines 42–47

    uses Finset.forall_mem_insert, Finset.mem_singleton, forall_eq, SimpleGraph.comap_adj, SimpleGraph.pathGraph_adj, And.intro

      intro t
      fin_cases t <;>
        simp only [twelveTable, Finset.forall_mem_insert, Finset.mem_singleton, forall_eq] <;>
        simp only [twelveGraph, SimpleGraph.comap_adj, SimpleGraph.pathGraph_adj] <;>
        (repeat' apply And.intro) <;>
        decide
  2. Every reachable state (u, M) in the table at time 11 satisfies |M| ≤ 1. automation

    We unfold the definition of `twelveTable 11` using `Finset.forall_mem_insert`, `Finset.mem_singleton`, and `forall_eq`. This reduces the claim to verifying that each of the 21 explicitly listed target sets has cardinality at most 1, which `decide` checks by finite computation.

    lines 56–57

    uses Finset.forall_mem_insert, Finset.mem_singleton, forall_eq

      simp only [twelveTable, Finset.forall_mem_insert, Finset.mem_singleton, forall_eq]
      decide
  3. The candidate temporal graph `twelveGraph` has the property that each snapshot is a spanning path graph.

    We provide `twelveGraph` as the witness for the existential quantifier. For each time t, `twelveGraph t` is defined as the pullback of the standard 12-vertex path graph along the permutation `twelveOrder t`. Since pulling back a graph along a permutation preserves the graph structure up to isomorphism, `twelveOrder t` witnesses that `twelveGraph t` is a spanning path graph by definition of `SimpleGraph.pathGraph_adj`.

    lines 65–67

    uses SimpleGraph.pathGraph_adj

      refine ⟨twelveGraph, ?_, ?_⟩
      · intro t
        exact ⟨twelveOrder t, fun a b => SimpleGraph.pathGraph_adj⟩
  4. For any temporal walk w starting at 0, there exists a target set M such that (w(11), M) belongs to `twelveTable 11` and M contains every designated target visited by w up to time 11.

    We introduce the walk w, the start condition w(0) = 0, and the assumption that w is a temporal walk. Applying the soundness theorem `temporal_target_state_table_sound` with graph `twelveGraph`, target set `twelveTargets`, start vertex 0, horizon 11, table `twelveTable`, and initial target set ∅ produces the desired set M. The side conditions (0, ∅) ∈ `twelveTable 0` and 0 ∈ `twelveTargets` → 0 ∈ ∅ are discharged by `decide`, and the one-step induction hypothesis is provided by `twelveClosed`.

    lines 68–70

    uses temporal_target_state_table_sound, twelveClosed

      · intro w hw0 hw
        obtain ⟨M, hM, hcover⟩ :=
          temporal_target_state_table_sound twelveGraph twelveTargets 0 11 twelveTable ∅ (by decide) (by decide) twelveClosed w hw0 hw
  5. The set M of visited targets has |M| ≤ 1, and every target vertex with index at least 8 visited by w up to time 11 belongs to M, completing the theorem.

    We instantiate the existential goal with M. Its cardinality bound |M| ≤ 1 is given by `twelveCard` applied to the fact that (w(11), M) ∈ `twelveTable 11`. For any time step i ≤ 11 at which w(i) ≥ 8, the vertex belongs to `twelveTargets`, so the coverage guarantee from the soundness theorem ensures that w(i) ∈ M.

    lines 71–73

    uses twelveCard

        refine ⟨M, twelveCard (w 11, M) hM, ?_⟩
        intro i hi hui
        exact hcover i hi (by simpa [twelveTargets] using hui)
And.intro
From proofs of propositions A and B, constructs a proof of their conjunction A ∧ B.
Finset.forall_mem_insert
A property holds for every element of `insert a s` if and only if it holds for `a` and for every element of `s`.
Finset.mem_singleton
An element belongs to the singleton set {a} if and only if it equals a.
SimpleGraph.comap_adj
Vertices u and v are adjacent in the pullback graph G.comap f if and only if f(u) and f(v) are adjacent in G.
SimpleGraph.pathGraph_adj
Two vertices in the path graph of size n are adjacent if and only if their natural-number values differ by exactly 1.
forall_eq
A quantified implication (∀ x, x = a → p x) is logically equivalent to p(a).
temporal_target_state_table_sound
If a target-tracking state table containing the initial configuration is closed under one-step temporal graph transitions, then any temporal walk ends at time T in a reachable pair (w(T), M) where M contains all designated targets visited up to time T.
twelveCard
Every reachable pair (u, M) in `twelveTable 11` has target set cardinality at most 1.
twelveClosed
The reachability table `twelveTable` is forward-invariant: from any reachable state at time t < 11, any valid temporal move or pause leads to a reachable state at time t + 1 with the target set updated.

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

private def twelveOrder (t : ℕ) : Equiv.Perm (Fin 12) :=  if t < 8 then Equiv.refl _  else if t < 9 then Equiv.swap 0 8  else if t < 10 then (Equiv.swap 0 8).trans (Equiv.swap 4 9)  else ((Equiv.swap 0 8).trans (Equiv.swap 4 9)).trans (Equiv.swap 7 10)private def twelveGraph (t : ℕ) : SimpleGraph (Fin 12) :=  (SimpleGraph.pathGraph 12).comap (twelveOrder t)private instance twelveGraphDec (t : ℕ) : DecidableRel (twelveGraph t).Adj :=  fun a b => decidable_of_iff    (((twelveOrder t a : Fin 12) : ℕ) + 1 = twelveOrder t b ∨      ((twelveOrder t b : Fin 12) : ℕ) + 1 = twelveOrder t a)    SimpleGraph.pathGraph_adj.symmprivate def twelveTargets : Finset (Fin 12) :=  Finset.univ.filter fun v => 8 ≤ v.valprivate def twelveTable : ℕ → Finset (Fin 12 × Finset (Fin 12))  | 0 => {(0, ∅)}  | 1 => {(0, ∅), (1, ∅)}  | 2 => {(0, ∅), (1, ∅), (2, ∅)}  | 3 => {(0, ∅), (1, ∅), (2, ∅), (3, ∅)}  | 4 => {(0, ∅), (1, ∅), (2, ∅), (3, ∅), (4, ∅)}  | 5 => {(0, ∅), (1, ∅), (2, ∅), (3, ∅), (4, ∅), (5, ∅)}  | 6 => {(0, ∅), (1, ∅), (2, ∅), (3, ∅), (4, ∅), (5, ∅), (6, ∅)}  | 7 => {(0, ∅), (1, ∅), (2, ∅), (3, ∅), (4, ∅), (5, ∅), (6, ∅), (7, ∅)}  | 8 => {(0, ∅), (1, ∅), (2, ∅), (3, ∅), (4, ∅), (5, ∅), (6, ∅), (7, ∅), (8, {8})}  | 9 => {(0, ∅), (1, ∅), (1, {8}), (2, ∅), (3, ∅), (4, ∅), (5, ∅), (6, ∅), (7, ∅), (8, {8}), (9, {9})}  | 10 => {(0, ∅), (1, ∅), (1, {8}), (2, ∅), (2, {8}), (3, ∅), (3, {9}), (4, ∅), (5, ∅), (5, {9}), (6, ∅), (7, ∅), (8, {8}), (9, {9}), (10, {10})}  | 11 => {(0, ∅), (0, {10}), (1, ∅), (1, {8}), (2, ∅), (2, {8}), (2, {9}), (3, ∅), (3, {8}), (3, {9}), (4, ∅), (5, ∅), (5, {9}), (6, ∅), (6, {9}), (6, {10}), (7, ∅), (8, {8}), (9, {9}), (10, {10}), (11, {11})}  | _ => ∅set_option maxRecDepth 100000 inset_option maxHeartbeats 0 inset_option synthInstance.maxSize 100000 inprivate theorem twelveClosed :    ∀ t : Fin 11, ∀ p ∈ twelveTable t.val, ∀ u : Fin 12,      u = p.1 ∨ (twelveGraph t.val).Adj p.1 u →      (u, if u ∈ twelveTargets then insert u p.2 else p.2) ∈ twelveTable (t.val + 1) := by  intro t  fin_cases t <;>    simp only [twelveTable, Finset.forall_mem_insert, Finset.mem_singleton, forall_eq] <;>    simp only [twelveGraph, SimpleGraph.comap_adj, SimpleGraph.pathGraph_adj] <;>    (repeat' apply And.intro) <;>    decideset_option maxRecDepth 100000 inset_option maxHeartbeats 0 inset_option synthInstance.maxSize 100000 inprivate theorem twelveCard :    ∀ p ∈ twelveTable 11, p.2.card ≤ 1 := by  simp only [twelveTable, Finset.forall_mem_insert, Finset.mem_singleton, forall_eq]  decidetheorem temporal_path_twelve_one_frame_target_trap :    ∃ G : ℕ → SimpleGraph (Fin 12),      (∀ t, is_spanning_path_graph (G t)) ∧      ∀ w : ℕ → Fin 12, w 0 = 0 → is_temporal_walk G w →        ∃ M : Finset (Fin 12), M.card ≤ 1 ∧          ∀ i ≤ 11, 8 ≤ (w i).val → w i ∈ M := by  refine ⟨twelveGraph, ?_, ?_⟩  · intro t    exact ⟨twelveOrder t, fun a b => SimpleGraph.pathGraph_adj⟩  · intro w hw0 hw    obtain ⟨M, hM, hcover⟩ :=      temporal_target_state_table_sound twelveGraph twelveTargets 0 11 twelveTable ∅ (by decide) (by decide) twelveClosed w hw0 hw    refine ⟨M, twelveCard (w 11, M) hM, ?_⟩    intro i hi hui    exact hcover i hi (by simpa [twelveTargets] using hui)
See it in the graphDiscuss this resultChallenge it