math.LO — Logic
Algorithmic and Provable Precision of Monotone Approximations
We study how much information is needed to approximate a monotone limit and when arithmetic can prove that a finite approximation is accurate. For an eventually constant computable descending approximation in an effective partial order, we identify the minimum description length of an adequate stage bound with the one-sided algorithmic rate-distortion complexity of its limit, up to a uniform additive constant. For integer limits, this is also the complexity of a coarse quotient. Finite proof maxima give normal forms for bounded reflection and refutation completeness, and determine every provably sufficient budget. Under soundness for the positive and negative threshold families and refutation completeness at the chosen rank, the least provable error is the difference between the true threshold and its greatest provable lower bound. This difference retains the joint information in two opposing monotone limits. Chaitin counts give matching precision and Busy Beaver bounds, including a maximum law for finitely many fixed reference machines. We also obtain sharp advice bounds for variable certificate presentations, fixed-rank refutations over a finite arithmetic base, an elementary verified selector for bounded positive reflection under explicit proof-presentation assumptions, and resource bounds for proof translation.