temporal_path_twelve_one_frame_target_trap
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.
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`.
uses
Finset.forall_mem_insert,Finset.mem_singleton,forall_eq,SimpleGraph.comap_adj,SimpleGraph.pathGraph_adj,And.introintro 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
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.
uses
Finset.forall_mem_insert,Finset.mem_singleton,forall_eqsimp only [twelveTable, Finset.forall_mem_insert, Finset.mem_singleton, forall_eq] decide
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`.
uses
SimpleGraph.pathGraph_adjrefine ⟨twelveGraph, ?_, ?_⟩ · intro t exact ⟨twelveOrder t, fun a b => SimpleGraph.pathGraph_adj⟩
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`.
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
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.
uses
twelveCardrefine ⟨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.
- The inductive step `twelveClosed` and the cardinality bound `twelveCard` are proved by exhaustive finite computation: `fin_cases` splits time into 11 cases, and `decide` checks all one-step transitions and set cardinalities by kernel evaluation.
- The target set $\{8, 9, 10, 11\}$ is defined by the condition $8 \le v$, and `simpa` bridges this inequality with membership in `twelveTargets`.
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.
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)