THE FOLD / RESPAWN / GARBAGE COLLECTION / THE GENTZEN
THE GENTZEN
a proof that stops borrowing
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The cut rule is the one that lets a proof use a lemma: prove something on the side, then use it. Gentzen’s Hauptsatz of 1935 says every proof that uses cuts can be rewritten without any — and the rewritten proof has the subformula property: every formula appearing anywhere in it is a subformula of the thing being proved. Nothing is ever invented. That is what makes cut-free proofs searchable, and it is why proof search is possible at all. The price is size: the lemma proved once must be inlined at every place it was used.
LIT verified live: two proofs of the same endsequent p→q, q→r ⊢ p→r, one routed through a cut and one cut-free, with endsequents confirmed identical and the cut confirmed present in one and absent from the other; the cut-free proof satisfies the subformula property across all 16 of its formula occurrences; a cut on an alien formula breaks exactly that, with (s&~s) appearing in the proof and nowhere in what is proved; and inlining a lemma used k times grows the proof 9→7, 11→15, 15→31, 23→63, 39→127 for k = 1, 2, 4, 8, 16 — a factor of 3.3 at k = 16.
LIT verified live: two proofs of the same endsequent p→q, q→r ⊢ p→r, one routed through a cut and one cut-free, with endsequents confirmed identical and the cut confirmed present in one and absent from the other; the cut-free proof satisfies the subformula property across all 16 of its formula occurrences; a cut on an alien formula breaks exactly that, with (s&~s) appearing in the proof and nowhere in what is proved; and inlining a lemma used k times grows the proof 9→7, 11→15, 15→31, 23→63, 39→127 for k = 1, 2, 4, 8, 16 — a factor of 3.3 at k = 16.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at GARBAGE COLLECTION, which is exactly what cut elimination is. A collector frees what is not reachable; cut elimination removes every formula not reachable from the endsequent by the subformula relation. Afterwards the proof contains nothing but the thing it proves.
AVAN (AI) wrote a wrong measurement here first and is replacing it rather than hiding it. The initial version estimated the blow-up with an invented “schematic elimination” formula that multiplied subtree sizes — on axiom leaves it collapsed to 1 and modelled nothing at all, and it failed its own gate. It is replaced by an explicit construction of the real mechanism: build a proof that proves a lemma once and uses it k times, build the version with the lemma inlined at every use site, and count actual nodes in both. That is a demonstration of the duplication mechanism, not a proof of the general blow-up result — the non-elementary lower bound for first-order cut elimination (Statman 1979, Orevkov 1979) is cited and is not established by anything on this page.
AVAN (AI) wrote a wrong measurement here first and is replacing it rather than hiding it. The initial version estimated the blow-up with an invented “schematic elimination” formula that multiplied subtree sizes — on axiom leaves it collapsed to 1 and modelled nothing at all, and it failed its own gate. It is replaced by an explicit construction of the real mechanism: build a proof that proves a lemma once and uses it k times, build the version with the lemma inlined at every use site, and count actual nodes in both. That is a demonstration of the duplication mechanism, not a proof of the general blow-up result — the non-elementary lower bound for first-order cut elimination (Statman 1979, Orevkov 1979) is cited and is not established by anything on this page.
3 ONE DIMENSION
The same endsequent, twice. One borrows a lemma; one does not.
4 TWO DIMENSIONS · INTERACTIVE
Raise the number of uses and watch the inlined proof grow.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the cut proof, and the inlined tree standing behind it.
AVAN’s addition (the inverse-companion): the forward reading is “cuts can always be removed.” The inverse is that the cut is where the mathematics actually lives. A cut-free proof is fully explicit and completely local — and it is also, for anything interesting, enormous and unreadable, because every reusable idea has been expanded away. The lemma was the insight; removing it converts understanding into length. Read backwards, Gentzen’s theorem measures the exact value of abstraction: the size ratio between a proof that may name an idea once and a proof that must spell it out every time it is used.
LIT two proofs of the same endsequent p>q, q>r |- p>r, one routed through a cut and one cut-free, endsequents confirmed identical and the cut confirmed present in one and absent from the other; the cut-free proof satisfies the subformula property across all 16 of its formula occurrences; a cut on an alien formula breaks exactly that, with (s&~s) appearing in the proof and nowhere in what is proved; and inlining a lemma used k times grows the proof 9->7, 11->15, 15->31, 23->63, 39->127 for k = 1,2,4,8,16 — a factor of 3.3 at k=16
FIG AVAN's first version estimated the blow-up with an invented 'schematic elimination' formula that multiplied subtree sizes; on axiom leaves it collapsed to 1, modelled nothing, and failed its own gate. It is replaced by an EXPLICIT construction of the real mechanism — build the proof that proves a lemma once and uses it k times, build the version with it inlined at every site, count actual nodes. That demonstrates the duplication mechanism; it is NOT a proof of the general blow-up. The non-elementary lower bound for first-order cut elimination (Statman 1979, Orevkov 1979) is cited only.
FIG AVAN's first version estimated the blow-up with an invented 'schematic elimination' formula that multiplied subtree sizes; on axiom leaves it collapsed to 1, modelled nothing, and failed its own gate. It is replaced by an EXPLICIT construction of the real mechanism — build the proof that proves a lemma once and uses it k times, build the version with it inlined at every site, count actual nodes. That demonstrates the duplication mechanism; it is NOT a proof of the general blow-up. The non-elementary lower bound for first-order cut elimination (Statman 1979, Orevkov 1979) is cited only.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of GARBAGE COLLECTION · David Lee Wise (ROOT0), with AVAN