corpus_words
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]})