AFTD Auto-Formalizing Theoretical Domains

corpus_words

def

Given a finite type V with decidable equality and a simple graph G on V with decidable adjacency, corpus_words G is the Finset of lists over the alphabet V ⊕ (G.edgeSet × Fin 3) formed by taking the union over all edges e in G.edgeFinset of the four words [u, c, v], [u, c, r], [l, c, v], and [l, c, r], where (u, v) = Quot.out e gives the chosen orientation of the endpoints of e, and c = (e, 0), l = (e, 1), r = (e, 2) in G.edgeSet × Fin 3.

Statement

noncomputable def corpus_words {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] :
    Finset (List (V ⊕ (G.edgeSet × Fin 3)))
Defined in
arXiv:2611.15074 Reduction 1 (VC to FAC)
Verified
15 Nov 2026
Axioms
none listed

Read back from the Lean

corpus_words is a noncomputable definition that, given a finite type V with decidable equality and a simple graph G on V with decidable adjacency, constructs a Finset of 3-element lists over the alphabet V ⊕ (G.edgeSet × Fin 3). For each edge e in G.edgeFinset: - Let (u, v) = Quot.out e : V × V be an arbitrary representative of the unordered pair e. - Let u, v : V ⊕ (G.edgeSet × Fin 3) be Sum.inl u and Sum.inl v. - Let c, l, r : V ⊕ (G.edgeSet × Fin 3) be Sum.inr (⟨e, _⟩, 0), Sum.inr (⟨e, _⟩, 1), and Sum.inr (⟨e, _⟩, 2) respectively. The definition returns the union over all e ∈ G.edgeFinset of the four lists: 1. [u, c, v] 2. [u, c, r] 3. [l, c, v] 4. [l, c, r]

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- The reduction corpus X_G consisting of 4 words per edge of G over the alphabet V ⊕ (G.edgeSet × Fin 3). -/
noncomputable def corpus_words {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] :
    Finset (List (V ⊕ (G.edgeSet × Fin 3))) :=
  G.edgeFinset.attach.biUnion (fun ⟨e, he⟩ =>
    let u : V ⊕ (G.edgeSet × Fin 3) := Sum.inl (Quot.out e).1
    let v : V ⊕ (G.edgeSet × Fin 3) := Sum.inl (Quot.out e).2
    let c : V ⊕ (G.edgeSet × Fin 3) := Sum.inr (⟨e, SimpleGraph.mem_edgeFinset.mp he⟩, 0)
    let l : V ⊕ (G.edgeSet × Fin 3) := Sum.inr (⟨e, SimpleGraph.mem_edgeFinset.mp he⟩, 1)
    let r : V ⊕ (G.edgeSet × Fin 3) := Sum.inr (⟨e, SimpleGraph.mem_edgeFinset.mp he⟩, 2)
    {[u, c, v], [u, c, r], [l, c, v], [l, c, r]})
See it in the graphDiscuss this resultChallenge it