Information Kolmogorov Complexity3 From Jcost Kolmog Complx3 Cert

A certificate with a narrow scope

Kolmogorov complexity measures the length of the shortest description of a string. The Recognition Science framework models the cost of encoding an object with a function J, and this certificate packages three facts about that cost. The certificate is a structure, a container that bundles three proved statements: the cost vanishes when the two inputs are equal, the cost is never negative for positive inputs, and a certain threshold constant is positive. The machine-checked library of formal theorems proves each of these three statements, and the certificate assembles them into one object.

The three facts are general properties of the cost function J, not facts about Kolmogorov complexity itself. The cost function is defined as J(m/e), where m and e are real numbers. The certificate proves that J(r/r) = 0 for any nonzero r, that J(m/e) is nonnegative when m and e are positive, and that phi - 3/2 is greater than zero, where phi is the golden ratio. These are arithmetic properties of a formula, and they hold for any positive real inputs whatsoever.

What the certificate does not do is connect these facts to Kolmogorov complexity. The module defines no notion of a string, a description, or a length. The symbols m and e are just real numbers; nothing in the certificate says they represent a message and its encoding. The research note in the module records that the idea was meant to go further, but the formal content stops at the three general facts. The certificate is a scaffold for a future result, not the result itself.

In Recognition Science, the framework's own account of Kolmogorov complexity would require defining m and e in terms of descriptions and their lengths. The certificate proves the cost function behaves well, but it does not prove that this behavior captures anything about compression. The three facts are necessary conditions for a meaningful cost, not sufficient ones. A reader should take the certificate as a small, verified building block and not as a theorem about information theory.

structure KolmogComplx3Cert where
  cost_at_eq : ∀ r : ℝ, r ≠ 0 → domainCost r r = 0
  cost_nonneg : ∀ m e : ℝ, 0 < m → 0 < e → 0 ≤ domainCost m e
  threshold_pos : 0 < canonicalThreshold

def domainCost (m e : ℝ) : ℝ := Jcost (m / e)

theorem domainCost_at_eq (r : ℝ) (h : r ≠ 0) : domainCost r r = 0 := by
  unfold domainCost; rw [div_self h]; exact Jcost_unit0

theorem domainCost_nonneg (m e : ℝ) (hm : 0 < m) (he : 0 < e) : 0 ≤ domainCost m e := by
  unfold domainCost; exact Jcost_nonneg (div_pos hm he)

theorem canonicalThreshold_pos : 0 < canonicalThreshold := by
  unfold canonicalThreshold; linarith [phi_gt_onePointFive]

def domainCost (m e : ℝ) : ℝ := Jcost (m / e)

What this page does not claim

The certificate does not prove any statement about actual strings, descriptions, or compression. The certificate does not establish that J(phi) is the cost of encoding a regular string. The certificate does not show that incompressible strings have zero cost in any information-theoretic sense.

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