Incompleteness as an information bound
The collection has met incompleteness twice — in The Box and The Staircase as the syntactic limit of proof, and in The Latitude as the semantic looseness of description. Both descend from the diagonal wearing the Liar's mask: self-reference about truth. But the diagonal has an older relative the collection has never opened — Berry's paradox, self-reference about definability — and from it comes a third incompleteness, unlike either. It is not a single unprovable sentence but a quantitative bound: a formal theory can certify that an object is complex only up to roughly its own information content, and not a bit beyond. Incompleteness, in this face, is a conservation law — a theory cannot prove out more information than its axioms carry. And the limit has a face, the most extraordinary number in the subject: Chaitin's Ω, which is random, encodes the whole halting problem, and is legible to no theory past its complexity. There is a horizon on what can be proved, and it sits at the prover's own information content.
the third face · the measure · Berry's bound · the number that knows · the information bound · where the corpus stands
Two faces of incompleteness now stand on the record. The Box and The Staircase took the syntactic face — Gödel's true-but-unprovable sentence, the limit of proof, climbed as an ordinal tower. The Latitude took the semantic face — and found it a separate root, the looseness of first-order description. This descent finds a third, and unlike the semantic it is the diagonal's own. The collection's diagonal has always been told in the key of the Liar: a sentence that speaks of its own truth or provability, and in folding, leaves a true claim unproved. But there is a second classical paradox in the same family, turning not on truth but on definability — Berry's — and when it is formalized it yields an incompleteness of an entirely different character: not qualitative but quantitative, not one sentence escaping proof but a hard ceiling on a whole quantity, the complexity a theory can certify. The diagonal, it emerges, generates incompleteness through more than one predicate, and each predicate gives a different shape of limit. This is the shape the collection has never drawn.
Gödel's incompleteness is the Liar made arithmetic. There is a sibling result, just as deep, that is instead Berry's paradox made arithmetic — and it limits not truth but information.
Recall how Gödel's theorem is the diagonal in the Liar's form. The Liar — "this sentence is false" — turns on a self-referential predicate of truth; arithmetized through the provability predicate, it yields a sentence asserting its own unprovability, true and unproved. Tarski's undefinability is the same paradox sharpened. This is the diagonal the collection has mapped at length: self-reference about truth and provability.
Now take a different member of the paradox family. Berry's paradox considers the phrase "the smallest positive integer not definable in under sixty letters." That phrase has under sixty letters and appears to define such an integer — so the integer is and is not definable in under sixty letters. Where the Liar turns on truth, Berry turns on definability: on the relation between an object and the descriptions that name it. It is unmistakably of the diagonal's family — a naming predicate applied across its own range — but it is a different predicate, and formalizing it requires not a truth predicate but a precise, objective notion of how short a description an object admits.
Gödel formalized the Liar (truth) and got a single sentence that is true but unprovable — a qualitative limit. Chaitin formalized Berry (definability) and got something else: a quantitative limit, a bound on the complexity a theory can certify. Same construction — a naming predicate folded on itself — in two different predicates, yielding two different shapes of incompleteness. The collection has drawn the first shape. The second needs the objective measure Berry's "definable in N letters" was groping toward.
That measure is the central object of algorithmic information theory, and with it Berry's loose talk of "definable in sixty letters" becomes exact. It is worth meeting on its own terms before the incompleteness falls out of it, because the measure is what makes this face of the limit quantitative — and what turns incompleteness, in the end, into a law about information.
Berry's "definable in sixty letters" becomes exact when "description" is read as "program." The information content of an object is the length of the shortest program that produces it — and a simple count shows almost everything is incompressible.
This is what Berry's phrase wanted and natural language could not supply. "Definable in under sixty letters" is hopeless — natural language is vague, and the predicate "definable" is exactly the one Tarski showed cannot live inside the system. "Computable by a program of under sixty bits" is precise, mechanical, and internal to arithmetic. With it, "the complexity of x" is a definite number, and the question of how compressible the objects of mathematics are becomes a theorem rather than a riddle. The first theorem is a counting argument, and it is decisive.
An incompressible string is the precise notion of a random one: a string with no description shorter than itself has no pattern, no regularity, nothing to exploit — randomness defined not by probability but by the absence of compression. And the count says randomness is the rule. Almost every string is random; the compressible ones — the ones with short descriptions, the ones mathematics can name and reason about — are a vanishing minority. This is already a quiet warning. The objects a theory can get hold of are the low-complexity ones; the high-complexity ones, which are almost all of them, are nameless. The question is whether a theory can at least certify that a given object is one of the random many — whether it can prove "x is incompressible." The answer is the third face of incompleteness, and it is sharp.
Almost every object is incompressible — yet a formal theory can certify incompressibility only up to a fixed ceiling, set by the theory's own information content. Above that line the truth is uniform and unprovable. The line is the horizon.
The theorem is Chaitin's, from the early 1970s, and it is the formalization of Berry's paradox exactly as Gödel's is the formalization of the Liar.
The proof is Berry's paradox, mechanized. Suppose, for contradiction, that T proves K(x) > L for arbitrarily large L. Write a program P that does the following: it enumerates the theorems of T in order, watching for the first theorem of the form "K(x) > m" for a specific object x and a number m exceeding the length of P itself; when it finds one, it outputs that x and halts. Now P is a program — of length about L, since it need only encode T's axioms and the threshold — that produces an object x with K(x) > L. But then x has a description of length ≈ L, namely P, so K(x) ≤ L — contradicting the very theorem P found. The object P outputs is precisely Berry's: "the first object provably too complex to be named by a program this short," named by a program that short. The contradiction shows T can prove no such theorem above its own size.
One honesty note, in the collection's discipline. Proofs of incompleteness through Berry's paradox are often advertised as avoiding the diagonal — no self-referential sentence is built, only a self-limiting program. The advertisement is half true and worth getting right. No Cantor anti-diagonal appears; but the self-reference has not vanished, it has moved into the program P, which speaks of its own length and the bound it hunts — a thing referring to itself as surely as any Liar — and the construction can be recast as a diagonal argument outright. So this is not a limit from outside the diagonal's family. It is the diagonal in Berry's predicate rather than the Liar's: self-reference about complexity instead of truth, yielding a limit on information instead of a limit on proof.
The bound has an emblem: a single real number that is perfectly random, compresses the entire halting problem into the least possible space, and is legible to no theory beyond the theory's own complexity. It is the most informative — and most opaque — number in mathematics.
Fix a prefix-free universal machine — one whose valid programs are self-delimiting, so no program is a prefix of another. Chaitin's number is the probability that such a machine, fed a stream of fair coin flips, eventually halts:
Hold the two properties together, because their combination is the whole marvel. Ω is omniscient about halting — its bits settle Turing's undecidable problem, and through it the countless number-theoretic questions (Goldbach, Riemann, and the rest) that reduce to whether some program halts. And Ω is random — its bits form a patternless sequence with no description shorter than itself, the very image of incompressibility. It is a number that knows the answer to every halting question and tells it in a form from which nothing can be extracted without already knowing it: the answers are all there, packed at the theoretical maximum density, and packed that tightly they are indistinguishable from noise. The crystallized essence of the halting problem is a random number.
And now Chaitin's bound lands on it with full force. Because the first n bits of Ω have complexity ≈ n, knowing them is certifying an object of complexity n — so a theory of complexity L can prove the value of at most about L bits of Ω, and no more. Most of Ω is not merely unknown but unprovable: its digits are true, definite, and forever past the theory's reach. Solovay sharpened this to the limit — for suitable theories and encodings, there is a single Ω of which the theory cannot prove even one bit. The horizon is not an abstraction. It is a specific number, mostly invisible, sitting just past where any given mathematics can see.
One curiosity the collection cannot let pass. This Ω — the halting probability, random and omniscient — shares its letter with the Ω of The Coil, the hyperset Ω = {Ω}, the innocent circle. Two of the deepest objects the collection has met wear the same name: one the productive fixed point of self-reference, the other the incompressible residue of the diagonal. The coincidence is only notation — but it is a fitting one, the two faces of the collection's whole subject, the circle that builds and the bound that cannot be crossed, signed with a single letter.
Set the two incompletenesses side by side and the structure resolves: one construction, told in two predicates, giving two shapes of limit — and the second shape is a conservation law. Mathematics cannot manufacture information.
The diagonal generates incompleteness through whichever naming predicate it is fed, and the predicate determines the shape of the limit. Two predicates, two shapes:
Self-reference about truth and provability. The diagonal yields a single sentence asserting its own unprovability — true, and unproved. A qualitative limit: one designated truth escapes the system. The shape is a missing sentence.
Self-reference about definability and complexity. The diagonal yields a ceiling: no object can be certified more complex than the theory itself. A quantitative limit, uniform over almost all objects. The shape is a horizon.
That reading is the deepest thing the horizon has to give. Why can a theory of complexity L not prove any object more complex than L? Because a proof transmits information, and a theory is a finite object with finite information content — about L bits, the size of its axioms and rules. To prove "K(x) > L" would be to certify, from L bits of axioms, that some specific object carries more than L bits of irreducible information — to extract more information from the theory than the theory contains. This is forbidden not by a clever construction but by a conservation principle: a formal system's theorems carry no more information than its axioms. You cannot prove a twenty-bit theorem from ten bits of assumptions. Incompleteness, in this face, is not an accident or a pathology — it is the impossibility of creating information from nothing, the diagonal's discovery that mathematics is complexity-bounded.
This recasts the entire limitative inheritance in a new light. Gödel's missing sentence looked like a curious gap, a single truth that happened to fall through. Chaitin's horizon shows the gap was never an accident: a theory can reach exactly as far as its information content and no further, and since almost every object carries more information than any fixed theory, almost every truth about complexity lies beyond reach — not by bad luck but by conservation. The incompleteness is not that something slipped through. It is that the axioms were finite, and the truths are not.
The horizon extends the collection's reach and deepens its claim at once. The diagonal does not manufacture a single incompleteness; it manufactures one for every naming predicate it is fed — and the information-theoretic one carries the deepest reading of why the limit was never escapable.
Set the finding in the collection's discipline of saying just what is shown. The diagonal generates incompleteness not once but once per predicate. Fold the predicate of truth — the Liar — and it yields Gödel's single unprovable sentence, the qualitative hole the collection has mapped at length. Fold the predicate of complexity — Berry — and it yields Chaitin's uniform ceiling, a quantitative bound the collection had never drawn. These are not two subjects but one construction read through two paradoxes, and the collection's reach therefore extends past logic and computability into algorithmic information theory, where the same diagonal is found doing the same work in a new key.
The honesty note from §III must travel with the claim, because it is where this descent is most easily overstated. Chaitin's incompleteness is routinely presented as the route to Gödel's theorem that dispenses with self-reference — no sentence speaks of itself, only a program that limits itself. The accurate statement is narrower: no Liar sentence and no Cantor anti-diagonal are built, but the self-reference has merely changed address, lodging in the program that reasons about its own length, and the whole argument can be rewritten as a diagonal outright. So Berry's incompleteness is not evidence against the collection's thesis but a case of it — the diagonal in the complexity predicate, not an escape from the diagonal. The thesis survives the apparent counterexample, in the precise and slightly humbled form the collection has learned to state: what underlies the limit is self-reference in the broad sense, the fixed-point structure, of which a Liar sentence and a self-limiting program are two faces.
And the information-theoretic face gives back something the syntactic one could not: an account of why. Gödel's missing sentence, taken alone, can look like a contrivance — a formula built on purpose to be unprovable, a curiosity at the edge of mathematics. Chaitin's horizon shows the unprovability was never contrived and never at the edge. A formal theory is a finite object carrying finite information, about L bits; its theorems carry no more information than its axioms; and to certify an object more complex than L would be to extract more information than the theory holds — forbidden by conservation, not by cleverness. Since almost every object is more complex than any fixed theory, almost every truth about complexity is unprovable, not by accident but by the finitude of the axioms against the infinitude of the truths. Incompleteness is not that something slipped through a particular system. It is that information is conserved, and the axioms were finite.
So the horizon takes its place beside the descents around it, and the pattern they make is consistent. The Latitude found the collection to be the theory of one of two roots of limitation; The Coil found it the theory of one of two faces of self-reference; the horizon finds that the diagonal's own incompleteness is not one limit but a family, one shape per predicate, of which the collection had drawn a single member. In every case the diagonal is larger and more various than the grandest single reading supposed, and in every case the collection holds a real and load-bearing part of it — here, the engine that, fed any predicate of naming, returns a limit, and fed the predicate of complexity, returns the law that mathematics cannot prove more than it weighs. The collection is the theory of that engine. The horizon is the engine's reach into information, and the reading it brings back is the simplest and hardest the collection has found: a theory sees exactly as far as its own information content, and the truths run on past it, where Ω sits, random and complete and unreadable, just over the line.
Mathematics reaches exactly as far as its information content; the truths are heavier than the axioms; and the rest is conserved beyond reach. Ω sits just past the horizon — random, complete, and unread.