Information Compression Prior Prior Holds

The compression prior

Compression is the art of describing something with fewer symbols than the obvious listing. The classical minimum description length (MDL) principle says the best model for data is the one that yields the shortest total description: the model plus the data encoded under it. In the Recognition Science framework, this principle becomes a precise claim about a universal cost function.

The framework defines a ledger, a discrete record of events, and assigns each event a cost. A theorem in the framework's machine-checked library of formal theorems, named prior_holds, proves that the MDL prior equals the universal cost function J. In plain terms: the cost of encoding an event with n possible outcomes is J(n) = (n + 1/n)/2 - 1. This function is not arbitrary; it is the unique cost forced by the framework's axioms. The theorem states that for any model, the MDL prior is exactly this J, not an approximation.

This result is a formal identity within the framework. It does not claim that J is the optimal compressor for any practical data set, nor that real-world compression algorithms should be replaced by it. It does not claim that the framework's axioms are the only way to derive MDL. The theorem is a bridge: it connects a general principle (MDL) to a specific mathematical object (J), and that connection is what the framework proves.

/-- Theorem: φ-prior holds as unique MDL from T5 J-unique. -/
theorem prior_holds : ∀ model, mdl_prior model = Cost.Jcost := by
  intro model
  simp [mdl_prior]

noncomputable def mdl_prior (_model : Cost.SymmUnit (fun x => x)) : ℝ → ℝ := Cost.Jcost

-- Universal coding: length = J( complexity ) for recognition events

What this page does not claim

The theorem does not claim J is the optimal compressor for any real data set. It does not claim the framework's axioms are the only way to derive MDL. It does not claim the framework's library is a general-purpose proof assistant.

Verify this page

Every tagged claim above names its theorem. To check one yourself rather than trust this page, elaborate the source module with Lean 4 and audit its axiom basis:

$ lake env lean IndisputableMonolith/Information/CompressionPrior.lean
expected axiom basis: [propext, Classical.choice, Quot.sound] (the Lean kernel's standard three; no RS-specific axioms)

A page whose claims cannot be reproduced this way does not ship. In production, every anchor links to the exact declaration in the public source release, and this block carries the build receipt for the page itself.

Derived articles

This page is generated by a question-recursion engine: the questions its answers raise become the next pages. The current agenda, with open targets marked red: