AFTD Auto-Formalizing Theoretical Domains

op75_subset_compiler_function_correct

theoremverified

The explicit total compiler preserves language membership.

Statement

theorem op75_subset_compiler_function_correct (w : List Bool) :
    w ∈ op75_subset_language ↔ op75_subset_compiler_function w ∈ relu_width3_unit_interval_zero_language
Source
OP-75: explicit total subset-sum to width-three network compiler.
Verified
15 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 10
  • op75_subset_compiler_functionCompile a canonical subset-sum input to the explicit width-three network encoding; map malformed input to the fixed no-instance.
  • op75_subset_compiler_semanticsAny total binary function that maps canonical subset-sum instances to their specified networks and maps malformed inputs outside the zero…
  • op75_parse_subset_specThe total decoder returns a weight list and target exactly when their canonical encoding equals its input.
  • 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.
  • 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…
  • op75_subset_encodingThe source word encodes each nonnegative integer weight as a true marker followed by its self-delimiting natural encoding, then a false…
  • op75_parse_subsetDecode a canonical subset-sum bit string, rejecting malformed or trailing data.
  • 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…
  • op75_subset_languageThe language of canonical binary words encoding a finite list of nonnegative integer weights and a target that is a subset sum of the list.
  • op75_compact_networkThe width-three network obtained by concatenating a seven-layer block for each integer weight, followed by the final target-checking layer…
Used by 1

Lean source view module on GitHub

theorem op75_subset_compiler_function_correct (w : List Bool) :
    w ∈ op75_subset_language ↔ op75_subset_compiler_function w ∈ relu_width3_unit_interval_zero_language := by
  apply op75_subset_compiler_semantics op75_subset_compiler_function
  · intro as t
    have hp := (op75_parse_subset_spec (op75_subset_encoding as t) as t).2 rfl
    simp [op75_subset_compiler_function, hp]
  · intro w hbad
    cases hp : op75_parse_subset w with
    | none => simpa [op75_subset_compiler_function, hp] using op75_invalid_input_fallback_nonmember
    | some value =>
        rcases value with ⟨as, t⟩
        have he := (op75_parse_subset_spec w as t).1 hp
        exact False.elim (hbad ⟨as,t,he⟩)
See it in the graphDiscuss this resultChallenge it