AFTD Auto-Formalizing Theoretical Domains

relu_network3_encode_injective

theoremverified

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

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.

  1. 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.

    lines 5–21

    uses List.flatMap_cons, List.cons_append, List.nil_append, List.cons.injEq, true_and, decide_eq_decide

      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⟩
  2. 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.

    lines 25–30

    uses List.append_assoc, List.cons_append, List.nil_append, relu_encode_digits_prefix, Nat.digits_lt_base, Nat.digits_inj_iff.mp

      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⟩
  3. 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.

    lines 34–38

    uses List.cons_append, List.cons.injEq, decide_eq_decide, relu_encode_nat_prefix

      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⟩
  4. 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.

    lines 42–46

    uses List.append_assoc, relu_encode_int_prefix, relu_encode_nat_prefix, Rat.ext

      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⟩
  5. 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.

    lines 50–60

    uses List.append_assoc, relu_encode_rat_prefix

      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 e2
  6. 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.

    lines 64–82

    uses List.append_assoc, relu_encode_vec3_prefix

      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]
  7. 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.

    lines 87–100

    uses List.flatMap_cons, List.cons_append, List.cons.injEq, true_and, List.append_assoc, relu_encode_hidden_layer3_prefix

      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⟩
  8. 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.

    lines 103–106

    uses List.append_assoc, List.cons_append, List.nil_append

      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'
  9. 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.

    lines 107–111

    uses relu_encode_vec3_prefix, relu_encode_layers_prefix, relu_encode_rat_prefix

      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
  10. 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.

    line 112

      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

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
See it in the graphDiscuss this resultChallenge it