Where the forced fixed point has no host
When the codomain cannot hold the twist's fixed point, the diagonal stops building and starts forbidding: no surjection onto the power set, no definition of truth, no decider for halting, no test for any behaviour a program computes. These are the limitative theorems — and read together they reveal something the textbooks rarely say plainly. Limitation is not a wall but a staircase. Every ceiling is surpassable, but only from above; and the construction that forbids the fixed point at one level is the very thing that builds the next. The limit has no top.
component III of the diagonal · the negative face, isolated and deepened — Cantor and the hierarchy of sizes, Tarski's undefinability of truth, Turing's halting problem and the texture of semi‑decidability, Rice's theorem by way of the recursion theorem, and the unification the others only gesture at: the Turing jump, the arithmetical hierarchy, and limitation as endless stratification
One conditional, run backwards, generates every limit on these pages. When a single twist cannot rest, the naming it would require simply cannot exist — and the diagonal is the explicit proof that it does not.
the contrapositive is the engine Lawvere's theorem says that a point‑surjective naming A → BA forces every twist α : B → B to have a fixed point. Negate the conclusion and the hypothesis falls with it: if even one α has no fixed point, no such naming can exist — for any A. This is the whole of the negative face. A single obstruction in the codomain — a swap with nothing to fix, a negation with no resting value — propagates outward and outlaws reflexivity everywhere it would have appeared. The four great limitative theorems are four readings of this one inference, distinguished only by which fixed‑point‑free twist supplies the obstruction.
the witness is always the same shape The proof of impossibility is never a mere non‑existence claim; it is constructive in the negative. Given any candidate naming φ, the diagonal exhibits an object the naming misses — the anti‑diagonal d, built to differ from φ(a) precisely at the index a, for every a at once. Because d disagrees with each φ(a) at a, it equals none of them; the naming was not onto. Cantor's escaping subset, Turing's contrarian program, the Liar sentence — each is this one d, wearing the costume of its setting. The witness is universal; only the alphabet changes.
the universal anti-diagonal — one witness, four costumes
It is worth marking precisely how the negative face differs from the explosive one to come. Here the fixed‑point‑free twist does not detonate the system; it simply cannot be hosted, and so the structure that would have hosted it — the surjection, the truth predicate, the total decider — is shown not to exist. No contradiction is derived; a verdict is delivered. The diagonal does not break the world but bounds it: it draws the edge past which a certain completeness is impossible. That edge is the ceiling. What the rest of this volume shows is that the ceiling is never the last one — that each verdict of impossibility, examined closely, opens onto a strictly higher level at which the forbidden object reappears as a legitimate one. Limitation conserves; it relocates the fixed point upward rather than abolishing it, exactly as the law of the wider fascicle requires.
The oldest diagonal forbids the simplest naming — a set cannot enumerate its own subsets — and in forbidding it opens an endless ascent of magnitudes. The first ceiling, and the first proof that ceilings recede.
no set numbers its own subsets The twist is the swap on {0,1}, which fixes nothing, so by the contrapositive no map A → 𝒫(A) is point‑surjective: no set surjects onto its power set. The anti‑diagonal is explicit — the set D = {a ∈ A : a ∉ φ(a)} differs from each φ(a) on the question of whether a belongs, so it is named by no a. Since the singleton map a ↦ {a} injects A into 𝒫(A), the verdict sharpens to a strict inequality of magnitudes, |A| < |𝒫(A)| — with no appeal to Cantor–Schröder–Bernstein, because the diagonal is intrinsically about the impossibility of covering.
the ceiling recedes — the cumulative hierarchy One application of the diagonal is one step; iterated, it builds the universe of sets itself. Let V₀ = ∅, Vα+1 = 𝒫(Vα), and Vλ = ⋃α<λ Vα at limits. Each level is strictly larger than the last — that is Cantor's theorem at every step — and the whole, V = ⋃α Vα, is not a set: a universal set would surject onto its own power set, which the diagonal forbids. The same is true of the cardinals. The beth numbers ℶ₀ = ℵ₀, ℶα+1 = 2ℶα climb without bound, each strictly above the last by the theorem. There is no largest set, no largest cardinal, no top. The very first limitative result already exhibits the pattern the whole volume is about: the ceiling is real at every level and final at none.
The hierarchy is endless but not determined, and that under‑determination is itself a limitative phenomenon. Cantor asked where the size of the continuum 2ℵ₀ falls among the ℵ's — is it ℵ₁, the next cardinal above the countable? The continuum hypothesis says yes; Gödel (1940) and Cohen (1963) together showed the standard axioms ZFC can neither prove nor refute it. The staircase has rungs the axioms leave unplaced. Higher still, the large cardinals — inaccessible, measurable, and beyond — are sizes so vast that the hierarchy below one of them already models all of set theory: an inaccessible κ gives Vκ ⊨ ZFC, a self‑contained universe. Their existence cannot be proved from ZFC — for to prove it would be to prove ZFC consistent, which the second incompleteness theorem forbids. These cardinals are, in effect, demands for more reflexivity than the axioms can certify, and they line up by exactly the consistency strength that incompleteness measures. The hierarchy of sizes and the hierarchy of provability turn out to be the same ladder, seen from two ends.
A language rich enough to talk about its own sentences cannot define its own truth — and the proof is the Liar, read not as a paradox to be solved but as a fixed‑point‑free twist that forces a predicate out of existence.
the undefinability theorem Suppose arithmetic could define its own truth — a formula True(x) with True(⌜φ⌝) ↔ φ for every sentence φ, the T‑schema. Coding makes the system reflexive, so the diagonal lemma applies to the predicate ¬True(x) and produces a sentence L ↔ ¬True(⌜L⌝) — the Liar. Combine the two equivalences: True(⌜L⌝) ↔ L ↔ ¬True(⌜L⌝), an outright contradiction. The only premise to reject is the one that was optional: no such True exists. Truth is not arithmetically definable. This is Lawvere with B the truth‑values, α negation — fixed‑point‑free — and the codomain the genuine article: because True would obey the T‑schema, its fixed point could not be quietly absorbed, so the predicate itself is forbidden.
truth, too, is a staircase Tarski's resolution was not to abandon truth but to stratify it. The truth of sentences in a language L is undefinable within L, but perfectly definable in a richer metalanguage L′ that contains L and can quantify over its sentences. Truth for L′ then needs a higher L″, and so on up an endless hierarchy of languages, each defining the truth of those below and never its own. The Liar cannot be written because "true" always means "true‑in‑the‑language‑below," and the sentence that would refer to its own level has no level to refer to. Here is the same recession as Cantor's: a thing forbidden at every level is available at the next, and the forbidding is what generates the next. Truth has no top.
This is the precise hinge between limitation and incompleteness, and it deserves to be stated sharply. Truth is undefinable; provability is definable. The provability predicate Prov(x) — "x codes a theorem" — is a perfectly good Σ₁ formula of arithmetic, and the diagonal applies to ¬Prov exactly as it does to ¬True. Why does one detonate and the other survive? Because Prov does not satisfy the T‑schema. It obeys only the weaker derivability conditions — provable sentences are provably provable, and provability respects implication — but not Prov(⌜φ⌝) → φ, internal soundness. The Liar over truth gives a contradiction; the "Liar" over provability gives Gödel's sentence, which lands not as a contradiction but as a sentence that is true and unprovable. The fixed‑point‑free twist is the same; the codomain's strength is different, and that difference is the entire distance between "truth cannot be named" (this volume) and "proof cannot be completed" (the volume on incompleteness). The two are one diagonal divided by one schema.
No program decides which programs halt — the same diagonal, now over the truth‑values of termination. But the impossibility is not flat: halting is verifiable though not decidable, and that asymmetry is the first grain of a much finer structure.
the halting problem Suppose a total computable H(e, x) decided whether program e halts on input x. Build the contrarian D: on input e, run H(e, e) and do the opposite — loop if it says "halts," halt if it says "loops." Then D(⌜D⌝) halts exactly when H says it does not. The contradiction kills H. This is Lawvere once more: the codomain is {halts, loops}, the twist is the swap — fixed‑point‑free — and the reflexivity is the stored‑program principle, since D must be handed its own code. A total halting decider is a naming the swap forbids.
verifiable, not decidable — the Σ₁/Δ₁ gap What kind of impossibility is this? Not the flat kind. The halting set K = {e : φe(e)↓} is semi‑decidable: to confirm that a program halts, run it and wait — if it halts, you will see it. What you cannot do is confirm non‑halting, for no finite observation rules out a later stop. In the language of the hierarchy, K is Σ₁ — definable as "∃ a halting computation" — but not Π₁, so not decidable (Δ₁ = Σ₁ ∩ Π₁). Its complement, non‑halting, is Π₁ and not Σ₁. The undecidable is textured: a problem can be confirmable‑but‑not‑refutable, refutable‑but‑not‑confirmable, or neither — and exactly which determines how far above the decidable it sits.
the first floor of the hierarchy — verifiable, refutable, decidable
Halting is not one pathological question among many. By Rice's theorem, every non‑trivial property of the function a program computes is undecidable — and the proof routes the diagonal through the recursion theorem of the previous volume.
the theorem Distinguish a program's syntax — how it is written — from its semantics — the partial function φe it computes. A property is semantic, or extensional, if it depends only on φe: any two programs computing the same function have it or lack it together. Rice's theorem (1953) is absolute: every semantic property that is neither always true nor always false is undecidable. Whether a program halts on all inputs, ever outputs 0, computes a total function, computes the constant 0, matches a given specification — none can be decided. The only testable semantic properties are the two trivial ones, true of every program or of none.
Rice's theorem partitions properties cleanly. Syntactic properties — "has fewer than a hundred symbols," "contains a loop," "halts within a thousand steps" — are about the program e as a string and are routinely decidable. Semantic properties — about the function φe — are, if non‑trivial, never decidable. But the undecidable semantic properties are themselves stratified, and the Rice–Shapiro theorem draws the next line: a semantic property is even semi‑decidable (Σ₁, recognisable in the limit) exactly when it is determined by finite sub‑functions — when φe has it iff some finite part of φe already does. "φe(5)↓" passes this test and is Σ₁; "φe is total" fails it and is not even semi‑decidable — it is Π₂, two full quantifier alternations above the decidable. Which is the cue for the structure the next section makes explicit: the undecidable is not a region but a ladder.
Here the volume turns. The halting problem is not a single barrier but the first step of an operation that repeats without end — and that operation, the Turing jump, is the diagonal lifted from a one‑off construction to a machine that builds the whole hierarchy of the unsolvable.
relativise, and iterate Give a machine an oracle — free answers to membership in a fixed set A — and ask the halting question of these stronger machines. The set of oracle programs that halt on their own code, A′ = {e : ΦeA(e)↓}, is the Turing jump of A. The same diagonal that defeated the unrelativised decider defeats the relativised one: A can confirm halting in its own oracle but cannot decide it, so A <T A′ strictly. The jump is exactly the diagonal made into an operator on degrees of difficulty — and operators can be iterated.
the jump ladder — click a rung
the climb has no last rung Above the finite jumps stands ∅(ω), the effective join of them all — strong enough to settle every arithmetical question, and Turing‑equivalent to true arithmetic, the set of all true sentences of ℕ. Yet even it has a jump, ∅(ω+1), strictly harder; and the tower continues up the computable ordinals, then past them, the diagonal forging a strictly higher degree at every successor and a join at every limit, without end. Beyond the arithmetical lies the analytical hierarchy, where the quantifiers range over functions and sets rather than numbers — Σ1n — and beyond that the structure of the Turing degrees in its full, intricate vastness. There is no greatest degree, no hardest problem, no final ceiling. The diagonal that forbids one completeness is the engine that manufactures the next, forever.
Read together, the limitative theorems are not four walls but four staircases — and they are the same staircase. The construction that forbids a fixed point at each level is precisely what builds the level above, where the forbidden object returns legitimised.
the common form Cantor's sizes, Tarski's languages, the arithmetical definability classes, the tower of Turing jumps — four times now the same shape has appeared. At each level a diagonal forbids a certain completeness: a set cannot enumerate its subsets, a language cannot define its truth, a level cannot decide its own halting. And each time the forbidding is generative: the power set is the next cardinal, the metalanguage is the next truth, the jump is the next degree. The object impossible at level n is the ordinary furniture of level n+1. Limitation, examined closely, is never a single edge. It is an endless ascent in which every step is both a ceiling and a floor.
conservation, in the negative This is the law of the wider fascicle, read on its limitative face. The diagonal never abolishes the forced fixed point; it relocates it. In the positive settings the relocation is sideways — into a divergent computation, an undecided sentence, a half‑truth. In the limitative settings it is upward: the fixed point forbidden at one level — the surjection, the truth predicate, the decider — is exactly what the next level supplies. So the impossibility is conserved as an ascent. The cardinal you cannot reach, the truth you cannot define, the problem you cannot decide: each exists, one storey up, and the proof that it cannot exist here is the same construction that places it there. The ceiling is not a denial of the fixed point. It is the fixed point, receding — and because the diagonal can always be applied once more, it recedes without limit. There is no top, only the next floor, and the staircase the diagonal climbs is the true shape of every limit on these pages.
One inference underlies every limit: a twist that cannot rest forbids the naming that would have hosted it. From it follow the strict hierarchy of sizes, the undefinability of truth, the unsolvability of halting, and the untestability of everything a program does — four verdicts of impossibility, each the same diagonal over a different codomain. And read together they say more than any one of them alone: the verdict is never final. Iterate the diagonal and it becomes the jump, the operator that turns each impossibility into the floor of the next, climbing the cardinals, the languages, the definability classes, and the degrees in a single endless ascent. The forbidden object is never destroyed; it is lifted one level beyond reach, where it waits as the ordinary furniture of a larger world. d ≠ φ(a) at every a is the witness that the ceiling is real — and the proof, applied once more, that it has no top.