relu_network3_encode_injective
Sanity check of the encoding: distinct width-3 ReLU networks have distinct Bool encodings.
Statement
theorem relu_network3_encode_injective : Function.Injective relu_network3_encode- Source
- Sanity lemma for relu_network3_encode, serving OP-75 (arXiv:2610.06092, Remark 5.15).
- Verified
- 09 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 8
- relu_network3_encodeEncoding of a width-3 ReLU network as a Bool word, of length linear in the total bit length of its rational entries: input weights, input…
- ReLUHiddenLayerA hidden layer of width k consists of a k-by-k rational weight matrix and a rational bias vector of length k.
- relu_encode_intEncoding of an integer as a Bool word: a sign bit followed by the binary encoding of its absolute value.
- ReLUNetworkA feedforward ReLU neural network from the real line to the real line with hidden layers of width k, specified by rational affine input…
- relu_encode_hidden_layer3Encoding of a width-3 ReLU hidden layer as a Bool word: its 3 by 3 weight matrix row by row, then its bias vector.
- relu_encode_ratEncoding of a rational in lowest terms as a Bool word: its numerator and denominator in binary.
- relu_encode_vec3Encoding of a rational vector of length 3 as the concatenation of the encodings of its three entries.
- relu_encode_natBinary encoding of a natural number as a self-delimiting Bool word: each base-2 digit, least significant first, is preceded by a true…
- Used by 2
- op75_subset_encoding_injectiveThe binary source encoding uniquely determines the finite list of weights and the target.
- relu_width3_language_mem_iffSanity check of the language: the encoding of a width-3 ReLU network lies in the verification language exactly when the network has a zero…
The proof, explained
The proof establishes injectivity of the ReLU network encoding by constructing a bottom-up hierarchy of prefix-free decodability lemmas for each subcomponent (digits, natural numbers, integers, rationals, 3-vectors, hidden layers, and layer lists). For the full network, appending an empty suffix allows each component—input weights, input bias, hidden layers, output weights, and output bias—to be peeled off sequentially using the corresponding prefix lemma. Once all component fields are shown to match, the two networks are identical by constructor equality.
Encoding of binary digit lists is prefix-free: equality of encoded lists with trailing suffixes implies equality of the digit lists and tails.
By induction on the first digit list l and case analysis on l'. The empty list starts with false, whereas a non-empty list starts with true, preventing collisions. For non-empty lists, matching the first pair of bits forces the leading digits to be equal (since both are < 2), and the inductive hypothesis equates the tails.
uses
List.flatMap_cons,List.cons_append,List.nil_append,List.cons.injEq,true_and,decide_eq_decideinduction l generalizing l' with | nil => cases l' with | nil => simpa using h | cons d t => simp at h | cons d t ih => cases l' with | nil => simp at h | cons d' t' => simp only [List.flatMap_cons, List.cons_append, List.nil_append, List.cons.injEq, true_and, decide_eq_decide] at h obtain ⟨h1, h2⟩ := h have hd := hl d (by simp) have hd' := hl' d' (by simp) have e : d = d' := by omega obtain ⟨e1, e2⟩ := ih t' (fun z hz => hl z (by simp [hz])) (fun z hz => hl' z (by simp [hz])) h2 exact ⟨by rw [e, e1], e2⟩
Encoding of natural numbers is prefix-free.
Unfolding the natural number encoding into base-2 digits terminated by false, we apply prefix-free injectivity of digit lists using the fact that base-2 digits are strictly less than 2. Injectivity of the digit expansion then recovers equality of the natural numbers.
uses
List.append_assoc,List.cons_append,List.nil_append,relu_encode_digits_prefix,Nat.digits_lt_base,Nat.digits_inj_iff.mpunfold relu_encode_nat at h simp only [List.append_assoc, List.cons_append, List.nil_append] at h obtain ⟨e1, e2⟩ := relu_encode_digits_prefix _ _ (fun d hd => Nat.digits_lt_base (by norm_num) hd) (fun d hd => Nat.digits_lt_base (by norm_num) hd) x y h exact ⟨Nat.digits_inj_iff.mp e1, e2⟩
Encoding of integers is prefix-free.
An integer is encoded as a sign bit followed by the encoding of its absolute value. Matching the leading bit equates the signs (whether a < 0), and prefix decoding of the natural number encoding equates their absolute values, which together uniquely determine the integer.
uses
List.cons_append,List.cons.injEq,decide_eq_decide,relu_encode_nat_prefixunfold relu_encode_int at h simp only [List.cons_append, List.cons.injEq, decide_eq_decide] at h obtain ⟨h1, h2⟩ := h obtain ⟨e1, e2⟩ := relu_encode_nat_prefix _ _ _ _ h2 exact ⟨by omega, e2⟩
Encoding of rational numbers is prefix-free.
A rational number is encoded as the concatenated encodings of its numerator and denominator. We peel off the integer numerator using integer prefix injectivity, then peel off the natural denominator using natural prefix injectivity, and conclude equality of the rationals via Rat.ext.
uses
List.append_assoc,relu_encode_int_prefix,relu_encode_nat_prefix,Rat.extunfold relu_encode_rat at h simp only [List.append_assoc] at h obtain ⟨e1, h2⟩ := relu_encode_int_prefix _ _ _ _ h obtain ⟨e2, e3⟩ := relu_encode_nat_prefix _ _ _ _ h2 exact ⟨Rat.ext e1 e2, e3⟩
Encoding of rational 3-vectors is prefix-free.
A 3-vector is encoded by concatenating the encodings of its three components. Peeling off the components sequentially via rational prefix injectivity yields equality at indices 0, 1, and 2, which proves vector equality by function extensionality.
uses
List.append_assoc,relu_encode_rat_prefixunfold relu_encode_vec3 at h simp only [List.append_assoc] at h obtain ⟨e0, h1⟩ := relu_encode_rat_prefix _ _ _ _ h obtain ⟨e1, h2⟩ := relu_encode_rat_prefix _ _ _ _ h1 obtain ⟨e2, e3⟩ := relu_encode_rat_prefix _ _ _ _ h2 refine ⟨?_, e3⟩ funext i fin_cases i · exact e0 · exact e1 · exact e2
Encoding of width-3 hidden layers is prefix-free.
A hidden layer consists of three weight rows and a bias vector. Applying vector prefix injectivity four times recovers equality of each row of the weight matrix and of the bias vector. Decomposing the layer into its fields and using function extensionality on the weights yields equality of the layers.
uses
List.append_assoc,relu_encode_vec3_prefixunfold relu_encode_hidden_layer3 at h simp only [List.append_assoc] at h obtain ⟨e0, h1⟩ := relu_encode_vec3_prefix _ _ _ _ h obtain ⟨e1, h2⟩ := relu_encode_vec3_prefix _ _ _ _ h1 obtain ⟨e2, h3⟩ := relu_encode_vec3_prefix _ _ _ _ h2 obtain ⟨e3, e4⟩ := relu_encode_vec3_prefix _ _ _ _ h3 refine ⟨?_, e4⟩ cases a with | mk w c => cases b with | mk w' c' => simp only at e0 e1 e2 e3 have : w = w' := by funext i fin_cases i · exact e0 · exact e1 · exact e2 rw [this, e3]
Encoding of lists of width-3 hidden layers is prefix-free.
By induction on the list of layers. Each layer is marked by a leading true bit, while the empty list terminates with false, preventing confusion. In the inductive step, hidden layer prefix injectivity recovers the head layer, and the inductive hypothesis recovers the remaining layers and suffix.
uses
List.flatMap_cons,List.cons_append,List.cons.injEq,true_and,List.append_assoc,relu_encode_hidden_layer3_prefixinduction l generalizing l' with | nil => cases l' with | nil => simpa using h | cons d t => simp at h | cons d t ih => cases l' with | nil => simp at h | cons d' t' => simp only [List.flatMap_cons, List.cons_append, List.cons.injEq, true_and, List.append_assoc] at h obtain ⟨e1, h2⟩ := relu_encode_hidden_layer3_prefix _ _ _ _ h obtain ⟨e2, e3⟩ := ih t' h2 exact ⟨by rw [e1, e2], e3⟩
The equality of network encodings is recast as an equality with an empty suffix and reassociated into sequential components.
We assume relu_network3_encode a = relu_network3_encode b and append an empty list [] to both sides. Unfolding the network encoding definition and reassociating list concatenation sets up a chain of prefixed encodings.
uses
List.append_assoc,List.cons_append,List.nil_appendintro a b h have h' : relu_network3_encode a ++ [] = relu_network3_encode b ++ [] := by rw [h] unfold relu_network3_encode at h' simp only [List.append_assoc, List.cons_append, List.nil_append] at h'
Each architectural component of the two networks is sequentially proven equal.
We peel off the components from left to right using their respective prefix injectivity lemmas: first the input weight vector, then the input bias vector, then the list of hidden layers, then the output weight vector, and finally the output bias rational.
uses
relu_encode_vec3_prefix,relu_encode_layers_prefix,relu_encode_rat_prefixobtain ⟨e0, h1⟩ := relu_encode_vec3_prefix _ _ _ _ h' obtain ⟨e1, h2⟩ := relu_encode_vec3_prefix _ _ _ _ h1 obtain ⟨e2, h3⟩ := relu_encode_layers_prefix _ _ _ _ h2 obtain ⟨e3, h4⟩ := relu_encode_vec3_prefix _ _ _ _ h3 obtain ⟨e4, -⟩ := relu_encode_rat_prefix _ _ _ _ h4
The networks a and b are identical, establishing injectivity of relu_network3_encode. automation
Decomposing both networks into their constructor fields, the component equalities already established suffice to show that all fields coincide, closing the goal.
cases a; cases b; simp_all
List.flatMap_cons- Mapping a function returning lists over a non-empty list and flattening equals the function applied to the head concatenated with the flattened tail.
List.cons_append- Prepending an element to a list before concatenating another list is associative with respect to list formation.
List.nil_append- Concatenating the empty list onto any list returns the list unchanged.
List.cons.injEq- Two non-empty lists are equal if and only if their heads are equal and their tails are equal.
true_and- Conjunction of True with any proposition p simplifies to p.
decide_eq_decide- The boolean evaluations of two decidable propositions are equal if and only if the propositions are logically equivalent.
relu_encode_digits_prefix- Prefix-free injectivity for binary digit lists: if two encoded digit lists followed by false and remaining bits are equal, then the digit lists and tails are equal.
Nat.digits_lt_base- Any digit in the base-b representation of a natural number m is strictly less than b, provided b > 1.
Nat.digits_inj_iff.mp- Two natural numbers are equal if their base-b digit expansions are equal.
List.append_assoc- List concatenation is associative.
relu_encode_nat_prefix- Prefix-free injectivity for natural numbers: an encoded natural number uniquely determines the number and any trailing suffix.
relu_encode_int_prefix- Prefix-free injectivity for integers: an encoded integer uniquely determines the integer and any trailing suffix.
Rat.ext- Two rational numbers are equal if their numerators and denominators are respectively equal.
relu_encode_vec3_prefix- Prefix-free injectivity for rational 3-vectors: an encoded vector uniquely determines the vector and any trailing suffix.
relu_encode_hidden_layer3_prefix- Prefix-free injectivity for width-3 hidden layers: an encoded layer uniquely determines the layer and any trailing suffix.
relu_encode_layers_prefix- Prefix-free injectivity for lists of width-3 hidden layers: an encoded layer list uniquely determines the list and any trailing suffix.
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.
theorem relu_encode_digits_prefix (l l' : List ℕ) (hl : ∀ d ∈ l, d < 2) (hl' : ∀ d ∈ l', d < 2) (x y : List Bool) (h : l.flatMap (fun d => [true, decide (d = 1)]) ++ false :: x = l'.flatMap (fun d => [true, decide (d = 1)]) ++ false :: y) : l = l' ∧ x = y := by induction l generalizing l' with | nil => cases l' with | nil => simpa using h | cons d t => simp at h | cons d t ih => cases l' with | nil => simp at h | cons d' t' => simp only [List.flatMap_cons, List.cons_append, List.nil_append, List.cons.injEq, true_and, decide_eq_decide] at h obtain ⟨h1, h2⟩ := h have hd := hl d (by simp) have hd' := hl' d' (by simp) have e : d = d' := by omega obtain ⟨e1, e2⟩ := ih t' (fun z hz => hl z (by simp [hz])) (fun z hz => hl' z (by simp [hz])) h2 exact ⟨by rw [e, e1], e2⟩theorem relu_encode_nat_prefix (a b : ℕ) (x y : List Bool) (h : relu_encode_nat a ++ x = relu_encode_nat b ++ y) : a = b ∧ x = y := by unfold relu_encode_nat at h simp only [List.append_assoc, List.cons_append, List.nil_append] at h obtain ⟨e1, e2⟩ := relu_encode_digits_prefix _ _ (fun d hd => Nat.digits_lt_base (by norm_num) hd) (fun d hd => Nat.digits_lt_base (by norm_num) hd) x y h exact ⟨Nat.digits_inj_iff.mp e1, e2⟩theorem relu_encode_int_prefix (a b : ℤ) (x y : List Bool) (h : relu_encode_int a ++ x = relu_encode_int b ++ y) : a = b ∧ x = y := by unfold relu_encode_int at h simp only [List.cons_append, List.cons.injEq, decide_eq_decide] at h obtain ⟨h1, h2⟩ := h obtain ⟨e1, e2⟩ := relu_encode_nat_prefix _ _ _ _ h2 exact ⟨by omega, e2⟩theorem relu_encode_rat_prefix (a b : ℚ) (x y : List Bool) (h : relu_encode_rat a ++ x = relu_encode_rat b ++ y) : a = b ∧ x = y := by unfold relu_encode_rat at h simp only [List.append_assoc] at h obtain ⟨e1, h2⟩ := relu_encode_int_prefix _ _ _ _ h obtain ⟨e2, e3⟩ := relu_encode_nat_prefix _ _ _ _ h2 exact ⟨Rat.ext e1 e2, e3⟩theorem relu_encode_vec3_prefix (a b : Fin 3 → ℚ) (x y : List Bool) (h : relu_encode_vec3 a ++ x = relu_encode_vec3 b ++ y) : a = b ∧ x = y := by unfold relu_encode_vec3 at h simp only [List.append_assoc] at h obtain ⟨e0, h1⟩ := relu_encode_rat_prefix _ _ _ _ h obtain ⟨e1, h2⟩ := relu_encode_rat_prefix _ _ _ _ h1 obtain ⟨e2, e3⟩ := relu_encode_rat_prefix _ _ _ _ h2 refine ⟨?_, e3⟩ funext i fin_cases i · exact e0 · exact e1 · exact e2theorem relu_encode_hidden_layer3_prefix (a b : ReLUHiddenLayer 3) (x y : List Bool) (h : relu_encode_hidden_layer3 a ++ x = relu_encode_hidden_layer3 b ++ y) : a = b ∧ x = y := by unfold relu_encode_hidden_layer3 at h simp only [List.append_assoc] at h obtain ⟨e0, h1⟩ := relu_encode_vec3_prefix _ _ _ _ h obtain ⟨e1, h2⟩ := relu_encode_vec3_prefix _ _ _ _ h1 obtain ⟨e2, h3⟩ := relu_encode_vec3_prefix _ _ _ _ h2 obtain ⟨e3, e4⟩ := relu_encode_vec3_prefix _ _ _ _ h3 refine ⟨?_, e4⟩ cases a with | mk w c => cases b with | mk w' c' => simp only at e0 e1 e2 e3 have : w = w' := by funext i fin_cases i · exact e0 · exact e1 · exact e2 rw [this, e3]theorem relu_encode_layers_prefix (l l' : List (ReLUHiddenLayer 3)) (x y : List Bool) (h : l.flatMap (fun z => true :: relu_encode_hidden_layer3 z) ++ false :: x = l'.flatMap (fun z => true :: relu_encode_hidden_layer3 z) ++ false :: y) : l = l' ∧ x = y := by induction l generalizing l' with | nil => cases l' with | nil => simpa using h | cons d t => simp at h | cons d t ih => cases l' with | nil => simp at h | cons d' t' => simp only [List.flatMap_cons, List.cons_append, List.cons.injEq, true_and, List.append_assoc] at h obtain ⟨e1, h2⟩ := relu_encode_hidden_layer3_prefix _ _ _ _ h obtain ⟨e2, e3⟩ := ih t' h2 exact ⟨by rw [e1, e2], e3⟩theorem relu_network3_encode_injective : Function.Injective relu_network3_encode := by intro a b h have h' : relu_network3_encode a ++ [] = relu_network3_encode b ++ [] := by rw [h] unfold relu_network3_encode at h' simp only [List.append_assoc, List.cons_append, List.nil_append] at h' obtain ⟨e0, h1⟩ := relu_encode_vec3_prefix _ _ _ _ h' obtain ⟨e1, h2⟩ := relu_encode_vec3_prefix _ _ _ _ h1 obtain ⟨e2, h3⟩ := relu_encode_layers_prefix _ _ _ _ h2 obtain ⟨e3, h4⟩ := relu_encode_vec3_prefix _ _ _ _ h3 obtain ⟨e4, -⟩ := relu_encode_rat_prefix _ _ _ _ h4 cases a; cases b; simp_all