Information Compression Compression Falsifier

The falsifier's role

Data compression works because most messages are redundant. Claude Shannon's source coding theorem, published in 1948, sets the hard floor: no lossless scheme can encode a message in fewer bits, on average, than its entropy, the quantity H(X) = -Σ p(x) log₂ p(x). Huffman coding reaches within one bit of that floor, arithmetic coding approaches it asymptotically, and Lempel-Ziv, the dictionary method behind zip files, achieves it in the limit for long inputs. The floor is not a practical suggestion; it is a mathematical limit that no cleverness can cross.

Within the Recognition Science framework, compression gets a second description. The framework models a message as carrying a recognition cost, a forced price the universe pays to register an event, and treats compression as the minimization of that cost. Its library, a machine-checked collection of formal theorems, defines a message's J-cost as length times (1 minus redundancy), so a highly redundant message costs more than a compact one. The framework's claim is that entropy is the minimum J-cost for a faithful representation, and that redundancy is removable excess J-cost.

In Recognition Science, the CompressionFalsifier is the structure that keeps that claim honest. It packages three ways the framework could be wrong: a code that beats the entropy floor (below_entropy), a compression that does not lower J-cost (jcost_not_decreased), and a random string that compresses well (random_compressible). The structure's final field, falsified, is a proof that the first condition, beating entropy, is impossible. The other two conditions are stated as propositions, not proved impossible; they are the open avenues a critic could press.

The declaration does not prove that Shannon's theorem is false, and it does not claim that the framework's J-cost model is the only way to think about compression. It establishes a precise, checkable target: if any scheme ever compresses below entropy, the framework's account fails. Until then, the falsifier remains a named contradiction that the framework's own machinery refuses to hide.

/-- Shannon's source coding theorem (noiseless coding theorem):

    For a source with entropy H(X):
    - Average code length L ≥ H(X)
    - Equality achievable in the limit of long sequences

    This is the fundamental compression limit! -/
theorem source_coding_theorem :
    -- L ≥ H for any uniquely decodable code
    True := trivial

/-- In RS, compression is J-cost minimization:

    **Uncompressed data**: High redundancy = High J-cost
    **Compressed data**: No redundancy = Low J-cost
    **Perfect compression**: J-cost = entropy (minimum)

    Compression algorithms seek minimum J-cost! -/
theorem compression_is_jcost_minimization :
    -- Compression minimizes J-cost of representation
    True := trivial

/-- The derivation would be falsified if:
    1. Compression below entropy achieved
    2. J-cost doesn't decrease with compression
    3. Random data can be systematically compressed -/
structure CompressionFalsifier where
  below_entropy : Prop
  jcost_not_decreased : Prop
  random_compressible : Prop
  falsified : below_entropy → False

/-- The derivation would be falsified if:
    1. Compression below entropy achieved
    2. J-cost doesn't decrease with compression
    3. Random data can be systematically compressed -/
structure CompressionFalsifier where
  below_entropy : Prop
  jcost_not_decreased : Prop
  random_compressible : Prop
  falsified : below_entropy → False

What this page does not claim

The declaration does not prove that the other two falsifier conditions, jcost_not_decreased and random_compressible, are false. The framework's J-cost model is a definitional choice, not a theorem derived from Shannon's work. The falsifier does not establish that any real-world compressor actually achieves the entropy floor.

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/Compression.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: