op75_parse_subset_aux_sound
theoremverified
Every successful fuel-bounded parse reconstructs exactly the original canonical subset-sum word.
Statement
theorem op75_parse_subset_aux_sound (fuel : ℕ) (w : List Bool) (as : List ℕ) (t : ℕ)
(h : op75_parse_subset_aux fuel w = some (as, t)) : op75_subset_encoding as t = w- Source
- OP-75: canonical subset-sum input decoder for the width-three ReLU compiler.
- Verified
- 15 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- op75_parse_subset_auxA total fuel-bounded decoder for canonical subset-sum instances.
- op75_parse_nat_soundEvery successful natural parse exactly consumes the canonical encoding of its returned value and returns the correct nonzero flag.
- op75_subset_encoding_consEncoding a nonempty weight list emits its marker, the head natural, then the remaining instance.
- 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…
- op75_parse_natDecode one canonical self-delimiting binary natural, returning its value, the unconsumed suffix, and whether the value is nonzero; reject…
- op75_subset_encodingThe source word encodes each nonnegative integer weight as a true marker followed by its self-delimiting natural encoding, then a false…
- Used by 1
- op75_parse_subset_specThe total decoder returns a weight list and target exactly when their canonical encoding equals its input.
Lean source view module on GitHub
theorem op75_parse_subset_aux_sound (fuel : ℕ) (w : List Bool) (as : List ℕ) (t : ℕ) (h : op75_parse_subset_aux fuel w = some (as, t)) : op75_subset_encoding as t = w := by induction fuel generalizing w as t with | zero => simp [op75_parse_subset_aux] at h | succ fuel ih => cases w with | nil => simp [op75_parse_subset_aux] at h | cons mark tail => cases mark with | false => cases hp : op75_parse_nat tail with | none => simp [op75_parse_subset_aux, hp] at h | some value => rcases value with ⟨n, rest, nz⟩ cases rest with | nil => simp [op75_parse_subset_aux, hp] at h obtain ⟨rfl, rfl⟩ := h have hs := (op75_parse_nat_sound tail n [] nz hp).1 simpa [op75_subset_encoding] using congrArg (List.cons false) hs.symm | cons b rest => simp [op75_parse_subset_aux, hp] at h | true => cases hp : op75_parse_nat tail with | none => simp [op75_parse_subset_aux, hp] at h | some value => rcases value with ⟨a, rest, nz⟩ cases hq : op75_parse_subset_aux fuel rest with | none => simp [op75_parse_subset_aux, hp, hq] at h | some value => rcases value with ⟨bs, u⟩ simp [op75_parse_subset_aux, hp, hq] at h obtain ⟨rfl, rfl⟩ := h have hs := (op75_parse_nat_sound tail a rest nz hp).1 have hr := ih rest bs u hq rw [op75_subset_encoding_cons, hr, ← hs]