relu_width3_language_mem_iff
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
netof width $k$ has a zero in the unit interval $[0, 1]$ if there exists some real number…
- Used by 2
- op75_invalid_input_fallback_nonmemberThe encoding of the empty-weight target-one network is a no-instance of the width-three unit-interval zero language.
- op75_subset_compiler_semanticsAny total binary function that maps canonical subset-sum instances to their specified networks and maps malformed inputs outside the zero…
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.
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].
uses
relu_network3_encode_injectiveconstructor · rintro ⟨n, e, hz⟩ rwa [← relu_network3_encode_injective e]
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.
· 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
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_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⟩