AFTD Auto-Formalizing Theoretical Domains

relu_width3_language_mem_iff

theoremverified

Sanity check of the language: the encoding of a width-3 ReLU network lies in the verification language exactly when the network has a zero in [0, 1].

Statement

theorem relu_width3_language_mem_iff (net : ReLUNetwork 3) :
    relu_network3_encode net ∈ relu_width3_unit_interval_zero_language ↔
      relu_network_has_unit_interval_zero net
Source
Sanity lemma for relu_width3_unit_interval_zero_language, serving OP-75 (arXiv:2610.06092, Remark 5.15).
Verified
09 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • relu_width3_unit_interval_zero_languageThe verification language at width 3 on the unit interval, for the fixed encoding relu_network3_encode: the set of Bool words w such that…
  • relu_network3_encode_injectiveSanity check of the encoding: distinct width-3 ReLU networks have distinct Bool encodings.
  • 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_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…
  • relu_network_has_unit_interval_zeroA feedforward ReLU neural network net of width $k$ has a zero in the unit interval $[0, 1]$ if there exists some real number…
Used by 2

The proof, explained

The theorem shows that the encoding of a width-3 ReLU network belongs to the verification language if and only if the network has a zero in [0, 1]. In the forward direction, language membership yields an encoded network with a zero; injectivity of the encoding guarantees that this witness is the original network itself. The converse direction holds immediately by taking the network itself as the witness.

  1. If the encoding of a network belongs to the verification language, then the network has a zero in [0, 1].

    We split the equivalence into both directions. For the forward direction, by definition of the language, membership of `relu_network3_encode net` means there exists some network `n` whose encoding matches `relu_network3_encode net` and which has a zero in [0, 1]. Injectivity of the encoding function (`relu_network3_encode_injective`) implies `n = net`, which establishes that `net` has a zero in [0, 1].

    lines 4–6

    uses relu_network3_encode_injective

      constructor
      · rintro ⟨n, e, hz⟩
        rwa [← relu_network3_encode_injective e]
  2. If the network has a zero in [0, 1], then its encoding belongs to the verification language.

    For the reverse direction, assuming the network has a zero in [0, 1], the definition of language membership is satisfied by witnessing the existential quantifier with the network itself, since its encoding is trivially identical to itself.

    lines 7–8

      · intro hz
        exact ⟨net, rfl, hz⟩
relu_network3_encode_injective
The encoding function `relu_network3_encode` mapping width-3 ReLU networks to boolean lists is injective; that is, distinct networks produce distinct encodings.

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_width3_language_mem_iff (net : ReLUNetwork 3) :    relu_network3_encode net ∈ relu_width3_unit_interval_zero_language ↔      relu_network_has_unit_interval_zero net := by  constructor  · rintro ⟨n, e, hz⟩    rwa [← relu_network3_encode_injective e]  · intro hz    exact ⟨net, rfl, hz⟩
See it in the graphDiscuss this resultChallenge it