Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Zero-error codes for the route/survival channel

Definition
TranscendenceTowerZeroError

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

contextformalizationinformation-theorylogicnonmonotonic-reasoning

Zero-error coding for the finite route/survival channel.

The underlying channel has two inputs. A fact transferred directly always survives; a fact transferred through an intermediate context survives with probability one half. Writing KnK_nKn​ for the nnn-fold memoryless product of that channel, this bundle adds the notions needed to ask whether the route can ever be recovered with certainty rather than merely on average.

A code of length nnn carrying MMM messages is an encoder e:{1,…,M}→{direct,viaMid}ne:\{1,\dots,M\}\to\{\mathsf{direct},\mathsf{viaMid}\}^{n}e:{1,…,M}→{direct,viaMid}n together with a decoder ddd on output words. It is a zero-error code when the decoder is correct on the entire support of each codeword:

Kn(e(m),y)>0  ⟹  d(y)=m.K_n(e(m), y) > 0 \;\Longrightarrow\; d(y) = m .Kn​(e(m),y)>0⟹d(y)=m.

The bundle also names the rate log⁡M/n\log M / nlogM/n, in nats per channel use, and the all-survive output word.

Formalization note. The zero-error condition is stated as a support condition rather than as an error probability equal to zero. The two agree, but the support form mentions no probability measure and makes the argument finite combinatorics: what matters is only which output words a codeword can produce, not how often.

Definition code
/-
Zero-error coding for the finite route/survival channel.

A zero-error code is formulated as a support condition rather than as an
error probability equal to zero: the decoder must be correct on every output
word the codeword can actually produce.  No probability appears in the
definition, only the support of the product channel.

Definitions only; every claim about these objects is proved in the theorem
that imports this bundle.
-/

import Definitions.Def_TranscendenceTowerChannelCapacity

set_option autoImplicit false

open scoped BigOperators
open TranscendenceTower TranscendenceTower.ContextTheories
  TranscendenceTower.Lifting
open TranscendenceTower.InformationTheoryPlatform
open TranscendenceTower.InformationTheoryCapacityPlatform

namespace TranscendenceTower.ZeroErrorPlatform

noncomputable section

/-- `y` is a possible observation when the input word `x` is transmitted:
the product channel assigns it positive mass. -/
def Possible (n : ℕ) (x : Fin n → Route) (y : Fin n → Bool) : Prop :=
  0 < blockChannel n x y

/-- The output word on which every fact survives. -/
def allSurvive (n : ℕ) : Fin n → Bool := fun _ => true

/-- A block code of length `n` carrying `M` messages whose decoder is never
wrong: every output word that can actually arise from codeword `m` is decoded
back to `m`. -/
structure ZeroErrorCode (n M : ℕ) where
  /-- The encoder, sending each message to an input word. -/
  enc : Fin M → (Fin n → Route)
  /-- The decoder, reading an output word back to a message. -/
  dec : (Fin n → Bool) → Fin M
  /-- Correctness on the whole support of each codeword. -/
  correct : ∀ m y, Possible n (enc m) y → dec y = m

/-- Rate of a length-`n`, size-`M` block code, in nats per channel use. -/
def codeRate (n M : ℕ) : ℝ := Real.log M / n

end

end TranscendenceTower.ZeroErrorPlatform
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