AFTD Auto-Formalizing Theoretical Domains

carpool_forest_edge_sequence_nil

theoremverified

The empty list of edges is an oblivious forest edge sequence on Fin n.

Statement

theorem carpool_forest_edge_sequence_nil (n : ℕ) :
    CarpoolForestEdgeSequence n []
Source
arXiv:2611.00388: Online carpooling against an oblivious adversary; OP-1106
Verified
09 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • CarpoolForestEdgeSequenceA list of edges on Fin n is an oblivious forest edge sequence for online carpooling if all edges connect distinct vertices, no undirected…

Read back from the Lean

For every natural number $n$, the empty list of edges satisfies CarpoolForestEdgeSequence n [].

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

To show that the empty list is a valid carpool forest edge sequence, we unfold the definition into three conditions: no self-loops, no duplicate edges, and acyclicity of the induced graph. The first two conditions hold trivially because the empty list has no elements. The third holds because the empty list yields an empty edge set, and the graph with no edges is acyclic.

  1. It suffices to show that the graph formed by the empty list of edges is acyclic.

    Unfolding the definition of a carpool forest edge sequence yields three conditions: every edge in the list must connect distinct vertices (no self-loops), the list must contain no duplicate undirected edges, and the graph formed by these edges must be acyclic. The first condition holds vacuously because the empty list has no elements. The second condition holds because the empty list has no duplicates (`List.nodup_nil`).

    lines 4–5

    uses List.nodup_nil

      dsimp [CarpoolForestEdgeSequence, ValidCarpoolEdgeSequence]
      refine ⟨by simp, List.nodup_nil, ?_⟩
  2. The set of undirected edges induced by the empty list is the empty set.

    By extensionality, an undirected edge belongs to this set if and only if it arises from some element of the edge list. Because the empty list contains no elements, no such edge exists, so the set is empty.

    lines 6–7

      have h_empty : {x | ∃ e ∈ ([] : List (Fin n × Fin n)), s(e.1, e.2) = x} = ∅ := by
        ext x; simp
  3. The graph formed by the empty list is the empty graph ⊥, which is acyclic.

    Rewriting the edge set with the fact that it is empty reduces the induced graph to `SimpleGraph.fromEdgeSet ∅`, which is the empty graph ⊥ (`SimpleGraph.fromEdgeSet_empty`). The empty graph has no edges and is therefore acyclic (`SimpleGraph.isAcyclic_bot`).

    lines 8–9

    uses SimpleGraph.fromEdgeSet_empty, SimpleGraph.isAcyclic_bot

      rw [h_empty, SimpleGraph.fromEdgeSet_empty]
      exact SimpleGraph.isAcyclic_bot
List.nodup_nil
An empty list has no duplicate elements.
SimpleGraph.fromEdgeSet_empty
The simple graph constructed from the empty set of edges is the empty graph ⊥ (the graph with no edges).
SimpleGraph.isAcyclic_bot
The empty graph ⊥ has no cycles.

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

/-- The empty edge sequence is a valid carpool forest edge sequence. -/theorem carpool_forest_edge_sequence_nil (n : ℕ) :    CarpoolForestEdgeSequence n [] := by  dsimp [CarpoolForestEdgeSequence, ValidCarpoolEdgeSequence]  refine ⟨by simp, List.nodup_nil, ?_⟩  have h_empty : {x | ∃ e ∈ ([] : List (Fin n × Fin n)), s(e.1, e.2) = x} = ∅ := by    ext x; simp  rw [h_empty, SimpleGraph.fromEdgeSet_empty]  exact SimpleGraph.isAcyclic_bot
See it in the graphDiscuss this resultChallenge it