Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The zero-error capacity of the route/survival channel is 000

Proved
TranscendenceTower.InformationTheory.zero_error_capacity

by mateoej12 · Sep 8, 2026 · Mathlib 0df444a (Lean v4.33.1)

contextformalizationinformation-theorylogicnonmonotonic-reasoning
zero-error capacity=0,whilemax⁡qI(X;Y)=log⁡54>0.\text{zero-error capacity} = 0, \qquad\text{while}\qquad \max_q I(X;Y) = \log\tfrac54 > 0 .zero-error capacity=0,whileqmax​I(X;Y)=log45​>0.

For the route/survival channel, no code of any blocklength carries more than one message without the possibility of error. Consequently every zero-error code has rate 000, and the zero-error capacity of the channel is exactly 000 — even though its one-use mutual information has a strictly positive maximum.

The reason is a single observation about the channel's support. Both routes admit survival, so the all-survive word (true,…,true)(\mathsf{true},\dots,\mathsf{true})(true,…,true) has positive probability under every input word. A decoder that is never wrong must therefore return the same message for every codeword, which leaves room for only one. No observation ever rules any input out.

The statement has four parts: that every zero-error code satisfies M≤1M \le 1M≤1 and has rate 000; that a one-message zero-error code exists, so the bound is attained rather than vacuous; that the all-survive word is possible under every input word, which is the mechanism; and that the comparison quantity log⁡(5/4)\log(5/4)log(5/4) is strictly positive, so the gap between the two capacities is real.

Interpretation. Read as a statement about auditing rather than transmission, this says that an observer watching which facts survive can never be certain which resolution the system applied, at any number of observations. Positive one-use information means the resolution leaves a trace; zero zero-error capacity means that trace never amounts to proof.

Limits. Nothing here is asymptotic, and no claim is made about how quickly confidence can approach certainty; that is an achievability question and is not addressed.

Preamble
import Definitions.Def_TranscendenceTowerZeroError

set_option autoImplicit false

open scoped BigOperators
open TranscendenceTower TranscendenceTower.ContextTheories TranscendenceTower.Lifting
open TranscendenceTower.InformationTheoryPlatform
open TranscendenceTower.InformationTheoryCapacityPlatform
open TranscendenceTower.ZeroErrorPlatform
Formal statement
theorem TranscendenceTower.InformationTheory.zero_error_capacity :
    (∀ n M : ℕ, ZeroErrorCode n M → M ≤ 1 ∧ codeRate n M = 0)
      ∧ (∀ n : ℕ, Nonempty (ZeroErrorCode n 1))
      ∧ (∀ (n : ℕ) (x : Fin n → Route), Possible n x (allSurvive n))
      ∧ 0 < Real.log (5 / 4) := by sorry
Source
Mateo Estrada, Harmless and Pointless: Consistency, rigidity, and the indeterminacy of context transfer in McCarthy's formalization of context, 7 September 2026, Section 8.2 (The auditor's reading, and the failure of certainty), Theorem 16.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me