Identifier
F:fo-formula-decoder
Proof route
Not assigned
External status
proved
Axiom footprint
Empty

Recorded description

FO.Formula.decode : Nat -> FO.Formula, which is decodeAux n n -- the code is its own fuel -- inverts the Goedel numbering: decode (code p) = p for every formula p. STILL NOT PROVED, and the reason changed. The FUEL-ADDITIVE round trip IS now proved (F:fo-formula-decode-code, F:fo-term-decode-code): decodeAux (Nat.add f (size p)) (code p) = p for every f. What that does NOT give is the self-fuelled wrapper, which would need Nat.le (size p) (code p) -- and that statement is FALSE, measured: FO.Formula.code FO.Formula.bot and FO.Term.code (FO.Term.var 0) are both Nat.zero while both sizes are 1, pinned by Kernel::def_eq in fo_roundtrip/tests.rs::size_is_not_bounded_by_the_code. So ADR-1640's item (3) is not an unproved lemma but a refuted one, and the remaining route is different work: a strong induction on the code using Nat.lt (FO.Code.snd n) n -- true, because FO.Code.pair a b is strictly larger than b -- which needs monotonicity of FO.Code.tri, a Nat.lt development on top of it, and a well-founded Nat recursion. That is a slice, not a step, and it buys only the removal of one Nat argument from four statements, which is why this lane routed every downstream theorem through fuel-explicit siblings (FO.Code.substCodeAux, FO.Code.isFormulaCodeAux, FO.Code.diagAux) instead.

Formal statement
theorem FO.Formula.decode_code_self_fuelled : ((x0 : FO.Formula) -> Eq.{1} FO.Formula (FO.Formula.decode (FO.Formula.code x0)) x0)

Dependencies

The graph shows direct ledger edges. Follow a node to open its artifact page.

Evidence

Provenance

{
  "date": "2026-09-05",
  "curation": "curated",
  "established_by": "not established in this ledger",
  "source": "this row records the measured remaining gap after lane arithmetization landed the numbering, its injectivity and the decoder CONSTRUCTION (W3-7, ADR-1640)",
  "prior_art": [
    {
      "who": "Kurt Goedel",
      "what": "arithmetization of syntax, in which decoding is done by primitive-recursive functions built from a pairing's projections",
      "year": 1931,
      "where": "Goedel, 'Ueber formal unentscheidbare Saetze der Principia Mathematica und verwandter Systeme I', Monatshefte fuer Mathematik und Physik 38 (1931)",
      "attribution": "standard textbook attribution; this lane did not consult the primary source"
    }
  ]
}