Rate-Distortion Theory for Deductive Sources under Closure Fidelity
This work formulates deductive compression as a structured source coding problem, offering theoretical foundations for communication systems that leverage shared inference, but remains theoretical and domain-specific.
The paper studies lossy compression of finite statement sources in a deductive environment, where fidelity is measured by preservation of deductive closure. It shows that the rate-distortion function depends only on the core of the source, and provides exact characterizations for zero-distortion and bounded inference steps.
We study lossy compression of a finite statement source generated in a fixed deductive environment. The source symbols are statements in a knowledge base endowed with a proof system, and reconstruction fidelity is measured by preservation of deductive closure rather than by symbolwise equality. This induces, once the proof system and canonical order are fixed, a decomposition of the source into an irredundant core and redundant stored consequences. Under a natural disjointness condition on zero-distortion reconstruction sets, we show that the minimum zero-distortion rate equals the source mass of the core times the entropy of the source conditioned on that core. For reconstruction alphabets contained in the deductive closure of the source knowledge base, we further prove that the full rate-distortion function depends only on the core, so redundant states are invisible to both rate and distortion. When the decoder is limited to a bounded number of inference steps, we obtain an exact fixed depth rate-delay-distortion characterization. Under an additional order-robustness assumption identifying the chosen core with the order-free essential set, this characterization interpolates between classical symbolwise compression and unconstrained deductive compression. These results formulate deductive compression as a structured source coding problem and quantify how shared inference structure changes the fundamental limits of communication.