Information Channel Capacity Mutual Information Nonneg

What the nonnegativity theorem proves

Mutual information is a quantity from information theory, the branch of mathematics that studies how much one random variable tells you about another. For two variables X and Y, their mutual information I(X; Y) is the reduction in uncertainty about X that comes from knowing Y, measured in bits. The classical result, due to Claude Shannon in 1948, is that this quantity is always nonnegative: learning something about one variable cannot increase your uncertainty about the other. It is zero when the variables are independent, and positive when they are correlated.

The Recognition Science library contains a machine-checked proof of this fact. The declaration mutual_information_nonneg states that for any channel and any input distribution, the mutual information is greater than or equal to zero. A ledger, in this framework a discrete record of events, defines the channel's structure. The proof itself is short: the definition of mutual information in the library is given as a maximum of zero and a sum, so nonnegativity follows immediately from the fact that a maximum is at least as large as either argument.

This theorem is a formal building block, not a new physical claim. It does not assert that mutual information is always finite, nor that it is always achievable in practice. It does not say anything about the channel capacity, the maximum rate of reliable transmission, which is a separate definition in the library. The theorem only establishes the nonnegativity of the quantity as defined, which is a necessary condition for the later development of capacity results.

What the theorem does do is clear the ground. Before the library can prove that channel capacity is nonnegative, it needs to know that the mutual information values being maximized are themselves nonnegative. The capacity_nonneg theorem, which states that the supremum of these values is nonnegative, explicitly uses mutual_information_nonneg as a premise. So this small result is a load-bearing step in the framework's derivation of Shannon's channel capacity from its ledger structure.

/-- **THEOREM**: Mutual information is non-negative. -/
theorem mutual_information_nonneg (ch : Channel) (p : InputDistribution ch.inputSize) :
    mutualInformation ch p ≥ 0 := by
  unfold mutualInformation
  exact le_max_left 0 _

/-- **THEOREM**: Mutual information is non-negative. -/
theorem mutual_information_nonneg (ch : Channel) (p : InputDistribution ch.inputSize) :
    mutualInformation ch p ≥ 0 := by
  unfold mutualInformation
  exact le_max_left 0 _

/-- **THEOREM**: Channel capacity is non-negative.
    This follows from mutual information being non-negative for all input distributions. -/
theorem capacity_nonneg (ch : Channel) : channelCapacity ch ≥ 0 := by
  unfold channelCapacity
  -- The supremum of non-negative quantities is non-negative
  apply le_ciSup_of_le
  · -- Bounded above
    use Real.log (ch.inputSize * ch.outputSize)
    intro x ⟨p, hp⟩
    rw [← hp]
    exact mutual_info_bounded ch p
  · -- Use the uniform distribution
    exact mutual_information_nonneg ch (uniformDistribution ch.inputSize ch.input_nonempty)

What this page does not claim

The theorem does not prove that mutual information is finite. The theorem does not prove that the channel capacity is achievable. The theorem does not derive the value of the fundamental bit rate from first principles.

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