edge_list_bool_encode_injective
The unary encoding edge_list_bool_encode of edge lists as Bool words is injective: different edge lists get different words.
Statement
theorem edge_list_bool_encode_injective : Function.Injective edge_list_bool_encode- Source
- Sanity check of edge_list_bool_encode (the encoding is uniquely decodable), for arXiv:2610.35794 (Computational complexity of the H-coloring problem in cubic graphs)
- Verified
- 30 Oct 2026
- Axioms
propext- Built on 1
- edge_list_bool_encodeEncodes an edge list es : List (ℕ × ℕ) as a word over Bool: es.flatMap of the map sending a pair e to List.replicate e.1 true ++ false ::…
The proof, explained
The proof proceeds by structural induction on the edge list l₁. Each edge (u, v) is encoded as 1^u 0 1^v 0, which is prefix-free because the counts u and v are uniquely recovered by counting the consecutive true values before each terminating false delimiter. In the inductive step, the encoding of a :: l₁ begins with the code of a, so prefix-freeness forces the leading edges to match (a = b) and strips them from both encodings; the induction hypothesis then proves that the remaining lists are equal.
List concatenation is associative for boolean lists: (a ++ b) ++ c = a ++ (b ++ c).
Proved by induction on the first list a. In the base case where a is empty, both sides simplify to b ++ c definitionally. In the inductive step where a = x :: xs, the head element x factors out on both sides, and the tails xs ++ b ++ c and xs ++ (b ++ c) are equal by the induction hypothesis.
induction a with | nil => rfl | cons x xs ih => simp [ih]
If two boolean words of the form 1^a 0 u and 1^b 0 v are equal, then a = b and u = v.
Proved by induction on a generalizing b. In the base case a = 0, if b = 0 both sides are false :: u = false :: v, yielding u = v; if b = succ b', the right-hand side starts with true while the left starts with false, which is a contradiction via List.replicate_succ. In the inductive step a = succ a', if b = 0 the sides again disagree on the first element (true vs false); if b = succ b', both start with true. Stripping the leading true via List.replicate_succ, List.cons_append, and List.cons.injEq yields 1^(a') 0 u = 1^(b') 0 v, so the induction hypothesis gives a' = b' (hence a = b) and u = v.
uses
List.replicate_succ,List.cons_append,List.cons.injEqinduction a generalizing b with | zero => cases b with | zero => simpa using h | succ b => simp [List.replicate_succ] at h | succ a ih => cases b with | zero => simp [List.replicate_succ] at h | succ b => simp only [List.replicate_succ, List.cons_append, List.cons.injEq] at h obtain ⟨-, h'⟩ := h obtain ⟨e1, e2⟩ := ih b h' exact ⟨by simp [e1], e2⟩
The code of a single edge is prefix-free: code(e₁) ++ x = code(e₂) ++ y implies e₁ = e₂ and x = y.
Unfolding the edge code definition and reassociating concatenation with List.append_assoc gives 1^(e₁.1) 0 (1^(e₁.2) 0 ++ x) = 1^(e₂.1) 0 (1^(e₂.2) 0 ++ y). Applying edge_list_bool_encode_injective_prefix_rep to the first components yields e₁.1 = e₂.1 and equates the remaining suffixes. Reassociating the remaining suffixes via edge_list_bool_encode_injective_append_assoc and List.singleton_append brings the second components into the form 1^(e₁.2) 0 x = 1^(e₂.2) 0 y. A second application of edge_list_bool_encode_injective_prefix_rep then gives e₁.2 = e₂.2 and x = y. Combining the coordinate equalities with Prod.ext yields e₁ = e₂.
uses
edge_list_bool_encode_injective_code,List.append_assoc,edge_list_bool_encode_injective_prefix_rep,edge_list_bool_encode_injective_append_assoc,List.singleton_append,Prod.extsimp only [edge_list_bool_encode_injective_code, List.append_assoc] at h obtain ⟨h1, h2⟩ := edge_list_bool_encode_injective_prefix_rep e₁.1 e₂.1 _ _ h have h2' : (List.replicate e₁.2 true ++ [false]) ++ x = (List.replicate e₂.2 true ++ [false]) ++ y := h2 rw [edge_list_bool_encode_injective_append_assoc, edge_list_bool_encode_injective_append_assoc, List.singleton_append, List.singleton_append] at h2' obtain ⟨h3, h4⟩ := edge_list_bool_encode_injective_prefix_rep e₁.2 e₂.2 x y h2' exact ⟨Prod.ext h1 h3, h4⟩
The encoding of a non-empty list a :: l decomposes into the code of edge a concatenated with the encoding of l. automation
Unfolding edge_list_bool_encode (defined via List.flatMap) and edge_list_bool_encode_injective_code reduces the flatMap over a cons cell directly to code(a) ++ encode(l). Automated simplification closes the goal by definitional expansion.
uses
edge_list_bool_encode,edge_list_bool_encode_injective_code,List.flatMapsimp [edge_list_bool_encode, edge_list_bool_encode_injective_code, List.flatMap]In the base case of induction on l₁, if encode([]) = encode(l₂), then [] = l₂.
We proceed by structural induction on l₁. In the base case l₁ = [], we case split on l₂. If l₂ = [], the equality [] = [] holds by reflexivity. If l₂ = b :: l₂', the encoding of l₂ contains at least one false from the code of b, while the encoding of [] is empty; simplifying with edge_list_bool_encode and List.flatMap derives a contradiction.
uses
edge_list_bool_encode,List.flatMapintro l₁ induction l₁ with | nil => intro l₂ h cases l₂ with | nil => rfl | cons b l₂ => simp [edge_list_bool_encode, List.flatMap] at h
In the inductive step, if encode(a :: l₁) = encode(l₂), then a :: l₁ = l₂.
We assume the claim holds for l₁ and inspect l₂. If l₂ = [], its encoding is empty while that of a :: l₁ is non-empty, which simplification refutes via edge_list_bool_encode and List.flatMap. If l₂ = b :: l₂', rewriting both sides with edge_list_bool_encode_injective_cons gives code(a) ++ encode(l₁) = code(b) ++ encode(l₂'). By single-edge prefix injectivity (edge_list_bool_encode_injective_code_prefix), this implies a = b and encode(l₁) = encode(l₂'). Applying the induction hypothesis to the tail encodings yields l₁ = l₂', and prefixing both sides with a via congrArg (List.cons a) establishes a :: l₁ = a :: l₂'.
uses
edge_list_bool_encode,List.flatMap,edge_list_bool_encode_injective_cons,edge_list_bool_encode_injective_code_prefix,congrArgintro l₂ h cases l₂ with | nil => simp [edge_list_bool_encode, List.flatMap] at h | cons b l₂ => rw [edge_list_bool_encode_injective_cons, edge_list_bool_encode_injective_cons] at h obtain ⟨rfl, h'⟩ := edge_list_bool_encode_injective_code_prefix a b _ _ h exact congrArg (List.cons a) (ih h')
List.replicate_succ- Replicating an element n + 1 times is equal to that element prepended to the list replicating it n times.
List.cons_append- Prepending an element to the first of two concatenated lists is equal to prepending it to their concatenation.
List.cons.injEq- Two non-empty lists are equal if and only if their heads are equal and their tails are equal.
edge_list_bool_encode_injective_code- The unary encoding of a single edge (u, v) as a boolean list consisting of u copies of true, a false separator, v copies of true, and a trailing false separator.
List.append_assoc- Concatenation of lists is associative.
edge_list_bool_encode_injective_prefix_rep- If two boolean lists each starting with a block of true values followed by false are equal, then the counts of true values are equal and the remainder lists are equal.
edge_list_bool_encode_injective_append_assoc- Concatenation of boolean lists is associative.
List.singleton_append- Appending a single-element list [x] to a list l is equal to prepending x to l.
Prod.ext- Two ordered pairs are equal if their first components are equal and their second components are equal.
edge_list_bool_encode- The unary boolean encoding of an edge list, formed by concatenating the boolean encodings of all individual edges.
List.flatMap- Maps a function producing a list over each element of an input list and concatenates the resulting lists.
edge_list_bool_encode_injective_cons- The encoding of a list a :: l decomposes into the code of the edge a concatenated with the encoding of the tail l.
edge_list_bool_encode_injective_code_prefix- If prepending the code of edge e₁ to suffix x yields the same boolean list as prepending the code of edge e₂ to suffix y, then e₁ = e₂ and x = y.
congrArg- If two inputs are equal, applying the same function to both yields equal results.
- The proof defines and proves four private helper lemmas inline to establish the prefix-freeness and homomorphic structure of the encoding before proving the main injectivity result by list induction.
- Step 4 relies on automated simplification to unfold the definition of List.flatMap over a cons cell.
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 edge_list_bool_encode_injective_code (e : ℕ × ℕ) : List Bool := List.replicate e.1 true ++ false :: (List.replicate e.2 true ++ [false])private theorem edge_list_bool_encode_injective_append_assoc (a b c : List Bool) : (a ++ b) ++ c = a ++ (b ++ c) := by induction a with | nil => rfl | cons x xs ih => simp [ih]private theorem edge_list_bool_encode_injective_prefix_rep (a b : ℕ) (u v : List Bool) (h : List.replicate a true ++ false :: u = List.replicate b true ++ false :: v) : a = b ∧ u = v := by induction a generalizing b with | zero => cases b with | zero => simpa using h | succ b => simp [List.replicate_succ] at h | succ a ih => cases b with | zero => simp [List.replicate_succ] at h | succ b => simp only [List.replicate_succ, List.cons_append, List.cons.injEq] at h obtain ⟨-, h'⟩ := h obtain ⟨e1, e2⟩ := ih b h' exact ⟨by simp [e1], e2⟩private theorem edge_list_bool_encode_injective_code_prefix (e₁ e₂ : ℕ × ℕ) (x y : List Bool) (h : edge_list_bool_encode_injective_code e₁ ++ x = edge_list_bool_encode_injective_code e₂ ++ y) : e₁ = e₂ ∧ x = y := by simp only [edge_list_bool_encode_injective_code, List.append_assoc] at h obtain ⟨h1, h2⟩ := edge_list_bool_encode_injective_prefix_rep e₁.1 e₂.1 _ _ h have h2' : (List.replicate e₁.2 true ++ [false]) ++ x = (List.replicate e₂.2 true ++ [false]) ++ y := h2 rw [edge_list_bool_encode_injective_append_assoc, edge_list_bool_encode_injective_append_assoc, List.singleton_append, List.singleton_append] at h2' obtain ⟨h3, h4⟩ := edge_list_bool_encode_injective_prefix_rep e₁.2 e₂.2 x y h2' exact ⟨Prod.ext h1 h3, h4⟩private theorem edge_list_bool_encode_injective_cons (a : ℕ × ℕ) (l : List (ℕ × ℕ)) : edge_list_bool_encode (a :: l) = edge_list_bool_encode_injective_code a ++ edge_list_bool_encode l := by simp [edge_list_bool_encode, edge_list_bool_encode_injective_code, List.flatMap]theorem edge_list_bool_encode_injective : Function.Injective edge_list_bool_encode := by intro l₁ induction l₁ with | nil => intro l₂ h cases l₂ with | nil => rfl | cons b l₂ => simp [edge_list_bool_encode, List.flatMap] at h | cons a l₁ ih => intro l₂ h cases l₂ with | nil => simp [edge_list_bool_encode, List.flatMap] at h | cons b l₂ => rw [edge_list_bool_encode_injective_cons, edge_list_bool_encode_injective_cons] at h obtain ⟨rfl, h'⟩ := edge_list_bool_encode_injective_code_prefix a b _ _ h exact congrArg (List.cons a) (ih h')